Assume we have a box of size $n$, some items $X\_i, i \in N$ of unknown distribution, with expected size $\mu>0$ and variance $\sigma^2$. We want to randomly and greedily pack the box with the items until one item does not fit anymore. Let $I$ denote the number of packed items.


I would like to show that, for a function $f(n)$ where $\omega (1) << f(n) << \sqrt{n}$, this holds:


$P[\frac{n}{\mu}(1-\frac{1}{f(n)})\leq I \leq \frac{n}{\mu}(1+\frac{1}{f(n)})] = 1- \mathcal{O}(\frac{f(n)^2}{n})$


I've tried using Chebyshev's inequality on the complementary probability ($I$ outside of the interval) to bound the probability. But this requires knowledge of the variance of $I$ which I am having problems figuring out.



Expected number of packed items in box
If $S\_i$ is the sum of the first $i$ items chosen (I assume this is with replacement), then $S\_i$ has mean $\mu i$ and variance $\sigma^2 i$.
Now $a(n) \le I < b(n)$ iff $S\_{a(n)} \le n$ and $S\_{b(n)} > n$.
Use Chebyshev on those.


