Subgaussian Random Variables

Some details on Subgaussian and Hoeffdings

Sub-Gaussian Random Variables and Hoeffding’s Bound

Some Comments

When I started to read multi armed bandit (a.k.a. sequential treatment allocation) literature, had to deal with concentration bounds, the key idea is essentially bounding the tail probabilities of the random variables. Since I myself sometimes forget many details, I decided to write someting about it... hopefully by this I will learn many things and this helps people who has struggled like me.

This is the first post of the series of posts on bandits that I will try to write. Below I do a short recap of sub-Gaussian random variables. There are different but equivalent ways to define a sub-Gaussian random variable, I will follow following definition

Basic Definitions and Properties

Definition 1 [Sub-Gaussian random variable]: We say a random variable is a sub-Gaussian random variable with sub-Gaussian parameter $\sigma$, we write $X \sim s\mathcal{G}(\sigma)$, if for all $\lambda \in \mathbb{R}$ we have $\mathbb{E}(e^{\lambda X}) \leq e^{\frac{1}{2} \lambda^2 \sigma^2}$.

Now let's quickly state some important properties of sub-Gaussian random variables,

Some Properties of sub-Gaussian Random Variables

• Using Markov's inequality, it is possible to show that for any $\epsilon > 0$, $\mathbb{P}(X \geq \epsilon) \leq e^{-\frac{\epsilon^2}{2 \sigma^2}}$ $\mathbb{P}(|X| \geq \epsilon) \leq 2 e^{-\frac{\epsilon^2}{2 \sigma^2}}$. This is often called Chernoff bound, and often very useful in many places. The important thing to note here is location of the parameter $\sigma^2$ is in the bound.

• If $X_i \sim s\mathcal{G}(\sigma_i)$ and all of the random variables are independent, then $\sum_{i = 1}^{n} X_i \sim s\mathcal{G}\left(\sqrt{\sum_{i = 1}^{n}\sigma_i^2}\right)$. A special case of this is when all $\sigma_i$s are same, i.e., $\sigma_i = \sigma$ then we have a i.i.d setup, $X_i \overset{i.i.d.}{\sim} s\mathcal{G}(\sigma)$, and we have $\sum_{i = 1}^{n} X_i \sim s\mathcal{G}(\sqrt{n} \sigma)$

• If $X \sim s \mathcal{G}(\sigma)$, then $a X \sim s \mathcal{G}(|a|\sigma)$

• Many random variables are sub-Gaussian, for example,

  • If $X \sim \mathcal{N}(\mu, \sigma^2)$, then $X - \mu \sim s\mathcal{G}(\sigma)$, so in this case the $\sigma$ is the standard deviation of the normal random variable.
  • Bounded Random Variable, for example $X \in [a, b]$ then $X - \mu \sim s\mathcal{G}\left(\cfrac{b-a}{2}\right)$ , so in this case the $\sigma$ is the half of the range of the random variable.
  • and there are others, however also many variables are not sub-Gaussian, for example, Poisson, then we need a concept known as sub-exponential random variables (but we will not discuss this here).

Hoeffding’s Bound

The idea of the Hoeffding's Bound is to get a tail bound for the average / sum of the sub-Gaussian random variables, i.e., we are looking for

or more simply,

In this case the key step is to first derive the sub-Gaussian parameter of $\frac{1}{n}\sum_{i=1}^n\left(X_i-\mu_i\right)$ or $\overline{X}_n - \mu$. This might vary depending on the setup. But if we know this, for example, if we know

then applying Chernoff bound is easy and we get,

So the idea is to know $\tilde{\sigma}_{S}$ and then applying Chernoff bound is easy. The Hoeffdings inequality is an application for this,

We write the general proposition below,

Proposition [Hoeffding's bound]: Suppose we have a sequence $X_i - \mu_i \overset{i.i.d.}{\sim} s\mathcal{G}(\sigma_i)$, then for all $\epsilon \geq 0$, we have

This is easy to show using the sub-Gaussian rules we have outlined above, here $X_i - \mu_i \overset{i.i.d.}{\sim} s\mathcal{G}(\sigma_i)$, now applying the sub-Gaussian rules we get $\frac{1}{n}\sum_{i=1}^n\left(X_i-\mu_i\right) \sim s\mathcal{G}\left(\frac{1}{n}\sqrt{\sum_{i = 1}^{n}\sigma_i^2}\right)$. This means $\tilde{\sigma}_{S}^{2} = \frac{\sum_{i=1}^{n}\sigma_{i}^{2}}{n^2}$ . And finally if we apply Chernoff bound we get, for all $\epsilon \geq 0$,

Usually Hoeffding's bound is written for the bounded random variables, here we just wrote the proposition with general independent sub-Gaussian random variables. One thing to note is, the fast way to get the Hoeffding's bound is to apply sub-Gaussain rules and calculate the $\tilde{\sigma}_{S}^{2}$, then apply Chernoff bound. We will give two examples now,

 

Example 1. Let $X_i - \mu \overset{i.i.d.}{\sim} s\mathcal{G}(\sigma)$, then again applying sub-Gaussian rules we get $\overline{X}_n - \mu \sim s\mathcal{G}\left(\frac{\sigma}{\sqrt{n}}\right)$, and this means $\tilde{\sigma}_{S}^{2} = \frac{\sigma^2}{n}$. And applying Chernoff bound we get, for all $\epsilon \geq 0$,

Example 2. Let $X_i$ are bounded random variables in $[a_i, b_i]$ , in this case we already know that this is a special case of sub-Gaussian random variables and we have $X_i - \mu_i \sim s\mathcal{G}\left(\frac{b_i - a_i}{2}\right)$. Now applying the sub-Gaussian rules we get $\frac{1}{n}\sum_{i=1}^n\left(X_i-\mu_i\right) \sim s\mathcal{G}\left(\frac{1}{n}\sqrt{ \sum_{i =1}^{n} \frac{(b_i - a_i)^2}{4} }\right)$. This means $\tilde{\sigma}_{S}^{2} = \frac{1}{n^2}\sum_{i=1}^n \frac{(b_i - a_i)^2}{4}$. And finally applying Chernoff bound we get, for all $\epsilon \geq 0$,

This is possibly the most well known Hoeffding's bound. We can also let $X_i \in [a, b]$, then $X_i - \mu \sim s\mathcal{G}\left(\frac{b-a}{2}\right)$, and we have $\overline{X}_n - \mu \sim s\mathcal{G}\left(\frac{1}{\sqrt{n}}\frac{(b-a)}{2}\right)$, this means $\tilde{\sigma}_{S}^{2} = \frac{(b-a)^2}{4n}$ and applying Chernoff bound, we get for all $\epsilon \geq 0$,

for $a = 0$ and $b = 1$, we have a very simple bound,

This is also used in many places, where for simplicity we assume the random variables are bounded between $0$ and $1$.