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!

  • $\begingroup$ 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. $\endgroup$
    – Neal Young
    Feb 7, 2014 at 3:14
  • $\begingroup$ 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. $\endgroup$
    – xmerge
    Feb 7, 2014 at 14:19
  • $\begingroup$ 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. $\endgroup$
    – Neal Young
    Feb 7, 2014 at 20:02
  • $\begingroup$ @NealYoung Thanks so much! your argument makes great sense to me. $\endgroup$
    – xmerge
    Feb 7, 2014 at 22:44


Your Answer

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