1
$\begingroup$

Let us define $M_0=2^n$ for $n\in\mathbb{N}$. Let $\ell\in\mathbb{N}$ be the number of random variables we are working with. For $1\leqslant i\leqslant\ell$, we define $M_i$ to be a random variable following a binomial distribution with parameters $M_{i-1}$ and $2^{-n}$.

I'm interested in computing $\mathbb{P}\left[M_\ell=1\middle|M_\ell\geqslant1\right]$. To be fair, I only needed to lower-bound this probability, which is easy to do by computing $\mathbb{P}\left[M_1=1\middle|M_1\geqslant1\right]\approx\frac{\mathrm{e}^{-1}}{1-\mathrm{e}^{-1}}>\frac12$, but, out of curiosity, I was wondering if it was possible to get a closed-form for $\mathbb{P}\left[M_\ell=1\middle|M_\ell\geqslant1\right]$, and I do not know of any theorem that would help me with this.

Intuitively, this probability should decrease exponentially fast to $1$, and it might be possible to get the closed-form expression of the probability for $\ell\leqslant3$ by hand, but it will quickly become tedious to operate that way. Is there any clever way I'm missing for this?

$\endgroup$

1 Answer 1

1
$\begingroup$

Abbreviate $N=M_0=2^n$ and $b=1/N$. As described, the conditional distribution of $M_i$, given that $M_{i-1}=n$, is binomial with parameters $n$ and $b$. The conditional generating function of $M_i$ is therefore $$ E[s^{M_i}\mid M_{i-1}]=(1-b+bs)^{M_{i-1}}. $$ Using $g_i$ to denote the generating function of $M_i$, this leads to the recursion $$ g_{i}(s) = g_{i-1}(1-b+bs), $$ and, because $g_0(s) = s^N$, by recursion, $$ g_i(s) = (1-b^i+b^is)^N, \qquad0\le s\le 1. $$ In other words, $M_i$ has the binomial distribution with parameters $N$ and $b^i$.

In particular, $$ P[M_i=1\mid M_i\ge 1] = {Nb^i(1-b^i)^{N-1}\over 1-(1-b^i)^N}. $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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