Instructor: David A. MEYER
Email: dmeyer "at" math "dot" ucsd "dot" edu
Office hours (Spring Quarter): AP&M 7256 F 1:00pm- 2:00pm, or by appointment
Lectures: Center Hall 109, MWF 12:00pm-12:50pm
Teaching Assistant: Sameeksha KHILLAN
Office hours: Mayer Hall 5722, TuTh 9:30am-11:30am, or by appointment
Section A01: Center 217A, M 6:00pm-6:50pm; section will not meet M Apr 1
Section A02: Center 217A, M 7:00pm-7:50pm; section will not meet M Apr 1
Email: skhillan "at" eng "dot" ucsd "dot" edu
Teaching Assistant: Daniel COPELAND
Office hours: AP&M 5768, W 3:30pm-5:30pm, or by appointment
Section A03: AP&M 2402, M 5:00pm-5:50pm; section will not meet M Apr 1
Email: drcopela "at" ucsd "dot" edu
The topic for this course is random walk algorithms, which I have chosen because (1) there are several practically important random walk algorithms, including, for example, PageRank and MCMC sampling; (2) there is a conceptually important connection with physics, specifically the heat equation; and (3) they provide a convenient entryway to quantum algorithms.
After providing some background information I will introduce random walks, explain the connection with physics, and describe several random walk algorithms in detail. This will take the first 6-7 weeks of the course. In the last few weeks I plan to introduce quantum walks, explain their connection to physics, and work through at least one quantum walk algorithm in detail.
The prerequisites are first year calculus through the level of Math 20C and linear algebra (Math 18 or Math 31AH). Since this is partly a computer science course, I will expect students to be able to write and run their own computer code, at least in Matlab (since that is used in Math 18). There will be programming assignments, to complete which students will be free to use any language they like. Some familiarity with probability (e.g., Math 180AB) and differential equations (e.g., Math 110AB) will make the course easier, but since these are not prerequisites, I plan to explain the necessary concepts in lecture. Finally, there will be proofs, both in lecture and in homework assignments, so Math 109 will be helpful. Since almost all the students are junior or senior math or CS majors, I do not expect this to be an obstacle.
There is no textbook. I will point to online resources, i.e., mathematics or computer science papers, for some of the material.
Grading: There will be weekly homework assignments, which will constitute 40% of the course grade. Students must write up their own homework solutions; multiple identical solutions will receive no credit. Homework will be submitted online, to Gradescope. Information on student computer accounts is available on TritonLink; locations of computer labs are listed at ETS; as is available software. There will be a midterm exam (20%) and a final exam (40%).
May 10, 2019 |
Undergraduate Mathematics Honors Thesis presentations Clara Woods, Quantum walks AP&M, room 6402, 10:20am-10:40am |
Spring 2019 |
Art of Problem Solving (AoPS) Summer Teaching Assistant job application |
Apr 1, 2019 DM lecture |
administrative details overview/motivation What is an algorithm? etymology, from Muhammad ibn Musa al-Khwarizmi example: completing the square [1] example: primality testing pseudocode running time big-O notation [notes 1] |
Apr 3, 2019 DM lecture |
digression on the primality of 1 history [2] irreducibility and primality in integral domains review of complex numbers and norms probability review/introduction [3] sample space, events discrete probability distribution conditional probability independence [notes 2] |
Apr 5, 2019 DM lecture |
(real-valued) random variables expectation value and its properties variance and its properties [notes 3] |
Apr 8, 2019 DM lecture |
independence for sets of events and random variables sequence of independent coin flips probability distribution for the number K of heads up expectation value and variance of K "step" random variable St which is 1 for head and -1 for tail Xt = S1 + ... + St [notes 4] HWK (due 5:00pm M Apr 15; submission instructions). Write code to simulate 100 steps of a random walk, with Pr(St = 1) = p. Plot the results for one run for each of p = 0.5, p = 0.4, and p = 0.6. Run this routine many times and plot the histogram of X100, for some fixed p. Compute the mean and the variance of your data. |
Apr 10, 2019 DM lecture |
random walk on Z is {Xt} definition of stochastic process definition of Markov process states and transition probabilities random walks on Z and Z/lZ as Markov processes [notes 5] |
Apr 12, 2019 DM lecture |
diagrams of random walks on Z and Z/lZ probability distribution of Xt is given by Ptu0 x + t (mod 2) is a conserved quantity on Z and Z/lZ for even l defining a new Markov process from two steps of a random walk [notes 6] |
Apr 15, 2019 DM lecture |
a system of difference equations for the probabilities at each state at each time review of limit definition of first and second derivatives continuum limit of random walk difference equation is heat equation with drift solution of the the drift (advection) equation [notes 7] HWK (due 5:00pm M Apr 22) 1. Let P be a stochastic NxN matrix, i.e., Pij ≥ 0, ∑i Pij = 1, for all j. Prove that if v ∈ RN has ∑j vj = c, then Pv ∈ RN has ∑j(Pv)j = c. 2. Modify, or rewrite, your code for a random walk with p = 1/2 on Z to implement a random walk on Z/6Z. Run this routine many times and plot the histogram of X100. |
Apr 17, 2019 DM lecture |
solving the heat equation by analogy with the random walk probability distribution Stirling's approximation for n! Laplace's derivation of the normal approximation to a binomial distribution [notes 8] |
Apr 19, 2019 DM lecture |
the heat kernel limit of the heat kernel as t goes to 0 definition of distribution and Dirac delta "function" [notes 9] |
Apr 22, 2019 DM lecture |
initial condition for solution to heat equation analogy with evolution of random walk from initial probability distribution solution of heat equation by convolution of initial condition with heat kernel [notes 10] HWK (due 5:00pm M Apr 29; submission instructions) Homework 3 [pdf] [TeX] |
Apr 24, 2019 DM lecture |
numerical algorithm for simulating the heat equation physical intuition for relation between random walk and heat/diffusion equation two particles randomly walking without interaction in 1D one particle randomly walking in 2D simulation of the heat equation in 2D [notes 11] |
Apr 26, 2019 DM lecture |
Gaussian blurring is blurring invertible? element in nullspace of B on Z/2kZ nontrivial kernel of B implies not invertible computing the nullspace diagonalizing X diagonalizes B [notes 12] |
Apr 29, 2019 DM lecture |
eigenvalues of X are Nth roots of 1 computing the corresponding eigenvectors the discrete Fourier transform eigenvalues of B [notes 13] HWK (due 11:59pm W May 8) Homework 4 [pdf] [TeX] |
May 1, 2019 DM lecture |
dimensions and real basis vectors for the eigenspaces of B initial probability distribution in this Fourier basis evolution in the Fourier basis limiting distribution and rate of approach to it inverting the evolution and unblurring [notes 14] |
May 1, 2019 DM lecture |
Midterm review; Peterson 103; 7:00pm-8:30pm overview of course and main ideas [practice exam problems] [solutions] |
May 3, 2019 |
Midterm Please bring bluebooks and your student ID. You may bring a page of handwritten notes, but nothing else. [seat assignments] [exam] [solutions] [results] |
May 6, 2019 DM lecture |
properties of general stochastic matrix P P has at least one eigenvalue 1 definition of stationary distribution as eigenvector of P with eigenvalue 1 every eigenvalue of P has norm less than or equal to 1 |
May 8, 2019 DM lecture |
properties of real symmetric matrix M M has only real eigenvalues the eigenvectors of M can be chosen to be real the eigenvectors of M with different eigenvalues are orthogonal M can be diagonalized by an orthogonal matrix HWK (due 11:59pm W May 15) Homework 5 [pdf] [TeX] |
May 10, 2019 DM lecture |
Google PageRank algorithm model user behavior by random walk modify model to have symmetric transition probability matrix compute PageRank from stationary state |
May 13, 2019 DM lecture |
Guess a number problem (SEARCH) very naive algorithm as random walk on possible answers {1,2,...,N} number of guesses is O(N log(1/ε)) less naive algorithm as random walk on possible answers {1,2,...,N} number of guesses is still O(N log(1/ε)) least naive algorithm as random walk on number of remaining possibilities {N,N-1,...,1} number of guesses is still O(N) |
May 15, 2019 DM lecture |
Boolean expressions de Morgan's laws satisfying assignments disjunctive normal form (DNF) conjunctive normal form (CNF) HWK (due 11:59pm W May 22) Homework 6 [pdf] [TeX] |
May 17, 2019 DM lecture |
basics of computational complexity: P, NP and NPC 2-SAT: satisfiability for 2-CNF expressions application to clustering Papadimitriou's random walk algorithm for 2-SAT [5] |
May 20, 2019 DM lecture |
analysis of Papadimitriou's algorithm as random walk on Hamming distance from solution expected time to solution if one exists Markov inequality to bound probability using expectation value failure of analogous random walk algorithm for 3-SAT Bonus points (due 11:59pm M May 27) Problem [pdf] [TeX] |
May 22, 2019 DM lecture |
axiomatic introduction to quantum mechanics unitary matrix as transition amplitude matrix HWK (due 11:59pm W May 29) Homework 7 [pdf] [TeX] |
May 24, 2019 DM lecture |
analogy between homogeneous Markov process and repeated multiplication by unitary matrix eigenvalues and diagonalization of unitary matrices consquent non-convergence of "unitary process" a quantum walk algorithm for guess a number (SEARCH) derivation of unitary matrix to represent transition to new guess |
May 27, 2019 |
No lecture; Memorial day. |
May 29, 2019 DM lecture |
including a "sink" at the answer would destroy unitarity so expand vector space to include flag for having found, or not, the solution quantum algorithm as product of unitary matrix for checking guess and unitary matrix for making new guess with clever initial state, reduce back down to N dimensional vector space HWK (due 11:59pm W Jun 5) Homework 8 [pdf] [TeX] |
May 31, 2019 |
No lecture. |
Jun 3, 2019 DM lecture |
identification of unitary operations as relections geometrical analysis of algoritm to find O(N1/2) run time this is Grover's quantum SEARCH algorithm [6] quantum walk on Z/NZ a X + b X-1 is only unitary if one of a and b is 0 |
Jun 5, 2019 DM lecture |
expand vector space to include direction as well as position general form of 2x2 unitary matrix impose left-right symmetry for "unbiased" quantum walk |
Jun 7, 2019 DM lecture |
as with classical random walk, consider new process consisting of two timesteps a system of difference equations for the amplitudes at each state at each time continuum limit of quantum walk difference equation is Dirac equation analogously to classical case, can solve for amplitudes, derive solution to Dirac equation |
Jun 10, 2019 DM lecture |
Final review; AP&M B402A; 6:00pm-7:00pm overview of course and main ideas [practice exam problems] [solutions] |
Jun 12, 2019 |
Final; Center 109; 11:30am-2:29pm Please bring bluebooks and your student ID. You may bring a page of handwritten notes, but nothing else. [seat assignments] [exam] [solutions] [results] |
[1] | P. Maher, "From al-jabr to algebra", Mathematics in School 27 (1998) 14—15. |
[2] | C. K. Caldwell and Y. Xiong, "What is the smallest prime?", Journal of Integer Sequences 15 (2012) Article 12.9.7. |
[3] | K. Baclawski and G.-C. Rota, Introduction to Probability and Random Processes (1979). |
[4] | G. F. Simmons, Differential Equations with Applications and Historical Notes, Third Edition (Boca Raton, FL: CRC Press 2017). |
[5] | C. H. Papadimitriou, "On selecting a satisfying truth assignment", in Proceedings 32nd Annual Symposium of Foundations of Computer Science (Los Alamitos, CA: IEEE 1991). |
[5] | L. K. Grover, "A fast quantum mechanical algorithm for database search", in Proceedings of the twenty-eighth annual ACM symposium on Theory of Computing (New York, NY: ACM 1996) 212-219 |