I'm trying to understand this claim on page 205 of "The Probabilistic Method" by Alon and Spencer:

Set $p=c/n$. A key observation is that $Z_1 \sim Bin[n-1, c/n]$ approaches (in $n$) the Poisson distribution with mean $c$. Further, in a more rough sense, the same holds for $Z_t$ as long as $N_{t-1} \sim o(n)$.

Here $Z_t \sim Bin[N_{t-1}, c/n]$. So if $N_{t-1} \sim o(n)$ then wouldn't $Bin[N_{t-1}, c/n]$ approach a Poisson distribution with mean $0$? What am I missing here?


This is probably a typo; the rest of the sentence clarifies

or equivalently, the number of live and dead vertices is $o(n)$.

$N_{t-1}$ is not the number of live and dead vertices; it is the number of neutral vertices. Since all vertices are live, dead, or neutral, the number of live and dead vertices is $n - N_{t-1}$.

So the condition that should make this observation true is $N_{t-1} = n - o(n)$, at which point the Poisson approximation is not surprising any more.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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