# Sum of sequences of random variables, with variable success probabilities

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

• Are you assuming that given $p_i$, $X_i$ and $Y_i$ are independent of each other? – Marcus M Mar 6 at 0:04
• @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? – Mathman Mar 6 at 0:10
• You're right it shouldn't matter, actually. I'll add an answer. – 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.