Assignment 2

Assigned 2025-09-03, due 2025-09-10

Question 1

Let $(X_n)$ be a Markov chain on $\mathcal X$.

  1. True or false: For any events $A_0$, $A_1$, …, $A_{n-1} \subseteq \mathcal X$, and any $a_n, a_{n+1} \in \mathcal X$, must we have \begin{align} \P( X_{n+1} = a_{n+1} \given X_n = a_n,&~X_{n-1} \in A_{n-1},~ X_{n-2} \in A_{n-2},~ \dots,~ X_0 \in A_0 ) \\ &= \P( X_{n+1} = a_{n+1} \given X_n = a_n) \end{align} Prove it, or find a counter example.

  2. True or false: For any events $A_0$, $A_1$, …, $A_{n} \subseteq \mathcal X$, and any $a_{n+1} \in \mathcal X$, must we have \begin{equation} \P( X_{n+1} = a_{n+1} \given X_n \in A_n, X_{n-1} \in A_{n-1}, \dots, X_0 \in A_0 ) = \P( X_{n+1} = a_{n+1} \given X_n \in A_n) \end{equation} Prove it, or find a counter example.

Question 2

Let $(X_n)$ be a Markov chain on $\mathcal X$.

  1. True or false: The random variables $X_2$ and $X_0$ are independent. Prove it, or find a counter example.

  2. True or false: For every $x_1 \in \mathcal X$, conditioned on the event $\set{X_1 = x_1}$, the random variables $X_2$ and $X_0$ are (conditionally) independent.

Question 3

  1. Prove Proposition 17, obtaining a (discrete) Poisson equation for the expected cumulative reward function $v$.

  2. Use this to find the expected ruin time in both the cases $p = q = 1/2$ and $p \neq q$.

Question 4

Consider a tournament with 10 teams. Consider the graph with vertices corresponding to the teams, and edges corresponding to games that were played. Each team plays exactly 3, and the graph above is connected. For every game, the winner gets $1$ point and loser gets $0$. We rank teams using the ranking algorithm used in this notebook (download), with $\beta = 0.1$.

Find an example where exactly one team, say team $T_0$ wins all their games, and this team is ranked in the bottom half. Also, think about (but don’t turn in) why this ranking may be “better” than ranking teams by counting the number of wins.

If you figure out an example, one convenient way to create the tournament graph is the following code snippet:

# List of games; first team is the winner.
games = [
    (0, 1),
    (0, 2),
    (0, 3),
    # figure out and add the rest of the games here.
]

# Create a tournament graph based on the outcome of the above games
G = nx.DiGraph()
N = 10
G.add_nodes_from(list(range(N)))
G.add_edges_from([(a, a, {'score': 0}) for a in G.nodes])
for (a, b) in games:
    G.add_edge( a, b, score=1 )
    G.add_edge( b, a, score=0 )

To make grading easier, fix node 0 to be the only team that wins all games, and include a validation test showing your tournament satisfies all the required criterion. This can, for instance, done with the following:

# Check rules were satisfied
def validate(G):
    assert(nx.is_connected(nx.Graph(G.edges)))
    assert(all(array(G.degree)[:,1] == 8))
    assert(all([G[a][b]['score'] == 1 - G[b][a]['score'] for a, b in G.edges if a != b]))
    wins = array([sum(G[a][b]['score'] == 1 for b in G.neighbors(a) if b != a) for a in G.nodes])
    assert(wins[0] == 3)
    assert(all(wins[1:] < 3))

    return True
validate(G)

To make grading easier, turn in a snippet showing how you defined the tournament (e.g. the games array above), a screenshot showing how you validated your tournament (code and output), and a screenshot showing the ranks of all teams (code and output).

Note: It is possible to “brute force” this problem; but with a little intuition you should be able to guess an example “quickly”.