1 Probability and Computing 1.2 Discrete Random Variable and Expectation 1.4 Chernoff and Hoeffding Bounds

1.3 Moments and Deviations

Exercise 1.3.1 (Exercise 3.9 [MU17]).

Let $\{X_{i}\}_{i\in[1,m]}$ be Bernoulli random variables that are not necessarily mutually independent, and $X=\sum_{i}X_{i}$ . Then

\operatorname*{\mathbb{E}}\left[X^{2}\right]=\sum_{i\in[1,m]}\Pr\left[X_{i}=1% \right]\operatorname*{\mathbb{E}}\left[X\mid X_{i}=1\right].

Proof.

We can derive the proof by

	$\displaystyle\operatorname*{\mathbb{E}}\left[X^{2}\right]$	$\displaystyle=\operatorname{\mathbb{E}}\left[\sum_{i\in[1,m]}X_{i}X\right]=% \sum_{i\in[1,m]}\operatorname{\mathbb{E}}\left[X_{i}X\right]$
		$\displaystyle=\sum_{i\in[1,m]}\Pr\left[X_{i}=1\right]\operatorname*{\mathbb{E}% }\left[X\mid X_{i}=1\right],$

where the first two equalities hold from linearity of expectation, and the last one holds by conditional expectation. ∎

Lemma 1.3.2.

Let $\{X_{i}\}_{i\in[1,m]}$ be Bernoulli random variables that are not necessarily mutually independent, and $X=\sum_{i}X_{i}$ . Then

	$\displaystyle\mathrm{Var}\left[X\right]$	$\displaystyle=\sum_{i\in[1,m]}\mathrm{Var}\left[X_{i}\right]+\sum_{\begin{% subarray}{c}i,j\in[1,m]\\ i\neq j\end{subarray}}\mathrm{Cov}\left[X_{i},X_{j}\right]$
		$\displaystyle=\sum_{i\in[1,m]}\mathrm{Var}\left[X_{i}\right]+2\cdot\sum_{% \begin{subarray}{c}i,j\in[1,m]\\ i<j\end{subarray}}\mathrm{Cov}\left[X_{i},X_{j}\right].$

Exercise 1.3.3 (Exercise 3.11 [MU17]).

Recall the Bubblesort algorithm. Determine the variance of the number of inversions that need to be corrected by Bubblesort.

Proof.

We introduce $\{X_{i,j}\}$ 0-1 random variables, where $j\in[1,n]$ and $i\in[1,j-1]$ . $X_{i,j}$ is 1 if and only if the $i^{\mathrm{th}}$ and the $j^{\mathrm{th}}$ element are inverted during the sorting. The variance of $X=\sum_{i,j}X_{i,j}$ can be expressed by lemma 1.3.2

\mathrm{Var}\left[X\right]=\sum_{\begin{subarray}{c}j\in[1,n]\\ i\in[1,j-1]\end{subarray}}\mathrm{Var}\left[X_{i,j}\right]+2\cdot\sum_{\begin{% subarray}{c}j_{0},j_{1}\in[1,n]\\ i_{0}\in[1,j_{0}-1],i_{1}\in[1,j_{1}-1]\\ (i_{0},j_{0})<(i_{1},j_{1})\end{subarray}}\mathrm{Cov}\left[X_{i_{0},j_{0}},X_% {i_{1},j_{1}}\right].

$X_{i,j}=1$ if and only if the $i^{\mathrm{th}}$ element is greater than $j^{\mathrm{th}}$ element, and thus $\Pr\left[X_{i,j}=1\right]=1/2$ . Since $\operatorname*{\mathbb{E}}\left[X_{i,j}\right]=1/2$ , therefore $\mathrm{Var}\left[X_{i,j}\right]=1/4$ .

For $\mathrm{Cov}\left[X_{i_{0},j_{0}},X_{i_{1},j_{1}}\right]$ , if the two pairs are disjoint, that $\{i_{0},j_{0}\}\cap\{i_{1},j_{1}\}=\varnothing$ , then $X_{i_{0},j_{0}}$ and $X_{i_{1},j_{1}}$ are independent, therefore $\mathrm{Cov}\left[X_{i_{0},j_{0}},X_{i_{1},j_{1}}\right]=0$ .

On the other hand, if $i_{0},i_{1},j_{0},j_{1}$ have index overlap, there are $\binom{n}{3}$ choices, each breaking into 3 categories:

•

if $i_{0}=i_{1}$ , then $X_{i_{0},j_{0}}\cdot X_{i_{1},j_{1}}=1$ if and only if $i_{0}^{\mathrm{th}}$ element is the largest among 3, and thus $\operatorname*{\mathbb{E}}\left[X_{i_{0},j_{0}}\cdot X_{i_{1},j_{1}}\right]=1/3$ .
•

if $j_{0}=i_{1}$ , then $X_{i_{0},j_{0}}\cdot X_{i_{1},j_{1}}=1$ if and only if $j_{0}^{\mathrm{th}}$ element is in the middle, and $i_{0}^{\mathrm{th}}$ element is the largest, which halves the probability, and therefore $\operatorname*{\mathbb{E}}\left[X_{i_{0},j_{0}}\cdot X_{i_{1},j_{1}}\right]=1/6$ .
•

if $j_{0}=j_{1}$ , then $X_{i_{0},j_{0}}\cdot X_{i_{1},j_{1}}=1$ if and only if $j_{0}^{\mathrm{th}}$ element is the smallest among 3, and thus $\operatorname*{\mathbb{E}}\left[X_{i_{0},j_{0}}\cdot X_{i_{1},j_{1}}\right]=1/3$ .

We conclude that

\mathrm{Var}\left[X\right]=\sum_{j\in[1,n]}\sum_{i\in[1,j-1]}\frac{1}{4}+2% \cdot\binom{n}{3}\cdot\left(\frac{1}{3}+\frac{1}{3}+\frac{1}{6}-\frac{3}{4}% \right)=\frac{n(n-1)}{8}+2\cdot\frac{1}{12}\cdot\binom{n}{3}=\frac{1}{72}n(n-1% )(2n+5).

∎

Exercise 1.3.4 (Exercise 3.13 [MU17]).

Find an example of random variable with finite $j^{\mathrm{th}}$ moment for $j\in[1,k]$ , but an unbounded $k+1^{\mathrm{th}}$ moment.

Proof.

Let $X\in\mathbb{N}^{+}$ have $\Pr\left[X=x\right]=c\cdot x^{-k-2}$ with $c=(\sum_{x\in\mathbb{N}^{+}}x^{-k-2})^{-1}$ . $\operatorname*{\mathbb{E}}\left[X^{k}\right]$ converges, $\operatorname*{\mathbb{E}}\left[X^{k+1}\right]$ doesn’t. ∎

Remark 1.3.5.

Ever heard of Pareto tails?

Theorem 1.3.6.

For any random variable $X$ and finite expectation $\operatorname*{\mathbb{E}}\left[X\right]$ , finite $\operatorname*{\mathbb{E}}\left[X^{2}\right]$ , and finite median $m$ ,

•

$\operatorname*{\mathbb{E}}\left[X\right]$ is the value $c$ that minimizes the expression $\operatorname*{\mathbb{E}}\left[\left(X-c\right)^{2}\right]$ .
•

$m$ is the value $c$ that minimizes the expression $\operatorname*{\mathbb{E}}\left[\left|X-c\right|\right]$ .

Proof.

The first one is immediate, as $\operatorname*{\mathbb{E}}\left[\left(X-c\right)^{2}\right]$ minimizes at $c=\operatorname*{\mathbb{E}}\left[X\right]$ by expanding the expression.

For second case, we assume that there exists $c$ such that $\operatorname*{\mathbb{E}}\left[\left|X-c\right|\right]<\operatorname*{\mathbb% {E}}\left[\left|X-m\right|\right]$ , or $\operatorname*{\mathbb{E}}\left[\left|X-m\right|-\left|X-c\right|\right]>0$ . Since $c>m$ or $c<m$ works the same by symmetry, WLOG we let $c>m$ , then

\left|X-m\right|-\left|X-c\right|=\begin{cases}m-c&X\leq m\\ 2X-m-c&m\leq X\leq c\\ c-m&X\geq c\end{cases}.

For $m<X<c$ , we have $2X-m-c\leq c-m$ , and for $X\geq c$ the expression equals $c-m$ , so

\operatorname*{\mathbb{E}}\left[\left|X-m\right|-\left|X-c\right|\right]\leq(m% -c)\Pr\left[X\leq m\right]+(c-m)\Pr\left[X>m\right].

Since for a median $m$ , $\Pr\left[X\leq m\right]\geq 1/2$ and $\Pr\left[X>m\right]\leq 1/2$ , the right-hand side is at most $0$ , contradicting the prior assumption of existence of $c$ , and proves that $m$ minimizes the expression $\operatorname*{\mathbb{E}}\left[\left|X-c\right|\right]$ . ∎

Lemma 1.3.7.

Let $X$ be a random variable, with mean $\mu$ , median $m$ , and finite standard deviation $\sigma$ . Then $\left|\mu-m\right|\leq\sigma$ .

Proof.

	$\displaystyle\left\|\operatorname*{\mathbb{E}}\left[X\right]-m\right\|$	$\displaystyle\leq\operatorname*{\mathbb{E}}\left[\left\|X-m\right\|\right]$
		$\displaystyle\leq\operatorname{\mathbb{E}}\left[\left\|X-\operatorname{% \mathbb{E}}\left[X\right]\right\|\right]$
		$\displaystyle\leq\sqrt{\operatorname{\mathbb{E}}\left[\left(X-\operatorname{% \mathbb{E}}\left[X\right]\right)^{2}\right]}=\sigma,$

where the first and the third inequality follow from theorem 1.2.5, and the second one follows from theorem 1.3.6. ∎

Exercise 1.3.8 (Exercise 3.18 [MU17]).

Show that, for a random variable $X$ with standard deviation $\sigma[X]$ and $t\in\mathbb{R}^{+}$ :

•

$\Pr[X-\operatorname*{\mathbb{E}}[X]\geq t\sigma[X]]\leq 1/\left(1+t^{2}\right);$
•

$\Pr[\left|X-\operatorname*{\mathbb{E}}[X]\right|\geq t\sigma[X]]\leq 2/\left(1% +t^{2}\right).$

Proof.

Cantelli’s inequality (or one-sided Chebyshev’s inequality) can be proved by:

	$\displaystyle\Pr[X-\operatorname*{\mathbb{E}}[X]\geq t\sigma[X]]$	$\displaystyle=\Pr[X-\operatorname*{\mathbb{E}}[X]+u\geq t\sigma[X]+u]$
		$\displaystyle\leq\Pr[(X-\operatorname*{\mathbb{E}}[X]+u)^{2}\geq(t\sigma[X]+u)% ^{2}]$
		$\displaystyle\leq\frac{\operatorname{\mathbb{E}}[(X-\operatorname{\mathbb{E}% }[X]+u)^{2}]}{(t\sigma[X]+u)^{2}}=\frac{\operatorname{\mathbb{E}}[(X-% \operatorname{\mathbb{E}}[X])^{2}]+u^{2}}{(t\sigma[X]+u)^{2}}$
		$\displaystyle=\frac{\sigma[X]^{2}+u^{2}}{(t\sigma[X]+u)^{2}}=\varphi(u).$

The last inequality was established by Chebyshev’s inequality.

$\varphi(u)$ is minimized at $u=\sigma[X]/t$ , and thus the first inequality is upper bounded by $1/(1+t^{2})$ .

By symmetry, the second inequality is proven. ∎

Exercise 1.3.9 (Exercise 3.19 [MU17]).

Using 1.3.8, show lemma 1.3.7.

Proof.

By 1.3.8, we have $\Pr[X\leq\sigma+\mu]\geq 1/2$ and $\Pr[X\geq\mu-\sigma]\geq 1/2$ .

By definition of median $m$ , $\Pr[X\geq m]\geq 1/2$ and $\Pr[X\leq m]\geq 1/2$ .

Since $\sigma>0$ is finite, $\mu$ is finite, we have $\mu-\sigma\leq m\leq\mu+\sigma$ , and thus completes the proof for $\left|m-\mu\right|\leq\sigma$ . ∎

Exercise 1.3.10 (Exercise 3.20 [MU17]).

Let $Y$ be a nonnegative integer-valued random variable with positive expectation. Prove

\frac{\operatorname*{\mathbb{E}}[Y]^{2}}{\operatorname*{\mathbb{E}}[Y^{2}]}% \leq\Pr[Y\neq 0]\leq\operatorname*{\mathbb{E}}[Y].

Proof.

By conditional expectation, we have

	$\displaystyle\operatorname*{\mathbb{E}}[Y^{2}]$	$\displaystyle=\operatorname{\mathbb{E}}[Y^{2}\mid Y=0]\cdot\Pr[Y=0]+% \operatorname{\mathbb{E}}[Y^{2}\mid Y\neq 0]\cdot\Pr[Y\neq 0]$
		$\displaystyle=\operatorname*{\mathbb{E}}[Y^{2}\mid Y\neq 0]\cdot\Pr[Y\neq 0]$
		$\displaystyle\geq\operatorname*{\mathbb{E}}[Y\mid Y\neq 0]^{2}\cdot\Pr[Y\neq 0],$

where the last inequality follows from Jensen’s inequality.

Again by conditional expectation, we have $\operatorname*{\mathbb{E}}[Y]=\operatorname*{\mathbb{E}}[Y\mid Y\neq 0]\cdot% \Pr[Y\neq 0]$ , and thus

\frac{\operatorname*{\mathbb{E}}[Y]^{2}}{\operatorname*{\mathbb{E}}[Y^{2}]}% \leq\Pr[Y\neq 0].

Since $Y$ is an integer-valued random variable,

	$\displaystyle\Pr[Y\neq 0]$	$\displaystyle=0\cdot\Pr[Y=0]+\sum_{y\neq 0}1\cdot\Pr[Y=y]$
		$\displaystyle\leq\sum_{y\in\mathbb{N}}y\cdot\Pr[Y=y]=\operatorname*{\mathbb{E}% }[Y].$

Another way of seeing it is by a direct application of Markov’s inequality, that $\Pr\left[Y\geq 1\right]\leq\operatorname*{\mathbb{E}}\left[Y\right]$ . ∎

1.3.1 Weak Law of Large Numbers (WLLN)

Theorem 1.3.11 (WLLN).

If $\{X_{i}\}_{i\in[1,n]}$ are independent, identically distributed random variables with mean $\mu$ and standard deviation $\sigma$ , then for any constant $\varepsilon>0$ ,

\lim_{n\to\infty}\Pr\left[\left|\frac{1}{n}\sum_{i}X_{i}-\mu\right|>% \varepsilon\right]=0.

	$\displaystyle\left\|\operatorname*{\mathbb{E}}\left[X\right]-m\right\|$	$\displaystyle\leq\operatorname*{\mathbb{E}}\left[\left\|X-m\right\|\right]$
		$\displaystyle\leq\operatorname{\mathbb{E}}\left[\left\|X-\operatorname{% \mathbb{E}}\left[X\right]\right\|\right]$
		$\displaystyle\leq\sqrt{\operatorname{\mathbb{E}}\left[\left(X-\operatorname{% \mathbb{E}}\left[X\right]\right)^{2}\right]}=\sigma,$