Ch.9: Probability theory
Chapter 9 of the book "No Bullshit Guide to Linear Algebra" by Ivan Savov Probability distributions Markov chains Google's PageRank algorithm
52 flashcards · Mathematics · by lakesare
Part of Textbooks › No Bullshit Guide to Linear Algebra (Ivan Savov) · 10 courses
[Probability distributions] What does the probability distribution of a random event describe?
How likely each of the possible outcomes is. Each entry is the probability mass of one outcome.Example: fair die: pX=(16,16,16,16,16,16)Tp_X = (\frac{1}{6}, \frac{1}{6}, \frac{1}{6}, \frac{1}{6}, \frac{1}{6}, \frac{1}{6})^{\mathsf{T}}pX=(61,61,61,61,61,61)T ; fair coin: pY=(12,12)Tp_Y = (\frac{1}{2}, \frac{1}{2})^{\mathsf{T}}pY=(21,21)T .
[Probability distributions] Which two conditions on the probability masses of a distribution are the Kolmogorov axioms of probability?
Every probability mass is a number between 0 and 1, and the masses sum to 1. Example: (0.3,0.3,−0.1,0.5)T(0.3, 0.3, -0.1, 0.5)^{\mathsf{T}}(0.3,0.3,−0.1,0.5)T sums to 1 but is not a probability distribution, since −0.1<0-0.1 < 0−0.1<0 .
[Probability distributions] For a random variable XXX , what does the calligraphic X\mathcal{X}X denote?
The set of possible outcomes of XXX . ∣X∣|\mathcal{X}|∣X∣ is the number of possible outcomes.Example: rolling a die: X={1,2,3,4,5,6}\mathcal{X} = \{1, 2, 3, 4, 5, 6\}X={1,2,3,4,5,6} , ∣X∣=6|\mathcal{X}| = 6∣X∣=6 ; tossing a coin: Y={heads,tails}\mathcal{Y} = \{\texttt{heads}, \texttt{tails}\}Y={heads,tails} , ∣Y∣=2|\mathcal{Y}| = 2∣Y∣=2 .
[Probability distributions] The set of all possible outcomes of a random variable is called the sample space.
Example: {1,2,3,4,5,6}\{1, 2, 3, 4, 5, 6\}{1,2,3,4,5,6} for the roll of a six-sided die.
[Probability distributions] When is a random variable discrete?
Its set of possible outcomes is finite. Example: the roll of a six-sided die, with 6 outcomes.
[Probability distributions] L∈NL \in \mathbb{N}L∈N is the number of years a hard disk works before it fails. How do you write the event "the disk works correctly for at least 8 years"?
L≥8\boldsymbol{L \ge 8}L≥8 A random variable lets you state such scenarios as conditions on its value, and reason about their probabilities.
[Probability distributions] State the definition of the probability distribution pXp_XpX of a discrete random variable X∈XX \in \mathcal{X}X∈X as a vector.
pX∈R∣X∣\boldsymbol{p_X \in \mathbb{R}^{|\mathcal{X}|}}pX∈R∣X∣ with pX(x)≥0\boldsymbol{p_X(x) \ge 0}pX(x)≥0 for all x∈X\boldsymbol{x \in \mathcal{X}}x∈X and ∑x∈XpX(x)=1\boldsymbol{\sum_{x \in \mathcal{X}} p_X(x) = 1}∑x∈XpX(x)=1 An ordinary vector with nonnegative entries that sum to one.Example: a die has pX∈R6p_X \in \mathbb{R}^6pX∈R6 .
[Probability distributions] XXX is a discrete random variable with distribution pXp_XpX , and xxx is an outcome. What three notations does the book use for the same number?
The xxx -th element of pXp_XpX ≡ pX(x) ≡ Pr({X=x})\;\equiv\; p_X(x) \;\equiv\; \Pr(\{X = x\})≡pX(x)≡Pr({X=x}) Pr({X=x})\Pr(\{X = x\})Pr({X=x}) is the most precise: the probability of the event that a random draw from XXX gives the outcome xxx . When XXX is clear from the context, the book writes pxp_xpx .Example: for a fair die, pX(3)=Pr({X=3})=16p_X(3) = \Pr(\{X = 3\}) = \frac{1}{6}pX(3)=Pr({X=3})=61 .
[Probability distributions] Strictly speaking, what kind of object is the distribution pYp_YpY of a coin toss YYY , and how does the book treat it?
A function pY:{heads,tails}→[0,1]p_Y : \{\texttt{heads}, \texttt{tails}\} \to [0, 1]pY:{heads,tails}→[0,1] , treated as the vector (pY(heads),pY(tails))T(p_Y(\texttt{heads}), p_Y(\texttt{tails}))^{\mathsf{T}}(pY(heads),pY(tails))T . The outcomes are matched with the entries of the vector in a fixed order.
[Probability distributions] In the frequentist interpretation, how is the probability mass pX(a)p_X(a)pX(a) of an outcome aaa defined?
pX(a)=limn→∞N({X=a},n)n\boldsymbol{p_X(a) = \lim_{n \to \infty} \frac{N(\{X = a\}, n)}{n}}pX(a)=limn→∞nN({X=a},n) , the relative frequency of aaa in nnn repetitions N({X=a},n)N(\{X = a\}, n)N({X=a},n) is the number of times the outcome aaa occurs in nnn repetitions. The limit is a thought experiment: nobody repeats an experiment infinitely often.Example: pX(a)=0.3p_X(a) = 0.3pX(a)=0.3 means about 300 of 1000 draws give the outcome aaa .
[Probability distributions] In the Bayesian interpretation, what does a probability distribution pXp_XpX represent?
A state of knowledge (belief) about the phenomenon that XXX describes, updated as new facts are learned. Named after Thomas Bayes, an 18th-century statistician.
[Probability distributions] A coin of unknown bias is tossed a few times and gives many more heads\texttt{heads}heads than tails\texttt{tails}tails . How does Bayesian reasoning model the coin?
Start from a prior belief (the coin is fair), then update the distribution with the observed tosses using Bayes' rule. With no information about a bias, (12,12)T(\frac{1}{2}, \frac{1}{2})^{\mathsf{T}}(21,21)T is the natural prior.
[Probability distributions] In Bayesian reasoning, the initial belief before any observations is called the prior, and the technique for updating it with new observations is called Bayes' rule.
[Probability distributions] What is each of the frequentist and the Bayesian approaches to probability well suited for?
Frequentist: conclusions from empirical observations. Bayesian: combining observations with priors that encode expert knowledge. Frequentist methods suit data analysis, reports and hard numbers. The book names machine learning applications like voice recognition as a use of the Bayesian approach.
[Probability distributions] What is the conditional probability distribution pX∣Y(x∣y)p_{X|Y}(x|y)pX∣Y(x∣y) ?
pX∣Y(x∣y)=Pr({X=x} given {Y=y})\boldsymbol{p_{X|Y}(x|y) = \Pr(\{X = x\} \text{ given } \{Y = y\})}pX∣Y(x∣y)=Pr({X=x} given {Y=y}) The vertical bar is read "given". It separates the unknown random variable XXX from the random variable YYY whose value is known.Example: XXX a die roll, YYY which die is used: pX∣Y(6∣b)=0p_{X|Y}(6|b) = 0pX∣Y(6∣b)=0 for a die bbb that never shows 6.
[Probability distributions] Which conditions does a conditional probability distribution pX∣Yp_{X|Y}pX∣Y satisfy?
pX∣Y(x∣y)≥0\boldsymbol{p_{X|Y}(x|y) \ge 0}pX∣Y(x∣y)≥0 and ∑x∈XpX∣Y(x∣y)=1\boldsymbol{\sum_{x \in \mathcal{X}} p_{X|Y}(x|y) = 1}∑x∈XpX∣Y(x∣y)=1 for every y∈Y\boldsymbol{y \in \mathcal{Y}}y∈Y For each fixed yyy , pX∣Y(⋅∣y)p_{X|Y}(\cdot|y)pX∣Y(⋅∣y) is a probability distribution of XXX .
[Probability distributions] How is a conditional probability distribution pX∣Yp_{X|Y}pX∣Y represented as a matrix?
As an ∣X∣×∣Y∣|\mathcal{X}| \times |\mathcal{Y}|∣X∣×∣Y∣ matrix whose column yyy is the distribution of XXX given Y=yY = yY=y . So every column sums to one.Example: 5 possible outcomes, conditioned on a variable with 10 possible states: a 5×105 \times 105×10 matrix.
[Probability distributions] A fair die has distribution (16,…,16)T(\frac{1}{6}, \dots, \frac{1}{6})^{\mathsf{T}}(61,…,61)T , a biased die has (14,14,14,14,0,0)T(\frac{1}{4}, \frac{1}{4}, \frac{1}{4}, \frac{1}{4}, 0, 0)^{\mathsf{T}}(41,41,41,41,0,0)T . Y∈{f,b}Y \in \{f, b\}Y∈{f,b} says which die is rolled, and XXX is the result. What is the matrix pX∣Yp_{X|Y}pX∣Y ?
pX∣Y=[1614161416141614160160]\boldsymbol{p_{X|Y} = \begin{bmatrix} \frac{1}{6} & \frac{1}{4} \\ \frac{1}{6} & \frac{1}{4} \\ \frac{1}{6} & \frac{1}{4} \\ \frac{1}{6} & \frac{1}{4} \\ \frac{1}{6} & 0 \\ \frac{1}{6} & 0 \end{bmatrix}}pX∣Y=⎣⎡6161616161614141414100⎦⎤ Column 1 is the fair die ( Y=fY = fY=f ), column 2 the biased die ( Y=bY = bY=b ).
[Probability distributions] pX∣Yp_{X|Y}pX∣Y is a conditional distribution and pYp_YpY the distribution of YYY . What is pX(x)p_X(x)pX(x) ?
pX(x)=∑y∈YpX∣Y(x∣y) pY(y)\boldsymbol{p_X(x) = \sum_{y \in \mathcal{Y}} p_{X|Y}(x|y) \, p_Y(y)}pX(x)=∑y∈YpX∣Y(x∣y)pY(y) Example: a die chosen by a coin: pX(x)=pX∣Y(x∣f) pY(heads)+pX∣Y(x∣b) pY(tails)p_X(x) = p_{X|Y}(x|f) \, p_Y(\texttt{heads}) + p_{X|Y}(x|b) \, p_Y(\texttt{tails})pX(x)=pX∣Y(x∣f)pY(heads)+pX∣Y(x∣b)pY(tails) .
[Probability distributions] Why can pX(x)=∑ypX∣Y(x∣y) pY(y)p_X(x) = \sum_{y} p_{X|Y}(x|y) \, p_Y(y)pX(x)=∑ypX∣Y(x∣y)pY(y) be written as the matrix-vector product pX=pX∣Y pYp_X = p_{X|Y} \, p_YpX=pX∣YpY ?
pXp_XpX is a linear combination of the columns of pX∣Yp_{X|Y}pX∣Y with the coefficients pY(y)p_Y(y)pY(y) , and that is what a matrix-vector product computes. Column yyy of pX∣Yp_{X|Y}pX∣Y is the distribution of XXX given Y=yY = yY=y .
[Probability distributions] Fair die: (16,…,16)T(\frac{1}{6}, \dots, \frac{1}{6})^{\mathsf{T}}(61,…,61)T . Biased die: (14,14,14,14,0,0)T(\frac{1}{4}, \frac{1}{4}, \frac{1}{4}, \frac{1}{4}, 0, 0)^{\mathsf{T}}(41,41,41,41,0,0)T .A coin with pY=(34,14)Tp_Y = (\frac{3}{4}, \frac{1}{4})^{\mathsf{T}}pY=(43,41)T is tossed: on heads\texttt{heads}heads the fair die is rolled, on tails\texttt{tails}tails the biased die. What is the distribution pXp_XpX of the roll?
pX=(316,316,316,316,18,18)T\boldsymbol{p_X = (\frac{3}{16}, \frac{3}{16}, \frac{3}{16}, \frac{3}{16}, \frac{1}{8}, \frac{1}{8})^{\mathsf{T}}}pX=(163,163,163,163,81,81)T pX=34(16,…,16)T+14(14,14,14,14,0,0)Tp_X = \frac{3}{4} (\frac{1}{6}, \dots, \frac{1}{6})^{\mathsf{T}} + \frac{1}{4} (\frac{1}{4}, \frac{1}{4}, \frac{1}{4}, \frac{1}{4}, 0, 0)^{\mathsf{T}}pX=43(61,…,61)T+41(41,41,41,41,0,0)T , e.g. 34⋅16+14⋅14=18+116=316\frac{3}{4} \cdot \frac{1}{6} + \frac{1}{4} \cdot \frac{1}{4}…
[Probability distributions] Give a real-world system that the book models as a conditional probability distribution.
A noisy communication channel: the distribution of the channel outputs given each possible channel input. Many machine learning algorithms characterize, estimate and use conditional probability distributions, collectively called the model.
[Markov chains] What is a random process?
A model of a system that undergoes transitions between states over time, with the state at time ttt described by a random variable XtX_tXt . In general, Xt+1X_{t+1}Xt+1 depends on all previous states, through pXt+1∣XtXt−1⋯X0(xt+1∣xtxt−1⋯x0)p_{X_{t+1}|X_t X_{t-1} \cdots X_0}(x_{t+1}|x_t x_{t-1} \cdots x_0)pXt+1∣XtXt−1⋯X0(xt+1∣xtxt−1⋯x0) .
[Markov chains] What is a Markov chain (Markov process)?
A random process whose next state depends only on the current state: pXt+1∣XtXt−1⋯X0(xt+1∣xtxt−1⋯x0)=pXt+1∣Xt(xt+1∣xt)p_{X_{t+1}|X_t X_{t-1} \cdots X_0}(x_{t+1}|x_t x_{t-1} \cdots x_0) = p_{X_{t+1}|X_t}(x_{t+1}|x_t)pXt+1∣XtXt−1⋯X0(xt+1∣xtxt−1⋯x0)=pXt+1∣Xt(xt+1∣xt) It is memoryless: the states Xt−1,…,X0X_{t-1}, \dots, X_0Xt−1,…,X0 before the current one have no influence. It is the simplest type of random process.
[Markov chains] Which object fully describes a Markov chain?
The conditional distribution pXt+1∣Xt(xt+1∣xt)p_{X_{t+1}|X_t}(x_{t+1}|x_t)pXt+1∣Xt(xt+1∣xt) , written as the transition matrix MMM . Column xtx_txt of MMM is the distribution of the next state given the current state xtx_txt , so MijM_{ij}Mij is the probability of moving from state jjj to state iii and each column sums to 1.
[Markov chains] Alice ( AAA ), Bob ( BBB ) and Charlie ( CCC ) pass a ball. Alice keeps it with probability 0.2 and passes to Bob or to Charlie with probability 0.4 each. Bob keeps it with probability 0.8 and passes to Alice or to Charlie with probability 0.1 each. Charlie keeps it or passes to Alice or to Bob with probability 13\frac{1}{3}31 each.Model the ball possession as a Markov chain with states A,B,CA, B, CA,B,C . What is its transition matrix MMM ?
M=[0.20.10.3‾0.40.80.3‾0.40.10.3‾]\boldsymbol{M = \begin{bmatrix} 0.2 & 0.1 & 0.\overline{3} \\ 0.4 & 0.8 & 0.\overline{3} \\ 0.4 & 0.1 & 0.\overline{3} \end{bmatrix}}M=⎣⎡0.20.40.40.10.80.10.30.30.3⎦⎤ Columns and rows in the order A,B,CA, B, CA,B,C . Column jjj is the distribution of who has the ball next, given that jjj has it now. The transition probabilities as a graph.
[Markov chains] A Markov chain has transition matrix MMM and the state at time ttt has distribution pXtp_{X_t}pXt . What are pXt+1p_{X_{t+1}}pXt+1 and pXtp_{X_t}pXt in terms of pX0p_{X_0}pX0 ?
pXt+1=MpXt\boldsymbol{p_{X_{t+1}} = M p_{X_t}}pXt+1=MpXt and pXt=MtpX0\boldsymbol{p_{X_t} = M^t p_{X_0}}pXt=MtpX0 Example: pX3=MpX2=MMpX1=MMMpX0=M3pX0p_{X_3} = M p_{X_2} = M M p_{X_1} = M M M p_{X_0} = M^3 p_{X_0}pX3=MpX2=MMpX1=MMMpX0=M3pX0 .
[Markov chains] Alice ( AAA ), Bob ( BBB ) and Charlie ( CCC ) pass a ball. Alice keeps it with probability 0.2 and passes to Bob or to Charlie with probability 0.4 each. Bob keeps it with probability 0.8 and passes to Alice or to Charlie with probability 0.1 each. Charlie keeps it or passes to Alice or to Bob with probability 13\frac{1}{3}31 each. M=[0.20.10.3‾0.40.80.3‾0.40.10.3‾]M = \begin{bmatrix} 0.2 & 0.1 & 0.\overline{3} \\ 0.4 & 0.8 & 0.\overline{3} \\ 0.4 & 0.1 & 0.\overline{3} \end{b…
pX1=(0.2,0.4,0.4)T\boldsymbol{p_{X_1} = (0.2, 0.4, 0.4)^{\mathsf{T}}}pX1=(0.2,0.4,0.4)T M(1,0,0)TM (1, 0, 0)^{\mathsf{T}}M(1,0,0)T is the first column of MMM : Alice's passing behaviour.
[Markov chains] Alice ( AAA ), Bob ( BBB ) and Charlie ( CCC ) pass a ball. Alice keeps it with probability 0.2 and passes to Bob or to Charlie with probability 0.4 each. Bob keeps it with probability 0.8 and passes to Alice or to Charlie with probability 0.1 each. Charlie keeps it or passes to Alice or to Bob with probability 13\frac{1}{3}31 each. M=[0.20.10.3‾0.40.80.3‾0.40.10.3‾]M = \begin{bmatrix} 0.2 & 0.1 & 0.\overline{3} \\ 0.4 & 0.8 & 0.\overline{3} \\ 0.4 & 0.1 & 0.\overline{3} \end{b…
pX2=(0.213‾, 0.53‾, 0.253‾)T\boldsymbol{p_{X_2} = (0.21\overline{3}, \, 0.5\overline{3}, \, 0.25\overline{3})^{\mathsf{T}}}pX2=(0.213,0.53,0.253)T M(0.2,0.4,0.4)TM (0.2, 0.4, 0.4)^{\mathsf{T}}M(0.2,0.4,0.4)T : e.g. Bob: 0.4⋅0.2+0.8⋅0.4+0.3‾⋅0.4=0.08+0.32+0.13‾=0.53‾0.4 \cdot 0.2 + 0.8 \cdot 0.4 + 0.\overline{3} \cdot 0.4 = 0.08 + 0.32 + 0.1\overline{3} = 0.5\overline{3}0.4⋅0.2+0.8⋅0.4+0.3⋅0.4=0.08+0.32+0.13=0.53 .Then pX3≈(0.180,0.596,0.223)Tp_{X_3} \approx (0.180, 0.596, 0.223)^{\mathsf{T}}p…
[Markov chains] Alice ( AAA ), Bob ( BBB ) and Charlie ( CCC ) pass a ball. Alice keeps it with probability 0.2 and passes to Bob or to Charlie with probability 0.4 each. Bob keeps it with probability 0.8 and passes to Alice or to Charlie with probability 0.1 each. Charlie keeps it or passes to Alice or to Bob with probability 13\frac{1}{3}31 each.Alice has the ball at t=0t = 0t=0 . The probability that Alice has it at t=2t = 2t=2 is 0.213‾0.21\overline{3}0.213 . Which paths make up this numbe…
Three paths A→A→AA \to A \to AA→A→A , A→B→AA \to B \to AA→B→A , A→C→AA \to C \to AA→C→A ; the probability is the sum over the paths of the products of their transition probabilities. 0.2⋅0.2+0.4⋅0.1+0.4⋅0.3‾=0.04+0.04+0.13‾=0.213‾0.2 \cdot 0.2 + 0.4 \cdot 0.1 + 0.4 \cdot 0.\overline{3} = 0.04 + 0.04 + 0.1\overline{3} = 0.21\overline{3}0.2⋅0.2+0.4⋅0.1+0.4⋅0.3=0.04+0.04+0.13=0.213 Multiplying the state vector by the transition matrix computes this sum over all paths at once.
[Markov chains] What is the stationary distribution pX∞p_{X_\infty}pX∞ of a Markov chain with transition matrix MMM ?
The distribution that stays unchanged when multiplied by MMM : MpX∞=pX∞\boldsymbol{M p_{X_\infty} = p_{X_\infty}}MpX∞=pX∞ If the chain runs long enough, the distribution of its state converges to pX∞p_{X_\infty}pX∞ .
[Markov chains] The stationary distribution pX∞p_{X_\infty}pX∞ of a Markov chain with transition matrix MMM is an eigenvector of MMM with eigenvalue one.
MpX∞=1⋅pX∞M p_{X_\infty} = 1 \cdot p_{X_\infty}MpX∞=1⋅pX∞ .
[Markov chains] Under suitable technical conditions on MMM , how does the stationary distribution that a Markov chain reaches depend on the starting distribution pX0p_{X_0}pX0 ?
It does not: the chain converges to the same unique stationary distribution from every starting point. Example: for the 3×33 \times 33×3 matrix with columns (0.2,0.4,0.4)T(0.2, 0.4, 0.4)^{\mathsf{T}}(0.2,0.4,0.4)T , (0.1,0.8,0.1)T(0.1, 0.8, 0.1)^{\mathsf{T}}(0.1,0.8,0.1)T , (13,13,13)T(\frac{1}{3}, \frac{1}{3}, \frac{1}{3})^{\mathsf{T}}(31,31,31)T , the starting distributions (1,0,0)T(1, 0, 0)^{\mathsf{T}}(1,0,0)T , (0,1,0)T(0, 1, 0)^{\mathsf{T}}(0,1,0)T and (0,0,1)T(0, 0, 1)^{\mathsf{T}}(0,…
[Markov chains] What are two ways to find the stationary distribution pX∞p_{X_\infty}pX∞ of a Markov chain with transition matrix MMM ?
Iterate the chain Multiply by MMM repeatedly until the distribution stops changing: pX∞=M∞pX0p_{X_\infty} = M^\infty p_{X_0}pX∞=M∞pX0 . Example: for MMM with columns (0.2,0.4,0.4)T(0.2, 0.4, 0.4)^{\mathsf{T}}(0.2,0.4,0.4)T , (0.1,0.8,0.1)T(0.1, 0.8, 0.1)^{\mathsf{T}}(0.1,0.8,0.1)T , (13,13,13)T(\frac{1}{3}, \frac{1}{3}, \frac{1}{3})^{\mathsf{T}}(31,31,31)T , M20(1,0,0)TM^{20} (1, 0, 0)^{\mathsf{T}}M20(1,0,0)T already agrees with pX∞p_{X_\infty}pX∞ to 7 decimal places. Solve a null spac…
[Markov chains] Alice ( AAA ), Bob ( BBB ) and Charlie ( CCC ) pass a ball. Alice keeps it with probability 0.2 and passes to Bob or to Charlie with probability 0.4 each. Bob keeps it with probability 0.8 and passes to Alice or to Charlie with probability 0.1 each. Charlie keeps it or passes to Alice or to Bob with probability 13\frac{1}{3}31 each. M=[0.20.10.3‾0.40.80.3‾0.40.10.3‾]M = \begin{bmatrix} 0.2 & 0.1 & 0.\overline{3} \\ 0.4 & 0.8 & 0.\overline{3} \\ 0.4 & 0.1 & 0.\overline{3} \end{b…
pX∞=(531,2031,631)T≈(0.161,0.645,0.194)T\boldsymbol{p_{X_\infty} = (\frac{5}{31}, \frac{20}{31}, \frac{6}{31})^{\mathsf{T}} \approx (0.161, 0.645, 0.194)^{\mathsf{T}}}pX∞=(315,3120,316)T≈(0.161,0.645,0.194)T v⃗=(5,20,6)T\vec{v} = (5, 20, 6)^{\mathsf{T}}v=(5,20,6)T solves (M−I)v⃗=0⃗(M - I)\vec{v} = \vec{0}(M−I)v=0 : first row −0.8⋅5+0.1⋅20+13⋅6=−4+2+2=0-0.8 \cdot 5 + 0.1 \cdot 20 + \frac{1}{3} \cdot 6 = -4 + 2 + 2 = 0−0.8⋅5+0.1⋅20+31⋅6=−4+2+2=0 . Dividing by 5+20+6=315 + 20 + 6 = 315+20+6=…
[Google's PageRank algorithm] What does PageRank take a link from page A to page B to mean?
A recommendation of page B by the author of page A. In web-speak, A "sends eyeballs" to B, presumably because B has something interesting to see.
[Google's PageRank algorithm] What is self-referential in the definition "the rank of a document is calculated from the ranks of the documents citing it"?
To know a document's rank you need the ranks of the documents linking to it, which in turn need the ranks of the documents linking to those, and so on. The stationary distribution of a Markov chain resolves this: it is a vector ppp with Mp=pMp = pMp=p , defined in terms of itself.
[Google's PageRank algorithm] What two strategies does Randy, the random surfer, follow in the PageRank model, and how often?
Strategy 1, 90% of the time Pick one of the outbound links of the current page at random and follow it. Example: on a page with links to pages 2 and 5, go to each with probability 12\frac{1}{2}21 . Strategy 2, 10% of the time Jump to a page of the Web chosen at random. Example: on a Web of 8 pages, each page with probability 18\frac{1}{8}81 . On a page with no outbound links, Randy always uses Strategy 2.
[Google's PageRank algorithm] The random surfer Randy, on a Web of nnn pages, with probability 0.9 clicks a random outbound link of the current page, and with probability 0.1 jumps to a random page (also always when the page has no outbound links).In the PageRank Markov chain, what is a state, and what size is the transition matrix?
The state is the page Randy is viewing; the matrix is n×nn \times nn×n , nnn the number of pages.
[Google's PageRank algorithm] The random surfer Randy, on a Web of nnn pages, with probability 0.9 clicks a random outbound link of the current page, and with probability 0.1 jumps to a random page (also always when the page has no outbound links).Page jjj has NjN_jNj outbound links. What is the entry (M1)ij(M_1)_{ij}(M1)ij of the transition matrix M1M_1M1 of Strategy 1 (follow a random link)?
(M1)ij={1Njif page j links to page i1nif page j has no outbound links0otherwise\boldsymbol{(M_1)_{ij} = \begin{cases} \frac{1}{N_j} & \text{if page } j \text{ links to page } i \\ \frac{1}{n} & \text{if page } j \text{ has no outbound links} \\ 0 & \text{otherwise} \end{cases}}(M1)ij=⎩⎨⎧Nj1n10if page j links to page iif page j has no outbound linksotherwise Column jjj is the distribution of Randy's next page when he is on page jjj .
[Google's PageRank algorithm] How do you get the Strategy 1 matrix M1M_1M1 of PageRank from the adjacency matrix AAA of the link graph ( Aij=1A_{ij} = 1Aij=1 if page iii links to page jjj )?
Transpose AAA , then divide each column by its sum so the columns become probability distributions. A column of zeros (a page with no outbound links) is replaced by (1n,…,1n)T(\frac{1}{n}, \dots, \frac{1}{n})^{\mathsf{T}}(n1,…,n1)T .
[Google's PageRank algorithm] The random surfer Randy, on a Web of nnn pages, with probability 0.9 clicks a random outbound link of the current page, and with probability 0.1 jumps to a random page (also always when the page has no outbound links).What is the transition matrix M2M_2M2 of Strategy 2 (jump to a random page)?
M2=1nJ\boldsymbol{M_2 = \frac{1}{n} \mathbb{J}}M2=n1J , with J\mathbb{J}J the n×nn \times nn×n matrix of all ones Wherever Randy is, every page is next with probability 1n\frac{1}{n}n1 , so every column is (1n,…,1n)T(\frac{1}{n}, \dots, \frac{1}{n})^{\mathsf{T}}(n1,…,n1)T .
[Google's PageRank algorithm] M1M_1M1 is the PageRank Strategy 1 matrix (follow a random link), M2=1nJM_2 = \frac{1}{n}\mathbb{J}M2=n1J the Strategy 2 matrix (random jump), and α\alphaα the probability of a random jump. What is the PageRank Markov chain MMM ?
M=(1−α)M1+αM2=(1−α)M1+αnJ\boldsymbol{M = (1 - \alpha) M_1 + \alpha M_2 = (1 - \alpha) M_1 + \frac{\alpha}{n} \mathbb{J}}M=(1−α)M1+αM2=(1−α)M1+nαJ α=0.1\alpha = 0.1α=0.1 gives the 90-10 mix of the two strategies; in general α\alphaα is a parameter tuned for the application.
[Google's PageRank algorithm] What is the PageRank vector, and what is the PageRank of a single page?
The stationary distribution pX∞p_{X_\infty}pX∞ of the PageRank chain MMM ; a page's PageRank is the probability that Randy is on it in the long run. It measures how well-connected, or important, each page is.
[Google's PageRank algorithm] For finding the PageRank vector, when is solving (M−I)v⃗=0⃗(M - I)\vec{v} = \vec{0}(M−I)v=0 the better method, and when is iterating p↦Mpp \mapsto Mpp↦Mp ?
The null space gives the answer directly; iterating the chain scales better to large graphs. III is the identity matrix. Both give pX∞p_{X_\infty}pX∞ , the eigenvector of MMM for λ=1\lambda = 1λ=1 , scaled so its entries sum to 1.
[Google's PageRank algorithm] Why does PageRank mix the Strategy 1 matrix M1M_1M1 with a bit of J\mathbb{J}J instead of using M1M_1M1 alone?
With M1M_1M1 alone the distribution of Randy's state does not mix well; adding J\mathbb{J}J guarantees convergence to the stationary distribution. Every entry of M=(1−α)M1+αnJM = (1 - \alpha) M_1 + \frac{\alpha}{n}\mathbb{J}M=(1−α)M1+nαJ is positive, so every page can be reached from every page in one step.
[Google's PageRank algorithm] How do you read off column jjj of a Markov chain transition matrix MMM by "probing" it?
Multiply MMM by the state e⃗j\vec{e}_jej with all probability on state jjj : Me⃗jM \vec{e}_jMej is column jjj . Example: in the micro-Web, Randy on page 1 follows its links to pages 2 and 5, so column 1 of the Strategy 1 matrix M1M_1M1 of PageRank (follow a random link) is (0,12,0,0,12,0,0,0)T(0, \frac{1}{2}, 0, 0, \frac{1}{2}, 0, 0, 0)^{\mathsf{T}}(0,21,0,0,21,0,0,0)T .
[Google's PageRank algorithm] In this micro-Web of 8 pages, what are columns 4, 7 and 8 of the Strategy 1 matrix M1M_1M1 (follow a random outbound link; on a page with no outbound links, jump to a random page)?
Column 4: 1 in row 5. Column 7: 13\frac{1}{3}31 in rows 5, 6, 8. Column 8: 18\frac{1}{8}81 in every row. All other entries of columns 4 and 7 are 0. Page 4 links only to page 5, page 7 links to pages 5, 6 and 8, and page 8 has no outbound links.
[Google's PageRank algorithm] The micro-Web: pages 1,…,81, \dots, 81,…,8 and the links 1→21 \to 21→2 , 1→51 \to 51→5 , 2→32 \to 32→3 , 2→52 \to 52→5 , 3→13 \to 13→1 , 3→53 \to 53→5 , 4→54 \to 54→5 , 5→65 \to 65→6 , 5→75 \to 75→7 , 6→36 \to 36→3 , 6→76 \to 76→7 , 7→57 \to 57→5 , 7→67 \to 67→6 , 7→87 \to 87→8 . M1M_1M1 is the Strategy 1 matrix (follow a random outbound link; a page with no outbound links gets the column (18,…,18)T(\frac{1}{8}, \dots, \frac{1}{8})^{\mathsf{T}}(81,…,81)T ) and J…
180, 3780, 7380, 516, 18\boldsymbol{\frac{1}{80}, \; \frac{37}{80}, \; \frac{73}{80}, \; \frac{5}{16}, \; \frac{1}{8}}801,8037,8073,165,81 A 0 of M1M_1M1 gives 180\frac{1}{80}801 ; 12\frac{1}{2}21 gives 920+180=3780\frac{9}{20} + \frac{1}{80} = \frac{37}{80}209+801=8037 ; 1 (page 4 to page 5) gives 7380\frac{73}{80}8073 ; 13\frac{1}{3}31 (page 7) gives 310+180=2580=516\frac{3}{10} + \frac{1}{80} = \frac{25}{80} = \frac{5}{16}103+801=8025=165 ; 18\frac{1}{8}81 (page 8) gives 98…
[Google's PageRank algorithm] Which pages of this micro-Web have the highest and the lowest PageRank (with α=0.1\alpha = 0.1α=0.1 ), and why?
Highest: page 5 (about 0.227). Lowest: page 4 (about 0.022). Page 5 has the most links pointing to it; page 4 has no links pointing to it, so Randy reaches it only by random jumps.Full order: 5, 7, 6, 3, 8, 1, 2, 4. Pages 7 and 6 come next because page 5 links to them.
[Google's PageRank algorithm] In the micro-Web example, pages 5, 7 and 6 have PageRanks of about 0.227, 0.208 and 0.186. What does their sum mean?
Randy views one of these three pages about 62% of the time. 0.227+0.208+0.186≈0.620.227 + 0.208 + 0.186 \approx 0.620.227+0.208+0.186≈0.62
[Google's PageRank algorithm] The real Web has n≈109n \approx 10^9n≈109 pages. How is the PageRank vector computed at that scale?
By the power iteration method, which finds the eigenvector for the largest eigenvalue, without building the n×nn \times nn×n matrix. The computation is split over a cluster of computers. The n×nn \times nn×n matrix would be far too large to store. The book credits the computational part to Larry Page and Sergey Brin, beyond the linear algebra insight.