Tools
L1: Motivations
Google Page Rank, Machine learning, Cryptography
L2: Simple Markov chains
• Basics of Markov chainscode
Rate of convergence. Coupling. Strong Stationary Times
Markov Chain Monte Carlo. Metropolis algorithm
Linear cryptanalysis tutorial
Problem set 1 (for developing intuition, so informal)
Use 3 examples from: code sample and modify the code.
• How can you get uniform distibution? You can modify initial distribution for each example.
• How can you get uniform distibution? You can modify only one row of transition matrix.
• Every plot seems to be constant from some point. How can you measure distance between the distrinution at time n and its "stationary distribution"?
• How would you define stationary distribution? The process is defined by its transition matrix P but it can have any initial distribution.
Problems
Project
Final grade is based on homeworks see here and a final project.
A final project is a problem that will be assigned to a student individually. You need to (1) solve a problem, (2) write down the solution e.g., in a Jupyter notebook, describing the steps leading to the solution, (3) present your solution during a video call. You may be asked additional questions related to (but not limited) to your project. The list of projects will be announced soon. You will be given 2 weeks to submit your solution.