I'm having trouble understanding this proof:
There's a couple of things that do not make sense to me.
- I do not understand why: $ X_{n+1}= \begin{cases} X_n-1, \text{if}\ X_n \geq 1\\ Y_{K_{n+1}}-1, \text{if}\ X_n=0\\ \end{cases} $
I think the transition probabilities, $P_{0,j}=P(Y_1=j+1)$, $P_{j+1,j}=1$ for all $j \geq 0$, are derived using the above formulation so I really want to understand why $ X_{n+1}= \begin{cases} X_n-1, \text{if}\ X_n \geq 1\\ Y_{K_{n+1}}-1, \text{if}\ X_n=0\\ \end{cases}$
- I don't how we can solve $\pi P=\pi$ to deduce $\pi_{i}=\frac{P(Y_1>i)}{\mu}$. I tried solving $\pi P=\pi$ but I couldn't do it, I tried setting up the equations, but there is an infinite number of states so I didn't know how to solve for the stationary distribution. Is there some trick to do it?
Out of these two questions, the first question, question 1 is what I'm more concerned with, as I really want to understand why its true, although it would also be nice to understand my second question. Thank you.
Suppose $X_n = 0$. This is equivalent to $$Y_1 + \cdots + Y_{K_n} = n. \tag{$*$}$$ This implies $Y_1 + \cdots + Y_{K_n} + Y_{K_n + 1} \ge n+1$, and $$X_{n+1} = Y_1 + \cdots + Y_{K_n} + Y_{K_n + 1} - (n+1) = Y_{K_n + 1} - 1,$$ where the last equality is due to substituting ($*$).
Suppose $X_n \ge 1$. Since $$X_n = Y_1 + \cdots + Y_{K_n} - n,\tag{$**$}$$ this is equivalent to $$Y_1 + \cdots + Y_{K_n} \ge n + 1. $$ Thus $$X_{n+1} = Y_1 + \cdots + Y_{K_n} - (n + 1) = X_n - 1,$$ where the last equality is due to substituting ($**$).
$\pi P = \pi$ can be written as $$\pi_j = \sum_{i \ge 0} \pi_i p_{i,j} = P(Y_1 = j + 1) \pi_0 + \pi_{j+1}, \qquad \forall j \ge 0.$$ You can use this to show by induction that $\pi_j = P(Y_1 > j) \pi_0$ for $j \ge 1$. Then using $\sum_{j \ge 1} \pi_j = 1$ you can show that $\pi_0 = 1/\mu$.