Expected value and state diagrams

Question

I have two questions:

I have a coin that is slightly unbalanced. The odds of getting heads are 60%. What are the odds that if I flip it endlessly, at some point during my flipping I have a total of three more tails than heads?

5 people stand in a line facing one direction. In every round, the person at the front moves randomly to any position in the line, including the front or the end. Suppose that $\frac{m}{n}$ is the expected number of rounds needed for the last person of the initial line to appear at the front of the line, where m and n are relatively prime positive integers. What is $m+n$?

I tried using state diagrams and infinite geometric sequences, but it got extremely complicated. Is there any way to solve the first question?

I also do not know where to start with the second problem. Any ideas?

Thanks!

Answer 1

Problem $2$)

Let $E$ be the required expected value.

Then $E = \displaystyle\sum_{n=5}^{\infty} n\times P(\text{last to first in }n\text{ moves})$

To calculate $P(\text{last to first in }n\text{ moves})$, you can note that a person needs to get inserted into the last position exactly $5$ times, the last time being in the last round.

So this boils down to counting strings of length $n$ made of an alphabet of size $5$ (denoting the $5$ positions in which the first person may get inserted) whose last letter is $L$, and the remaining $n-1$ letters contain exactly $4$ $L$'s. The number of such strings is ${n-1\choose 4}4^{n-5}$.

So $P(\text{last to first in }n\text{ moves}) = \dfrac{{n-1\choose 4}4^{n-5}}{5^n}\implies E = \displaystyle\sum_{n=5}^{\infty}\left(\dfrac{{n-1\choose 4}4^{n-5}}{5^n}\right) = 25$.

You can evaluate the last series by differentiating the geometric series $\sum x^n$ 4 times, multiplying appropriate constants and plugging in $x=4/5$.

$25$ as the answer makes sense because you'd expect $5$ rounds to get the first person to go into the last position, then $5$ more for that to happen again and so on 5 times.

---

Problem $1$)

Im not so sure if my crack at this is right but here goes -

Let $E_t$ be the event that at toss $t$, we obtain $3$ more heads than tails for the first time in our sequence. Such a $t$ has to be odd and greater than or equal to $3$, because $\#\text{Heads}+\#\text{Heads}-3$ is always odd.

Our required probability then is $P = P\left(\bigcup\limits_{i=k}^{\infty}E_{2k+1}\right)=\displaystyle\sum_{k=1}^{\infty}P(E_{2k+1})$ since $E_i$ are independent.

Also, $P(E_{2k+1}) = \frac{3}{5}P(\text{exactly 2 more heads than tails in } 2k \text{ tosses})$.

Also, $P(\text{exactly 2 more heads than tails in } 2k \text{ tosses}) = \dfrac{2k\choose k+1}{2^{2k}}$.

So our final expression then is $P = \displaystyle\sum_{k=1}^{\infty}\left(\frac{3}{5}\cdot\dfrac{2k\choose k+1}{2^{2k}}\right)$

This series happens to diverge, so either Ive made a blunder or this is happening because our required set of sequences is dense in thr set of all $HT$ sequences.

Answer 2

(I’d remind the OP to post one question at a time, but the account no longer exists.)

The existing answer is wrong for both problems (perhaps unsurprisingly, as the user’s profile page says “Take my answers with a pinch of salt”).

For the first problem, let $p$ be the probability to obtain heads. To simplify things, start with $3$ fictitious flips of heads, and ask for the probability that we ever get back to $0$ excess heads. The probability $p_n$ for this to happen when the current excess is $n$ satisfies the recurrence relation

$$ p_n=p\cdot p_{n+1}+(1-p)p_{n-1}\;. $$

The general solution can be obtained using the characteristic equation $\lambda=p\lambda^2+1-p$, with solutions $\lambda_1=1$ and $\lambda_2=\frac1p-1$, so

$$ p_n=c_1+c_2\left(\frac1p-1\right)^n\;. $$

Since $\lim_{n\to\infty}p_n=0$, we must have $c_1=0$, and then $p_0=1$ yields $c_2=1$, so

$$ p_n=\left(\frac1p-1\right)^n\;. $$

In your case, with $p=\frac35$ and $n=3$, the desired probability is

$$ \left(\frac53-1\right)^3=\frac8{27}\approx30\%\;. $$

For the second problem, let $\ell=5$ denote the length of the line. In every move, there are $\ell+1$ equiprobable possibilities. To move the last person forward by one, we first have to wait until $1$ of these possibilities is realized, then until one out of $2$ of them is realized, and so on, until in the last step any of $\ell$ possibilities moves the person to the front. The expected total number of steps is thus

$$ \sum_{k=1}^\ell\frac{\ell+1}k=(\ell+1)H_\ell\;, $$

where $H_\ell$ is the $\ell$-th harmonic number. In your case, with $\ell=5$, this is

$$ (5+1)H_5=6\cdot\frac{137}{60}=\frac{137}{10}\;, $$

so $m+n=147$.