Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
This looks like a branching process problem in disguise. If you want to calculate the exact distribution for a single player, then my first offhand impression is that one would get some kind of recurrence relation which should be amenable to direct attack or else to some kind of "generating function" machine? Does that sound plausible, familiar or useful to you? or are the expressions you get still intractable for your purposes? –  Yemon Choi Dec 14 '09 at 2:28
    
To clarify my previous comment: nothing personal, but I'd prefer to have some indication of how far you've got or how much you've worked at this problem before I sit down and start scribbling. It might also save people time in their answers if they knew whether or not to start from scratch. –  Yemon Choi Dec 14 '09 at 2:31
    
Sorry about that. I just want to know if there is a simple and straight-forward answer that I just couldn't find in a literature search. I'm actually trying to answer a more generalized version of this. Anyone who tries to sit down and solve it from scratch will probably encounter some pretty harsh difficulties, I think. All I've managed to do is find a recurrence and a very loose bound, and I want to know asymptotic behavior. Darsh's answer below looks very much like what I want. If not, I'll edit the question with more details, but for now I'm trying to do this mostly on my own. –  DoubleJay Dec 14 '09 at 3:43

2 Answers 2

up vote 4 down vote accepted

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

share|improve this answer

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$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.