Concentration for sum of a random length sequence

Exercise 7.1 from Bandit Algorithms [1]

Let

$(X_t{)}_t$ be a sequence of i.i.d. Gaussian random variables with mean

$\mu$ and unit variance defined on the probability space

$(\mathrm{\Omega },\mathcal{F},\mathbb{P})$. Let

$T:\mathrm{\Omega }\to \mathbb{N}=\{1,2,3,\dots \}$ be a random variable and let

$\hat{\mu }:=\frac{1}{T}\sum _{t=1}^T{X}_t$.

1. Show that if
   $T$ and
   $(X_t{)}_t$ are independent, the for any
   $\delta \in (0,1)$,
   
   $$\mathbb{P}(\hat{\mu }-\mu \ge \sqrt{\frac{2\log {\delta }^{-1}}{T}})\le \delta$$
2. Now drop the assumption that
   $T$ and
   $(X_t{)}_t$ are independent. Let
   ${\mathcal{F}}_t:=\sigma (X_1,\cdots ,X_t)$. For each
   $\delta \in (0,1)$ find
   $T$ such that
   $\{T=t\}\in {\mathcal{F}}_t$ for all
   $t=1,2,\dots$ and
   
   $$\mathbb{P}(\hat{\mu }-\mu \ge \sqrt{\frac{2\log {\delta }^{-1}}{T}})=1$$
3. Show that in general we have
   
   $$\mathbb{P}(\hat{\mu }-\mu \ge \sqrt{\frac{2\log (T(T+1)/\delta )}{T}})\le \delta$$

Without loss of generality assume

$\mu =0$. Recall that if

$Y\in \mathcal{N}(\mu ,{\sigma }^2)$ then for

$y\ge 0$ we have

$$\begin{array}{r}\mathbb{P}(Y\ge y)\le \exp (-\frac{y^2}{2{\sigma }^2}).\end{array}$$ Since

$X_i$'s are assumed to be independent standard normal, we have

$\hat{\mu }\sim \mathcal{N}(\mu ,1/T)$. Analogous results can be obtained for subgaussian random variables using Hoeffding's inequality instead. We also remark that tighter bounds in (3) are possible, which require more sophisticated tools.

(1)

By independence we can write

$$\begin{array}{rl}\mathbb{P}(\hat{\mu }\ge \sqrt{\frac{2\log {\delta }^{-1}}{T}})& =\sum _{t=1}^{\mathrm{\infty }}\mathbb{P}(\hat{\mu }\ge \sqrt{\frac{2\log {\delta }^{-1}}{T}}|T=t)\mathbb{P}(T=t)\\ & =\sum _{t=1}^{\mathrm{\infty }}\mathbb{P}(\frac{1}{t}\sum _{i=1}^t{X}_t\ge \sqrt{\frac{2\log {\delta }^{-1}}{t}})\mathbb{P}(T=t)\\ & \le \sum _{t=1}^{\mathrm{\infty }}\exp (-{\displaystyle \frac{\frac{2}{t}\log \frac{1}{\delta }}{2\cdot \frac{1}{t}}})\mathbb{P}(T=t)=\delta .\end{array}$$

(2)

For

$\omega \in \mathrm{\Omega }$ define

$$\begin{array}{r}T(\omega ):=inf\{n\ge 1:\frac{1}{n}\sum _{t=1}^n{X}_t(\omega )\ge \sqrt{\frac{2\log {\delta }^{-1}}{n}}\}.\end{array}$$ Then

$\mathbb{I}\{T=t\}$ is a function of

$X_1,\dots ,X_t$ and hence is

${\mathcal{F}}_t$-measurable. By the definition of

$T$ we have

$\hat{\mu }\ge \sqrt{2(\log {\delta }^{-1})/T}$ on the subset

$\mathrm{\Omega }$ where

$T$ is defined. It then remains to check that

$T$ is well-defined, namely

$T<\mathrm{\infty }$ almost surely.

By the law of iterated logarithm, we have for almost every

$\omega \in \mathrm{\Omega }$,

$$\begin{array}{r}\underset{n\to \mathrm{\infty }}{lim sup}\frac{\sum _{t=1}^n{X}_t(\omega )}{\sqrt{2n\log \log n}}=1.\end{array}$$
Thus for every

$ϵ\in (0,1)$ and

$m\ge 1$ there exists

$n\ge m$ such that

$$\begin{array}{r}\frac{\sum _{t=1}^n{X}_t(\omega )}{\sqrt{2n\log \log n}}\ge 1-ϵ,\end{array}$$ which implies

$$\begin{array}{r}\frac{\frac{1}{n}\sum _{t=1}^n{X}_t(\omega )}{\sqrt{(2\log {\delta }^{-1})/n}}\ge (1-ϵ)\sqrt{\frac{\log \log n}{\log {\delta }^{-1}}},\end{array}$$ which is greater than

$1$ for

$m$ sufficiently large. This means that the set in the definition of

$T$ is a nonempty subset of

$\mathbb{N}$, so

$T<\mathrm{\infty }$ almost surely.

(3)

Since

$\{T=t{\}}_{t\ge 1}$ partitions the sample space, we have

$$\begin{array}{rl}\mathbb{P}(\hat{\mu }\ge \sqrt{\frac{2\log (T(T+1)/\delta )}{T}})& =\sum _{t=1}^{\mathrm{\infty }}\mathbb{P}(\hat{\mu }\ge \sqrt{\frac{2\log (T(T+1)/\delta )}{T}}\text{ and }T=t)\\ & \le \sum _{t=1}^{\mathrm{\infty }}\mathbb{P}(\frac{1}{t}\sum _{i=1}^t{X}_i\ge \sqrt{\frac{2\log (t(t+1)/\delta )}{t}})\\ & \le \sum _{t=1}^{\mathrm{\infty }}\exp (-{\displaystyle \frac{\frac{2\log (t(t+1)/\delta )}{t}}{2\cdot \frac{1}{t}}})\\ & =\sum _{t=1}^{\mathrm{\infty }}\frac{\delta }{t(t+1)}=\delta .\end{array}$$

References

[1] Lattimore, Tor, and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.