Result of repeated applications of the binomial distribution?

Question

What is the result of multiplying several (or perhaps an infinite number) of binomial distributions together?

To clarify, an example.

Suppose that a bunch of people are playing a game with k (to start) weighted coins, such that heads appears with probability p < 1. When the players play a round, they flip all their coins. For each heads, they get a coin to flip in the next round. This is repeated every round until they have a round with no heads.

How would I calculate the probability distribution of the number or coins a player will have after n rounds? Especially if n is extremely high and p extremely close to 1?

Answer 1

Here's how I interpret your example: there are a bunch of coins (k initially), each being flipped every round until it comes up tails, at which point the coin is "out," And you want to know, after n rounds, the probability that exactly j coins are still active, for j = 0, ..., k. (The existence of multiple players seems irrelevant.)

In that case, this is pretty elementary: after n rounds, the probability of each individual coin being active is p^n, so you have a binomial distribution with parameter p^n, k trials. Since you want to send p to 1 and n to infinity, note that replacing p by its square root and doubling n gives you the same distribution.

Your problem has a surprisingly fascinating generalization, which I believe is called the Galton-Watson process. Its solution has a very elegant representation in terms of generating functions, but I think there are very few examples in which the probabilities are simple to compute in general. Your instance is one of those. (The generalization: at each round, you have a certain number of individuals, each of which turns (probabilistically, independently) into a finite number of identical individuals. If the individuals are coins and each coin turns into one coin with probability p and zero coins with probability 1-p, and you begin with k coins, then we recover your example.)

Answer 2

Do you want to get a quick but approximate answer or rather the exact law (or may be just expectation and variation)?

This is indeed the clasical Galton-Watson tree (http://en.wikipedia.org/wiki/Galton%E2%80%93Watson_process). A very good reference (and quite elementary!) is: "Athreya, Ney" - Branching processes. Each coin is an invidual which either survies to the next round with probability $p$ or dies with probability $1-p$.

1. (Approximate answer). You start with $n$ inviduals of which each has chance $p^k$ that it survives $k$ rounds. If $n$ is large, $p^k$ is small we can use the law of rare events. It says that approximately the number of the inviduals surviving $k$ rounds is the Poisson r.v. with parameter $\lambda := n p^k$. The error of this approximation is upperbounded by $\lambda^2/n$.

2. (Exact solution). Let $\mathbb{P}(X=1) = p^k = 1- \mathbb{P}(X=0)$. $X$ denote if an individual survied $k$ rounds (1) or not (0). Its generating function is $F_X(s) = (1-p^k) + p^k s$. If you start with $n$ individuals and denote the number of them surviving $k$ rounds by $Z$ then its generating function is $F_Z(s) = F(s)^n = \sum_{l=0}^n \binom{n}{l}(1-p^k)^{n-l}p^{kl}s^l$. Therefore

$\mathbb{P}(Z = l) = \binom{n}{l}(1-p^k)^{n-l}p^{kl}s^l$