Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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

1 Answer 1

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.

share|improve this answer
    
Ah! Thank you for this! –  Lachryma Papaveris Mar 8 '13 at 22:42

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.