Sum of sequences of random variables, with variable success probabilities

Question

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})$?

Answer 1

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.