MathB.in
New
Demo
Tutorial
About
Take $Y_i$ to be the random variable equal to the number of trials needed to fill the $i$th bin (after $i-1$ bins have already been filled). The probability of filling an unfilled bin is $\frac{n - (i - 1)}{n}$ where $n$ is the total number of bins and $i-1$ is the number of already filled bins. \\ Given this probability, we can see that $Y_i$ has the geometric distribution with expectation value of $\frac{n}{n - (i-1)}$. Since expectation is linear, we can see that $E(X_1) = E(Y_1) + E(Y_2) + ... + E(Y_n) = \frac{n}{n} + \frac{n}{n-1} + ... + n = n \sum_{i=1}^{n} \frac{1}{i}$, which is what we have been asked to show. \\ To analyze the asymptotic behavior of this expression, we can use the Euler-Maclaurin formula, which tells us that: $$ \sum_{i=1}^{n} \frac{1}{i} = \int_{1}^{n} \frac{1}{t} dt + \int_{1}^{n} (t - \lfloor t \rfloor) \frac{-1}{t^2} dt + \frac{1}{n} (\lfloor n \rfloor - n)$$ $$ = \log(n) - \int_{1}^{n} (t - \lfloor t \rfloor) \frac{1}{t^2} dt + O(\frac{1}{n})$$ $$ = \log(n) - \int_{1}^{\infty} (t - \lfloor t \rfloor) \frac{1}{t^2} dt + \int_{n}^{\infty} (t - \lfloor t \rfloor) \frac{1}{t^2} dt + O(\frac{1}{n})$$ Since $\int_{n}^{\infty} (t - \lfloor t \rfloor) \frac{1}{t^2} dt \leq \int_{n}^{\infty} \frac{1}{t^2} dt = \frac{1}{n}$, we are left with: $$\log(n) - \int_{1}^{\infty} (t - \lfloor t \rfloor) \frac{1}{t^2} dt + O(\frac{1}{n})$$ The integral $\int_{1}^{\infty} (t - \lfloor t \rfloor) \frac{1}{t^2} dt$ exists since it is less than or equal to $\int_{1}^{\infty} \frac{1}{t^2} dt = 1$, so we are left with an expression that is: $$\log(n) - C + O(\frac{1}{n})$$ Where C is some constant. Therefore $n \sum_{i=1}^{n} \frac{1}{i}$ behaves as $\Theta(n \log(n))$ for large $n$ (since the constant and the $O(\frac{1}{n})$ terms will become negligible). To calculate a strict bound on the probability, we can use Markov's inequality: $$P(X_1 \geq 10 n \log n) \leq \frac{1}{10}$$ Or, in other words, $X_1 = O(n \log n)$ with $90\%$ probability.
ERROR: JavaScript must be enabled to render input!
Mon, 02 Oct 2017 05:58 GMT