Machine Learning & Signals Learning
1 Discrete Random Variable
1.1 Introduction
Probability: The relative frequency of some phenomenon after infinitely many random experiments1.
Random variable: A random variable (also called a chance variable) is a model that describes the relation between the outcome of a random experiment and a real number2. It is denoted by a capital letter, for example \(X,Y\), and so on.
Discrete random variable: For discrete random variables, the possible outcomes of the experiment \(x_k\) are discrete (\(=\) countable), where the number of possible values of \(k\) may be finite or infinite.
Continuous random variable: For continuous random variables, the possible outcomes of the experiment are defined over an interval or a collection of intervals.
1 Other phenomena that are unrelated to random experiments, such as the chances of winning an election and the like, are not covered by this definition and are not treated in this book.
2 A more formal mathematical definition exists but is not presented in this book.
-
Example 1.1: (Discrete random variable with a finite number of outcomes) A random variable that relates the outcome of a die roll, \(\left \{1,2,3,4,5,6\right \}\), to the probability of that outcome.
1.2 Properties
1.2.1 Characterization
Probability density function (PDF): The relation between an outcome of the experiment \(x_k\) and the probability of that outcome:
\(\seteqnumber{0}{1.}{0}\)\begin{equation} p_X[x_k] = \Pr [X=x_k] \end{equation}
The use of brackets \([\cdot ]\) emphasizes that we are dealing with discrete values, as opposed to \((\cdot )\), which is used later for continuous values.
In this book, the term PDF applies to both discrete and continuous variables. In the literature, a different term, probability mass function (PMF), is sometimes used to emphasize that the variable is discrete. In those texts, the term PDF is reserved for continuous variables only.
The fundamental properties of random variables are as follows.
Range of PDF values: The range of PDF values is
\(\seteqnumber{0}{1.}{1}\)\begin{equation} 0\le p_X[x_i]\le 1\ \forall i \end{equation}
Sum of PDF values: The sum of PDF values is
\(\seteqnumber{0}{1.}{2}\)\begin{equation} \sum _i p_X[x_i] = 1 \end{equation}
Cumulative distribution function (CDF): The probability that a random variable \(X\) is less than or equal to a given value \(x\),
\(\seteqnumber{0}{1.}{3}\)\begin{equation} F_{X}(x) = \Pr (X\le x),\ x\in \mathbb {R}. \end{equation}
The value \(x\) is real and continuous.
Relation between the PDF and the CDF: The relation is based on the sum of \(p_X[x_k]\) over those \(x_k\) for which \(x_k\leqslant x\):
\(\seteqnumber{0}{1.}{4}\)\begin{equation} F_X(x) =\sum _{k:x_k\leqslant x}p_X[x_k] \end{equation}
Functional behavior: The CDF is non-decreasing and right-continuous.
-
Proof. For \(x_1\le x_2\) we have \(\{X\le x_1\}\subseteq \{X\le x_2\}\), hence \(F_X(x_1)\le F_X(x_2)\).
Probability over an interval: For \(x\in (a,b]\) we have
\(\seteqnumber{0}{1.}{5}\)\begin{equation} \Pr (a<X\leqslant b) = F_X(b)-F_X(a) \end{equation}
Extreme values: The range of CDF values is \(0\le F_X(x)\le 1\) (in accordance with Feature 1.2.1), where for extreme values of \(x\) we have
\(\seteqnumber{0}{1.}{6}\)\begin{equation} F_X(-\infty ) = 0, \quad F_X(\infty ) = 1 \end{equation}
Complementary probability: Since \(\Pr (X>x) + \Pr (X\le x) =1\),
\(\seteqnumber{0}{1.}{7}\)\begin{equation} \Pr (X>x) = 1- F_X(x) \end{equation}
1.2.2 Expectation
\(\seteqnumber{0}{1.}{8}\)\begin{equation} \E [X] =\sum _i x_i p_X[x_i] \end{equation}
The notation \(E\) is based on the word Expectation. An explanation of why this particular name is chosen appears later, in the context of prediction by a constant.
Properties of the expectation: The expectation is a linear operation, and the expectation of a constant is the constant itself.
\(\seteqnumber{1}{1.10}{0}\)\begin{align} \E [aX] =& a \E [X]\\ \E [b] =& b \label {eq:rand1:eb} \end{align}
Expectation of a function of a random variable:
\(\seteqnumber{0}{1.}{10}\)\begin{equation} \label {eq:rand1:egxd} \E [g(X)] = \sum _i g(x_i)p_X[x_i] \end{equation}
Expectation of an expectation:
\(\seteqnumber{0}{1.}{12}\)\begin{equation} \E [{\E [X]}] = \E [X] \end{equation}
-
Proof. Since the expectation is a constant, we may substitute \(\E [X]=b\) and use Eq. (1.10b).
-
Example 1.6: By Eq. (1.10b) we have,
\(\seteqnumber{0}{1.}{13}\)\begin{equation} \E [{X\E [X]}] = \E [X]\,\E [X] = \bigl (\E [X]\bigr )^2 \end{equation}
1.2.3 Variance
Variance: The variance of a random variable is
\(\seteqnumber{0}{1.}{14}\)\begin{equation} \Var [X] = \E [{\bigl (X-\E [X]\bigr )^2}] \end{equation}
Variance, alternative definition:
\(\seteqnumber{0}{1.}{15}\)\begin{equation} \Var [X] = \E [X^2] - \bigl (\E [X]\bigr )^2 \end{equation}
-
Proof.
\(\seteqnumber{0}{1.}{16}\)\begin{equation} \label {eq:rand1:var_basics} \begin{aligned} \E [{\bigl (X-\E [X]\bigr )^2}] &= \E [{X^2 - 2X\E [X] + \bigl (\E [X]\bigr )^2}]\\ &= \E [X^2] - 2\E [X]\E [X]+ \bigl (\E [X]\bigr )^2\\ &= \E [X^2] - \bigl (\E [X]\bigr )^2 \end {aligned} \end{equation}
Properties of the variance: Multiplication by a constant, and the variance of a constant:
\(\seteqnumber{1}{1.18}{0}\)\begin{align} \Var [aX+b] =& a^2 \Var [X]\label {eq:rand1d:var_prop}\\ \Var [b] =& 0 \end{align}
-
Proof. The proof is given in Exercise 1.1.
It always holds that \(\Var [X]\ge 0\).
In general3,
\[\begin {aligned} \E [g(X)] &\ne g\left (\E [X]\right ) \\ \Var [g(X)] &\ne g\left (\Var [X]\right ) \end {aligned}\]
For example,
\[\begin {aligned} \E [X^2] &\ne \bigl (\E [X]\bigr )^2 \\ \Var [X^2] &\ne \bigl (\Var [X]\bigr )^2 \end {aligned}\]
1.2.4 Numerical Computation
Computation from experiment outcomes: Given \(N\) outcomes \(x_1,\ldots ,x_N\) of a random experiment, the computation of the expectation is replaced by the computation of a mean, as follows.
\(\seteqnumber{0}{1.}{18}\)\begin{align} \E [X] &=\frac {1}{N}\sum _{i=1}^{N}x_i\\ \Var [X] &=\frac {1}{N}\sum _{i=1}^{N}\left (x_i - \E [X]\right )^2 \end{align}
There is no difference in the computation for continuous or discrete experiment outcomes.
There are additional methods for computing the variance.
1.3 Common Distributions
Distribution: A unique, useful, and common random model that has been given a name because of its importance. It is used to describe or characterize a random variable.
1.3.1 Bernoulli Distribution
PDF: For \(X\sim \mathrm {Ber}(p)\) we have (Fig. 1.1a)
\(\seteqnumber{0}{1.}{20}\)\begin{equation} \begin{aligned} p_X[k] &= \begin{cases} 1-p & k=0\\p &k =1 \end {cases}\\ &=p^k(1-p)^{1-k}\qquad k=0,1\\ &=(1-p)\delta [k] + p\delta [k-1] \end {aligned} \end{equation}
CDF: For \(X\sim \mathrm {Ber}(p)\) we have (Fig. 1.1b)
\(\seteqnumber{0}{1.}{21}\)\begin{equation} F_X(x) = \begin{cases} 0 & x<0\\ 1-p & 0 \le x < 1 \\ 1 & 1 \le x \end {cases} \end{equation}
-
Example 1.8: Compute the expectation and variance of the Bernoulli distribution.
-
Solution: The variance uses \(\E [X^2]\), computed with the formula for the expectation of a function of a random variable, Eq. (1.11).
\(\seteqnumber{0}{1.}{22}\)\begin{align*} \E [X] &= \sum _i x_i p_X[x_i]\\ &=(k=0)\,p_X[0] + (k=1)\,p_X[1]\\ &=0\cdot (1-p) + 1\cdot p = p\\ \Var [X] &= \E [X^2] - \bigl (\E [X]\bigr )^2\\ & =\bigl [(0)^2 p_X[0] + (1)^2p_X[1]\bigr ] - p^2 \\ &=0^2\cdot (1-p) + 1^2\cdot p - p^2 = p-p^2\\ &=p(1-p) \end{align*}
-
1.3.2 Binomial Distribution
PDF: For \(X\sim \mathrm {Bin}(n,p)\), the computation can be split into three parts:
-
1. there are \(\dbinom {n}{k} = \dfrac {n!}{k!(n-k)!}\) ways to obtain \(k\) successes out of \(n\) experiments.
-
2. the probability of \(k\) successes (outcomes “1”) is \(p^k\).
-
3. the probability of \(n-k\) failures (outcomes “0”) is \((1-p)^{n-k}\).
Combining the three probabilities,
\(\seteqnumber{0}{1.}{22}\)\begin{equation} p_X[k] = \dbinom {n}{k}p^k(1-p)^{n-k} \end{equation}
CDF: There is no closed-form expression, only the sum of the PDF according to Feature 1.2.1,
\(\seteqnumber{0}{1.}{23}\)\begin{equation} F_X(x) = \begin{cases} 0 & x < 0\\ \displaystyle \sum _{k=0}^{\lfloor x \rfloor }p_X[k] & 0\le x < n\\ 1 & n \le x \end {cases} \end{equation}
The symbol \(\lfloor \cdot \rfloor \) over the sum denotes rounding down.
Expectation and variance: For \(X\sim \mathrm {Bin}(n,p)\),
\(\seteqnumber{0}{1.}{24}\)\begin{align} \E [X] & =np\\ \Var [X] &=np(1-p) \end{align}
Relation to the Bernoulli distribution: For a single experiment \((n=1)\), we have the relation \(X\sim \mathrm {Bin}(1,p) \Leftrightarrow X\sim \mathrm {Ber}(p)\).
-
Example 1.9: A die is rolled 6 times. Compute the probability of exactly two outcomes of “6”.
-
Solution: The problem can be phrased as the probability of exactly \(k=2\) successes out of \(n= 6\) experiments, where the success probability of a single experiment is \(p=\frac {1}{6}\).
\(\seteqnumber{0}{1.}{26}\)\begin{align*} X&\sim \mathrm {Bin}\left (6,\frac {1}{6}\right )\\ p_X[2] &=\dbinom {6}{2}\left (\frac {1}{6}\right )^2\left (1-\frac {1}{6}\right )^{6-2}\approx 0.20 \end{align*}
-
1.3.3 Geometric Distribution
PDF, CDF, expectation, and variance: For a geometric distribution, \(X\sim \mathrm {Geo}(p)\), we have
\(\seteqnumber{0}{1.}{26}\)\begin{align} p_X[k] &= p(1-p)^{k-1},\quad k=1,2,\ldots \\ F_X[k] &= 1 - (1-p)^k\\ \E [X] & =\dfrac {1}{p}\\ \Var [X] &=\dfrac {1-p}{p^2} \end{align}
-
Example 1.10: What is the probability of not getting a “6” in the first 6 rolls of a die?
-
Solution: Define a random variable \(X\) that is the number of die rolls until the first “6” appears.
-
• the probability of a “6” exactly on the first roll is \(p_X[1]=\frac {1}{6}\).
-
• the probability of a “6” exactly on the second roll is the probability of not getting a “6” on the first roll times the probability of a “6” on the second roll, \(p_X[2]=\frac {5}{6}\cdot \frac {1}{6}\).
-
• the probability of a “6” exactly on the third roll is \(p_X[3]=\left (\frac {5}{6}\right )^2\cdot \frac {1}{6}\).
-
• the probability of a “6” exactly on the sixth roll is \(p_X[6]=\left (\frac {5}{6}\right )^5\cdot \frac {1}{6}\).
In summary,
\(\seteqnumber{0}{1.}{30}\)\begin{equation} \begin{aligned} \Pr (X > 6) &=1-\Pr (X\le 6)\\ &= 1 - \left (p_X[1] + p_X[2] + \cdots + p_X[6]\right )\\ & = 1 - F_X(6) = \left (1-\frac {1}{6}\right )^6 \approx 0.3349 \end {aligned} \end{equation}
-
-
Mode: The value \(x_k\) for which the PDF attains its maximum value,
\(\seteqnumber{0}{1.}{31}\)\begin{equation} x_k = \argmax _{x_k} p_X[x_k] \end{equation}
Median: The value \(m\) for which \(\Pr (X \le m) \ge \frac {1}{2}\) and also \(\Pr (X \ge m) \ge \frac {1}{2}\) hold simultaneously is called the median.
Relation between the expectation and the median: There is an interesting inequality that bounds the maximal difference between the expectation and the median,
\(\seteqnumber{0}{1.}{32}\)\begin{equation} \abs {\E [X]-m}\le \sqrt {\Var [X]}, \end{equation}
1.4 Exercises
1.1 Prove Eq. (1.18a).
1.2 The probability of a particular natural number \(k\) out of the set of all natural numbers \(\left \lbrace 1,2,3,\ldots \right \rbrace \) is given by
\(\seteqnumber{0}{1.}{33}\)\begin{equation*} p[k] = \begin{cases} \frac {4}{7} & k = 1 \\ \frac {2}{7} & k = 2 \\ \left (\frac {1}{8}\right )^{k-2} & k\ge 3 \end {cases} \end{equation*}
What is the probability \(p[K\ge 4]\)?
1.3 (simulation) Write a simulation to compute the outcome of rolling a pair of dice.
1.4 A random experiment is defined as tossing a fair coin \(n\) times in a row.
-
(a) What is the probability of \(n\) ones in a row?
-
(b) The experiment is repeated \(N=2^n\) times. What is the probability that, out of the \(N\) outcomes, there is at least one occurrence of \(n\) ones in a row?
-
(c) Compute the numerical value of this probability for \(n=10\).
1.5 A certain communication system is supposed to operate with an error probability of \(10^{-3}\), meaning one error per 1000 bits. Different customers decided to test the performance of the system:
-
(a) a customer transmitted 1000 bits and received 0 errors.
-
(b) a customer transmitted 1000 bits and received 1 error.
-
(c) a customer transmitted 1000 bits and received 3 errors.
Questions:
-
(a) What is the probability of customer (a)’s result?
-
(b) What is the probability of customer (b)’s result?
-
(c) What is the probability of 3 or more errors for customer (c)?
1.6 A communication system transmits messages of length 2 bits. To detect errors, the system uses a repetition protocol (Repetition Code): each message is transmitted twice in a row (a total of 4 bits per transmission). At the receiver, an integrity check is performed by comparing the first pair of bits (the original message) with the second pair of bits (the repetition):
-
• if the pairs are identical, the system assumes the transmission is valid and accepts it.
-
• if the pairs differ, the system detects an error and rejects the transmission.
For example, for the message “00”, the system transmits “0000”.
It is given that the error probability for a single bit is \(p\), and that the errors in different bits are independent.
-
1. What is the probability of a transmission error in a system that transmits 2 bits only, without the repetition mechanism (that is, the transmission is considered erroneous if at least one bit arrives corrupted)?
-
2. What is the probability that the double transmission (4 bits) is received completely correctly? (that is, the case in which all 4 transmitted bits are received on the other side without any error).
-
3. What is the probability of an undetected error in the system with the repetition mechanism (4 bits)? (that is, the case in which the receiver accepts the transmission as “valid” because the pairs are identical, but the received information is erroneous relative to the original information).
1.7 In 2003, the salary data in Israel were:
-
• an average salary of 8,027 NIS
-
• a median salary of 6,543 NIS.
This means that:
-
(a) most people receive a salary lower than the average salary.
-
(b) most people receive a salary higher than the average salary.
-
(c) approximately half of the people receive a salary above the average, and half below.
-
(d) most people receive a salary lower than the median salary.
-
(e) most people receive a salary higher than the median salary.
-
(f ) approximately half of the people receive a salary above the median, and half below.
-
1.8 A pair of dice is given. What is the probability of the outcome \(\mathbf {(6,6)}\) under the following circumstances:
-
(a) only after at least 10 die rolls, or more?
-
(b) at least once (one time or more), out of 10 rolls.
-
(c) exactly once, out of 10 rolls.