Consider two sequences of (not necessarily independent) Bernoulli random variables $X_1, X_2, \ldots, X_n$ and $Y_1, Y_2, \ldots, Y_n$. Suppose that for any $i$, we have $\Pr[X_i = 1] = \Pr[Y_i = 1] = p_i$, but the actual value of $p_i$ is determined only after observing $\{X_1, \ldots, X_{i-1}, Y_1, \ldots, Y_{i-1} \}$. That is, each $p_i$ is also a random variable.

Intuitively it seems that the two sums $\sum_i X_i$ and $\sum_i Y_i$ should typically be very close to each other. Are any such bounds known? Is there e.g. a simple argument to show that with high probability $\sum_i X_i = \sum_i Y_i \pm O(\sqrt{n \log n})$?

  • 1
    $\begingroup$ Are you assuming that given $p_i$, $X_i$ and $Y_i$ are independent of each other? $\endgroup$ – Marcus M Mar 6 at 0:04
  • $\begingroup$ @MarcusM Intuitively, I don't think that should matter much for the sums whether $X_i$ and $Y_i$ are independent since they have the same success probabilities. Would it help if we assume they are independent? $\endgroup$ – Mathman Mar 6 at 0:10
  • 1
    $\begingroup$ You're right it shouldn't matter, actually. I'll add an answer. $\endgroup$ – Marcus M Mar 6 at 0:12

Define the martingale $M_n = \sum_{i = 1}^n (X_i - Y_i)$ with the filtration $\mathcal{F}_n = \sigma( \{X_j,Y_j\}_{j=1}^n )$. Then $|M_{n + 1} - M_n| = |X_{n+1}-Y_{n+1}| \leq 1$ and it is indeed a martingale since $$\mathbb{E}[M_{n+1}\,|\,\mathcal{F}_n]= \mathbb{E}[X_{n+1} - Y_{n+1}\,|\,\mathcal{F}_n] + M_{n} = M_n\,. $$

By Azuma's inequality, we then have $$\mathbb{P}(|M_n| \geq \lambda) \leq 2 \exp\left( -\frac{\lambda^2}{2n}\right)\,.$$

Taking $\lambda \gg \sqrt{n}$ shows your desired behavior.

| cite | improve this answer | |
  • $\begingroup$ Very cute. Thanks for the super fast response. $\endgroup$ – Mathman Mar 6 at 0:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.