# What happens if I toss a coin with decreasing probability to get a head?

Yesterday night, while I was trying to sleep, I found myself stuck with a simple statistics problem. Let's imagine we have a "magical coin", which is completely identical to a normal coin but for a thing: every time you toss the coin, the probability to get a head halves. So at t = 1 we have 50:50, then 25:75, then 12.5:87.5 and so on. At t = ∞ we are going to have 0:100.

My question is: if I toss this magical coin infinite times, can I say I am sure I am going to get at least one head? On one hand, I thought, the law of large numbers states that if an event is repeated infinite times, every state that is possible is bound to happen. On the other side, however, at t = ∞ the probability to get a head is zero.

Surely the solution of the problem is fairly easy, so what am I doing wrong?

-
Calculate or estimate the probability of no head ever. We get an infinite product. You can estimate the sum of the logarithms. – André Nicolas Mar 6 '14 at 23:02
The probability of no head ever is about $0.289$. – André Nicolas Mar 6 '14 at 23:18

The probability of not getting a head on the first toss is $\frac{1}{2}$, the probability of not getting a head on the second toss is $\frac{3}{4}$, the probability of not getting a head on the third toss is $\frac{7}{8}$, and so on.

So the probability of not getting a head on the first $n$ tosses is $$\frac{1}{2}\cdot\frac{3}{4}\cdot\frac{7}{8}\cdots \cdot \frac{2^n-1}{2^n}.$$ We take the limit as $n\to \infty$. The convergence is rapid. The infinite product is about $0.289$, a bit under.

-
So what's the expected number of heads after inf tosses? How would you calculate that? – Cruncher Mar 7 '14 at 6:00
Hi @AndréNicolas, I think I am missing something. The limit of $$(2^n - 1) / 2^n$$ when n -> ∞ is ∞, isn't it? – Secret Parrot Mar 7 '14 at 7:33
@AnnoysParrot No its not, just simplify the equation for the $n^{th}$ term: $\frac{2^n-1}{2^n} = 1-\frac{1}{2^n}$ therefore, the limit approaches 1 as $n\rightarrow \infty$. Also, Andre has shown that the probability of never getting heads is not zero, so you are NOT guaranteed to get a head, even after an infinite number of tosses. – user76844 Mar 7 '14 at 13:52
I was in too much of a hurry, was computing mean waiting time. Let $X_i=1$ if we get a head on the $i$-th try, $0$ otherwise. Then we want $E(\sum X_i)$. Since $\Pr(X_i=1)=\frac{1}{2^i}$. the expectation is $\sum \frac{1}{2^i}$, which is $1$. – André Nicolas Mar 7 '14 at 16:07

The law of large numbers does not apply, because the tosses are not identically distributed. The law only applies to many repetitions of the same experiment, or samples from the same distribution – but you sample from a different distribution every time.

The total probability that you ever toss a head is just the complement of tossing tails forever. Assuming the coin tosses are independent, this is simply the infinite product:

$\prod_{k=1}^\infty \frac{2^k - 1}{2^k} = \prod_{k=1}^\infty (1 - 2^{-k})$

We want to know whether or not this product is zero. I'm sure there are clever ways to deal with these products, but I don't know what they are, so I'm just going to wing it.

As André suggests in a comment, let's try taking the logarithm:

$\log\prod_{k=1}^\infty (1 - 2^{-k}) = \sum_{k=1}^\infty \log(1 - 2^{-k})$

If this converges, it must be the case that the product was not zero. Well, we can be hopeful here: we know that for really small x, $\log(1 + x)$ is pretty close to $x$, and $\sum_{k=0}^\infty -2^{-k}$ certainly does converge.

More precisely, since the derivative of $\log$ at $1$ is $1$, we know that for all sufficiently small $x$, $\frac{\log(1-x)}{-x}$ is greater than, say, $1/2$, so in particular there is some $N$ such that for all $k > N$, $\log(1-2^{-k}) > -2^{-(k+1)}$. So then:

\begin{aligned} \sum_{k=1}^\infty \log(1 - 2^{-k}) &= \sum_{k=1}^N \log(1 - 2^{-k}) &+& \sum_{k=N+1}^\infty \log(1-2^{-k})\\ &> \sum_{k=1}^N \log(1 - 2^{-k}) &+& \sum_{k=N+1}^\infty -2^{-(k+1)} \\ &> \sum_{k=1}^N \log(1 - 2^{-k}) &-& 2^{-(N+1)} \end{aligned}

(once upon a time I knew how to make aligned equations not look terrible, but I have forgotten).

Anyway, we successfully bounded the sum from below, which means that the product (the probability) is strictly positive. So it's possible for you to get no heads ever.

Unfortunately I have basically no idea how likely it is, since I don't know how large $N$ is. You'll need another, more sophisticated answer to show you that.

-
I think the products should start from 1. – Mechanical snail Mar 7 '14 at 1:35
Yep, you're right. Fixed. – Ben Millwood Mar 7 '14 at 19:48

The probability of getting all tails is $$\prod_{k=1}^\infty\left(1-\frac1{2^k}\right)\tag{1}$$ For $0\le x\le\frac12$, we have that $$\log(1-x)\ge-2\log(2)\,x\tag{2}$$ Therefore, since $$\sum_{k=1}^\infty\frac1{2^k}=1\lt\infty\tag{3}$$ we have $$\prod_{k=1}^\infty\left(1-\frac1{2^k}\right)\ge\frac14\tag{4}$$ Thus, the probability of getting a head is less than $\frac34$.

-

We can show that the expected number of heads is 1 by saying that each flip is an independent Bernoulli trial and we can write that the PDF is $p(x)=\frac{1}{2^k}$, therefore the Expected Value $E(x)$ (or number of heads you expect to see) in $n$ flips is $\sum\limits_{k=1}^n \frac{1}{2^k}$, which means after an infinite number of flips we can say $E(x) = \sum\limits_{k=1}^\infty \frac{1}{2^k}=1$. This is a known geometric series and a proof of its convergence to 1 can be found here.

-
If your argument were valid, then the probability of rolling a '1' in six rolls (of a six sided fair die) is one. Each roll is independent and $\sum_{n=1}^{6}\frac{1}{6} = 1$ What you have calculated is the expected number of heads; that is one. – Andrew Kelley Mar 6 '14 at 23:30
correct, i'll update my answer – The Ref Mar 6 '14 at 23:32
This is actually also a neat way of showing it's possible to get $0$ heads. Clearly it's possible to get $2$, so if it were "almost impossible" to get fewer than $1$ you'd get an expectation strictly greater than $1$. – Ben Millwood Mar 7 '14 at 20:06