Assignment 1

Assigned 2025-08-27, due 2025-09-03

Question 1

Find the link for the discussion board on the class website. Join it, and write a comment with a random Math/CS fact. (Include a screenshot with your homework.)

Question 2

First get yourself setup with Python:

  • If you haven’t used Python before, do a quick read through of the Beginners Guide

  • I recommend installing Python locally. You will need: Python, Numpy, SciPy, matplotlib, Jupyter, tqdm, ipywidgets, networkx.

    (Alternately, if you don’t want to install Python locally, you can run all your notebooks in the cloud (e.g. Google Colab) Last I checked, this was about 10 times slower than my Intel i5 laptop from 2021. Your mileage may vary.

  • Download the team rankings notebook (you might have to right-click and save to avoid special characters getting borked). Then open the notebook with Jupyter, and run it. If it runs correctly, the output should look something like this.

Once you’re setup, here’s the actual homework problem: Consider the team ranking problem in the above notebook, and choose $\beta = 0.1$. The notebook sets up a directed graph $G$, and computes edge weights (based on tournament scores) to be the probability a spectator switches team allegiances.

  1. Notice for every team $x$, we add an edge from $x$ to itself, with score $0$. This is done by the condition a == b below. Why did we do this? Is it necessary?

    G.add_edges_from([
    (a, b, {'score': S[a, b]})
        for a in range(N)
            for b in range(N)
                 if S[a, b] + S[b, a] != 0 or a == b
    ])

  2. Fix $\alpha = 0.85$, and consider the page rank chain on this graph: To run this chain, you flip a coin that lands heads with probability $0.85$. If the coin lands heads, then jump to a neighboring node with probability to be the corresponding edge weight. If the coin lands tails, jump to any one of the nodes in $G$, chosen uniformly at random.

    For every node $x \in G$, let $\pi(x)$ be the fraction of time the chain spends at this node. Simulate “many” iterations of this chain, compute $\pi(x)$ numerically, and output it. (You may find the library function choice helpful.) For this question, you should turn in a working Python notebook, with output included, showing both your computed value of $\pi$, and the actual value computed using nx.pagerank().

    Note: If your code is correct, then as you take more and more iterations of the chain, your computed value should approach the value returned by the pagerank library function used in the notebook. Use this to check your code, and be sure you take enough iterations to get good agreement with the correct answer. You should turn in a notebook, with all the output included, showing both your computed value for $\pi$,and the value from the nx.pagerank() library function.

Question 3

  1. Suppose  $X$ is a Markov chain on a finite state space $\mathcal X$. Define \begin{equation} \pi(x) = \lim_{N \to \infty} \frac{1}{N} \sum_{n = 0}^{N-1} \one_{\set{X_n = x}} \end{equation} Compute $\sum_{x \in \mathcal X} \pi(x)$.

  2. If $\mathcal X$ is not a finite set, then your answer from the previous part need not hold anymore. Here’s an example: Suppose $\mathcal X = \Z$, $\paren{X_n}$ is the simple random walk on $\Z$ with $X_0 = 0$. Compute $\sum_{x \in \mathcal X} \pi(x)$.

    Hint: Using Stirling’s approximation one can show that there exists a constant $C > 0$ such that for all $n \in \N$ we have \begin{equation} \frac{1}{2^n}\binom{n}{(n+x)/2} \leq \frac{C}{\sqrt{n}} \end{equation} Check this! Then assume $\E \pi(x) = \lim_{N \to \infty} \frac{1}{N} \E \sum_{0}^{N-1} \one_{\set{X_n = x}}$, and compute $\E \pi(x)$. The answer will lead you to the value of $\sum_{x \in \mathcal X} \pi(x)$. (It’s also worth going over your solution of the previous part and seeing why it fails when $\mathcal X$ is infinite.)

Question 4

Let $\mathcal X = \set{x, y}$ and let $(X_n)$ be a Markov chain on $\mathcal X$ with transition probabilities \begin{equation} \P(x, x) = 1 - \alpha \,, \quad \P(x, y) = \alpha\in (0, 1)\,, \quad \P(y, y) = 1 - \beta\,, \quad \P(y, x) = \beta \in (0, 1)\,. \end{equation} Find a formula for $P^n(x, x) = \P( X_n = x \given X_0 = x)$, and show that $P^n(x, x) \to \beta / (\alpha + \beta)$ (exponentially fast) as $n \to \infty$.

Note. One quick way to solve this problem is by diagonalizing the appropriate matrix. An alternate way is to find, and then solve, a recurrence relation for $P^n(x, x)$.