Introduction to Cryptography with Coding Theory, 3rd Edition

20.1 Probability Review

In this section we briefly introduce the concepts from probability needed for what follows. An understanding of probability and the various identities that arise is essential for the development of entropy.

Consider an experiment $X$ with possible outcomes in a finite set $\mathit{X}$. For example, $X$ could be flipping a coin and $\mathit{X}=\{\text{heads, tails}\}$. We assume each outcome is assigned a probability. In the present example, $p(X=\text{heads})=1/2$ and $p(X=\text{tails})=1/2$. Often, the outcome $X$ of an experiment is called a random variable.

In general, for each $x\in \mathit{X}$, denote the probability that $X=x$ by

$$p_X(x)=p_x=p(X=x)\text{.}$$

Note that $\sum _{x\in \mathit{X}}{p}_x=1$. If $A\subseteq \mathit{X}$, let

$$p(A)=\sum _{x\in A}{p}_x\text{,}$$

which is the probability that $X$ takes a value in $A$.

Often one performs an experiment where one ...