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.

Improve this question
$\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$
    – Yoav Kallus
    Commented 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
    Commented 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$
    – The Masked Avenger
    Commented Oct 2, 2014 at 19:35

1 Answer 1

Reset to default
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.

Improve this answer
$\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
    Commented 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$
    – Robert Israel
    Commented Oct 3, 2014 at 1:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .