Result of repeated applications of the binomial distribution? - MathOverflow

Result of repeated applications of the binomial distribution?

2009-12-14T00:13:07Z

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 by Darsh Ranjan for Result of repeated applications of the binomial distribution?

2009-12-14T02:33:21Z

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 by Piotr Miłoś for Result of repeated applications of the binomial distribution?

2009-12-14T11:32:01Z

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

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