Defining the Markov chain for particles on the vertices of a cube and its expected value Two particles are on the vertices of a cube.If they are on the same edge at some time t, then they remain in the same position at time t+1. If not, one of the particles is chosen with equal probability and ant time t+1, it goes to one of the three neighboring vertices with probability 1/3. If the particles start at opposite vertices of the same face, what is the expected value of the minimum time they are in the same edge? 
Hi,
One thing that I am confused is that If $V_1$ and $V_3$ are tow opposite vertices on the same face, $V_1$ can go to the one of the three neighboring vertices with 1/3 probability, but it can never go to state $V_3$.
Thus, I can not explicitly define the transition matrix since $V_1$ can not go to the state $V_3$
Can anyone give me some ideas?  
 A: Let's assume that we are looking at the unit cube in $R^3$. Then the vertices are labeled by $(x,y,z) \in \{0,1\}^3$. We refer to $x,y,z$ as the coordinates of a vertex. 
With this notation, a face is simply all (four) vertices with some prescribed value for a given coordinate (and therefore there are 6 faces: 0 for the first coordinate, 1 for the first coordinate, etc.) and an edge consists of the (two) vertices with some prescribed values for two give coordinates (example: x=0 and y=1, then the edge consists of (0,1,0) and (0,1,1)). 
We start with particle a at $(0,0,0)$ and particle b at $(0,1,1)$. Then at each stage, exactly of the particles moves to a neighboring vertex (one on same edge, there are three such edges),  until they are on the same edge. Note that movement of the particle means flipping the value of exactly one of its coordinates.  
Let $N_t$ denote the number of coordinates at which the two particles differ at time $t$, with the initial configuration taken as time $t=0$. We assume $N_0=2$. We will run the process until it $N_t=1$ (both on same edge), because then it will not move ever again. Note that :


*

*If  $N_t=2$, $N_{t+1}$ will be $1$ if the particle that moves will flip one of the coordinates where they differ. This will occur with probability $2/3$ (two out of coordinates are such). Otherwise $N_{t+1}=3$.

*If $N_t=3$, $N_{t+1}$ will be $2$ with probability $1$. 


Therefore $N_t$ is a three-state markov chain with the transition matrix $P$:  
$$ P = \left (\begin{array}{ccc}1 & 0 &0 \\ \frac{2}{3} & 0 & \frac {1}{3} \\ 0 & 1 & 0\end{array} \right).$$
We are asked starting from $N_0=2$ find the expected time until $N_t=1$. Denote this random time by $T$. The easiest way to get it is by conditioning on the first step: 
$$ E T = \frac 23 \times 1 + \frac 13 (2+ET)$$
Explanation (look at second row of $P$): with probability $2/3$ we jump to $1$. With probability $1/3$ we jump to three, then move to 2 again, and start afresh from $2$. The solution is then 
$$E T = 2.$$
Think of this as a sequence of experiments, each time corresponds to a visit to $2$:  $\frac 23$ os success and $\frac 13$ of failure. We wait until the first success. This is of course a geometric random variable with parameter $\frac 13$. Call it $G$. Each failure costs two steps (moving to $3$ and back to $1$) and a success (only one) costs one step (moving to the state $1$). We have 
$$T = 1+ 2(G-1)=2G - 1.$$ 
The expectation of $T$ is then $2 \frac{3}{2}-1=2$. 
