I have an exercise with an answer which I don't completely understand:

Here's the exercise: Suppose $p$ is the transition (stochastic) matrix defined by $$p= \begin{pmatrix} 1-\alpha & \alpha \\ \beta & 1- \beta \\ \end{pmatrix}$$

What I need to find is $\Bbb P(X_n=1 | X_0=1)$.

So here's the solution:

Noting that $p^{n+1}=p^np$ this gives:

$$p^{n+1}_{11}= p^{n}_{12}\beta + p^n_{11}(1-\alpha)$$

and since p is a stochastic matrix $$p^n_{11}+p^n_{12}=1$$ for all $n$.

Then we suub the second into the first and solve for $p^n_{11}$ $\Rightarrow$ $$p^{n+1}_{11}=(1-\alpha-\beta)p^n_{11}+\beta$$

So for some reason they also write that $p^0_{11}=1.$

So then the solution is :

$$p^n_{11}= \begin{cases} \frac{\alpha}{\alpha+\beta} + \frac{\alpha}{\alpha+\beta}(1-\alpha-\beta)^n , & \text{for }\alpha+\beta \gt 0\\ 1, & \text{for } \alpha+\beta=0. \end{cases}$$

So how did they deduce the solution?

Is this even a correct solution?


There are two questions.

  1. Why is $p_{11}^0 = 1$? This concerns powers of the matrix (which I will write as $P$). Because matrix powers may be unfamiliar, here is a quick sketch of the theory. For powers to be useful, they need to have some basic properties, one of which is that $P^1=P$ and another is that for any natural number $n,$ $P^{n+1} = P\,P^n = P^n\, P.$ When $n=0$ this means $$P = P^1 = P^{0+1} = P^0\,P = P\, P^0.$$ There is an obvious universal solution $$P^0 = \mathbb{I} = \pmatrix{1&0\\0&1}.$$ In particular, its upper left hand entry is $$(P^0)_{11} = 1.$$

  2. How does one solve a recursive sequence of equations $$\begin{cases}x_0 &= 1 \\ x_{n+1} &= \rho\, x_n + \lambda, & n \gt 0\end{cases}$$ Here $x_n$ refers to the $1,1$ entry of $P^n;$ that is, to $(P^n)_{11}.$ The argument recounted in the question establishes that $\rho = 1-\alpha-\beta$ and $\lambda=\beta.$

    One way is to simplify this to a "homogeneous" relation by setting $y_n + \mu = x_n$ for some number $\mu$ to be found. Substituting in the recursion gives $$y_{n+1} + \mu = x_{n+1} = \rho\, x_n + \lambda = \rho(y_n + \mu) + \lambda.$$ Equivalently, we may isolate $y_{n+1}$ to give $$y_{n+1} = \rho(y_n + \mu) + \lambda - \mu = \rho\,y_n + (\lambda + (\rho-1)\mu).$$ Thus if we set $$\mu = \frac{\lambda}{1-\rho}$$ (assuming $\rho\ne 1$), this simplifies to $$y_{n+1} = \rho\, y_n.$$ This is a geometric series with the well-known (unique) solution $$y_{n} = \rho^n\, y_0 = \rho^n(x_0 - \mu),\quad n=0, 1, 2, \ldots.$$ Adding $\mu$ back to both sides yields $$x_{n} = y_{n} + \mu = \rho^n(x_0 - \mu) + \mu.$$ In the present application $$\mu = \frac{\lambda}{1-\rho} = \frac{\beta}{\alpha+\beta}.$$ Coupled with the initial condition $x_0 = (P^0)_{11} = 1$ this gives the stated solution when $\rho \ne 1;$ that is, when $\alpha+\beta\ne 0.$ In this last case necessarily $\alpha=\beta=0$ (because these are both transition probabilities), whence the recursion is simply $(P^{n+1})_{11} = (P^{n})_{11}$ whose solution obviously is $(P^{n})_{11}=(P^0)_{11} = 1$ for all $n.$

  • $\begingroup$ Thank you so much for clarifying! And thanks for editing! $\endgroup$ – user6969 Jan 14 at 18:27
  • $\begingroup$ so $x_n$ would be equal to $\rho^{n-1}(x_0-\mu)+\mu$? Because you defined $x_{n+1}$ to be $p^{n+1}_{11}$ $\endgroup$ – user6969 Jan 14 at 18:41
  • $\begingroup$ As I wrote at the outset, "$x_n$" is shorthand for "$(P^n)_{11}.$" $\endgroup$ – whuber Jan 14 at 18:44
  • $\begingroup$ I understand this, but in the end you wrote how much is $x_{n+1}$ equal to but not $x_n$. So that's why I asked, not because I was confused by your notation. $\endgroup$ – user6969 Jan 14 at 18:48
  • 1
    $\begingroup$ oh, okay, I see now. Yes, thank you! $\endgroup$ – user6969 Jan 14 at 18:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.