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 pack the box with the items until the box is full. 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.

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.