Markov Chain: Pensioner Problem A pensioner receives 2000 dollars at the beginning of each month. The amount of money he needs to spend during a month is independent of the amount he has and is equal to i (i.e. i thousand dollars) with probability Pi, i = 1, 2, 3, 4, $\displaystyle\sum\limits_{i=1}^4P_{i}=1$. If the pensioner has more than 3000 dollars at the end of a month, he gives the amount greater than 3000 to his son.
Q1.If, after receiving his payment at the beginning of a month, the pensioner has a capital of 5000, what is the probability that his capital is ever 1000 or less at any time within the following four months?
 A: Call $X_n$ the number of thousands of dollars the pensioner has at the end of the $n$th month just before he receives his payment. Modify the dynamics by considering that if the pensioner has or has had $0$ dollar or $1000$ dollars at time $n$ or anytime before time $n$, then $X_n=1$. 
The process $(X_n)$ is a Markov chain on the state space $S=\{1,2,3\}$ starting from $X_0=3$ and one asks for the probability $p$ that $X_4=1$. This is $Q^4(3,1)$, where $Q$ is the transition matrix of $(X_n)$ indexed by $S\times S$. Thus
$$
Q=\begin{pmatrix}1&0&0\\ 1/2&1/4&1/4\\ 1/4&1/4&1/2\end{pmatrix}.
$$
From here, the quickest route might be to (somewhat tediously) compute  the first column and the third line of $Q^2$, namely,
$$
Q^2=\begin{pmatrix}1&*&*\\ 11/16&*&*\\ 1/2&3/16&5/16\end{pmatrix},
$$
and to deduce the coefficient
$$
Q^4(3,1)=\sum_{i=1}^3Q^2(3,i)\times Q^2(i,1)=\frac12\times1+\frac3{16}\times\frac{11}{16}+\frac5{16}\times\frac12=\ldots
$$
A: Here is a partial answer.
At the end of the month, after giving money to his son if possible
under the rules, the pensioner will have $\$3000, \$2000, \$1000$
left with probabilities $P_1 + P_2, P_3$, and $P_4$ respectively.
Thus, after receiving his pension at the start of the second month,
the pensioner will have $\$5000$ again with probability $P_1 + P_2$
and will repeat this cycle all over again (or will have lesser amounts
and go off on a separate path, possibly towards destitution).
Thus, the probability that the pensioner will have $\$1000$ or less
at some time during the next four months is bounded below as follows:
$$P(\$1000~\text{or less during next four months}) > 
P_4[1 + (P_1+P_2) + (P_1+P_2)^2 + (P_1+P_2)^3]$$
You need to figure out what happens if the pensioner 
begins the second month with only $\$4000$ to find the
value of $P(\$1000~\text{or less during next four months})$.
