Finding the general pattern form

Question

Suppose a Markov chain given as follows. $p_{ii}=1-3a$ And $p_{ij}=a\ \forall i\ne j$ where $P=(p_{ij}), 1\le i,j\le 4$. Find $P_{1,1}^n$.

Attempts: I have tried to compute for the case $n=1, 2, 3$. And focus of the entry(1,1) but I couldn't get the general pattern. I guess there should be some way for get the general pattern. Any hints or sources are welcome (better if there is a little bit explanation).

Edit: I think the answer is not so important here. Thanks for the link of wolfram alpha and it shows the general form of it but what I concerned the most is that how it get that form. There should be a mathematical way to obtain that general form which is also used by wolfram alpha. Any related information about the general equation? Thanks.

Answer 1

Thanks to the symmetrical structure of $P$, one can compute every power $P^n$ rather easily. To see how, let us introduce $I$ the $4\times4$ identity matrix and $J$ the $4\times4$ matrix whose every entry is $\frac14$. Then, $$ P=(1-4a)I+4aJ. $$ The computations involving matrices that are polynomial in $J$ are simple, thanks to the identities $I^2=I$ and $IJ=JI=J^2=J$. For example, the binomial expansion $$ P^n=\sum_{k=0}^n{n\choose k}(1-4a)^{n-k}(4a)^kJ^k, $$ reads, using $J^0=I$ and $J^k=J$ for every $k\geqslant1$, $$ P^n=(1-4a)^nI+(1-(1-4a)^n)J. $$ In particular, $I_{1,1}=1$ and $J_{1,1}=\frac14$ hence

$$ (P^n)_{1,1}=\tfrac14(1+3(1-4a)^n). $$

There exists a probabilistic proof of this identity, which one may feel is more illuminating than the "algebraic" proof given above but is restricted to the case $a\leqslant\frac14$. Consider that, at each step of the Markov chain, either one stays at the same state with probability $p=1-4a$ or one moves to a new state with probability $1-p=4a$ and that this new state is chosen uniformly at random. Thus, one stays at the same state with total probability $p+\frac14(1-p)=1-3a$, as desired.

After $n$ steps, either one decided $n$ times to stay at the same state (this happens with probability $p^n$) or one decided at least once to move to a new state, chosen uniformly at random. In the latter case, irrespectively of the steps when one decided to move, the current position is uniform hence one can also be at the same state, with conditional probability $\frac14$. Summing up these two cases, one sees that one stayed at the same state with probability $p^n+\frac14(1-p^n)=\frac14(1+3p^n)$, that is, the result above.