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



Sum of sequences of random variables, with variable success probabilities
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.


