Probability for Applications

Instructor: Peter L. Ralph, email "plr" at the domain "stat.berkeley.edu". Office hours are Tuesdays, 12-2 in 429 Evans.
GSI: Josh Abramson, email "josh" at domain "stat.berkeley.edu". Office hours are Monday 4-5, and Wednesday 10-11 and 2-3 in 307 Evans.

Textbook: Probability and Random Processes, by Grimmett and Stirzaker (3rd edition).

Problem session: Mondays from 1-2:30pm, in 334 Evans, there will be a non-mandatory but highly recommended problem session/discussion section, where the TA covers additional examples of the material and/or the homework.

Target audience and prerequisites: This course is intended for graduate students with a good foundation in undergraduate mathematics and probability who anticipate using probability and stochastic processes in their work. The aim is to give graduate students the tools and background knowledge to create and use probability models, with an emphasis on calculations and useful properties. This course does not require measure theory and does not emphasize proofs, unlike Stat 205A/B, a year-long course taught this semester by David Aldous.

I will assume probability knowledge equivalent to Stat 134 (with some reminders), and will make frequent use of calculus (multivariable), basic linear algebra, and real analysis (limits, continuity, convergence, ...), as well as occasional use of complex numbers. We will move very quickly through the first four chapters of the text, which is mostly covered in a good undergraduate probability course.

Course description: This course aims to provide a treatment of the ideas and techniques most commonly found in the applications of probability, aimed at graduate students with a good foundation in undergraduate mathematics and probability who anticipate using probability and stochastic processes in their work. In contrast to Stat 205 (which requires use of measure theory and emphasizes rigorous proof techniques) this course will emphasize describing what's known and how to do calculations in range of probability models. Knowledge of undergraduate probability (on the level of Stat 134) and general mathematics (calculus; some linear algebra and real analysis) is assumed.

The topics to be covered include: generating and characteristic functions, branching processes, limit theorems, Markov chains, Markov chain Monte Carlo (MCMC), general Poisson processes, Brownian motion, diffusions, and additional topic(s) chosen by student interest. We will follow Grimmett & Stirzaker when reasonable, skipping sections tangential to the main point, and occasionally adding in supplemental material. For more detail, see the schedule.

Course responsibilities: Homework is due each Thursday by 3:30, either in class or in the envelope outside 429 Evans. These will be graded by the GSI, so no late homework will be accepted, barring major illness or the like. The homework exercises are an important part of the course, and necessary for good understanding of the content. Also, each Tuesday students are expected to hand in reading questions: one brief question, comment, or clarification from the reading for the coming week, on a half-sheet of scrap paper. These will be checked off, and will help adjust the pace and focus of the course, as well as encouraging reading ahead. The final exam will be a take--home, handed out on Thursday, December 2nd (the last day of class) and due on Tuesday, December 7th at 5pm. Grades will be based on either (5% reading questions, 60% homework, 35% final) or (5% reading questions, 35% homework, 60% final), whichever is greater. The lowest two homework scores will be dropped.

Schedule: Subject to revision. Chapter references are to Grimmett & Stirzaker.

• August 26: Review of probability: prerequisite material and notation. (Chapters 1-4)
• August 31: Simple random walk: gambler's ruin, reflection principle, ballot theorem, arcsine law, exchangeability and time of maximum deviation. (Sections 3.9,10)
• September 2: Coupling and Poisson approximation: total variation distance, Stein-Chen method, convergence of point processes, examples. (Section 4.12)
  • HW #1: Section 3.10: 1,3; section 3.11: 17; section 4.12: 3,5; and "Form a random graph G on N nodes by connecting each pair of nodes independently with probability p. Let T be the number of triangles in G, and show that T is approximately Poisson distributed for appropriate scaling of p as N becomes large." (solution)
• September 7: Stein-Chen, continued. Generating functions: definition and properties, examples, application to renewals. (Sections 5.1-3) (here is a write-up of the Stein-Chen example)
• September 9: Renewals, continued. Convergence and Limit Laws: characteristic functions, law of large numbers, central limit theorem. (Sections 5.7-10, 7.1-2, 7.7-8)
  • HW #2: (solution) Section 5.2: 3; section 5.7: 3; section 5.9: 3; section 5.12: (24 or 25),45; and "Given a random variable X define another random variable Y with distribution P(Y=y) = P(X>y)/E[X]. Find the distribution corresponding to (a) Uniform on {1,2,...,n}, (b) Poisson(l); and (c) give at least one example of a distribution invariant under this operation."
• September 14: Modes of convergence (in distribution, in probability, in $L^2$, almost surely). Branching processes: generating functions, probability of extinction, long-time behavior. (Sections 7.1-2, 7.7-8, 5.4)
• September 16: Branching processes: Yaglom's law; more applications. (Section 6.7+) (here is a write-up of Apert syndrome example)
  • HW #3: (solution) Section 7.11: 4, 17; section 5.4: 5; and continuing, "Find the mean of a branching process with immigration (described in 5.4#5), in terms of the mean and variance of the offspring and immigrant distributions;"
  • and finally, "(a) Show, for any two linear fractional transformations f(s) = (as+b)/(cs+d) and g(s) = (es+f)/(gs+h), that f(g(s)) = (As+B)/(Cs+D), where (A,B) and (C,D) are the rows in the matrix product of ((a,b),(c,d)) and ((e,f),(g,h)). Then, (b) show that if P{Y=0} = d and P{Y=k} = (1-d)p(1-p)^(k-1) for k>0, then the generating function of Y has this form. Explain how to find the generating function of the branching process whose offspring distribution is Y.
• September 21 & 23: Markov chains: Markov property; Chapman-Kolmogorov equations; transience and recurrence; stationary distribution and convergence to stationarity; examples. (Sections 6.1-4) Theorem 6.4.10 via harmonic extensions and hitting probabilities (see Chapter 2 of POTN by Lyons and Peres for this and much more).
  • HW #4: (solution) Section 6.1: 2 and Section 6.15: 6; also:
  • (similar to 6.4#7) (a) Show that simple random walk on the infinite (rooted, regular) binary tree is transient by finding the probability that the walk ever returns to the root as a function of its starting depth. (b) Call one subtree of the root the "right" subtree, and the other the "left", and say that the level of a node is the number of steps needed to reach the root, multiplied by (-1) if the node is in the left subtree. Show that the probability that the walk escapes to infinity out the right subtree is given by r(k), where for k nonnegative, r(k) = (1 + (1-2^(-k)))/2 and r(-k) = (1 - (1-2^(-k)))/2 .
  • and also, Let X be a Markov chain on (0,1,2,...) with transition probabilities given by P(k,k-1) = 1 and P(0,k) = P(Y=k) for k nonnegative, and where Y is a random variable taking values in (1,2,3,...). Find the stationary distribution of X if E[Y] is finite.
• September 28 & 30: Markov chains cont'd: reversibility and time reversal, diagonalizability of such, random walk on weighted graphs, more examples (birth-death chains, dog-flea model, gibbs distribution), MCMC, MCMC for Bayesian computation and graph coloring, mixing times and conductance bound. (chapter 6 sections 5-7, 14)
  • HW #5: (solution) Section 6.5: 9 (but do include possibility of loops) and Section 6.6: 6; also:
  • Let X be the Markov chain on {0,1} with P{ X_1 = 1 | X_0 = 0 } = a and P{ X_1 = 0 | X_0 = 1 } = b. Find the stationary distribution, and an explicit expression for the total variation distance between the distribution of X_n and the stationary distribution as a function of n and the starting point.
  • and also: Take a graph G and a pallet of k colors, and call any assignment of colors to the nodes of the graph such that no two adjacent nodes have the same color a coloring of the graph. Describe an MCMC algorithm that will sample (approximately) uniformly chosen colorings of the graph, as long as k is large enough, and discuss possible problems that may occur for smaller k.
• October 5-7: Poisson (point) processes: spatial/general PPP, memorylessness and independence, coloring/marking, superposition, thinning, and mapping, conditioning on the number of points, conditioning on presence of a point, examples. (Chapter 6 sections 8,13, plus)
  • HW #6: (solution) Section 6.8: 1 and Section 6.13: 8; also:
  • Let X be a nonnegative random variable with density f(x) and cumulative distribution function F(x). Let L be a Poisson point process on the nonnegative real line with intensity function g(x) = f(x) / (1-F(x)), and let Y = min { y in L } be the smallest point in L. Show that Y has the same distribution as X.
  • and also: A Poisson point process of raindrops of constant intensity u begins falling on the plane at time zero. Each raindrop splatters out to a circle of random radius; the radii are iid and exponentially distributed with mean 1. Find the probability that the origin has gotten wet by time t.
• October 12: PPP continued: Renyi's theorem, convergence to general PPP, Campbell-Hardy theorem and computation of moments, examples.
• October 14: Stationary processes and spectra: stationarity, covariance functions, linear prediction and autoregression, comparison to Poisson processes and more general point processes. (Chapter 9 sections 1, 2)
  • HW #7: (solution) Section 9.1: 2 and Section 9.2: 1; also:
  • Spiders live on a long telephone wire at the points of a Poisson point process with constant intensity 1; the spider at x has made a section of the wire sticky for the same distance R(x) in both directions from its home at x; these distances R(x) are iid and uniformly chosen on [0,1].
    • (a) Fix a length of wire L units long. Find the Laplace transform of the total amount of stickiness laid down by the spiders that live on that section. (i.e. the total area claimed by those spiders, counting overlapping areas once for each claiming spider)
    • (b) What is the probability that a given point on the wire is not sticky?
    • (c) A large number of flies land as a Poisson point process with constant intensity z on the wire. Denote by F_k the flies landing in sections claimed by exactly k spiders. What is the mean number of flies in F_k per unit length?
• October 19-21: Stationary processes and spectra: spectral theorem, moving averages, ergodicity and the ergodic theorem(s), Gaussian processes, examples. (Chapter 9 sections 3, 5 (lightly), 6)
  • HW #8: (solution) Section 9.5: 2; also:
  • Let (A_1,B_1,A_2,B_2) be uncorrelated RVs with mean zero and variance 1, let u_1 and u_2 be distinct nonnegative numbers, and let L be a RV with P(L=1)=p and P(L=2)=1-p, independently of the As and Bs. For each integer n, let
    • X(n) = p ( A_1 cos( n u_1 ) + B_1 sin( n u_1 ) ) + (1-p) ( A_2 cos( n u_2 ) + B_2 sin( n u_2 ) ), and
    • Y(n) = A_L cos( n u_L ) + B_L sin( n u_L ) .
    Show that X and Y are stationary, find their spectral distributions, and describe their spectral representations, in the sense of Theorem 9.4(4).
  • and also: Let X(t) be a Gaussian process on [0,infinity) (not stationary!) with mean zero, and covariance function cov(X(s),X(t)) = min(s,t)) for all t, s. For p between 0 and 1, find the distribution of Z = X(t+ps) - (1-p) X(t) - p X(t+s). Show that Z is independent of X(t) and X(t+s), for all p.
• October 26-28: Continuous-time Markov chains: transition probabilities, forward and backward equations, generators, embedded chains, hitting probabilities and mean hitting times; birth-death chains. (ch 6.9,11 and plus).
  • HW #9:(solution) Section 6.9: 3,4,5; also:
  • Let X be a CTMC on {1,2,3,...} with generator matrix G(n,n+1) = bn and G(n,n) = -bn. ("everyone gives birth independently at rate b") Show P{ X(t)=n | X(0)=1 } = exp(-bt) ( 1-exp(-bt) )^(n-1) by verifying that this solves the forwards equation. Then write down P{ X(t)=n | X(0)=m } using the observation that this is a geometric distribution.
• November 2-4: Martingales: hitting probabilities, generators, optional stopping. Birth-death chains: spectral expansions, continuum limits, honesty. (6.11, some of ch. 12).
  • HW #10: (solution) (Due Tuesday, November 16) Section 12.1: 3; section 12.5: 5; section 12.9: 10; and section 12.9: 18.
  • and: Let S(t) be a continuous-time Markov process that jumps at rate 1; if S(t)=z then the jump is to z+1 with probability (1+a/sqrt(N))/2 and to z-1 with probability (1-a/sqrt(N))/2 for fixed (large) N. Let X(t) = (1/sqrt(N)) S(N*t). Find the generator of the diffusion approximation for X and identify the diffusion process.
• November 9: Diffusions: motivated as continuum limits of birth-death (and other) chains; forwards and backwards equations, generators; hitting distributions and potentials (ch 13 sections 1-3 and a bit of 4).
  • HW #11: (solution) (Due Tuesday, November 23) Do two of the following: ( Section 13.12: 1; section 13.3: 9; section 13.12: 24; )
  • and: Describe explicitly the limiting procedure to obtain the diffusion process of Example 13.3.12 ("Diffusion approximation to the branching process."). Find hitting probabilities for the resulting diffusion, namely, the probability that the diffusion process hits a before hitting b if begun at x, for each a, b, and x.
• November 16-18: Brownian motion: hitting zero, quadratic variation; Bessel processes; excursions and the zero set. Stochastic integrals: as diffusions, simulation, white noise. (ch. 13 sections 6,7, and something about 8)
• November 23: Itô's formula and more about stochastic differential equations. (ch. 13 section 9)
• November 30, December 2: Review and applications -- including the Erdős-Rényi random graph: critcality and the emergence of the giant component.
• December 7: Final due, 5pm.

Links:

• A Second Course in Probability by Sheldon Ross and Erol Pekoz, and Applied Probability by Kenneth Lange, are two books also used at times for this course. They cover many of the same topics in less depth, and may be more accessible.