# A twist on a classic high school problem

$$\text{"Toss a fair coin, if heads: stop; if tails: toss again."}$$

Not a particularly fun game, but a classic probability exercise nonetheless; the probability of this process ending is easily shown to be $1:$

$$\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\cdots =1$$

This made me wonder, what happens if instead of two outcomes, we have three? In better terms, suppose we randomly generate a number from $\{0,1,2\}$ (each pick is equiprobable); if $0:$ stop, if $1:$ pick again, if $2:$ pick twice $($even if the first pick is $0)$. In the last case, sum the results of both picks, giving us the number of picks required for the next round. Here is an example of such a game:

$$\text{start}\to(1)\to(2)\to (1,2)\to (0,2,1)\to (0,1,0)\to (0)\to\text{end}$$

(the numbers in brackets represent the outcomes of each pick)

Again, the probability that this process will end is $1$ (justification below). Upon finding this, I was a tad puzzled. Surely this probability cannot be $1$ if the number of possible outcomes is large enough?

It turns out that it fails to give $1$ at the next integer. Indeed, if we randomly generate from $\{0,1,2,3\}$, same rules as previous, with the added "if $3:$ pick thrice", the probability that the process will end stoops down to $\sqrt{2}-1$.

$$\star$$

I was interested in finding an expression which gives us this probability in terms of the largest integer in the initial set (only looking at sets of the form $\{0,1,\cdots \,n\}$ for now); I believe I have found a polynomial whose solutions give the desired probability. There are several issues that I have not managed to solve:

• the aforementioned polynomial has two distinct roots in $[0,1]$: one is $1$ (when the set is $\{0,1\}$ (coin toss case) or $\{0,1,2\}$, the roots are not distinct). I am almost certain that the desired probability is the lower root. However, I have not found a decent way of supporting this claim.
• I would like some criticism on my working; I have never studied degree level maths, and even less taken a course in probability, so I may well have abused of some notation and made some assumptions which I shouldn't be allowed to make. Feel free to critise whatever you feel necessary!

$$\textbf{Problem}$$

Let $\Omega$ be a set of $\alpha\geq 2$ consecutive integers with smallest element $0:\;\Omega=\{0,1,\cdots\,\alpha-1\}$

Process:

Randomly and independently generate elements of $\Omega$ $r_n$ times. If the sum of the results is $r_{n+1}=0$ the process ends. If the sum of the results is $r_{n+1}\geq 1$, randomly and independently generate elements of $\Omega\;r_{n+1}$ times, etc. The process begins with $r_1=1$.

What is the probability of this process ending?

$$\textbf{Attempted solution}$$

$\phi:$ end of process , $r_n:$ number of picks required at stage $n$

Notice that for $n>1:$

$$\left\{ \begin{array}{l l} p(\phi|r_n=0)=0 &\\ p(\phi|r_n=1)=p(\phi|r_1)=p(\phi) & \; (r_n=1\;\text{returns us to the initial conditions}) \end{array} \right.$$

For $r_n\geq 1$ the event $(\phi|r_n)$ is equivalent to:

$$\left(\bigcap_{k=1}^{r_n}\phi|i_k\right)$$

where $(i_k)$ requires a single independent pick i.e. $(i_k)\Leftrightarrow (r_1)$

Therefore we may write for $n>1,r_n\geq 1:$

$$p(\phi|r_n)=p\left(\bigcap_{k=1}^{r_n}\phi|i_k\right)=\prod_{k=1}^{r_n}p(\phi|i_k)=p(\phi|r_1)^{r_n}=p(\phi)^{r_n}$$

Additionally, since all results are equipossible, $p(r_n=k\in\Omega)=\dfrac{1}{\alpha}$

The law of total probability gives:

\begin{align*}p(\phi)&=p(\phi|r_n=1)\\&=\sum_{k=0}^{\alpha-1}p(r_{n+1}=k)p(\phi|r_{n+1}=k)\\&=\frac{1}{\alpha}\sum_{k=0}^{\alpha-1}p(\phi|r_{n+1}=k)\\&=\frac{1}{\alpha}\sum_{k=0}^{\alpha-1}p(\phi)^k\end{align*}

For clarity, denote $\lambda$ the desired probability $p(\phi)$. We are left to solve:

$$\lambda =\frac{1}{\alpha}\sum_{k=0}^{\alpha-1}\lambda^k\Rightarrow\alpha\lambda =\sum_{k=0}^{\alpha-1}\lambda^k$$ $$\Rightarrow\lambda^{\alpha}-\alpha\lambda^2+\alpha\lambda-1 =0$$

Notice that for $\alpha=2$ this reduces to $(\lambda-1)^2=0\Rightarrow \lambda=1$ which agrees with the coin toss scenario, and $\alpha=3$ gives $(\lambda-1)^3=0\Rightarrow\lambda=1$ which is why my initial twist on the problem also has probability $1$.

By Descartes' rule of signs this polynomial has exactly three positive roots. It is easy to show that the these roots lie in $[0,1]$. In fact, two of them are $1$, and the other is $<1$ when $\alpha\geq 4$. This is why, for $\alpha=4$, I believe the probability is the lower solution:

$$(\lambda-1)^2(\lambda^2+2\lambda-1)=0\Rightarrow\lambda=\sqrt{2}-1\;\;\text{if}\;\;\lambda\neq 1$$

We can observe that this other solution approaches $0$ when $\alpha\to\infty$ which agrees with intuition. If what I have done so far is correct, and my intuition is correct, how can I justify that the solution is the smallest positive solution to $\lambda^{\alpha}-\alpha\lambda^2+\alpha\lambda-1 =0?$

$$\star$$

Many thanks to anyone who put the effort into reading this through. If those who answer wish to include any probability theory that is beyond the basic tools that I have used, I would be very grateful is you could explicitly name the tools you use, so that I can study them to fully understand your answers.

-
This rediscovers some results from the theory of branching processes, namely that the probability of extinction $q$ starting from one individual is the smallest root in $[0,1]$ of the equation $q=f(q)$, where $f$ denotes the generating function of the number of children of any individual (your case being when $f(x)=1+\cdots+x^{\alpha-1}$). If really you figured all this by yourself, congratulations are in order. –  Did Mar 8 '13 at 9:29
@Did I see. Thank you for the link, I shall read around branching processes then. Thank you for the compliment as well! :) –  Lachryma Papaveris Mar 8 '13 at 22:41

I shall provide a different approach to getting the same polynomial equation, as it will then be easy to see why the probability should be the smaller root when $\alpha \geq 4$.

Let $s_n$ be the random variable representing the sum of all the "picks" at stage $n$, for $n \geq 0$ (For $n=0$, we treat it as $s_0$ is always $1$, since we have 1 pick at stage 1. In comparison to your approach, $s_n=r_{n+1}$) We examine the probability generating function $f_n(x)=E(x^{s_n})$.

Since $s_0$ is always $1$ by definition, $f_0(x)=E(x^{s_0})=x$.

Note that if we let $X$ be the random variable representing 1 pick, then $s_{n+1}$ is the sum of $s_n$ identical copies of $X$. Thus $E(x^{s_{n+1}}|s_n=k)=\left(\frac{1+x+ \ldots + x^{\alpha-1}}{\alpha}\right)^k$, so by the law of total expectation, $f_{n+1}(x)=E(x^{s_{n+1}})=E(E(x^{s_{n+1}}|s_n=k))=E(\left(\frac{1+x+ \ldots + x^{\alpha-1}}{\alpha}\right)^{s_n})=f_n(\frac{1+x+ \ldots + x^{\alpha-1}}{\alpha})$.

Let $P(x)=\frac{1+x+ \ldots + x^{\alpha-1}}{\alpha}$, then we have by induction $f_n(x)=P^n(x)$, where $P^n(x)$ denotes the $n^{\text{th}}$ iterate of $P(x)$. Now $P(s_n=0)=f_n(0)=P^n(0)$.

The equation $P(x)=x$ has exactly 2 roots, a root at $x=1$, and a smaller root $0<x=c<1$. ( To see this, note that Descartes' rule of signs gives at most 2 roots, then $x=1$ is a root, and $P'(x)>1$ for $x=1- \epsilon$ for small enough $\epsilon>0$, so that $P(a)<0$ for $1-\epsilon<a<1$, and $P(0)>0$, so by Mean value theorem, since $P(x)$ is continuous, it has a root between $0$ and $1$.)

Since $P(0)=\frac{1}{\alpha}>0, P(c)=c$, $P(x) \not =x$ for $0<x<c$, and $P(x)$ is a continuous and strictly increasing function for $0 \leq x$, we have $x<P(x)<c$ for $0 \leq x<c$.

Note $P^0(0)=0<c$, so by induction we can show $P^n(x)<c$, and thus $P^n(x)<P^{n+1}(x)$, so the sequence $P_n(x)$ is strictly increasing and bounded from above by $c$, and thus has a limit $0<p\leq c$. $p$ must also be a root of $P(x)=x$, so $p=c$.

We have $c=\lim_{n \to \infty}{P^n(0)}=\lim_{n \to \infty}{P(s_n=0)}=P(\phi)$, where $P(\phi)$ is the probability of ending, in accordance to your notation.

-
Ah! Thank you for this! –  Lachryma Papaveris Mar 8 '13 at 22:42