Introduction to Probability PDF Download – Grinstead & Snell (2nd Edition) BS Math/Stats

BS Mathematics, BS Statistics, and BSCS students can download the complete textbook “Introduction to Probability” by Charles M. Grinstead (Swarthmore College) and J. Laurie Snell (Dartmouth College), free from its official source, the Dartmouth Mathematics Department. Originally published by the American Mathematical Society, this 2nd edition is freely redistributable under the GNU Free Documentation License, and it is the standard, widely-cited free textbook for a university Probability Theory course — covering everything from basic discrete probability through Markov chains and random walks in twelve chapters.

For BS Math and BS Statistics students, this book is built for a full two-term Probability Theory sequence, with the mathematics developed rigorously but explained through concrete, worked examples rather than dense proofs. BSCS students taking a shorter Probability & Statistics module can use it just as effectively by reading the discrete-only path the book’s own preface lays out — skipping the continuous-probability sections without losing anything the exam actually needs. Either way, every chapter ends with exercises that mirror the kind of questions that show up in a university probability exam, from Bayes’ theorem calculations to expected-value and variance problems.

Book Overview

Chapter List

Chapter 1: Discrete Probability Distributions

Difficulty: Easy · Key topics: sample spaces, random variables, distribution functions, simulation, the addition rule, inclusion-exclusion, odds, the Chevalier de Méré’s dice bets

The chapter opens with the correspondence between Pascal and Fermat that started probability theory — specifically the Chevalier de Méré’s two dice bets, which the text solves exactly (1 − (5/6)⁴ ≈ .518 for one bet, showing why the “equivalent” 24-roll double-six bet is actually a loser at ≈ .491). From there it defines a random variable, a sample space, and a distribution function m formally, states the five basic properties of probability as a numbered theorem, and proves the addition rule and inclusion-exclusion for two events. Simulation is treated as a first-class tool throughout, not an afterthought: worked programs generate random numbers and confirm the theoretical answers for coin tosses, the “Peter and Paul” heads-or-tails game, and a four-horse race with unequal win probabilities.

Key Points:

• A distribution function m must satisfy m(ω) ≥ 0 for every outcome and Σm(ω) = 1 over the whole sample space.
• For a uniform sample space of size n, every outcome has probability m(ω) = 1/n.
• Odds of r:s correspond to a probability p = r/(r+s), and conversely p converts to odds p : (1−p).
• Inclusion-exclusion for two events: P(A ∪ B) = P(A) + P(B) − P(A ∩ B).
• The probability of the first head appearing on toss n of a fair coin is m(n) = 1/2n, an infinite but perfectly valid discrete distribution.
• Simulation with enough trials converges to the theoretical probability — but de Méré’s own dice records show how badly a small sample can mislead you.

Memory Tip: Re-derive de Méré’s two bets by hand before moving on. The whole chapter’s point is that “four rolls for one six” and “twenty-four rolls for double six” look equivalent by naive scaling but are not (.518 vs .491) — once that trap is visible, inclusion-exclusion and the addition rule stop feeling abstract.

Common Mistake: Assuming that because two events “sound similar” they must have the same probability, the way 18th-century gamblers assumed de Méré’s two bets were equivalent. Always compute both sides, don’t estimate by symmetry.

Important Questions:

• What two conditions must a distribution function m satisfy? m(ω) ≥ 0 for every outcome ω, and the sum of m(ω) over the entire sample space equals 1.
• Why does the Chevalier de Méré lose money on the 24-roll double-six bet? Because 1 − (35/36)24 ≈ .491, just under even odds, while the single-die bet he compared it to is 1 − (5/6)4 ≈ .518 — the two are not actually equivalent despite the naive 6×4 = 24 scaling.

Chapter 2: Continuous Probability Densities

Difficulty: Medium · Key topics: density functions, cumulative distribution functions, the uniform density, the exponential density, the memoryless property, transformations of densities

The chapter moves from counting outcomes to measuring them, defining a density function f so that P(a ≤ X ≤ b) = ∫ab f(x)dx and the cumulative distribution function F(x) = P(X ≤ x), with F′(x) = f(x) wherever f is continuous. The uniform density on [a,b] and the exponential density f(t) = λe−λt are worked out in full, including a hard-drive lifetime example that demonstrates the exponential’s defining property: the memoryless property, meaning a component that has already survived 15 months has exactly the same remaining-life distribution as a brand-new one. The chapter also solves the sum of two uniform [0,1] variables by hand, producing a triangular density, previewing the convolution idea developed fully in Chapter 7.

Key Points:

• A density function need not itself be a probability — only ∫f(x)dx over a range gives one; f(x) can exceed 1.
• The exponential density is the only continuous density with the memoryless property: P(T > r+s | T > r) = P(T > s).
• For the uniform density on [a,b], f(x) = 1/(b−a) inside the interval and 0 outside it.
• The sum of two independent uniform [0,1] variables is triangular: f(z) = z on [0,1] and f(z) = 2−z on [1,2] — not uniform.
• Differentiating the cumulative distribution function recovers the density: F′(x) = f(x).

Memory Tip: Whenever a problem describes “time until the next random event” with a constant rate, reach for the exponential density immediately — the memoryless property is the single fact that identifies it, and it is the continuous twin of the geometric distribution from Chapter 5.

Common Mistake: Treating f(x) as if it were a probability and expecting it to stay ≤ 1. A density can take any non-negative value; only its integral over an interval is bounded by 1.

Important Questions:

• What does the memoryless property of the exponential density mean in practice? That the probability a component survives an additional s time units, given it has already survived r units, does not depend on r — the component does not “age” in a probabilistic sense.
• What is the density of the sum of two independent Uniform[0,1] random variables? A triangular density: f(z) = z for 0 ≤ z ≤ 1, and f(z) = 2 − z for 1 ≤ z ≤ 2.

Chapter 3: Combinatorics

Difficulty: Medium · Key topics: permutations, factorials, the birthday problem, combinations, the binomial coefficient, Pascal’s triangle, the binomial theorem, the hat-check (matching) problem, card shuffling

Combinatorics supplies the counting tools the rest of the book leans on. Permutations and the factorial n! = n·(n−1)·•••·1 are introduced through concrete counting problems (menus, initials), building to the famous birthday problem: with r people in a room, the probability all birthdays differ is (365)r/365r, and the surprising crossover point where a shared birthday becomes more likely than not is only 23 people. Combinations follow, with the binomial coefficient C(n,j) = n!/(j!(n−j)!), its Pascal’s-triangle recurrence, and the binomial theorem. Worked poker-hand and committee examples turn the formula into a calculating tool, and the hat-check (matching) problem, solved by inclusion-exclusion, shows the probability nobody gets their own hat back converging to 1/e ≈ .368 as the number of hats grows — a genuinely surprising, size-independent limit.

Key Points:

• The number of ways to order n distinct objects is n!, with 0! defined as 1 by convention.
• With 23 people in a room, the probability at least two share a birthday already exceeds 50% — far fewer people than most students guess.
• The binomial coefficient C(n,j) = n!/(j!(n−j)!) counts the subsets of size j from a set of size n, order not mattering.
• Pascal’s triangle recurrence: C(n,j) = C(n−1,j) + C(n−1,j−1).
• The binomial theorem: (a+b)n = Σj=0n C(n,j)ajbn−j.
• As n grows, the probability that a random permutation of n hats fixes none of them converges to e−1 ≈ .368, regardless of how large n is.

Memory Tip: “Order matters → permutation, order doesn’t → combination” is the whole decision rule. Before computing anything, ask whether swapping two chosen items produces a genuinely different outcome; if yes, use n!/(n−k)!, if no, divide by k! and use C(n,k).

Common Mistake: Solving the birthday problem by computing the probability that a specific pair shares a birthday, instead of the probability that any pair among all C(r,2) pairs does. That single confusion accounts for most wrong answers to this problem.

Important Questions:

• How many people are needed before there is better than a 50% chance two share a birthday? Just 23 — far fewer than the 365 days in a year would suggest, because the comparison is across all pairs of people, not one fixed pair.
• What is the probability that, in a room of hats returned at random to n people, nobody gets their own hat back? It converges to 1/e ≈ 0.368 as n grows, computed via inclusion-exclusion on the events “person i gets their own hat”.

Chapter 4: Conditional Probability

Difficulty: Medium · Key topics: conditional probability, independence, Bayes’ formula, the Monty Hall problem, the two-children paradox, the two-envelopes paradox, joint distributions, the memoryless property (continuous case)

Conditional probability is defined as P(F|E) = P(F ∩ E)/P(E) and immediately put to work on the Monty Hall problem: a careful probability-tree argument (not intuition) shows switching doors wins with probability 2/3. Independence is defined precisely as P(E ∩ F) = P(E)P(F), distinguishing it sharply from the everyday sense of “unrelated”. Bayes’ formula for posterior probabilities, P(Hi|E) = P(Hi)P(E|Hi) / ΣkP(Hk)P(E|Hk), is applied to a medical-testing example with disease prior 0.001, test sensitivity 0.99 and specificity 0.95, where a positive result still leaves roughly a 98% chance the patient is disease-free — a result the text notes has genuinely confused medical students. Section 4.3 collects four classic conditional-probability paradoxes (two children, meeting Mr. Smith, two envelopes, and a beagle problem) to show that the answer depends critically on exactly how the evidence was obtained, not just what the evidence says.

Key Points:

• The definition of conditional probability: P(F|E) = P(F ∩ E) / P(E), requiring P(E) > 0.
• Switching doors in the Monty Hall problem wins the car with probability 2/3, not 1/2 — the host’s forced choice of which door to open carries information.
• Independence means P(E ∩ F) = P(E)P(F); it must be checked with numbers, never assumed from context.
• Bayes’ formula turns a prior probability plus new evidence into a posterior probability, and is the formal engine behind every medical-test and spam-filter style calculation.
• A rare disease with an accurate test can still yield mostly false positives among positive results, because the low prior dominates the calculation — this is the base-rate fallacy.
• In the classic “two children, at least one is a boy” problem, the answer is 1/3, not 1/2, because “BG” and “GB” are both still live outcomes.

Memory Tip: For any Bayes’ formula question, write the 2×2 (or larger) table of joint counts or joint probabilities before touching the formula. Every mistake in this chapter’s examples comes from skipping the table and trying to do the algebra from the word problem directly.

Common Mistake: Answering the “two children” style paradoxes by pure symmetry (“the other child is 50/50”) without asking how the information was actually obtained. The book shows this reasoning gives 1/3 in one framing and 1/2 in a superficially similar one (Mr. Smith walking with his son) — the acquisition method changes the answer.

Important Questions:

• In the Monty Hall problem, what is the probability of winning if the contestant always switches? 2/3 — switching doubles the win probability compared to staying, because the host’s forced reveal of a losing door concentrates the original 2/3 chance onto the remaining unopened door.
• Why can a 99%-accurate medical test still be mostly wrong when it comes back positive? Because with a low disease prior (e.g. 0.001), the large pool of healthy people generates far more false positives in absolute numbers than the small pool of sick people generates true positives — Bayes’ formula, not the test’s accuracy alone, gives the real posterior probability.

Chapter 5: Distributions and Densities

Difficulty: Medium · Key topics: the binomial, geometric, negative binomial, hypergeometric and Poisson distributions, the Benford distribution, the normal (Gaussian), exponential and Cauchy densities, the Box-Muller transform

This chapter is a working catalogue of the named distributions used throughout the rest of the book, each given its formula, its simulation recipe, and a real worked application. The Poisson distribution, P(X=k) = (λk/k!)e−λ, is derived as the large-n, small-p limit of the binomial and applied to World War II flying-bomb hits on London and to typesetting errors. The hypergeometric distribution drives a Fisher’s-exact-test style independence test on real survey data. On the continuous side, the normal density is given with its Box-Muller simulation trick, standardization Z=(X−μ)/σ, and a worked example computing P(4 ≤ X ≤ 16) for μ=10, σ=3. The Cauchy density closes the chapter as a deliberate counter-example: its sample averages never settle down, previewing why the Law of Large Numbers (Chapter 8) needs a finite-variance condition.

Key Points:

• Binomial: b(n,p,k) = C(n,k)pkqn−k; for large n it is well approximated by a normal with μ=np, σ=√(npq).
• Geometric: P(T=j) = qj−1p, the number of trials to the first success; it is the discrete twin of the exponential density and is also memoryless.
• Poisson: P(X=k) = (λk/k!)e−λ, the natural model for rare, independent events over a fixed interval.
• Hypergeometric: models sampling without replacement, unlike the binomial, and converges to the binomial as the population grows large relative to the sample.
• Normal density: f(x) = (1/(σ√2π))e−(x−μ)²/(2σ²); it has no closed-form cumulative distribution, hence the standard normal table.
• The Cauchy density, f(x) = 1/(π(1+x²)), has no finite mean or variance — averaging Cauchy samples gives no more precision than a single sample.

Memory Tip: Match the story to the distribution: counting successes in a fixed number of independent trials is binomial; waiting for the first success is geometric; counting rare events in a continuous interval is Poisson; sampling without replacement is hypergeometric. Misreading which story applies is the single biggest source of wrong answers in this chapter’s exercises.

Common Mistake: Using the binomial formula when sampling is actually without replacement from a small, finite population (a hypergeometric situation) — the two only agree when the population is large relative to the sample.

Important Questions:

• How is the Poisson distribution related to the binomial distribution? The Poisson arises as the limit of the binomial as n → ∞ and p → 0 with np = λ held fixed — it is the right model when trials are numerous but successes are rare.
• Why does the Law of Large Numbers fail for the Cauchy distribution? Because the Cauchy density has infinite variance (and technically no defined mean), so its sample averages never converge to a fixed number — the average of n Cauchy variables has exactly the same distribution as a single one.

Chapter 6: Expected Value and Variance

Difficulty: Medium · Key topics: expected value, linearity of expectation, variance, standard deviation, the computational formula for variance, independent sums, conditional expectation

Expected value is defined as E(X) = Σxm(x) for a discrete random variable and immediately shown to be linear — E(X+Y) = E(X)+E(Y) — a property that holds whether or not X and Y are independent, which the chapter stresses because it is what makes expectation so useful in practice. A worked craps example computes an expected loss of roughly −7/495 per dollar bet, and a St. Petersburg-paradox style discussion shows expectation can be infinite even for a “reasonable”-looking game. Variance is then defined as V(X)=E((X−μ)²), with the computational shortcut V(X)=E(X²)−μ², and the key independent-sum results E(Sn)=nμ, V(Sn)=nσ², so that the variance of an average of n independent trials shrinks as σ²/n — the fact that underlies every opinion-poll margin of error later in the book.

Key Points:

• Expected value: E(X) = Σx x·m(x); it is linear, E(X+Y)=E(X)+E(Y), regardless of independence.
• Expected value of a Bernoulli-trials sum: E(Sn) = np.
• E(XY) = E(X)E(Y) holds only when X and Y are independent — it is not a general property like linearity is.
• Variance’s computational formula: V(X) = E(X²) − μ², almost always faster than the direct definition.
• For independent trials, V(Sn) = nσ², so the variance of the sample average A_n is σ²/n — averages get more reliable as n grows.

Memory Tip: “Expectation is linear even when the variables aren’t independent, variance isn’t.” Keep that one asymmetry in mind and most of this chapter’s formulas become predictable instead of memorised.

Common Mistake: Adding variances, V(X+Y) = V(X)+V(Y), without first checking that X and Y are independent. Unlike expectation, this identity genuinely requires independence (or at least zero covariance) to hold.

Important Questions:

• Does E(X+Y) = E(X) + E(Y) require X and Y to be independent? No — linearity of expectation holds unconditionally, for any random variables with finite expectation, independent or not.
• What happens to the variance of an average of n independent trials as n grows? It shrinks: V(An) = σ²/n, which is the formal reason larger samples give more reliable averages.

Chapter 7: Sums of Random Variables

Difficulty: Hard · Key topics: convolution, the discrete convolution formula, continuous convolution, sums of uniform/exponential/normal/Cauchy variables, the chi-squared distribution, goodness-of-fit testing

Given the distribution of X and of Y separately, this chapter answers how to get the distribution of X+Y: convolution. In the discrete case, m3(j) = Σk m1(k)m2(j−k), worked out concretely for two dice and for a bridge hand’s point count. In the continuous case, (f*g)(z) = ∫f(z−y)g(y)dy, and the chapter derives several named results outright: two uniforms give the triangular density from Chapter 2, two exponentials give a gamma density, two independent normals combine into another normal with added variances, and — the chapter’s showpiece counter-example — two Cauchy variables average back into another Cauchy, so averaging never sharpens the estimate. The chapter closes by building the chi-squared distribution as a sum of squared normals and using it for an actual goodness-of-fit test on 60 die rolls.

Key Points:

• Discrete convolution: m3(j) = Σk m1(k)·m2(j−k), the distribution of a sum of independent variables.
• Convolving two binomials with the same p, parameters (m,p) and (n,p), gives a binomial (m+n, p).
• Sum of two independent standard normals: density (1/√4π)e−z²/4 — in general, N(μ1,σ1²) + N(μ2,σ2²) = N(μ1+μ2, σ1²+σ2²).
• Sum of two Cauchy variables is Cauchy again, and the average of two Cauchy variables has the same distribution as one Cauchy variable — averaging buys nothing.
• A chi-squared statistic V = Σ(Oi−Ei)²/Ei compared against a chi-squared distribution is the standard tool for testing whether observed frequencies match a hypothesized distribution.

Memory Tip: Convolution is just “the addition rule done at every possible split point” — for each way j could be built as k + (j−k), multiply the two probabilities and add over every k. Once that mechanical picture is fixed, both the discrete formula and the continuous integral read the same way.

Common Mistake: Assuming that summing two variables from the same distribution family always keeps you in that family. It is true for binomial, normal, Poisson and Cauchy, but false in general — the sum of two uniforms is triangular, not uniform.

Important Questions:

• What is the discrete convolution formula for the sum of two independent random variables? m3(j) = Σk m1(k)m2(j−k), summing over every way the total j could split between the two variables.
• Why is the sum of two Cauchy-distributed variables a special counter-example? Because it is Cauchy again, with the same shape as a single variable, so averaging Cauchy measurements never reduces the spread the way it does for variables with finite variance.

Chapter 8: Law of Large Numbers

Difficulty: Medium · Key topics: Chebyshev’s inequality, the weak law of large numbers, the strong law, Monte Carlo estimation, the Cauchy counter-example

This chapter makes precise the intuition that “the average of many trials approaches the true mean.” Chebyshev’s inequality, P(|X−μ| ≥ ε) ≤ V(X)/ε², is proved first as a general tool, then used to prove the Weak Law of Large Numbers: for independent trials with common mean μ and finite variance, P(|Sn/n − μ| ≥ ε) → 0 as n → ∞. A concrete numerical comparison shows just how conservative Chebyshev’s bound is — for 100 Bernoulli(0.3) trials it guarantees only P(|A100−0.3| ≥ 0.1) ≤ 0.21 while the true probability is about 0.963. The Monte Carlo method for estimating an integral by averaging random samples is derived directly from the law, and the chapter ends by revisiting the Cauchy distribution: because it has no finite variance, the law simply does not apply to it, and its sample average never settles down no matter how large n gets.

Key Points:

• Chebyshev’s inequality: P(|X−μ| ≥ ε) ≤ V(X)/ε², true for any random variable with finite variance, no distributional assumption needed.
• The Weak Law of Large Numbers requires only a finite variance, not any particular distribution shape.
• Chebyshev’s bound is usually far looser than the true probability — it is a guarantee, not an estimate.
• Monte Carlo estimation of an integral works because the sample average of g(X) converges to E(g(X)) by the law of large numbers.
• The law of large numbers requires finite variance; the Cauchy distribution is the standard counter-example where it provably fails.

Memory Tip: Chebyshev’s inequality is “guaranteed but pessimistic” — use it to prove that convergence happens and to get a safe (if loose) sample-size estimate, never to predict the actual probability, which the Central Limit Theorem (Chapter 9) does far more precisely.

Common Mistake: Treating Chebyshev’s bound as if it were the actual probability of a large deviation, rather than an upper bound on it. The gap between the two can be enormous, as the 0.21-vs-0.963 example in this chapter shows directly.

Important Questions:

• What does Chebyshev’s inequality guarantee? That for any random variable X with mean μ and variance V(X), the probability X deviates from μ by at least ε is no more than V(X)/ε² — a universal, distribution-free upper bound.
• Why does the Law of Large Numbers not apply to the Cauchy distribution? Because the law’s proof (via Chebyshev’s inequality) requires finite variance, and the Cauchy distribution’s variance is infinite, so its sample average never converges to a fixed value as n grows.

Chapter 9: Central Limit Theorem

Difficulty: Hard · Key topics: the standard normal density, standardized sums, the CLT for Bernoulli trials, the continuity correction, confidence intervals, polling margins of error, de Moivre and Galton

The Central Limit Theorem is developed in three passes — Bernoulli trials, general discrete independent trials, then continuous trials — each time showing that the standardized sum Sn* = (Sn − nμ)/√(nσ²) converges to the standard normal density φ(x) = (1/√2π)e−x²/2, regardless of the shape of the original distribution. Worked examples ground the theorem in real calculations: 100 coin tosses giving P(exactly 55 heads), a Dartmouth-admissions yield problem, and a polling example computing that a ±3% margin of error at 95% confidence needs about 1,111 respondents, with an actual 1936–1996 Gallup accuracy table alongside it. The historical remarks credit Abraham de Moivre (1718) with the first proof, for the Bernoulli case, and describe Galton’s quincunx device as a physical demonstration of the same convergence.

Key Points:

• The Central Limit Theorem says the standardized sum of many independent trials approaches the standard normal density, whatever the shape of the individual trials’ distribution.
• Standardization: Sn* = (Sn − nμ) / √(nσ²).
• The continuity correction (using 39.5 to 60.5, not 40 to 60) measurably improves the normal approximation to a discrete binomial probability.
• A poll needs roughly 1,111 respondents for a ±3% margin of error at 95% confidence — the sample-size formula behind every political poll you read.
• De Moivre proved the Bernoulli-trials case of the CLT in 1718, long before the general theorem was established.

Memory Tip: The CLT is “why the normal curve shows up everywhere” — any time you are adding up many small, independent, similarly-distributed contributions (exam scores, measurement errors, poll responses), expect a bell curve, even if no single contribution is itself normal.

Common Mistake: Applying the normal approximation to a binomial probability without the continuity correction, or when np or n(1−p) is too small for the approximation to be reasonable in the first place.

Important Questions:

• What does the Central Limit Theorem say, in one sentence? The standardized sum of a large number of independent, identically distributed random variables with finite variance converges to the standard normal density, regardless of the shape of the original distribution.
• Roughly how many people does a poll need for a ±3% margin of error at 95% confidence? About 1,111 respondents, derived directly from the CLT’s normal approximation to the sampling distribution of a proportion.

Chapter 10: Generating Functions

Difficulty: Hard · Key topics: moments, moment generating functions, ordinary generating functions, branching processes, extinction probability, the characteristic function

Generating functions package an entire distribution’s moments into one function: the moment generating function g(t) = E(etX) and, for nonnegative-integer variables, the ordinary generating function h(z) = Σp(j)zj, with p(j) = h(j)(0)/j! recovering the original probabilities. Named distributions get closed-form generating functions (binomial: (pet+q)n; Poisson: eλ(et−1)), and these are then turned on the historically famous branching-process (Galton-Watson) problem of surname extinction: with offspring generating function h(z), the extinction probability d is the smallest positive root of d = h(d), and d = 1 (certain extinction) exactly when the mean number of offspring per parent, m, is ≤ 1. A worked Japanese-census example estimates real extinction probability at about 0.324 from actual family-size data, and a chain-letter example turns the same machinery into an expected-profit calculation.

Key Points:

• The moment generating function g(t) = E(etX) encodes every moment: μn = g(n)(0).
• For a branching process with offspring generating function h(z), the extinction probability d solves d = h(d).
• If the mean offspring count m ≤ 1, extinction is certain (d = 1); if m > 1, there is a genuine positive probability of indefinite survival (d < 1).
• Sum of independent variables corresponds to multiplying generating functions: gX+Y(t) = gX(t)·gY(t).
• The characteristic function kX(τ) = g(iτ) exists even for distributions like the Cauchy, whose moment generating function does not.

Memory Tip: Generating functions turn “find the distribution of a sum” into “multiply two functions” — whenever convolution algebra from Chapter 7 gets messy, switching to generating functions and multiplying is almost always faster.

Common Mistake: Concluding a family line or population is “safe” just because its mean offspring count m is greater than 1. m > 1 only means extinction is not certain — the extinction probability d is still strictly positive unless m is very large.

Important Questions:

• In a branching process, when is extinction certain? Exactly when the mean number of offspring per individual, m, is less than or equal to 1 — then the extinction probability d, the smallest positive root of d = h(d), equals 1.
• How does the generating function of a sum of independent random variables relate to the generating functions of the individual variables? It is their product: gX+Y(t) = gX(t)·gY(t), which is why generating functions turn convolution into simple multiplication.

Chapter 11: Markov Chains

Difficulty: Hard · Key topics: transition matrices, the Land of Oz weather example, absorbing chains, the fundamental matrix, ergodic and regular chains, the fundamental limit theorem

A Markov chain is a process on states where the next state depends only on the current one, encoded in a transition matrix P whose entry pij is the probability of moving from state i to state j; the book’s running example is the three-state “Land of Oz” weather model (Rain, Nice, Snow), whose long-run probabilities converge to (.4, .2, .4) regardless of the starting day’s weather. Absorbing chains — those with at least one state, once entered, never left — get their own machinery: the fundamental matrix N = (I−Q)−1 gives expected visits to each transient state before absorption, and B = NR gives the probability of ending up in each absorbing state, worked out fully on a five-block “drunkard’s walk” between home and a bar. Regular and ergodic chains get the Fundamental Limit Theorem: Pn → W, a matrix with identical rows equal to a unique fixed probability vector w, proved two different ways (direct contraction, and Doeblin’s coupling argument).

Key Points:

• Transition matrix entry pij is the one-step probability of moving from state i to state j; Pn gives n-step probabilities.
• An absorbing state has pii = 1; the fundamental matrix N=(I−Q)−1 gives expected time in each transient state before absorption.
• A regular chain (some power of P has all-positive entries) always converges: Pn → W, with every row of W equal to the same fixed vector w.
• The fixed vector w solves wP = w together with the constraint that its entries sum to 1.
• Every regular chain is ergodic, but not every ergodic chain is regular — a chain that strictly alternates between two states is ergodic but never regular.

Memory Tip: To find a Markov chain’s long-run behaviour, don’t multiply matrices by hand forever — set up and solve wP = w with the probabilities summing to 1. For the Land of Oz, this small linear system gives (.4, .2, .4) directly, matching what P⁶ already shows numerically.

Common Mistake: Assuming every Markov chain converges to a fixed long-run distribution. Only regular (and more generally ergodic) chains do; a chain that strictly alternates between two states, or one with multiple absorbing states, behaves completely differently.

Important Questions:

• What equation determines a regular Markov chain’s fixed (long-run) probability vector w? wP = w, solved together with the requirement that the entries of w are non-negative and sum to 1.
• What does the fundamental matrix N = (I−Q)⁻¹ tell you in an absorbing Markov chain? Its entry n_ij gives the expected number of times the chain visits transient state j before being absorbed, starting from transient state i.

Chapter 12: Random Walks

Difficulty: Hard · Key topics: random walks in Euclidean space, return to the origin, the gambler’s ruin problem, the arc sine law, de Moivre’s martingale solution

A random walk is a sum of i.i.d. steps, and this chapter’s first surprise is dimensional: a random walk on the integer line or the plane returns to its starting point with probability 1, but in three dimensions the return probability drops to only about 0.65, giving the book’s own memorable summary — “one should not get drunk in more than two dimensions.” The gambler’s ruin problem is solved in closed form: starting with stake z out of a total M, the probability of ruin before reaching M is [(q/p)M−(q/p)z]/[(q/p)M−1] for p≠q, and simply (M−z)/M for a fair game, with De Moivre’s 1711 martingale-based proof presented as the historical solution. The chapter closes with the arc sine law: in a game of length 2m, the time spent in the lead is U-shaped, not bell-shaped — being in the lead for close to exactly half the game is the least likely outcome, not the most likely one, which routinely surprises students on first reading.

Key Points:

• Probability of eventual return to the origin: 1 in one and two dimensions, but only about 0.65 in three dimensions.
• Gambler’s ruin (fair game, p=q=1/2): probability of ruin starting from stake z out of M is (M−z)/M.
• Gambler’s ruin (unfair game, p≠q): probability of ruin is [(q/p)M − (q/p)z] / [(q/p)M − 1].
• Against an infinitely rich adversary, ruin is certain unless your per-bet edge (p > q) is positive.
• The arc sine law: the fraction of time a random walk spends in the lead follows a U-shaped density, so extreme outcomes (leading almost the whole time, or almost none of it) are more likely than an even split.

Memory Tip: “Two dimensions is the drunkard’s safe zone” — a 1-D or 2-D random walk always wanders home eventually (probability 1), but a 3-D walk genuinely can escape forever with probability ≈ 0.35. That one phrase fixes the dimension result better than the underlying series-convergence proof does.

Common Mistake: Assuming a fair coin-toss game keeps the lead roughly balanced between two players over a long run. The arc sine law shows the opposite: long, one-sided leads are the typical outcome, not a rare one.

Important Questions:

• In gambler’s ruin with a fair coin, starting with stake z out of a total M, what is the probability of going broke before reaching M? (M−z)/M — exactly proportional to how far the starting stake is from the target.
• What does the arc sine law say about time spent “in the lead” during a long fair coin-toss game? The fraction of time in the lead follows a U-shaped (arc sine) density, so spending almost the entire game in the lead, or almost none of it, is far more likely than a roughly even split.

Download Introduction to Probability PDF (Free)

Click the button below to open the free, official PDF of Introduction to Probability hosted by the Dartmouth Mathematics Department. No sign-up or payment is required — the book is freely redistributable under the GNU Free Documentation License.

How to Study This Book

If your course covers both discrete and continuous probability in one semester (the standard sequence for BS Math and BS Statistics), read the twelve chapters in order — each one is built on the last, and the book’s own preface assumes two terms of calculus, including multiple integrals, for exactly this path. Chapters 1 and 3 (Discrete Probability Distributions, Combinatorics) give you the counting and simulation vocabulary everything else depends on. Chapter 4 (Conditional Probability) and Chapter 5 (named distributions) are the load-bearing chapters of the whole book — slow down here, work every worked example by hand, and do not move on until Bayes’ formula and the binomial/Poisson/normal families feel automatic.

If your course is a one-term, discrete-probability-only class (common in a BSCS Probability & Statistics module), the book’s own preface tells you exactly what to skip: the continuous sections. Read Chapter 1, Chapter 3, Section 4.1 only (skip 4.2 and the paradoxes in 4.3 unless your instructor wants them), Section 5.1 only, the discrete parts of Chapter 6, Section 8.1 only, Sections 9.1–9.2, and Sections 10.1–10.2. Chapter 11 (Markov Chains) stands almost entirely on its own and can be read any time after Chapter 4 — note that it explicitly assumes matrix theory, so review matrix multiplication and inverses first if that course hasn’t come yet.

Chapter 7 (Sums of Random Variables) and Chapter 9 (Central Limit Theorem) are the hardest material in the book and depend directly on Chapters 5 and 6 — do not attempt them before expectation, variance and the named distributions are solid. Chapter 10 (Generating Functions) is best read after Chapter 7; the branching-process material inside it is self-contained enough to read as a standalone topic if your course only wants that section. Chapter 12 (Random Walks) is the book’s most advanced chapter and leans on Chapter 4’s conditional probability and Chapter 11’s Markov-chain ideas — treat it as optional enrichment unless your syllabus specifically names gambler’s ruin or the arc sine law.

The short appendices near the end of the book (just before the index) are reference material only — mainly the standard normal table used throughout Chapters 5 and 9 — not teaching content, so there is no need to “read” them in order; just know they’re there when a worked example says “from the table.”

One honest caveat on the computing side: the preface describes programs written in TrueBASIC, Maple and Mathematica, and the companion website’s Java applets date from the early 2000s. None of that affects the mathematics, which is exactly as correct today as it was in 1997, but don’t expect to run the book’s original programs on a modern machine without adaptation — rebuild the simulations in Python or R instead, using the book’s own pseudocode as your spec.

Used In These Programs

This book is used for the Probability / Probability Theory course in: BS Computer Science · BS Mathematics. Browse all Probability books, all Statistics books, or all Mathematics books.

Who Should Read This

This book is written for sophomores, juniors and seniors in mathematics, statistics, computer science and the sciences who have completed at least one term of calculus — two terms, including multiple integrals, if the course covers continuous probability as well as discrete. It suits a BS Mathematics or BS Statistics Probability Theory course directly, and works equally well for the Probability & Statistics module inside a BSCS or BS Data Science degree, provided the continuous chapters are read selectively as described above. It is not the right starting point for a student who has not yet taken calculus, and it is not a computing book — the mathematics is the point, and the probability itself does not depend on which programming language you simulate it in. Because combinatorics (Chapter 3) leans directly on counting techniques, pairing this book with Discrete Mathematics: An Open Introduction gives a stronger footing before tackling the harder counting arguments in Chapters 3 and 4.

Applicable Universities

This book is useful for students at Pakistani universities offering BS Mathematics, BS Statistics, BSCS and BS Data Science including Punjab University, Virtual University, COMSATS, FAST, UET, NUST, and other HEC-recognized institutions.

FAQs

Related Books

• Discrete Mathematics: An Open Introduction – Oscar Levin (the counting foundations behind Chapters 3 and 4)
• Calculus Volume 1 – Strang & Herman (OpenStax) (the single-variable calculus this book’s continuous chapters assume)
• Calculus Volume 2 – Strang & Herman (OpenStax) (multiple integrals, needed for the full continuous-probability sequence)

Introduction to Probability by Grinstead and Snell is the classic, freely licensed textbook for a university Probability Theory course — from discrete distributions and combinatorics through Markov chains and random walks, with worked examples throughout. Browse more Mathematics books for the rest of your semester.

Introduction to Probability, 2nd Edition, by Charles M. Grinstead and J. Laurie Snell. Originally published by the American Mathematical Society, copyright 2003 Charles M. Grinstead and J. Laurie Snell. This GNU version, copyright 2006 Peter G. Doyle, is freely redistributable under the terms of the GNU Free Documentation License. Access for free at https://math.dartmouth.edu/~prob/prob/prob.pdf