1

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?

theQman
  • 1,097

1 Answers1

0

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.

Misha Lavrov
  • 142,276