Probability theory revisit, and proofs

18 Mar, 2026

The following exercises are from Appendix 1 of Quantum Computation and Quantum Information by Isaac Chuang & Michael Nielsen. I am currently reading this book.

Conditional probability:

$p(Y=y|X=x)\equiv {\displaystyle \frac{p(X=x,Y=y)}{p(X=x)}}$

Bayes’ rule:

$p(x|y)=p(y|x){\displaystyle \frac{p(x)}{p(y)}}$

Proof: From the definition of conditional probability,

$p(x|y)={\displaystyle \frac{p(x,y)}{p(y)}}$, $p(y|x)={\displaystyle \frac{p(x,y)}{p(x)}}$,

then $p(x|y)p(y)=p(y|x)p(x)$,

therefore $p(x|y)=p(y|x)p(x)/p(y)$. QED.

The law of total probability:

${\displaystyle p(y)={\sum }_{x}p(y|x)p(x)}$

Proof: From the definition of conditional probability,

$p(y|x)p(x)=p(x,y)$,

summing over $x$ from both sides,

${\displaystyle {\sum }_{x}p(y|x)p(x)={\sum }_{x}p(x,y)=p(y)}$. QED.

Expectation: ${\displaystyle \mathbf{E}(X)\equiv {\sum }_{x}p(x)x}$.

Variance: $var(X)\equiv \mathbf{E}\left\{\right[X-\mathbf{E}(X){]}^2\}=\mathbf{E}(X^2)-\mathbf{E}(X{)}^2$.

Standard deviation: $\Delta (X)\equiv \sqrt{var(X)}$.

Exercise A1.3: Prove that there exists a value of $x\ge \mathbf{E}(X)$ such that $p(x)>0$.

Proof by contradiction: assume every $x$ with $p(x)>0$ must satisfy $x<\mathbf{E}(X)$,

then ${\displaystyle 𝐄(X)={\sum }_{x}p(x)x<{\sum }_{x}p(x)·𝐄(X)=𝐄(X){\sum }_{x}p(x)=𝐄(X)}$,

which is a contradiction. QED.

Exercise A1.4: Prove that $\mathbf{E}(X)$ is linear in $X$.

Proof: Additivity: ${\displaystyle \mathbf{E}(X+Y)={\sum }_x{\sum }_{y}p(x,y)(x+y)}$

${\displaystyle ={\sum }_x{\sum }_{y}p(x,y)x+{\sum }_x{\sum }_{y}p(x,y)y}$

${\displaystyle ={\sum }_{x}p(x)x+{\sum }_{y}p(y)y=\mathbf{E}(X)+\mathbf{E}(Y)}$.

Homogeneity: ${\displaystyle \mathbf{E}(kX)={\sum }_{x}p(x)kx=k·{\sum }_{x}p(x)x=k\mathbf{E}(X)}$.

QED.

Exercise A1.5: Prove that for independent random variables $X$ and $Y$, $\mathbf{E}(XY)=\mathbf{E}(X)\mathbf{E}(Y)$.

Proof: ${\displaystyle \mathbf{E}(XY)={\sum }_x{\sum }_{y}p(x,y)xy}$

${\displaystyle ={\sum }_x{\sum }_{y}p(x)p(y)xy={\sum }_{x}p(x)x·{\sum }_{y}p(y)y}$

$=\mathbf{E}(X)\mathbf{E}(Y)$. QED.

Chebyshev’s inequality: For any $\lambda >0$ and random variable $X$ with finite variance, $p[|X-\mathbf{E}(X)|\ge \lambda \Delta (X)]\le {\displaystyle \frac{1}{{\lambda }^2}}$.

Proof: Consider ${\displaystyle var(X)={\sum }_{x}p(x)[x-𝐄(X){]}^2}$

${\displaystyle \ge {\sum }_{|x-\mathbf{E}(X)|\ge \lambda \Delta (X)}p(x)[x-𝐄(X){]}^2}$

${\displaystyle \ge {\sum }_{|x-\mathbf{E}(X)|\ge \lambda \Delta (X)}p(x){\lambda }^2{\Delta }^2(X)={\lambda }^2{\Delta }^2(X){\sum }_{|x-\mathbf{E}(X)|\ge \lambda \Delta (X)}p(x)}$

$=var(X)·{\lambda }^{2}p[|X-\mathbf{E}(X)|\ge \lambda \Delta (X)]$ ,

therefore $p[|X-\mathbf{E}(X)|\ge \lambda \Delta (X)]\le {\displaystyle \frac{1}{{\lambda }^2}}$. QED.

#Math notes