# Azuma's inequality for a simple case of Polya's urn

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?

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