<s>[INST] Consider a Stochastic process X which moves between the corners of a regular tetrahedron. Find P(Xn = 1) Consider a Stochastic process $X$ which moves between the corners of a regular tetrahedron. The process starts at time 0 in node 1. At each time step, the process chooses an one of the connected edges and follows it to a new corner. The edges are selected uniformly, and independently of the past. Let $X_n$ be the number of the corner the process is in after step $n$. 
Determine the $P(X_n = 1)$ for all $n$ in the Natural numbers.


*

*I have done the previous 3 parts to this question, but am completely stumped by this part. There were two hints; you could try $n = 1,2,3$ first and then try to find a formula for general $n$. Or you could turn it into a two-state Markov chain.


Bearing in mind, I have only started introduction to markov processes two weeks ago, it would be greatly aprreciated if somebody could help me out please.
Note: I have found that $P(X_1 = 1)$ = 0, $P(X_2 = 1)$ = 1/3, $P(X_3 = 1)$ = 6/27 - are these correct?
 [/INST] We show how to find an answer using not much machinery. Matrices, or recurrences, would make it easier. 
At any time, we can be in one of two states, $A$ or $B$, where State $A$ means we are at vertex $1$, and State $B$ means we are at one of the $3$ other vertices.
At time $0$ we are in State $A$.
If at time $n$ we are in State $A$, then with probability $1$ we are in State $B$ at time $n+1$.
If at time $n$ we are in State $B$, then at time $n+1$ we are in State $A$ with probability $\frac{1}{3}$, and remain in State $B$ with probability $\frac{2}{3}$. 
Now let us compute:
Time $1$: with probability $0$, we are in State $A$, and with probability $1$ we are in State $B$.
Time $2$: With probability $\frac{1}{3}$ we are in $A$, with probability $1-\frac{1}{3}$ we are in $B$.
From now on, we just calculate the probabilities for $A$. We simplify a bit, but not very much, to preserve structure. It would be a mistake to use a calculator!
Time $3$: With probability $\frac{1}{3}(1-\frac{1}{3})$ we are in $A$. This simplifies to $\frac{1}{3}-\frac{1}{9}$. 
At time $4$, the probability we are in $A$ is $\frac{1}{3}\left(1-\frac{1}{3}+\frac{1}{9}\right)$. This is $\frac{1}{3}-\frac{1}{9}+\frac{1}{27}$. 
For time $5$, subtract the answer for $5$ from $1$, and multiply by $\frac{1}{3}$. We get $\frac{1}{3}-\frac{1}{9} + \frac{1}{27}-\frac{1}{81}$. 
The pattern is clear. We can use the expression for the sum of a finite geometric progression to get a closed form for the probability we are in State $A$ at time $n$, that is, for the probability that $X_n=1$. 
In general for time $n$, we get 
$$\frac{1}{3}\left(1-\frac{1}{3}+\frac{1}{3^2}-\frac{1}{3^3}+\cdots +(-1)^{n-1}\frac{1}{3^{n-2}}\right).$$
This is a geometric progression with common ratio $-\frac{1}{3}$ and sum
$$\frac{1}{4}\cdot\frac{3^{n-1}+(-1)^n}{3^{n-1}}.$$
</s>