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

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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