Understanding a Markov chain problem

Question

Assume there are $2$ cans filled with $\frac{N}{2}$ balls each. Every time, we move a ball from the second can to the first can with probability $\frac{3}{4}$, or we move a ball from the first can to the second can with probability $\frac{1}{4}$. Assume we stop the process when one of the cans are full of N balls

Problem: Find the expected time until one of the cans contains all $N$ balls.

My idea: Let $X_n$ be the number of balls in the first can. Obviously it is equivalent to finding the expected time until $X_n = 0$ or $X_n = N$.

Assume $E_0$ is the expected time for the first can to be empty, and $E_N$ is the expected time for the first can to be full.

My question is: because we obviously know that the expected time for the first can to be full is less than its expected time to be empty (according to the probabilities), is the expected time for one of the cans to be full $\min(E_0, E_N)$ which is $E_N$?

If it is not true, how should I solve the question?

Answer 1

There is a positive probability $X_n=0$ before $X_n=N$ so the expectation is lower for "first time either can to be full" than for "first time first can will be full".

As an illustration, suppose you have $N=4$ balls, with $x$ in the first can and $N-x$ in the second, and the expected number of turns until the first time either can is empty is $F(x)$. With $x=1,2,3$ you need to move a ball so can add $1$ to the weighted sum of the expectation of the states you then find yourself in. Then you have: $$F(0)=0$$ $$F(1)=1+\tfrac34F(2)+\tfrac14 F(0)$$ $$F(2)=1+\tfrac34F(3)+\tfrac14 F(1)$$ $$F(3)=1+\tfrac34F(4)+\tfrac14 F(2)$$ $$F(4)=0$$ which is five simultaneous equations in five unknowns, and has the solution $$F(0)=0, F(1)=\tfrac{17}{5}, F(2)=\tfrac{16}{5}, F(3)=\tfrac{9}{5}, F(4)=0$$ and for the original question you want $F(2)=\frac{16}{5}=3.2$.

Let's deal with Benjamin Wang's first comment by saying that when one can is full then the next transfer will be to the other can.

Now suppose you do not stop when $x=0$, so you would change to using $F(0)=1+F(1)$. This is still five simultaneous equations in five unknowns, but this time the solution is $F(0)=\frac{176}{27}$, $F(1)=\frac{149}{27}$, $F(2)=\frac{104}{27}$, $F(3)=\frac{53}{27}$, $F(4)=0$, and your $E_N = F(2)=\frac{104}{27}\approx 3.85$ is higher than the answer to the original question.

You can also find $E_0$: go back to $F(0)=0$ but this time use $F(4)=1+F(3)$. This time the solution is $F(0)=0$, $F(1)=79$, $F(2)=104$, $F(3)=111$, $F(4)=112$, and your $E_0 = F(2)=104$, much higher than the other two values.

Answer 2

Like @lonza leggiera mentioned in a comment, the solution can be found by solving the recurrence

$$E_n = 1 + pE_{n-1} + (1-p)E_{n+1},$$

with boundary conditions $E_0=E_N=0$ and $p=3/4$. Your answer is then $E_{N/2}$ (note: $N$ is even).

To see why, we need some setup: $(X_k)_{k\ge 0}$ is a Markov chain on state space $\{0, 1, \dots, N\}$, where $X_k$ is the number of balls in the first can at (discrete) time $k$. The transition probabilities are $P_{i,i+1} = 1/4$ and $P_{i,i-1}=3/4$ for $i=1,\dots, N-1$, while $P_{0,0} = P_{N,N} = 1$, and zero otherwise. So $\{0,N\}$ is an absorbing set.

Let $E_n$ be the number of moves until absorption starting in state $n$. More rigorously, $E_n = \inf_{k}\{k: X_k\in \{0, N\}, X_0=n\}$.

The recurrence relation can be rearranged as

$$-1 = (1-p)E_{n+1} - E_n + pE_{n-1}, \cdots (\ast)$$

so it has characteristic equation

$$(1-p)x^2 - x + p = 0$$

which has solution $x=1$ or $\frac{p}{1-p}$, so the solution to the recurrence relation is

$$E_n = \underbrace{A1^n+B\left(\frac{p}{1-p}\right)^n}_{h(n)}+f(n),$$

where $f(n)$ is a particular solution we need to guess. Although the left hand side of $(\ast)$ is a constant, we cannot simply guess $f(n) = C$ because there is already a constant function, $A1^n = A$, in the homogeneous part $h(n)$. (Try it: you'll end up with $E_n \equiv 0$)

So we guess $f(n) = Cn$. Substituting into $(\ast)$ gives

$$-1 = (1-p)C(n+1)-Cn+pC(n-1)$$

and therefore $C = \frac{1}{2p-1}$. (You know you're correct because it doesn't depend on $n$; other attempts will fail because they will depend on $n$.) Then substituting boundary conditions $E_0=E_N=0$ into the expression for $E_n$ gives

$$E_n = \frac{1}{2p-1}\left(n - N \frac{1 - (p/(1-p))^n}{1 - (p/(1-p))^N}\right).$$

Which, for $p=3/4$ is $2(n-N(1-3^n)/(1-3^N))$ and for $n=N/2$ is $N(1-2/(1+3^{N/2}))$,

Addressing your original question

We answered the question "time to absorption to $\{0,N\}$". However, it is not actually immediately sensible to ask for "time to absorption to $\{0\}$", because it might be infinity as the chain might get absorbed into $\{N\}$. However, it is sensible, as in this question, to ask for the time to absorption conditioned on absorption into $\{0\}$.