0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ I is a "first passage time" for a biased random walk. That term might help you with finding a useful reference. $\endgroup$ Oct 2, 2014 at 17:42
  • $\begingroup$ Thanks Yoav, will look into that. But won't that require some knowledge about the distribution of $X_i$? $\endgroup$
    – murv
    Oct 2, 2014 at 18:09
  • $\begingroup$ If the X_i hands you the items, I don't see what choice you have where greedily applies, unless you can choose to stop before the box is full. $\endgroup$ Oct 2, 2014 at 19:35

1 Answer 1

0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thank you very much. Could you please explain in little more detail how I would apply Chebyshev on the intersection of the two events $S_{a(n)} \leq n$ and $S_{b(n)} > n$. Are they independent events? $\endgroup$
    – murv
    Oct 2, 2014 at 23:47
  • $\begingroup$ No, they're certainly not independent, but you can use $P(A \cap B) \ge 1 - P(A^c) - P(B^c)$. $\endgroup$ Oct 3, 2014 at 1:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.