1
$\begingroup$

The following is taken from page 8 of Alon and Spencer's The Probabilistic Method.

$ \prod_{i = 0}^{n-1} \frac{v - 2i}{v-i} \sim e^{-n^2/2v} $ as long as $v \gg n^{3/2}$, estimating $\frac{v-2i}{v-i} = 1 - \frac{i}{v} + O\left(\frac{i^2}{v^2}\right) = e^{-i/v + O(i^2/v^2)}$

I'm able to derive the asymptotics expression on the first line given the equality on the second line, and it is in this derivation that the condition $v \gg n^{3/2}$ is used. What I do not understand:

  1. Why is $\frac{v-2i}{v-i} =1 - \frac{i}{v} + O\left(\frac{i^2}{v^2}\right)?$ At a gut level, I see that $i$ is quite small compared to $v$, so the ratio should be a little less than $1$, but I think I proper derivation would be instructive to me.

  2. Why is $1 - \frac{i}{v} + O\left(\frac{i^2}{v^2}\right) = e^{-i/v + O(i^2/v^2)}?$ I am familiar with the fact that $1 - x \sim e^{-x}$ for small, positive $x$, but what justifies taking $O(i^2/v^2)$ directly into the exponent?

1 Answers 1

2

Let $a = \dfrac{i}v \ll 1$. Then \begin{align} \dfrac{v-2i}{v-i} & = \dfrac{1-2a}{1-a} = (1-2a)(1+a+O(a^2))\\ & = 1 + a + O(a^2) -2a + O(a^2) = 1 - a + O(a^2) \end{align}

For the second part, $e^{-a + O(a^2)} = e^{-a} \cdot e^{O(a^2)} \leq e^{-a} \cdot e^{ca^2} = \left( 1-a + O(a^2)\right) \left( 1 + O(a^2)\right) = 1 - a + O(a^2)$

  • 0
    Both my questions result from a failure to consider Taylor expansions (first for $(1-x)^{-1}$ and second for $e^x$), which should have been my first thought. Thank you for the insight.2012-12-16