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?
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}}.$$