Azuma’s inequality for a simple case of Polya’s urn

martingalespolya-urn-modelprobabilityprobability theoryupper-lower-bounds

Suppose that an urn contains one red ball and one blue ball. A ball
is drawn from the urn uniformly at random. After that, the ball is put back into the
urn and another ball of the same colour is added to the urn. This process is repeated
$n$ times. Denote by $X_n$ the proportion of red balls in the urn after these $n$ steps (i.e.
number of red balls divided by total number of balls). Use Azuma’s inequality to prove that

$$\mathbb{P}\bigg[ \bigg\lvert X_n – \frac{1}{2} \bigg\rvert\ge \varepsilon \bigg] \le 2\exp\bigg(-\frac{6\varepsilon^2}{2\pi^2-15} \bigg)$$

Remark: In class I learned the following version of Azuma's inequality:

Let $(X_0, \ldots, X_n)$ be a martingale with $X_0 = 0$ and $\lvert X_i – X_{i-1} \rvert \le 1 \quad (\forall 1 \le i \le n)$. Then for any $t > 0$ it holds

$$\mathbb{P}\bigg[\lvert X_n – \mathbb{E}[X_n]\rvert \ge \varepsilon \bigg] \le 2\exp\bigg(-\frac{\varepsilon^2}{2n} \bigg)$$

I already know that $(X_n)_n$ is a martingale that fullfills the conditions for Azuma's inequality and has the property that $\mathbb{E}[X_n] = 1/2$. However I do not see where the term $-\frac{6\varepsilon^2}{2\pi^2-15} $ should come from. Could you please give me a hint?

Best Answer

Wikipedia cites a different version of Azuma's inequality: Suppose $(X_n)_n$ is a martingale and $|X_k - X_{k-1}| \le c_k$ almost surely. Then for all $N \in \mathbb{N}$ and all $\varepsilon > 0$, $$P(|X_N - X_0| \ge \varepsilon) \le 2 \exp \left( \frac{-\varepsilon^2}{2 \sum_{k=1}^N c_k^2 }\right).$$

Are you sure you don't have access to a result like that? Anyway I'll show how to move forward assuming Wikipedia's version and you can contemplate whether it helps you find a way forward given what you're allowed to assume.

In this particular martingale, suppose $X_{k-1} = \frac{r}{k+1}$ for some $1 \le r \le k$. Then $X_{k}$ could be $\frac{r+1}{k+2}$ or $\frac{r}{k+2}$ depending on what color ball we pull on turn $k$. Thus we have $$\begin{align} |X_{k} - X_k-1| &\le \max\left \{ \frac{r+1}{k+2} - \frac{r}{k+1}, \frac{r}{k+1} - \frac{r}{k+2} \right\} \\ &= \max \left \{ \frac{k+1 - r}{(k+1)(k+2)}, \frac{r}{(k+1)(k+2)} \right \} \\ &\le \frac{k+1}{(k+1)(k+2)} \\ &= \frac{1}{k+2}. \end{align}$$ Thus we can choose $c_k = \frac{1}{k+2}$, which gives $$\begin{align} \sum_{k=1}^\infty c_k^2 &= \sum_{j=3}^\infty \frac{1}{j^2} = \zeta(2) - 1 - \frac 1 4 = \frac{\pi^2}{6} - \frac{5}{4} \end{align}$$

and so, for any $N$, we have the bound $$\begin{align} P\left(\left|X_N - \frac 1 2\right| \ge \varepsilon \right) &\le 2 \exp \left( \frac{-\varepsilon^2}{2 \sum_{k=1}^N c_k^2 }\right) \\ &= 2 \exp \left( \frac{-\varepsilon^2}{\frac{\pi^2}{3} - \frac{5}{2} }\right) \\ &= 2 \exp \left( \frac{-6 \varepsilon^2}{2 \pi^2 - 15 }\right). \end{align}$$

The final bound works out so neatly that I kinda suspect you're meant to have access to something more like the result I'm quoting. But anyway I'll leave the problem of fully understanding what assumptions are legal up to you.