Expected number of tosses for a biased coin with Markov chain

I have used a different method for confirmation, converting a straight line to a $2D$ lattice path.

• Number of tosses taken has to be of the form $(2k+1)$, i.e. odd

• $k$ can range from $0$ to $\infty$

• in $(2k+1)$ tosses, there will be $(k+1)$ "$p\;$steps" and $\;k\;$ "$q$ steps" $(p= 0.7)$
  $$\text{Thus the formula} = \sum_{k=0}^\infty \binom{2k+1}{k+1}p^{k+1}q^k$$

Wolfram shows that the sum converges,

and confirms the answer $= 2.5$

PS: Explanation of the Formula

The basic idea is to conceive the problem as one of a $2D$ lattice path rather than a straight line.

If equality is achieved at the $(2k+1)^{\text{th}}$ toss, the first $2k$ tosses must be such that the number of heads is always strictly less than tails till that point, and equality achieved only on the last toss. The number of such arrangements is the well known Catalan Number and is equal to $\dfrac{1}{k+1}\dbinom{2k}{k}$.

Thus with equality being achieved at the $(2k+1)^{th}$ toss, the expected number of tosses is:

$$ = \sum_{k=0}^{\infty}\frac{2k+1}{k+1}\binom{2k}{k}0.7^{k+1}0.3^{k}$$

which further simplifies to the formula used in the body.

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

This is an interesting problem and all the above solutions I think can be obtained using the law of the total expectation, with an assumption that the expected number of flips gets doubled when we have an additional tail to start with.

Let $X$ be the r.v. denoting the number of flips required. Also let's define a r.v $Y$ denoting the first flip after the initial tail.

Now, we have,

$E[X|Y=H]=1$

$E[X|Y=T]=1+2E[X]$

with an assumption that we need to double the number of required flips if we get an additional T (but is the assumption correct?)

Now, by law of total expectation, we have,

$E[X]=E[E[X|Y]]=P(Y=H)E[X|H]+P(Y=T)E[X|T]=p.1+(1-p)(1+2E[X])$

$\implies E[X] = \frac{1}{2p-1}=2.5$, when we have $p=P(Y=H)=0.7$.

Now, let's consider the following Markov chain (which looks like the Gambler's ruin or the birth-death process, but it's not finite, can be extended indefinitely to the right and there is no absorbing state).

• A state in the chain is represented as the difference in number of tails and heads (#T - #H) in the coin-tossing experiment.

• We start at state $1$ (one single tail) and want to compute the expected time to reach state $0$ (equal heads and tails).

• When a head shows up in the coin flip we move to the immediate left state with transition probability $p$ (except for state 0) and if a tail shows up we move to the immediate right state with transition probability $1-p$.

• Note that the chain is not finite, there is no last state to the right.

• In this scenario, the problem gets reduced to computing the hitting time from state $1$ to state $0$.

• In general hitting time $x_n$ from state $n$ to state $0$ can be represented as the following recurrence relation:

  $x_n=1+px_{n-1}+(1-p)x_{n+1}$, with $x_0=0$.

• We are interested to compute $x_1$.

• The above is a non-homogeneous recurrence relation $(1-p)x_{n+1}-x_n+px_{n-1}=-1$ and let's solve the homogeneous version of it first, which has characteristic equation as $(1-p)\lambda^2-\lambda+p=0$, with roots $1, \frac{p}{1-p}$, so that the homogeneous solution is:

  $x_h=A\left(\frac{p}{1-p}\right)^n+B.1^n$

• Now, let's guess a particular solution $x_p=Cn$, s.t., plugging it into the non-homogeneous equation with some algebra, we get $C=\frac{1}{2p-1}$ and $x_p=\frac{n}{2p-1}$, s.t., the solution is

  $x_n=x_h+x_p=A\left(\frac{p}{1-p}\right)^n+B.1^n+\frac{n}{2p-1}$.

• Note that the particular solution $x_p=\frac{5}{2}$, for $n=1$.

• With boundary condition $x_0=0$, we get

  $x_n=x_h+x_p=A\left(\left(\frac{p}{1-p}\right)^n-1\right)+\frac{n}{2p-1}$

• For $p=0.7$, $x_n=A\left(\left(\frac{7}{3}\right)^n-1\right)+\frac{5n}{2}$.

• If we have an additional boundary condition for the rightmost state $T$ as $x_T=0$ as we have in birth-date process etc., we have $A=-\frac{\frac{5T}{2}}{\left(\left(\frac{7}{3}\right)^T-1\right)}$, but such a state can't exist for a finite $n$, i.e. $T = \infty$ and the limiting value of $A$ at $T \to \infty$ is $0$, i. e., $\lim\limits_{T\to\infty}A=0$.

• Now, $x_1=\frac{4A}{3}+\frac{5}{2}$.

• Letting $A=0$, we get back our earlier solution $x_1=\frac{5}{2}=2.5$

The following simulation in R supports the above fact:

set.seed(123) N <- 10000 ns <- replicate(N, { n <- 0 nT <- 1 nH <- 0 while (nT != nH) { toss <- sample(0:1, 1, prob = c(0.3, 0.7)) if (toss == 1) { nH <- nH + 1 } else { nT <- nT + 1 } n <- n + 1 } n }) mean(ns) #[1] 2.493 

with the following histogram of the hitting time for $x_1$.