Each of n hunters selects a rabbit at random from a group of m rabbits, aims a gun at it, and then all the hunters shoot at once. The hunters select a rabbit independently.
Using Markov inequality and suitable estimates, show that if we have $n > m( \ln{m + 5})$, then with probability at least $0.99$, no rabbit survives.
I have been struggling with this problem for a while. I need some help. Thank you for your time!
Solution:
Let $X$ be a random variable that counts the number of surviving rabbits. Now using indicator variables (taking $A_i$ as the event that the ith rabbit survives) $I_{A_i}$, the expected value for $X$ = $\sum_{1}^{m} I_{A_i}$. With this, the expected value for $X$, i.e $\mathbb{E}[X] = \sum_{1}^{m} \mathbb{E}[I_{A_i}] = \sum_{1}^{m} P(A_i)$. This is just revising basic concepts.
Now,
$$P(A_i) = \Biggl(1-\frac{1}{m}\Biggr)^{n}$$.
This implies that the expected value is
$$\mathbb{E}[X] = m\Biggl(1-\frac{1}{m}\Biggr)^{n}$$.
Since $n> m (\ln{m} +5)$, we obtain,
$$\mathbb{E}[X] = m\Biggl(1-\frac{1}{m}\Biggr)^{m(\ln{m}+5)} \le m\mathit{e}^{-(\ln{m}+5)} = \frac{1}{\mathit{e}^{5}}$$
Markov's inequality is $$P({\omega \in \bigtriangleup ; X(\omega) \ge t\mu}) \le \frac{1}{t}$$.
Simply stated, it is saying that the probability that the random variable for some event would exceed $t\mu$, where $\mu$ is the expected value for the random variable, is at most $\frac{1}{t}$.
Therefore, the probability that $X(\omega) \ge 1$ is at most $\frac{1}{e^5}$. This is the probability that at least one rabbit survives. It follows that the probability that no rabbit survives is $\ge 1 - \frac{1}{e^5} > 0.99 $
This isn't a difficult problem, but I kept reading the $n>\ln{m} +5$ inequality as if the $5$ was in the natural logarithms.