# Bound the number of rounds in the sampling

Suppose we have a sequence $a_1,a_2,\ldots, a_n$, each $a_i$ is sampled uniformly and independently from $[0,1]$. Define

$$J_1=1,\\ \text{for}~i>1, ~J_i = 1 \iff a_i < \min \{a_1,a_2,\ldots,a_{i-1}\} \\ \text{otherwise}, J_i=0$$ By some sort of calculation, we can get $$E[J_i] = \frac{1}{i}$$ Thus if we let $J=\sum_{i=1}^nJ_i$, we have $$E[J] = \sum_{i=1}^n \frac{1}{i} \approx \ln(n)$$

Now, my question here is can we bound the probability $P(J-E[J] > \delta)$?

With Azuma's inequality, if we define $Y_i = E[J|J_1,J_2,\ldots,J_i]$, we can get $$P(J-E[J]>\delta)=P(Y_n-Y_0>\delta) < e^{-\frac{\delta^2}{2n}}$$ But this bound does not make much sense since when $n$ is large, it actually tends to be $1$.

The bound given by Markov inequality is also useless in our case. Any suggestion is welcome and highly appreciated.

Thanks so much!

• It seems to me that the $J_i$ are in fact independent, so a standard (relative error) Chernoff bound should give you $$Pr[J > (1+\epsilon) E[J]] ~\le~ \exp(-\epsilon^2 E[J] / 3) ~\approx~ n^{-\epsilon^2/3}$$ or so. Feb 7, 2014 at 3:14
• Hi, thanks for your comment. But it looks to me that $J_i$ are not independent, or at least non-trivial to show they are independent. Would you help to explain why they are independent? Thank you. Feb 7, 2014 at 14:19
• Hmm, if you know the order (but not the values) of $a_1,\ldots,a_i$, what information does that give you about $J_{i+1}$? Unless I'm mistaken, it seems like it would be a good exercise for homework. Feb 7, 2014 at 20:02
• @NealYoung Thanks so much! your argument makes great sense to me. Feb 7, 2014 at 22:44