1.5 Probabilistic Arithmetic
1.5 Probabilistic Arithmetic
In Section 1.4 we were interested in how the visiting times of a patient would become distributed over periods of half a year after many visits. We can formalize this problem as follows for one patient. Let \(X_k\) be the \(k\)th inter-arrival time, and write \(C\) for the length of the interval in which the patient has to see a doctor; here \(C\) is half a year. Then the arrival times modulo \(C\) satisfy
\begin{align*} Z_{k} = Z_{k-1} + X_{k} \bmod C, \quad Z_{0} = 0, \end{align*}where \(X_{k}\bmod C\) is the remainder of \(X_{k}/C.\) To compute the distribution of \(Z_k\) we need to be able to compute the distribution of \(Y_{k} = Z_{k-1} + X_k,\) and then find the distribution of \(f(Y_k)\) where \(f(x) = x \bmod C.\) Clearly, this is a very unattractive task to carry out by hand. In this section we develop algorithms that allow a computer to carry out this tedious work.
More generally, later sections require numerical work to gain insight into the behavior of stochastic processes. We therefore develop a small collection of functions for probabilistic arithmetic. The emphasis is on reusable algorithmic patterns: how probability distributions are stored, how functions transform and combine random variables, and why these functions work. At the end of this section, we use these algorithms to study the distribution of \(\set{Z_k}\) discussed above.
Let us start by making explicit what we mean by a pattern. As a first pattern, consider the \(+\) operator. Suppose that we only know how to do addition on the positive integers.1For example: \(3+5=8.\) Observe that the definition of addition on integers cannot be directly applied to rationals. To add fractions, we need to extend the symbol \(+\) to the following procedure: make the denominators of the fractions identical, and then add the numerators.2\(1/3+1/2 = 2/6 + 3/6 = (2+3)/6 = 5/6.\) However, this procedure does not work to compute \(\sqrt 2 + \sqrt 3.\)3\(\sqrt 2\) and \(\sqrt 3\) are not rationals so we cannot make the denominators equal. To add general real numbers, we need to extend the definition of \(+\) yet further.4One way is like this: \(\sqrt 2 + \sqrt 3 = \Sup{x + y : x, y \in \Q, x^{2} \leq 2, y^{2} \leq 3}.\) Next, we need to define addition for complex numbers, vectors, matrices, \(\ldots\). In summary, when learning mathematics, we have been silently overloading the \(+\) operator to many different situations.
In our present case, we write \(X+Y\) for two independent rvs to mean the convolution:
\begin{equation*} \P{X+Y=z} = \sum_{i} \sum_{j} p_{i} q_{j} \1{i+j=z}, \tag{1.5.1} \end{equation*}where \(p_{i} = \P{X=i},\) \(q_j = \P{Y=j}\) and the indicator \(\1{A} = 1\) if the event \(A\) occurs, and \(0\) otherwise. Below we express this as an algorithm.5For addition there exists a much faster method based on Fast Fourier transforms.
Thus, the first pattern that helps us to reason in more abstract ways about problems is to use operator overloading.
This brings us to a second pattern: observe that the expression \(X+Y\) combines two rvs \(X\) and \(Y\) and then applies some function. Similarly, the operations \(X-Y,\) \(XY,\) \(\Max{X, Y}\) are all functions applied to two independent rvs. What we therefore need is a method to compute the pmf of a new rv \(f(X,Y),\) where \(f\) is some general binary function.6A binary function depends on two arguments.
We identify a third pattern when we realize that to compute \(\V X,\) we need \(\E{X^{2}}.\) But \(\E{X^{2}}\) is the expectation of the rv \(g(X)\) where \(g(x) = x^{2}.\) So, we also need a method to compute the pmf of the rv \(g(X),\) where now \(g\) is some general unary function.7A unary function depends on just one argument.
In summary, we want to develop functions that support the following operations on rvs:
- operator overloading for addition, subtraction, and potentially other arithmetical operations;
- the application of a unary function to obtain a new rv;
- the application of a binary function.
We call these functions probabilistic arithmetic, and we will develop, step by step, clear and general algorithms to support this. However, we first need to introduce some computer science concepts.
A useful data structure for storing the pmf of a discrete rv is a map, as constructed by \(\pr{Map}\) in Alg. 1.2.13. Its keys are the possible values of the rv, and the value stored under each key is its probability. Since values outside the support have probability zero, we use the default value zero. We denote the pmf map of an rv \(X\) by \(p_X,\) so that \(p_X(x)=\P{X=x}.\)
\begin{algorithm}
\caption{Store two probability mass functions.}
\begin{algorithmic}[1]
\State \(p_X\gets\pr{Map}()\) \Comment{Initialize $p_{X}$.}
\State \(p_X(1)\gets1/2,\) \(p_X(2)\gets1/2\)
\State \(p_Y\gets\pr{Map}()\)
\State \(p_Y(1)\gets1/2,\) \(p_Y(2)\gets1/2\)
\end{algorithmic}
\end{algorithm}
It is obvious that the pmf map \(p_Z\) for \(Z=X+Y\) should satisfy \(p_Z(2)=1/4,\) \(p_Z(3)=1/2,\) and \(p_Z(4)=1/4.\) Let us use (1.5.1) to compute the pmf of \(Z=X+Y.\)
\begin{algorithm}
\caption{Compute the pmf of the sum.}
\begin{algorithmic}[1]
\State \textbf{Input:} pmf maps \(p_X,\, p_Y\).
\State \textbf{Output:} pmf map \(p_Z\) for \(X+Y\).
\State \(p_Z\gets\pr{Map}()\)
\For{\(i\in\qb{1,\, 2}\)}
\For{\(j\in\qb{1,\, 2}\)}
\State \(p_Z(i+j)\xleftarrow{+} p_X(i)\cdot p_Y(j)\)
\EndFor
\EndFor
\Return \(p_Z\)
\end{algorithmic}
\end{algorithm}
Because \(p_Z\) is a map with default value zero, the first contribution to a key is added to zero. Later contributions are added to the value already stored under that key. In particular, the two pairs \((1,2)\) and \((2,1)\) each add \(1/4\) to \(p_Z(3).\) Thus, the algorithm returns \(p_Z(2)=1/4,\) \(p_Z(3)=1/2,\) and \(p_Z(4)=1/4.\)
The above algorithm assumes that mathematically equal keys have the same representation in the computer. This requires care when the keys are stored as floating-point numbers. Most real numbers cannot be represented exactly with finitely many digits. Consequently, two expressions that are mathematically equal, such as \(1/3\) and \(1-2/3,\) can be stored as slightly different numbers. An implementation of \pr{Map} in a real computer language then treats them as different keys and does not combine their probabilities. This is a general problem of computer arithmetic, not a problem specific to a programming language. We avoid it by using exact numbers, such as integers or fractions, whenever possible. Otherwise, we round all keys to an agreed precision before storing them.
The function \(\pr{ToFraction}\) of Alg. 1.5.3 replaces a number \(x\in \R\) by a nearby fraction, rounded to \(d\) decimal places. It first uses denominator \(10^d\) and then reduces the fraction using the greatest common divisor.8The greatest common divisor can be computed with Euclid’s algorithm. See Euclidean algorithm for its implementation. Keeping this conversion in a separate function hides its details from the algorithms that use it. If we later change the precision or the conversion rule, we only have to change \(\pr{ToFraction}.\)
\begin{algorithm}
\caption{Convert a number to a fraction.}
\begin{algorithmic}[1]
\State \textbf{Input:} a number \(x\) and precision \(d\).
\State \textbf{Output:} a reduced fraction \(a/b\).
\Function{ToFraction}{\(x,\, d = 10\)}
\State \(q\gets10^d\)
\State \(p\gets\operatorname{round}(x\cdot q)\)
\State \(g\gets\pr{GCD}(|p|,\, q)\)
\Return \(p/g, q/g\)
\EndFunction
\end{algorithmic}
\end{algorithm}
The function \(\pr{MakePMF}\) of Alg. 1.5.4 uses the conversion to fractions to construct a pmf map from a map of outcomes and non-negative weights. It first converts every outcome with \(\pr{ToFraction}.\) When two outcomes are converted to the same fraction, their weights are added. Finally, \(\pr{NormalizeMap},\) Alg. 1.5.5, makes the stored weights sum to one. Rounding the outcomes and discarding small weights makes the resulting pmf a numerical approximation to the original distribution.
\begin{algorithm}
\caption{Construct a probability mass function.}
\begin{algorithmic}[1]
\State \textbf{Input:} a finite map \(w\) with non-negative values and positive sum.
\State \textbf{Output:} a pmf map \(p\).
\Function{MakePMF}{\(w\)}
\State \(r\gets\pr{Map}()\)
\For{\(x\in\pr{Keys}(w)\)}
\State \(r(\pr{ToFraction}(x))\xleftarrow{+}w(x)\)
\EndFor
\Return \(\pr{NormalizeMap}(r)\)
\EndFunction
\end{algorithmic}
\end{algorithm}
The function \(\pr{Normalize}\) of Alg. 1.2.8 normalizes a list of weights. For the given map \var{w}, we store the weights in a map whose keys are the possible outcomes. It then removes entries whose relative weight does not exceed the default numerical threshold \(\epsilon=10^{-16},\) and then normalizes the remaining weights.
\begin{algorithm}
\caption{Normalize the values stored in a map.}
\begin{algorithmic}[1]
\State \textbf{Input:} a finite map \(w\) with non-negative values and positive sum; threshold \(\epsilon\).
\State \textbf{Output:} a map \(p\) whose values sum to one.
\Function{NormalizeMap}{\(w,\, \epsilon = 10^{-16}\)}
\State \(T\gets\pr{Sum}\rb{\pr{Values}(w)}\)
\State \(S\gets\pr{Filter}\rb{\pr{Keys}(w),\, \lambdafun{k}{w(k)/T>\epsilon}}\)
\State \(\var{total}\gets\pr{Sum}\rb{\qb{w(k):k\in S}}\)
\State \(V\gets\pr{Apply}\rb{S,\, \lambdafun{k}{w(k)/\var{total}}}\)
\Return \(\pr{MakeMap}\rb{\var{keys}=S,\, \var{values}=V}\)
\EndFunction
\end{algorithmic}
\end{algorithm}
We now use \(\lambda\) functions to compute the different moments of a rv \(X.\)
The function \(\pr{Expectation}\) applies \(f\) to every possible value of the rv represented by \(p_X\) to compute \(\E{f(X)}.\)
\begin{algorithm}
\caption{Compute the expectation of functions of a discrete random variable \(X.\)}
\begin{algorithmic}[1]
\State \textbf{Input:} pmf map \(p_X,\) function \(f\).
\State \textbf{Output:} \(\E{f(X)}\).
\Function{Expectation}{\(p_X,\, f\)}
\Return \(\pr{Sum}\rb{\qb{f(x)\cdot p_X(x):x\in\pr{Keys}(p_X)}}\)
\EndFunction
\end{algorithmic}
\end{algorithm}
With this, Alg. 1.5.7 computes the mean and variance with calls to simple \(\lambda\) functions. We choose to build the \pr{Variance} as function, because as \(\lambda\) function it becomes somewhat long.
\begin{algorithm}
\caption{Compute moments of a discrete random variable.}
\begin{algorithmic}[1]
\State \textbf{Input:} pmf map \(p_X\).
\State \textbf{Output:} mean, second moment, variance, and standard deviation of \(X\).
\State \(\pr{Mean} \gets \lambdafun{p_X}{\pr{Expectation}(p_X,\, \lambdafun{x}{x})}\)
\State \(\pr{SecondMoment} \gets \lambdafun{p_X}{\pr{Expectation}(p_X,\, \lambdafun{x}{x^2})}\)
\Function{Variance}{\(p_X\)}
\Return \(\pr{SecondMoment}(p_X)-\pr{Mean}(p_X)^2\)
\EndFunction
\State \(\pr{StandardDeviation} \gets \lambdafun{p_X}{\sqrt{\pr{Variance}(p_X)}}\)
\end{algorithmic}
\end{algorithm}
Another nice example is the cdf; we can use that \(F_{X}(x) = \P{X\leq x}=\E{\1{X\leq x}}.\)
\begin{algorithm}
\caption{Compute the cdf through expectation.}
\begin{algorithmic}[1]
\State \textbf{Input:} pmf map \(p_X\).
\State \textbf{Output:} cdf \(F_X\).
\Function{CDF\_slow}{\(p_X\)}
\Return \(\lambdafun{x}{\pr{Expectation}(p_X,\, \lambdafun{y}{\1{y \leq x}})}\)
\EndFunction
\end{algorithmic}
\end{algorithm}
The function returned by \(\pr{CDF\_slow}(p_X)\) remembers the map \(p_X\). When called with \(x,\) it sums \(p_X(y)\) over all keys \(y\leq x,\) giving \(F_X(x)=\P{X\leq x}.\) For example:
\begin{algorithm}
\begin{algorithmic}[1]
\State \(\var{F}_X\gets\pr{CDF\_slow}(p_X)\) \Comment{Binds \(F_X\) to \(\lambdafun{x}{\E{\1{X\leq x}}}\).}
\State \(\var{F}_X(x)\) \Comment{Returns \(\P{X\leq x}.\)}
\end{algorithmic}
\end{algorithm}
To evaluate the cdf at many different values of \(x,\) we need not sum the probabilities again at every call. Instead, we compute the cumulative probabilities once and then use \(\pr{SearchSorted}\), Alg. 1.5.29, to find which cumulative probability to return.9SearchSorted takes some explanation. We prove its correctness at the end of the main text. First, we sort the support of \(X\) in increasing order and list the probabilities in that same order. We then use Alg. 1.5.10 to compute their cumulative sums, which give the cdf at the support points. \(\pr{PrepareCDF}\), Alg. 1.5.12, implements this as a function.
\begin{algorithm}
\caption{Compute the cumulative sums of a list.}
\begin{algorithmic}[1]
\State \textbf{Input:} a list \(A\).
\State \textbf{Output:} the list \(C\) of running totals of \(A\).
\Function{CumSum}{\(A\)}
\State \(C,\,\var{total}\gets\qb{},\,0\)
\For{\(a\in A\)}
\State \(\var{total}\xleftarrow{+}a\)
\State \(C\gets\pr{Append}\rb{C,\, \var{total}}\)
\EndFor
\Return \(C\)
\EndFunction
\end{algorithmic}
\end{algorithm}
Here is an example how this works. We use \(M\) for the map of cumulative probabilities and \(F\) for the cdf function.
\begin{algorithm}
\begin{algorithmic}[1]
\State \(p_X\gets\pr{Map}()\)
\State \(p_X(3)\gets1/4,\quad p_X(2)\gets1/3,\quad p_X(1)\gets5/12\)
\State \(S\gets\pr{QSort}\rb{\pr{Keys}(p_X)}\) \Comment{\(S=\qb{1,\,2,\,3}.\)}
\State \(P\gets\qb{p_X(s_1),\,p_X(s_2),\,p_X(s_3)}\) \Comment{\(P=\qb{5/12,\,1/3,\,1/4}.\)}
\State \(C\gets\pr{CumSum}\rb{P}\) \Comment{\(C=\qb{5/12,\,3/4,\,1}.\)}
\State \(M\gets\pr{MakeMap}\rb{\var{keys}=S,\,\var{values}=C}\)
\State \(F\gets\pr{CDF}(p_X)\)
\State \(F(1.1)\) \Comment{\(F(1.1)=5/12.\)}
\end{algorithmic}
\end{algorithm}
\begin{algorithm}
\caption{Prepare the support and cumulative probabilities of a discrete random variable.}
\begin{algorithmic}[1]
\State \textbf{Input:} pmf map \(p_X\).
\State \textbf{Output:} cumulative-probability map \(M\).
\Function{PrepareCDF}{\(p_X\)}
\State \(S\gets\pr{QSort}\rb{\pr{Keys}(p_X)}\)
\State \(C\gets\pr{CumSum}(\qb{p_X(s_1),\, \ldots,\, p_X(s_n)})\)
\Return \(\pr{MakeMap}\rb{\var{keys}=S,\, \var{values}=C}\)
\EndFunction
\end{algorithmic}
\end{algorithm}
To find the cdf \(\P{X\leq x}\) from the prepared map \(M,\) it now suffices to find how many of its keys are no larger than \(x.\) \(\pr{SearchSorted}\), Alg. 1.5.29, returns this number. We explain how it works at the end of the main text.
The returned value is zero when \(x<s_1.\) Otherwise it is the largest index \(k\) for which \(s_k\leq x,\) and the cdf is simply \(M(s_k).\)
The function \(\pr{CDF}\) first prepares the internal cdf map \(M.\) It then returns an inner function \(F.\) This function retains access to \(M.\) Its keys are the support in increasing order because \(\pr{PrepareCDF}\) inserted them in that order. Each call to \(F\) therefore only has to run \(\pr{SearchSorted}\) on these keys and retrieve the corresponding value from \(M.\)
\begin{algorithm}
\caption{Construct a cdf that uses search sorted.}
\begin{algorithmic}[1]
\State \textbf{Input:} pmf map \(p_X\).
\State \textbf{Output:} cdf function \(F\).
\Function{CDF}{\(p_X\)}
\State \(M\gets\pr{PrepareCDF}(p_X)\)
\State \(S\gets\pr{Keys}(M)\) \Comment{The keys of \(M\) are already sorted.}
\Function{F}{\(x\)}
\State \(k\gets\pr{SearchSorted}(S,\, x)\)
\If{\(k=0\)}
\Return \(0\)
\EndIf
\Return \(M(s_k)\)
\EndFunction
\Return \(F\)
\EndFunction
\end{algorithmic}
\end{algorithm}
The survivor function \(\P{X>x}=1-\P{X\leq x}=1-F(x)\) follows immediately. By binding \(\pr{CDF}(p_X)\) to \(F\) once, we avoid preparing the cdf again at each evaluation of the survivor function.
\begin{algorithm}
\caption{Compute the survivor function from the cdf.}
\begin{algorithmic}[1]
\State \textbf{Input:} pmf map \(p_X\).
\State \textbf{Output:} survivor function.
\Function{Survivor}{\(p_X\)}
\State \(F\gets\pr{CDF}(p_X)\)
\Return \(\lambdafun{x}{1-F(x)}\)
\EndFunction
\end{algorithmic}
\end{algorithm}
We can now also generate simulated realizations of \(X.\) Let \(F\gets\pr{CDF}(p_X)\) and \(U\sim\Unif{[0,1]}.\) The inverse-cdf method returns the smallest support value \(s_k\) for which \(F(s_k)\geq U.\) This has the required distribution because
\begin{align*} \P{F^{-1}(U)\leq x}=\P{U\leq F(x)}=F(x). \end{align*}The function \(\pr{Simulate}\) applies \(\pr{SearchSorted}\) to the cumulative probabilities. When \(U=c_k,\) it returns \(s_k;\) otherwise it returns the next support value \(s_{k+1}.\) The special case \(k=0\) returns the first support value.
\begin{algorithm}
\caption{Generate \(N\) simulated realizations of a discrete random variable.}
\begin{algorithmic}[1]
\State \textbf{Input:} pmf map \(p_X,\) number of draws \(N\).
\State \textbf{Output:} \(N\) simulated values.
\Function{Simulate}{\(p_X,\, N=1\)}
\State \(M\gets\pr{PrepareCDF}(p_X)\)
\State \(S\gets\pr{Keys}(M)\) \Comment{The keys of \(M\) are already sorted.}
\State \(C\gets\pr{Apply}\rb{S,\, M}\)
\State \(R\gets\qb{}\)
\For{\(j=1,\, \ldots,\, N\)}
\State Generate \(u\sim\Unif{[0,\, 1]}\).
\State \(k\gets\pr{SearchSorted}(C,\, u)\)
\If{\(k=0\)}
\State \(R\gets\pr{Append}\rb{R,\, s_1}\)
\ElsIf{\(c_k=u\)}
\State \(R\gets\pr{Append}\rb{R,\, s_k}\)
\Else
\State \(R\gets\pr{Append}\rb{R,\, s_{k+1}}\)
\EndIf
\EndFor
\Return \(R\)
\EndFunction
\end{algorithmic}
\end{algorithm}
The two remaining patterns are binary and unary functions. Supporting binary functions works the same as addition in (1.5.1). The function \(\pr{BinaryTransform}\) replaces the particular function \(x+y\) by a general binary function \(f(x,y).\) When several pairs produce the same value \(z,\) their probability masses accumulate in the pmf map \(p_Z.\)
\begin{algorithm}
\caption{Construct the pmf of \(f(X,Y)\) where \(X,Y\) are independent rvs.}
\begin{algorithmic}[1]
\State \textbf{Input:} pmf maps \(p_X,\, p_Y\) of independent rvs, binary function \(f\).
\State \textbf{Output:} pmf map of \(f(X,\, Y)\).
\Function{BinaryTransform}{\(p_X,\, p_Y,\, f\)}
\State \(p_Z\gets\pr{Map}()\)
\For{\(x\in\pr{Keys}(p_X)\)}
\For{\(y\in\pr{Keys}(p_Y)\)}
\State \(p_Z(f(x,\, y))\xleftarrow{+}p_X(x)\cdot p_Y(y)\)
\EndFor
\EndFor
\Return \(\pr{MakePMF}(p_Z)\)
\EndFunction
\end{algorithmic}
\end{algorithm}
For a unary function \(f,\) let \(Z=f(X).\) Its pmf satisfies
\begin{equation*} p_Z(z)=\P{Z=z}=\sum_{x\in\pr{Keys}(p_X)}p_X(x)\1{f(x)=z}. \tag{1.5.2} \end{equation*}The function \(\pr{UnaryTransform}\) implements this rule by applying \(f\) to each possible value of \(X.\) Different values of \(X\) can produce the same value \(z=f(x),\) so their probability masses accumulate in the pmf map \(p_Z.\)
\begin{algorithm}
\caption{Construct the pmf of \(f(X).\)}
\begin{algorithmic}[1]
\State \textbf{Input:} pmf map \(p_X,\) function \(f\).
\State \textbf{Output:} pmf map of \(f(X)\).
\Function{UnaryTransform}{\(p_X,\, f\)}
\State \(p_Z\gets\pr{Map}()\)
\For{\(x\in\pr{Keys}(p_X)\)}
\State \(p_Z(f(x))\xleftarrow{+}p_X(x)\)
\EndFor
\Return \(\pr{MakePMF}(p_Z)\)
\EndFunction
\end{algorithmic}
\end{algorithm}
With these two transform functions, we can now define many useful functions of rvs.
A constant rv takes one value (c) with probability one. Its pmf is useful as the starting point for several of the functions below.
\begin{algorithm}
\caption{Construct the pmf of a constant rv.}
\begin{algorithmic}[1]
\State \textbf{Input:} value \(c\).
\State \textbf{Output:} pmf map concentrated at \(c\).
\Function{Constant}{\(c\)}
\State \(p_c\gets\pr{Map}(),\) \(p_c(c)\gets1\)
\Return \(p_c\)
\EndFunction
\end{algorithmic}
\end{algorithm}
Addition is the special case of \(\pr{BinaryTransform}\) obtained by taking \(f(x,y)=x+y.\)
\begin{algorithm}
\caption{Add two independent rvs.}
\begin{algorithmic}[1]
\State \textbf{Input:} pmf maps \(p_X,\, p_Y\) of independent rvs.
\State \textbf{Output:} pmf map of \(X+Y\).
\Function{Add}{\(p_X,\, p_Y\)}
\Return \(\pr{BinaryTransform}\rb{p_X,\, p_Y,\, \lambdafun{(x,\, y)}{x+y}}\)
\EndFunction
\end{algorithmic}
\end{algorithm}
The \(N\)-fold convolution of \(p_X\) is the pmf of \(X_1+\cdots+X_N,\) where the \(X_k\) are independent copies of \(X.\) For \(N=0,\) the sum is zero. We use \(\pr{Add}\) as the accumulator function and \(\pr{Constant}\rb{0}\) as its start value in Alg. 1.2.5.
\begin{algorithm}
\caption{Construct the pmf of the sum of \(N\) independent copies of an rv.}
\begin{algorithmic}[1]
\State \textbf{Input:} pmf map \(p_X,\) number of copies \(N\).
\State \textbf{Output:} pmf map of the sum of \(N\) independent copies of \(X\).
\Function{Convolution}{\(p_X,\, N\)}
\Return \(\pr{Accumulate}\rb{\qb{p_X:k=1,\, \ldots,\, N},\, \pr{Add},\, \pr{Constant}\rb{0}}\)
\EndFunction
\end{algorithmic}
\end{algorithm}
The unary transform allows us to define \(-X\) as an rv: unary minus reflects all outcomes about zero.
\begin{algorithm}
\caption{Negate an rv.}
\begin{algorithmic}[1]
\State \textbf{Input:} pmf map \(p_X\).
\State \textbf{Output:} pmf map of \(-X\).
\Function{Negate}{\(p_X\)}
\Return \(\pr{UnaryTransform}\rb{p_X,\, \lambdafun{x}{-x}}\)
\EndFunction
\end{algorithmic}
\end{algorithm}
We can now implement subtraction as addition of the negative.
\begin{algorithm}
\caption{Subtract two independent rvs.}
\begin{algorithmic}[1]
\State \textbf{Input:} pmf maps \(p_X,\, p_Y\) of independent rvs.
\State \textbf{Output:} pmf map of \(X-Y\).
\Function{Subtract}{\(p_X,\, p_Y\)}
\Return \(\pr{Add}\rb{p_X,\, \pr{Negate}\rb{p_Y}}\)
\EndFunction
\end{algorithmic}
\end{algorithm}
The minimum of two independent rvs is another useful binary transform.
\begin{algorithm}
\caption{Take the minimum of two independent rvs.}
\begin{algorithmic}[1]
\State \textbf{Input:} pmf maps \(p_X,\, p_Y\) of independent rvs.
\State \textbf{Output:} pmf map of \(\Min{X,\, Y}\).
\Function{MinimumPMF}{\(p_X,\, p_Y\)}
\Return \(\pr{BinaryTransform}\rb{p_X,\, p_Y,\, \lambdafun{(x,\, y)}{\Min{x,\, y}}}\)
\EndFunction
\end{algorithmic}
\end{algorithm}
Likewise, we define the maximum of two independent rvs.
\begin{algorithm}
\caption{Take the maximum of two independent rvs.}
\begin{algorithmic}[1]
\State \textbf{Input:} pmf maps \(p_X,\, p_Y\) of independent rvs.
\State \textbf{Output:} pmf map of \(\Max{X,\, Y}\).
\Function{MaximumPMF}{\(p_X,\, p_Y\)}
\Return \(\pr{BinaryTransform}\rb{p_X,\, p_Y,\, \lambdafun{(x,\, y)}{\Max{x,\, y}}}\)
\EndFunction
\end{algorithmic}
\end{algorithm}
The positive part satisfies \(X^+=\Max{0,X}.\) We therefore construct a constant rv equal to zero and take its maximum with \(X.\)
\begin{algorithm}
\caption{Take the positive part of an rv.}
\begin{algorithmic}[1]
\State \textbf{Input:} pmf map \(p_X\).
\State \textbf{Output:} pmf map of \(X^+\).
\Function{PositivePart}{\(p_X\)}
\Return \(\pr{MaximumPMF}\rb{\pr{Constant}\rb{0},\, p_X}\)
\EndFunction
\end{algorithmic}
\end{algorithm}
Likewise, \(X^-=\Max{0,-X}=[-X]^+,\) so we first negate \(X\) and then take its positive part.
\begin{algorithm}
\caption{Take the negative part of an rv.}
\begin{algorithmic}[1]
\State \textbf{Input:} pmf map \(p_X\).
\State \textbf{Output:} pmf map of \(X^-\).
\Function{NegativePart}{\(p_X\)}
\Return \(\pr{PositivePart}\rb{\pr{Negate}\rb{p_X}}\)
\EndFunction
\end{algorithmic}
\end{algorithm}
Taking outcomes modulo \(C\) is also a unary transform.
\begin{algorithm}
\caption{Reduce the outcomes of an rv modulo \(C.\)}
\begin{algorithmic}[1]
\State \textbf{Input:} pmf map \(p_X,\) modulus \(C\).
\State \textbf{Output:} pmf map of \(X\bmod C\).
\Function{Modulo}{\(p_X,\, C\)}
\Return \(\pr{UnaryTransform}\rb{p_X,\, \lambdafun{x}{x\bmod C}}\)
\EndFunction
\end{algorithmic}
\end{algorithm}
With these functions we can study the content of Th. 1.4.1 numerically. In particular, how quickly do the arrival times on the circle converge to the uniform distribution? Recall that
\begin{align*} A_k=(A_{k-1}+X_k)\bmod C. \end{align*}We first use \(\pr{Add},\) and then use \(\pr{Modulo}.\)
In Alg. 1.5.28 we iteratively compute the arrival-time position \(\sum_{i=1}^{n}X_i\bmod C,\) where the \(X_i\) are mutually independent with \(X_i\sim\Unif{\set{-1,0,1}},\) and \(A_0=0.\) We track the positions that occur with the smallest and largest probability. Fig. 1.1 shows the result.
\begin{algorithm}
\caption{Track convergence of the arrival-time distribution on a cycle.}
\begin{algorithmic}[1]
\State \textbf{Input:} cycle length \(C,\) number of iterations \(n,\) and step pmf \(p_X\).
\State \textbf{Output:} smallest and largest probabilities \(m_k,\, M_k\).
\Function{ArrivalConvergence}{\(C,\, n,\, p_X\)}
\State \(p_{A_0}\gets\pr{Constant}\rb{0}\)
\State \(m,\,M\gets\qb{},\,\qb{}\)
\For{\(k=1,\, \ldots,\, n\)}
\State \(p_{A_k}\gets\pr{Modulo}\rb{\pr{Add}\rb{p_{A_{k-1}},\, p_X},\, C}\)
\State \(m\gets\pr{Append}\rb{m,\,\pr{Minimum}\rb{\qb{p_{A_k}(a):a=0,\, \ldots,\, C-1}}}\)
\State \(M\gets\pr{Append}\rb{M,\,\pr{Maximum}\rb{\qb{p_{A_k}(a):a=0,\, \ldots,\, C-1}}}\)
\EndFor
\Return \(m,\,M\)
\EndFunction
\end{algorithmic}
\end{algorithm}
Finally, we explain how \(\pr{SearchSorted}\) works. Given a sorted list \(A\) and a number \(x,\) it returns the number of entries of \(A\) that are less than or equal to \(x.\) We first give the algorithm, then provide an example, and finally prove that it returns the stated number.
The algorithm10Like sorting, efficiently searching sorted data is used almost everywhere that computers are used. The ideas behind this algorithm are very important. inspects the middle of the current part of the list and then calls itself on either the left or the right part. Each call therefore reduces the part that remains to be searched by about one half, so only about11\(\log\) is the natural logarithm, \(\log_2\) has base 2. \(\log_2 n\) comparisons are needed for a list of length \(n.\)
\begin{algorithm}
\caption{Find how many entries of a sorted list are \(\leq x.\)}
\begin{algorithmic}[1]
\State \textbf{Input:} a sorted list \(A=\qb{a_1,\, \ldots,\, a_n}\) and a number \(x\).
\State \textbf{Output:} the number of entries in \(A\) that are less than or equal to \(x\).
\Function{SearchSorted}{\(A,\, x,\, l=1,\, r=n\)}
\If{\(l>r\)}
\Return \(r\)
\EndIf
\State \(m\gets\lfloor(l+r)/2\rfloor\)
\If{\(x < a_m\)}
\Return \(\pr{SearchSorted}(A,\, x,\, l,\, m-1)\)
\EndIf
\Return \(\pr{SearchSorted}(A,\, x,\, m+1,\, r)\)
\EndFunction
\end{algorithmic}
\end{algorithm}
Consider \(A=\qb{1,2,3}\) and \(x=1.1.\) Initially, \(l=1\) and \(r=3,\) so \(m=2.\) Since \(x<a_2=2,\) the next call searches with \(l=1,\ r=1.\) Now \(m=1.\) Since \(a_1=1\leq x,\) the next call has \(l=2,\ r=1.\) As \(l>r,\) it returns \(r=1:\) exactly one entry is less than or equal to \(1.1.\)
To prove correctness, we keep track of what each recursive call leaves unchanged.12You may skip this proof, but I advise against it: it illustrates one of the most important ideas in reasoning about algorithms. Let \(k\) be the number of entries of \(A\) that are less than or equal to \(x.\)
The first major idea to find a loop invariant.13A loop invariant is a property that holds initially and remains true after each iteration; here, after each recursive call. For this algorithm, this invariant is \(l-1\leq k\leq r.\) It14Note, the loop invariant is not \(l\leq k\leq m\); the \(-1\) is essential. holds initially because \(l=1,\) \(r=n,\) and \(0\leq k\leq n.\) If \(x<a_m,\) sortedness gives \(k\leq m-1,\) so setting \(r=m-1\) preserves the invariant. Otherwise \(k\geq m,\) so setting \(l=m+1\) preserves it.15The key is that with choice, the loop invariant becomes \(m\leq k \leq r\).
Next, we should show that the algorithm terminates in a finite number of steps. Here, each call with \(l\leq r\) strictly reduces the number of indices still to be searched, so the recursion must terminate.
Finally, we need to check what is the terminal value of the algorithm. here, the terminal condition is \(l>r,\) and the loop invariant forces \(k=r=l-1.\) Thus the returned value \(r\) is correct. A bit of thought shows that the cases when no entry or every entry is less than or equal to \(x\) are included as terminal values.
TF 1.
Let \(w\) be the map with \(w(a)=1,\) \(w(b)=2,\) and \(w(c)=7.\) Apply \(\pr{NormalizeMap}(w,\epsilon=0.15).\) Claim: the resulting pmf map \(p\) satisfies \(p(b)=2/9.\)
Solution
Did you actually try? Write your solution down first for comparison.
Show the solution
True. The original relative weights are \(0.1,\) \(0.2,\) and \(0.7,\) so the key \(a\) is removed. The retained weights \(2\) and \(7\) are then normalized by their sum \(9.\)
TF 2.
The function \(\pr{CumSum}\) returns the running totals of a list. Claim: \[ \pr{CumSum}(\qb{3,-1,4,-2})=\qb{3,2,6,4}. \]
Solution
Did you actually try? Write your solution down first for comparison.
Show the solution
True. The successive sums are \(3,\) \(3-1=2,\) \(2+4=6,\) and \(6-2=4.\)
TF 3.
Let \(p_X\) and \(p_Y\) be the pmf maps of independent rvs \(X\) and \(Y.\) Consider the central part of \(\pr{BinaryTransform}\):
\begin{algorithm}
\begin{algorithmic}[1]
\State \(p_Z\gets\pr{Map}()\)
\For{\(x\in\pr{Keys}(p_X)\)}
\For{\(y\in\pr{Keys}(p_Y)\)}
\State \(z\gets f(x,\, y)\)
\State \(p_Z(z)\xleftarrow{+}\text{???}\)
\EndFor
\EndFor
\end{algorithmic}
\end{algorithm}
Claim: replacing \(\text{???}\) by \(p_X(x)p_Y(y)\) makes \(p_Z\) the pmf map of \(Z=f(X,Y).\)
Solution
Did you actually try? Write your solution down first for comparison.
Show the solution
True. Independence gives probability \(p_X(x)p_Y(y)\) to the pair \((x,y),\) and all pairs with the same value \(z=f(x,y)\) contribute to the same key.
TF 4.
Let \(A=\qb{a_1,\ldots,a_n}\) be sorted. Consider the recursive function \(\pr{SearchSorted}\):
\begin{algorithm}
\begin{algorithmic}[1]
\Function{SearchSorted}{\(A,\, x,\, l=1,\, r=n\)}
\If{\(l>r\)}
\Return \(r\)
\EndIf
\State \(m\gets\lfloor(l+r)/2\rfloor\)
\If{\(x < a_m\)}
\Return \(\pr{SearchSorted}(A,\, x,\, l,\, m-1)\)
\EndIf
\Return \(\pr{SearchSorted}(A,\, x,\, \text{???},\, r)\)
\EndFunction
\end{algorithmic}
\end{algorithm}
Claim: at \(\text{???},\) the algorithm should have \(m+1.\)
Solution
Did you actually try? Write your solution down first for comparison.
Show the solution
True. When \(a_m\leq x,\) the first \(m\) entries are no longer in doubt, so the recursive call searches the part starting at \(m+1.\)
TF 5.
Let the rv \(X\) have cumulative distribution function \(F_X\) and let \(U\sim\text{Unif}(0,1).\) Claim: \(F_{X}(F_{X}^{-1}(U))\sim\text{Unif}(0,1).\)
Solution
Did you actually try? Write your solution down first for comparison.
Show the solution
False when \(F\) has jumps.
TF 6.
Let \(X\) and \(Y\) be two independent rvs with support \(\set{0, 1, 2, \ldots}\) and pmf maps \(p_X\) and \(p_Y,\) respectively. Claim: \[ \P{X-Y\le k}=\sum_{i=0}^{\infty}\sum_{i=0}^{\infty}\1{i-j\le k}p_X(i)p_Y(j). \]
Solution
Did you actually try? Write your solution down first for comparison.
Show the solution
False. Check the index of the second summation.
TF 7.
The function \(\pr{ToFraction}(x,d)\) first rounds \(x\) to \(d\) decimal places and then reduces the resulting fraction. Claim: \(\pr{ToFraction}(1/3,2)=1/3.\)
Solution
Did you actually try? Write your solution down first for comparison.
Show the solution
False. It first uses denominator \(100\) and numerator \(\operatorname{round}(100/3)=33.\) Since \(33\) and \(100\) have greatest common divisor one, the function returns \(33/100.\)