Number of bins in best packing of bin packing problem is Martingale

179 Views Asked by At

I have items $a_1,..., a_n$ with $0\leq a_i\leq 1$ and $1\leq i\leq n$, where $a_i$ is chosen independently and the capacity of each bin is 1. I want to be able to apply the Hoeffding inequality to the number of bins used in the best packing of resulting items (let's call it $P$). For this, do I have to show it is Martingale? I began by saying that $$P = \left\lceil \sum_{i=1}^{ n } a_i \right\rceil$$. After that, should I show that $\mathbb{E}[P_{i+1}] = P_{i}$? How do I begin proving that?