Homework 3

This homework covers the material from lectures 9 to 12

Due date: October 25th, 11:59pm Waterloo time.

PDF version of Homework 3.

LaTeX template, in case you want to write it in LaTeX.

Required Exercises

Remember that you are only required to turn in 5 out of the 6 exercises below.

Problem 1 - Markov Chains (20 points)

1. Show that if a Markov chain with transition matrix $P$ is irreducible and has a state $i$ such that $P_{i,i} > 0$, then it is also aperiodic.
2. Let $a, b$ be positive integers and consider the Markov chain with state space $$ \{ (i,j) \mid 0 \leq i \leq a-1, \ \ 0 \leq j \leq b-1 \} $$ where $i,j$ are integers, and the following transition mechanism: if the chain is in state $(i,j)$ at time $t$, then at time $t+1$ it moves to $( (i+1) \bmod a, j)$ with probability $1/2$ or to $( i, (j+1) \bmod b)$ with probability $1/2$.

Show that this Markov chain is irreducible, and show that it is aperiodic if, and only if, $\gcd(a,b) = 1$.

3. Consider a chessboard with a lone white king making random (king) moves, meaning that at each move, he picks one of the possible squares to move to, uniformly at random. Is the corresponding Markov chain irreducible and/or aperiodic? If so, what is the stationary distribution?
4. Same question as part 3, except now we have a lone knight in the chessboard.

Problem 2 - Mixing Time of Random Walks (20 points)

Compute the mixing time (both upper bounds and lower bounds) of the dumbbell graph: the graph on $2n$ nodes that consists of two complete graphs on $n$ nodes joined by a single edge, where $n \geq 3$.

Hint: try breaking up the graph into 4 pieces which converge to the stationary distribution in the appropriate time, and then show that any other probability distribution converges quickly to one of these pieces.

Problem 3 - Pagerank (20 points)

Suppose someone searches a keyword (like “car”) and we would like to identify the webpages that are the most relevant for this keyword and the webpages that are the most reliable sources for this keyword (a page is a reliable source if it points to many of the most relevant pages).

First we identify the pages with this keyword and ignore all other pages. Then we run the following ranking algorithm on the remaining pages.

• Each vertex corresponds to a remaining page, and there is a directed edge from page $i$ to page $j$ if there is a link from page $i$ to page $j$. Call this directed graph $G(V, E)$, where $n = |V|$.
• For each vertex $i$, we have two values $s(i)$ and $r(i)$, where intendedly $r(i)$ represents how relevant is this page and $s(i)$ represents how reliable it is as a source (the larger the values the better).
• We start from some arbitrary initial values, say $s(i) = 1/n$ for all $i$, as we have no idea of their relevance at the beginning.
• At each step, we update $s$ and $r$ (where $s$ and $r$ are vectors whose $i^{th}$ entries are $s(i)$ and $r(i)$) as follows:
• First we update $$r(i) = \sum_{j: (j,i) \in E} s(j)$$ for all $i$, as a page is more relevant if it is linked by many reliable sources.
• Then we update $$s(i) = \sum_{j: (i,j) \in E} r(j)$$ for all $i$ (using the just updated values $r(j)$), as a page is a more reliable source if it points to many relevant pages.
• To keep the values small, we let $R = \sum_{i=1}^n r(i)$ and $S = \sum_{i=1}^n s(i)$, and divide each $s(i)$ by $S$ and each $r(i)$ by $R$.
• We repeat this step for many times to refine the values.

Let $s, r \in \mathbb{R}^n$ be the vectors of the $s$ and $r$ values.

1. Give a matrix formulation for computing $s$ and $r$.
2. Suppose $G$ is weakly connected (that is, when we ignore the direction of the edges, the underlying undirected graph is connected) and there is a self-loop at each vertex. Prove that there is a unique limiting $s$ and a unique limiting $r$ for any initial $s$ as long as $s \geq 0$ and $s \neq 0$.

Hint: use the Perron-Frobenius theorem.

Problem 4 - Linear Programming (20 points)

Let $S = \{ x \in \mathbb{R}^n \mid A x \leq b \}$ and $T = \{ x \in \mathbb{R}^n \mid B x \leq c \}$, where $A \in \mathbb{R}^{m \times n}$, $b \in \mathbb{R}^m$, $B \in \mathbb{R}^{t \times n}$ and $c \in \mathbb{R}^t$. Given $A, B, b, c$ as an input, give a polynomial time algorithm for the problem of checking whether $S \subset T$.

Problem 5 - More Linear Programming (20 points)

Suppose we are given a sequence of $n$ linear inequalities of the form $a_i x + b_i y \leq c_i$, where $x, y$ are variables and $a_i, b_i, c_i \in \mathbb{R}$. Collectively, these $n$ inequalities describe a convex polygon $P$ in the plane.

1. Describe a linear program whose solution describes the largest axis-aligned square that lies entirely inside $P$
2. Describe a linear program whose solution describes the maximum-perimeter axis-aligned rectangle that lies entirely inside $P$
3. Describe a linear program whose solution describes the largest circle that lies entirely inside $P$

Problem 6 - LP Duality (20 points)

Given a finite set of halfspaces $H_i := \{ x \in \mathbb{R}^d \mid a_i^T x \leq b_i, \ a_i \in \mathbb{R}^d, \ b_i \in \mathbb{R} \}$, where $1 \leq i \leq n$ such that any set of $d+1$ halfspaces have a non-empty intersection, prove that there is a point lying in the intersection of all these halfspaces.

Practice Problems

You are not required to submit the solution to these problems, but highly encouraged to attempt them for your own knowledge sake. :)

Problem 1

There are $n$ terminals on a circuit board. Each terminal is either positive or negative. A wire will be attached to each terminal. It must be the case that for every pair of terminals of opposite polarity the two wires must be long enough so that they can be made to touch.

E.g., if there’s a positive terminal at point $a = (0, 0)$, and a negative terminal at $b = (0, 10)$, and another negative terminal at $c = (10, 0)$ then one solution is to put a wires of length $5$ at all three terminals. Or to put a wire of length $10$ at $a$ and length zero at the others.

Or, for any $x \in [0, 10]$, wires of length $\geq 10 - x$ at $a$, and length $\geq x$ at both $b$ and $c$.

So given the locations of the terminals (and their polarities), the problem is to compute the shortest total length of wires needed to satisfy the stated requirement.

1. Consider the following specific instance of the problem. All the terminals are along the $x$-axis. There are positive terminals at $0, 110, 111, 112$. And there are $2$ negative terminals at $99$ and $100$.

What’s the optimal solution to the problem?

(You don’t need to prove your solution is optimal.)

2. Formulate this problem as an LP. (Illustrate your LP by writing this for an example with two positive and two negative terminals.)
3. Write the dual of the LP in part (2.). (Again, write down this dual for the two terminal example in part (2.).)
4. Show how to compute an optimal solution to the dual problem of part (3.), without using a general LP solver.

Hint: see Seidel’s 2D algorithm for LPs

Problem 2

Suppose we are given a sequence of $n$ linear inequalities of the form $a_i x + b_i y \leq c_i$, where $x, y$ are variables and $a_i, b_i, c_i \in \mathbb{R}$. Collectively, these $n$ inequalities describe a convex polygon $P$ in the plane.

1. Describe a polynomial time algorithm to compute two interior-disjoint axis-aligned squares with maximum total perimeter that lie entirely inside $P$
2. Describe a polynomial time algorithm to compute two interior-disjoint axis-aligned rectangles with maximum total perimeter that lie entirely inside $P$

Problem 3