Return to Answer

The accepted answer gets the correct result largely by coincidence. There is not a priori any relationship between the time when the expected number of heads and tails are equal vs. the expected time when the number of heads and tails are equal, and the latter is what is asked for.

You first convert to a random walk: look at the number of tails minus the number of heads and then the walk starts at $1$, moves right with probability $0.3$ and moves left with probability $0.7$. Now the expected time for the walk to net-move one step to the left can be determined by conditioning on the first step. If you move left in the first step, then the time is just $1$. If you move right in the first step, then you now need to net-move two steps to the left. Therefore using the total expectation formula,

$$E[T]=0.7 \cdot 1 + 0.3 \cdot (1+2E[T])=1+0.6E[T].$$

Solving for $E[T]$ you get $\frac{1}{0.4}=\frac{5}{2}$.

Another way to proceed, which can be applied in a wider variety of problems, is to use the same random walk but now consider starting at any $n \geq 0$ and compute the expected times $T(n)$ to hit $0$ starting from all such $n$ together. To do this you apply the total expectation formula to get the recursive relation

$$T(n)=1+0.3 T(n+1)+0.7T(n-1).$$

You can find the general homogeneous solution to this recurrence which is given by $T(n)=c_1 \lambda_1^n + c_2 \lambda_2^n$ where $\lambda_1,\lambda_2=\frac{1 \pm \sqrt{1-4 \cdot 0.3 \cdot 0.7}}{0.6}=\frac{1 \pm 0.4}{0.6}=1,\frac{7}{3}$.

A particular solution can be obtained by the method of undetermined coefficients; you can guess $T(n)=cn$ which yields $cn=1+0.3c(n+1)+0.7c(n-1)=1+cn-0.4c$ yielding $c=5/2$. So the general solution is $T(n)=\frac{5}{2}n + c_1 + c_2 \left ( \frac{7}{3} \right )^n$.

Now clearly $T(0)=0$, which implies that we have $T(n)=\frac{5}{2} n + c \left ( \left ( \frac{7}{3} \right )^n - 1 \right )$ for some $c$.

Now we want $T(1)$, and $T(1)$ actually depends on $c$, so we need to figure out what $c$ is. This is a bit subtle, since it's not obvious that we have any other boundary condition in the problem. One technique for circumventing this is to consider artificially stopping the process when the state $N>0$ is reached and then send $N \to \infty$ to "suppress" the artificial termination scenario. Thus we consider setting $T(N)=0$ also.

Proceeding in this manner you obtain the equation $\frac{5}{2} N + c \left ( \left ( \frac{7}{3} \right )^N-1 \right )=0$, and so $T(n)=\frac{5}{2} n - \frac{\frac{5}{2} N}{(7/3)^N-1} \left ( (7/3)^n-1 \right )$. Then $T(1)=\frac{5}{2} - \frac{\frac{5}{2} N}{(7/3)^N-1} \frac{4}{3} \to \frac{5}{2}$ as $N \to \infty$.

The one tricky matter in making this latter argument rigorous is to ensure that the probability that a path terminates at $N$ decays faster than the growth of an average length of a path that terminates at $N$.

The accepted answer gets the correct result largely by coincidence. There is not a priori any relationship between the time when the expected number of heads and tails are equal vs. the expected time when the number of heads and tails are equal, and the latter is what is asked for.

You first convert to a random walk: look at the number of tails minus the number of heads and then the walk starts at $1$, moves right with probability $0.3$ and moves left with probability $0.7$. Now the expected time for the walk to net-move one step to the left can be determined by conditioning on the first step. If you move left in the first step, then the time is just $1$. If you move right in the first step, then you now need to net-move two steps to the left, which takes on average twice as long as net-moving one step to the left. Therefore using the total expectation formula,

$$E[T]=0.7 \cdot 1 + 0.3 \cdot (1+2E[T])=1+0.6E[T].$$

Solving for $E[T]$ you get $\frac{1}{0.4}=\frac{5}{2}$.

Another way to proceed, which can be applied in a wider variety of problems, is to use the same random walk but now consider starting at any $n \geq 0$ and compute the expected times $T(n)$ to hit $0$ starting from all such $n$ together. To do this you apply the total expectation formula to get the recursive relation

$$T(n)=1+0.3 T(n+1)+0.7T(n-1).$$

You can find the general homogeneous solution to this recurrence which is given by $T(n)=c_1 \lambda_1^n + c_2 \lambda_2^n$ where $\lambda_1,\lambda_2=\frac{1 \pm \sqrt{1-4 \cdot 0.3 \cdot 0.7}}{0.6}=\frac{1 \pm 0.4}{0.6}=1,\frac{7}{3}$.

A particular solution can be obtained by the method of undetermined coefficients; you can guess $T(n)=cn$ which yields $cn=1+0.3c(n+1)+0.7c(n-1)=1+cn-0.4c$ yielding $c=5/2$. So the general solution is $T(n)=\frac{5}{2}n + c_1 + c_2 \left ( \frac{7}{3} \right )^n$.

Now clearly $T(0)=0$, which implies that we have $T(n)=\frac{5}{2} n + c \left ( \left ( \frac{7}{3} \right )^n - 1 \right )$ for some $c$.

Now we want $T(1)$, and $T(1)$ actually depends on $c$, so we need to figure out what $c$ is. This is a bit subtle, since it's not obvious that we have any other boundary condition in the problem. One technique for circumventing this is to consider artificially stopping the process when the state $N>0$ is reached and then send $N \to \infty$ to "suppress" the artificial termination scenario. Thus we consider setting $T(N)=0$ also.

Proceeding in this manner you obtain the equation $\frac{5}{2} N + c \left ( \left ( \frac{7}{3} \right )^N-1 \right )=0$, and so $T(n)=\frac{5}{2} n - \frac{\frac{5}{2} N}{(7/3)^N-1} \left ( (7/3)^n-1 \right )$. Then $T(1)=\frac{5}{2} - \frac{\frac{5}{2} N}{(7/3)^N-1} \frac{4}{3} \to \frac{5}{2}$ as $N \to \infty$.

The one tricky matter in making this latter argument rigorous is to ensure that the probability that a path terminates at $N$ decays faster than the growth of an average length of a path that terminates at $N$.

The accepted answer gets the correct result largely by coincidence. There is not a priori any relationship between the time when the expected number of heads and tails are equal vs. the expected time when the number of heads and tails are equal, and the latter is what is asked for.

To work this out, you can consider a Markov chain for the cumulative number of tails minus the cumulative number of heads. Then this jumps by $+1$ with probability $0.3$, jumps by $-1$ with probability $0.7$, and it starts at $1$. You want the expected time to hit $0$. One way to do this is to consider starting at any $n \geq 0$ and compute the expected times $T(n)$ to hit $0$ starting from all such $n$ together. To do this you apply the total expectation formula to get the recursive relation

$$T(n)=1+0.3 T(n+1)+0.7T(n-1).$$

You can find the general homogeneous solution to this recurrence which is given by $T(n)=c_1 \lambda_1^n + c_2 \lambda_2^n$ where $\lambda_1,\lambda_2=\frac{1 \pm \sqrt{1-4 \cdot 0.3 \cdot 0.7}}{0.6}=\frac{1 \pm 0.4}{0.6}=1,\frac{7}{3}$.

A particular solution can be obtained by the method of undetermined coefficients; you can guess $T(n)=cn$ which yields $cn=1+0.3c(n+1)+0.7c(n-1)=1+cn-0.4c$ yielding $c=5/2$. So the general solution is $T(n)=\frac{5}{2}n + c_1 + c_2 \left ( \frac{7}{3} \right )^n$.

Now clearly $T(0)=0$, which implies that we have $T(n)=\frac{5}{2} n + c \left ( \left ( \frac{7}{3} \right )^n - 1 \right )$ for some $c$.

Now we want $T(1)$, and $T(1)$ actually depends on $c$, so we need to figure out what $c$ is. This is a bit subtle, since it's not obvious that we have any other boundary condition in the problem. One technique for circumventing this is to consider artificially stopping the process when the state $N>0$ is reached and then send $N \to \infty$ to "suppress" the artificial termination scenario. Thus we consider setting $T(N)=0$ also.

Proceeding in this manner you obtain the equation $\frac{5}{2} N + c \left ( \left ( \frac{7}{3} \right )^N-1 \right )=0$, and so $T(n)=\frac{5}{2} n - \frac{\frac{5}{2} N}{(7/3)^N-1} \left ( (7/3)^n-1 \right )$. Then $T(1)=\frac{5}{2} - \frac{\frac{5}{2} N}{(7/3)^N-1} \frac{4}{3} \to \frac{5}{2}$ as $N \to \infty$.

The accepted answer gets the correct result largely by coincidence. There is not a priori any relationship between the time when the expected number of heads and tails are equal vs. the expected time when the number of heads and tails are equal, and the latter is what is asked for.

You first convert to a random walk: look at the number of tails minus the number of heads and then the walk starts at $1$, moves right with probability $0.3$ and moves left with probability $0.7$. Now the expected time for the walk to net-move one step to the left can be determined by conditioning on the first step. If you move left in the first step, then the time is just $1$. If you move right in the first step, then you now need to net-move two steps to the left. Therefore using the total expectation formula,

$$E[T]=0.7 \cdot 1 + 0.3 \cdot (1+2E[T])=1+0.6E[T].$$

Solving for $E[T]$ you get $\frac{1}{0.4}=\frac{5}{2}$.

Another way to proceed, which can be applied in a wider variety of problems, is to use the same random walk but now consider starting at any $n \geq 0$ and compute the expected times $T(n)$ to hit $0$ starting from all such $n$ together. To do this you apply the total expectation formula to get the recursive relation

$$T(n)=1+0.3 T(n+1)+0.7T(n-1).$$

You can find the general homogeneous solution to this recurrence which is given by $T(n)=c_1 \lambda_1^n + c_2 \lambda_2^n$ where $\lambda_1,\lambda_2=\frac{1 \pm \sqrt{1-4 \cdot 0.3 \cdot 0.7}}{0.6}=\frac{1 \pm 0.4}{0.6}=1,\frac{7}{3}$.

A particular solution can be obtained by the method of undetermined coefficients; you can guess $T(n)=cn$ which yields $cn=1+0.3c(n+1)+0.7c(n-1)=1+cn-0.4c$ yielding $c=5/2$. So the general solution is $T(n)=\frac{5}{2}n + c_1 + c_2 \left ( \frac{7}{3} \right )^n$.

Now clearly $T(0)=0$, which implies that we have $T(n)=\frac{5}{2} n + c \left ( \left ( \frac{7}{3} \right )^n - 1 \right )$ for some $c$.

Now we want $T(1)$, and $T(1)$ actually depends on $c$, so we need to figure out what $c$ is. This is a bit subtle, since it's not obvious that we have any other boundary condition in the problem. One technique for circumventing this is to consider artificially stopping the process when the state $N>0$ is reached and then send $N \to \infty$ to "suppress" the artificial termination scenario. Thus we consider setting $T(N)=0$ also.

Proceeding in this manner you obtain the equation $\frac{5}{2} N + c \left ( \left ( \frac{7}{3} \right )^N-1 \right )=0$, and so $T(n)=\frac{5}{2} n - \frac{\frac{5}{2} N}{(7/3)^N-1} \left ( (7/3)^n-1 \right )$. Then $T(1)=\frac{5}{2} - \frac{\frac{5}{2} N}{(7/3)^N-1} \frac{4}{3} \to \frac{5}{2}$ as $N \to \infty$.

The one tricky matter in making this latter argument rigorous is to ensure that the probability that a path terminates at $N$ decays faster than the growth of an average length of a path that terminates at $N$.

The accepted answer gets the correct result largely by coincidence. There is not a priori any relationship between the time when the expected number of heads and tails are equal vs. the expected time when the number of heads and tails are equal, and the latter is what is asked for.

To work this out, you can consider a Markov chain for the cumulative number of tails minus the cumulative number of heads. Then this jumps by $+1$ with probability $0.3$, jumps by $-1$ with probability $0.7$, and it starts at $1$. You want the expected time to hit $0$. One way to do this is to consider starting at any $n \geq 0$ and compute the expected times $T(n)$ to hit $0$ starting from all such $n$ together. To do this you apply the total expectation formula to get the recursive relation

$$T(n)=1+0.3 T(n+1)+0.7T(n-1).$$

You can find the general homogeneous solution to this recurrence which is given by $T(n)=c_1 \lambda_1^n + c_2 \lambda_2^n$ where $\lambda_1,\lambda_2=\frac{1 \pm \sqrt{1-4 \cdot 0.3 \cdot 0.7}}{0.6}=\frac{1 \pm 0.4}{0.6}=1,\frac{7}{3}$.

A particular solution can be obtained by the method of undetermined coefficients; you can guess $T(n)=cn$ which yields $cn=1+0.3c(n+1)+0.7c(n-1)=1+cn-0.4c$ yielding $c=5/2$. So the general solution is $T(n)=\frac{5}{2}n + c_1 + c_2 \left ( \frac{7}{3} \right )^n$.

Now clearly $T(0)=0$, which implies that we have $T(n)=\frac{5}{2} n + c \left ( \left ( \frac{7}{3} \right )^n - 1 \right )$ for some $c$.

Now we want $T(1)$, and $T(1)$ actually depends on $c$, so we need to figure out what $c$ is. This is a bit subtle, since it's not obvious that we have any other boundary condition in the problem. One technique for circumventing this is to consider artificially stopping the process when the state $N>0$ is reached and then send $N \to \infty$ to "suppress" the artificial termination scenario. Thus we consider setting $T(N)=0$ also.

Proceeding in this manner you obtain the equation $\frac{5}{2} N + c \left ( \left ( \frac{7}{3} \right )^N-1 \right )=0$. You see that then $c \to 0$ as $N \to \infty$, and so $T(n)=\frac{5}{2} n$. Thus the desired quantity is $T(1)=\frac{5}{2}$.

The accepted answer gets the correct result largely by coincidence. There is not a priori any relationship between the time when the expected number of heads and tails are equal vs. the expected time when the number of heads and tails are equal, and the latter is what is asked for.

To work this out, you can consider a Markov chain for the cumulative number of tails minus the cumulative number of heads. Then this jumps by $+1$ with probability $0.3$, jumps by $-1$ with probability $0.7$, and it starts at $1$. You want the expected time to hit $0$. One way to do this is to consider starting at any $n \geq 0$ and compute the expected times $T(n)$ to hit $0$ starting from all such $n$ together. To do this you apply the total expectation formula to get the recursive relation

$$T(n)=1+0.3 T(n+1)+0.7T(n-1).$$

You can find the general homogeneous solution to this recurrence which is given by $T(n)=c_1 \lambda_1^n + c_2 \lambda_2^n$ where $\lambda_1,\lambda_2=\frac{1 \pm \sqrt{1-4 \cdot 0.3 \cdot 0.7}}{0.6}=\frac{1 \pm 0.4}{0.6}=1,\frac{7}{3}$.

A particular solution can be obtained by the method of undetermined coefficients; you can guess $T(n)=cn$ which yields $cn=1+0.3c(n+1)+0.7c(n-1)=1+cn-0.4c$ yielding $c=5/2$. So the general solution is $T(n)=\frac{5}{2}n + c_1 + c_2 \left ( \frac{7}{3} \right )^n$.

Now clearly $T(0)=0$, which implies that we have $T(n)=\frac{5}{2} n + c \left ( \left ( \frac{7}{3} \right )^n - 1 \right )$ for some $c$.

Now we want $T(1)$, and $T(1)$ actually depends on $c$, so we need to figure out what $c$ is. This is a bit subtle, since it's not obvious that we have any other boundary condition in the problem. One technique for circumventing this is to consider artificially stopping the process when the state $N>0$ is reached and then send $N \to \infty$ to "suppress" the artificial termination scenario. Thus we consider setting $T(N)=0$ also.

Proceeding in this manner you obtain the equation $\frac{5}{2} N + c \left ( \left ( \frac{7}{3} \right )^N-1 \right )=0$, and so $T(n)=\frac{5}{2} n - \frac{\frac{5}{2} N}{(7/3)^N-1} \left ( (7/3)^n-1 \right )$. Then $T(1)=\frac{5}{2} - \frac{\frac{5}{2} N}{(7/3)^N-1} \frac{4}{3} \to \frac{5}{2}$ as $N \to \infty$.