Exercise 2.4.22* (Estimation of $\prod_{j=1}^{k-1} \left( 1 - \frac{j}{n} \right)$)

Question

Show that the product in Lemma 2.21 is smaller than $\exp\left(-\frac{k^2}{2n} + \frac{k}{2n}\right)$, but larger than $\exp\left(-\frac{k^2}{2n} - \frac{k^3}{3n^2}\right)$

Hint: Show that $1-v \leq e^{-v}$ for all real numbers $v$. Derive a corresponding lower bound from inequality (1.9) in Section 1.3.

Richard Ganaye · Accepted Answer

ewcommand{\R}{\mathbb{R}}

Note: There is a missing hypothesis. We must suppose that $k \leq n/2$ to prove the second inequality (see below).

We can give numerical counterexamples. For $k = 90, n =100$
$$ \exp\left(-\frac{k^2}{2n} - \frac{k^3}{3n^2}ight) > 7.20 \cdot 10^{-29} >  2.58\cdot 10^{-29} > \prod_{j=1}^{k-1} \left( 1 - \frac{j}{n} ight).$$

With Sage:

\begin{verbatim}
def left_member(k,n):
    return exp(-k^2/(2*n) - k^3/(3*n^2)).n()
    
def right_member(k,n):
    return prod([1- j/n for j in range(1,k)]).n()
    
left_member(90,100)

7.20638686090140e-29

right_member(90,100)

2.57182031095525e-29
\end{verbatim}

\begin{proof} The product in lemma 21, giving the probability that numbers $u_1,\ldots,u_k$ independently chosen from the set $\{1,2,\ldots, n\}$ are distinct, is
$$P = \left( 1 - \frac{1}{n} ight) \left( 1 - \frac{2}{n} ight)\cdots \left( 1 - \frac{k-1}{n} ight),$$
where $k \leq n$.

The function $\exp$ is convex, since $\exp''(x) = \exp(x)>0$ for all $x \in \R$. Therefore the graph of $f$ is above the tangent at $0$, which gives
$$\forall x \in \R,\ 1+x \leq e^x.$$
Substituting $-x$ to $x$, we obtain
$$\forall x \in \R,\  1-x \leq e^{-x}.$$
Therefore
\begin{align*}
P &= \prod_{j=1}^{k-1} \left( 1 - \frac{j}{n} ight) \
&\leq \prod_{j=1}^{k-1} \exp \left(-\frac{j}{n}ight)\
& = \exp\left( -\frac{1}{n} \sum_{j=1}^{k-1} jight)\
&= \exp\left( -\frac{1}{n} \frac{(k-1)k}{2} ight)\
&=\exp\left(-\frac{k^2}{2n} + \frac{k}{2n}ight).
\end{align*}

To prove the other inequality, we use inequality (1.9), page 27:
$$0< \frac{1}{1-x} \leq e^{x + x^2},\qquad 	ext{if } 0 \leq x \leq 1/2.$$
Then 
$$\exp(-x -x^2) \leq 1 -x,\qquad 	ext{if } 0 \leq x \leq 1/2.$$

We must suppose here that $k \leq n/2$, since this inequality is not true on $[0,1[$ (for instance, if $x = 0.7$, $\exp(-x -x^2) > 0.304 > 0.3 = 1-x$) .

We apply this inequality to $x = j/n$, where $0 \leq j/n \leq 1/2,$ for $1 \leq j \leq k-1$ (because $k \leq n/2$), so 
\begin{align*}
P &= \prod_{j=1}^{k-1} \left( 1 - \frac{j}{n} ight) \
&\geq \prod_{j=1}^{k-1} \exp \left(-\frac{j}{n} - \frac{j^2}{n^2}ight)\
&=\exp \left( -\frac{1}{n} \sum_{j=1}^{k-1} j -\frac{1}{n^2} \sum_{j=1}^{k-1} j^2ight)\
&=\exp \left(-\frac{1}{n} \frac{(k-1)k}{2} -\frac{1}{n^2} \frac{(k-1)k(2k-1)}{6} ight)\
&=\exp \left( -\frac{k^2}{2n} - \frac{k^3}{3n^2} + \frac{k}{2n}   +\frac{k^2}{2n^2} - \frac{k}{6n^2} ight)\
&=\exp \left( -\frac{k^2}{2n} - \frac{k^3}{3n^2} + \frac{k}{2n}  + \frac{3k^2 - k}{6n^2} ight)\
&\geq \exp \left( -\frac{k^2}{2n} - \frac{k^3}{3n^2} ight),
\end{align*}
because $\frac{k}{2n}  + \frac{3k^2 - k}{6n^2}\geq 0$.

To conclude, $\prod_{j=1}^{k-1} \left( 1 - \frac{j}{n} ight)$ is smaller than  $\exp\left(-\frac{k^2}{2n} + \frac{k}{2n}ight)$, and {\bf if $k \leq 2n$}, is larger than $\exp\left(-\frac{k^2}{2n} - \frac{k^3}{3n^2}ight)$.
\end{proof}

Exercise 2.4.22* (Estimation of $\prod_{j=1}^{k-1} \left( 1 - \frac{j}{n} \right)$)

Answers

Comments

Exercise 2.4.22* (Estimation of $\prod_{j=1}^{k-1} \left( 1 - \frac{j}{n} \right)$)

Answers

Comments

Add answer