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

<p>$$
    J_1=1,\\
    \text{for}~i&gt;1, ~J_i = 1 \iff a_i &lt; \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)
$$</p>

<p><strong>Now, my question here is can we bound the probability $P(J-E[J] &gt; \delta)$?</strong></p>

<p>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]&gt;\delta)=P(Y_n-Y_0&gt;\delta) &lt; e^{-\frac{\delta^2}{2n}}
$$
But this bound does not make much sense since when $n$ is large, it actually tends to be $1$.</p>

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

<p>Thanks so much!</p>

CC BY-SA 3.0
2014-02-07T03:14:52.263Z
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.
Neal Young
CC BY-SA 3.0
2014-02-07T14:19:09.760Z
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.
xmerge
CC BY-SA 3.0
2014-02-07T20:02:27.080Z
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.
Neal Young
CC BY-SA 3.0
2014-02-07T22:44:14.883Z
@NealYoung Thanks so much! your argument makes great sense to me.
xmerge
<approximation-algorithms><randomized-algorithms><upper-bounds><data-streams>
Bound the number of rounds in the sampling
xmerge
# Bound the number of rounds in the sampling

(Asked by: username_0 on 2014-02-06)

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!

**Tags:** approximation-algorithms, randomized-algorithms, upper-bounds, data-streams
> **Comments:**
> **username_1**: 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.  
> **username_0**: 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.  
> **username_1**: 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.  
> **username_0**: @NealYoung Thanks so much! your argument makes great sense to me.  

---

## 0 answers

