Result of repeated applications of the binomial distribution? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T18:23:54Z http://mathoverflow.net/feeds/question/8816 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/8816/result-of-repeated-applications-of-the-binomial-distribution Result of repeated applications of the binomial distribution? DoubleJay 2009-12-14T00:13:07Z 2009-12-14T11:32:01Z <p>What is the result of multiplying several (or perhaps an infinite number) of binomial distributions together?</p> <p>To clarify, an example.</p> <p>Suppose that a bunch of people are playing a game with k (to start) weighted coins, such that heads appears with probability p &lt; 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.</p> <p>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?</p> http://mathoverflow.net/questions/8816/result-of-repeated-applications-of-the-binomial-distribution/8826#8826 Answer by Darsh Ranjan for Result of repeated applications of the binomial distribution? Darsh Ranjan 2009-12-14T02:33:21Z 2009-12-14T02:33:21Z <p>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.) </p> <p>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. </p> <p>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.) </p> http://mathoverflow.net/questions/8816/result-of-repeated-applications-of-the-binomial-distribution/8868#8868 Answer by Piotr Miłoś for Result of repeated applications of the binomial distribution? Piotr Miłoś 2009-12-14T11:32:01Z 2009-12-14T11:32:01Z <p>Do you want to get a quick but approximate answer or rather the exact law (or may be just expectation and variation)?</p> <p>This is indeed the clasical <strong>Galton-Watson</strong> tree (<a href="http://en.wikipedia.org/wiki/Galton%E2%80%93Watson_process" rel="nofollow">http://en.wikipedia.org/wiki/Galton%E2%80%93Watson_process</a>). A very good reference (and quite elementary!) is: "Athreya, Ney" - Branching processes. Each coin is an invidual which either <em>survies</em> to the next round with probability $p$ or <em>dies</em> with probability $1-p$.</p> <ol> <li><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 <em>the law of rare events</em>. It says that approximately the number of the inviduals surviving $k$ rounds is the <strong>Poisson</strong> r.v. with parameter $\lambda := n p^k$. The error of this approximation is upperbounded by $\lambda^2/n$.</p></li> <li><p>(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</p></li> </ol> <p>$\mathbb{P}(Z = l) = \binom{n}{l}(1-p^k)^{n-l}p^{kl}s^l$</p>