\documentclass{article} \input{6856-preamble} \usepackage{clrscode} \begin{document} \psetnum{10} \date{2005/04/22} \collab{Collaborators: $\set{\mathtt{sarahl}, \mathtt{gpickard}}$} \newcommand{\ones}{\left[ \begin{matrix} 1 & 1 & \cdots & 1 \end{matrix} \right]} \begin{pset} \begin{problem} \begin{subproblem} Let $A$ be a $n \times n$ doubly-stochastic matrix. Then consider the uniform distribution $\pi = \frac{1}{n} \ones{}$. Then consider $\pi' = \pi A$. This is the sum of the rows of $A$ divided by $n$. Since $A$ is doubly-stochastic, the sum of each column is 1, so the sum of the rows is $\ones$, and so $\pi' = \frac{1}{n} \ones = \pi$. So $\pi$ is a stationary distribution. \end{subproblem} \begin{subproblem} Suppose $p_{ij} = p_{ji}$. Then $A$ is a symmetric matrix by definition, so $A = A^T$. Each column of $A$ sums to 1 since it is stochastic, so by symmetry each row also sums to 1, and it is doubly-stochastic. By the previous subproblem, the uniform distribution is stationary. \end{subproblem} \begin{subproblem} Now suppose $\pi_i p_{ij} = \pi_j p_{ji}$, and consider the individual terms of $\pi' = \pi A$. By definition, $\pi'_i = \sum_{j = 1}^n \pi_j p_{ji}$. By the assumption, this is $\sum_{j = 1}^n \pi_i p_{ij} = \pi_i \sum_{j = 1}^n p_{ij}$. But since the matrix is stochastic, $\sum_{j = 1}^n p_{ij} = 1$, and so $\pi' = \pi$. So $\pi$ is a stationary distribution. \end{subproblem} \end{problem} \begin{problem} We give an algorithm for coloring the vertices of a 3-colorable graph with two colors such that no triangle has all three vertices colored the same. We begin by coloring the vertices randomly with equal probability for each color. Then we identify any triangles that have all three vertices the same color. If any exist, we select a random one and change the color of one of its vertices, selected at random; note that this change may cause some other triangle to now have all vertices the same color. We repeat this process until no such conflicting triangle exists. We analyze this process in the same way as the \textsf{2-SAT} algorithm. Suppose the colors in the 2-coloring are $c_1$ and $c_2$. Let $A$ be some 3-coloring of the graph, using colors $c_1$, $c_2$, and a third color $c_3$. Suppose that at some point during the execution of the algorithm, the assignment differs from $A$ at $i$ vertices. We select a random conflicting triangle that has all vertices the same color, and randomly change the color of one of them. Note that in the 3-coloring, each vertex has a different color. Assume \WLOG{} that in the 2-coloring assignment each vertex has color $c_1$ (the argument is symmetric in the other case), so we change some vertex to $c_2$. If the randomly selected vertex is the one colored $c_1$ in $A$, the new assignment differs at $i+1$ vertices; if it is the one colored $c_2$, it now differs at $i-1$ vertices; and if it is the one colored $c_3$, it still differs at $i$ vertices. All three possibilities occur with probability $\nicefrac13$. So we can view this process as a Markov chain on a line graph of $n$ vertices, with probability $\nicefrac13$ of increasing, decreasing, or staying at the same value, respectively. The process continues until no conflicting triangles remain. Certainly no conflicting triangles remain if the assignment is the same as $A$, i.e. $i = 0$; it can certainly be more, but this does not affect the runtime. The cover time for a line graph is $\bigO{n^2}$, so $\bigO{n^2}$ steps are required. \end{problem} \begin{problem} We model the path of a car in New York as a random walk over a connected non-bipartite undirected graph $G = (V,E)$ (note that non-bipartiteness can be achieved by adding reflexive edges to the graph). We consider two simultaneous random walks over the same graph, starting from potentially different locations. We can represent this as a random walk over a graph $\mathscr{G}$, where $\mathscr{G}$ has vertices given by the Cartesian product $V \times V$, and has an edge connecting vertices $\tup$ and $\tup$ if there exists both an edge from $u$ to $w$ and an edge from $v$ to $x$ in $E$. This models the two simultaneous random walks. Suppose the first random walk is at vertex $u$ and the second is at vertex $v$; this is represented as $\tup$ in $\mathscr{G}$. Then the first random walk moves to some neighbor $w$ of $u$ with probability $\frac{1}{d(u)}$ and similarly the second moves to some neighbor $x$ of $v$ with probability $\frac{1}{d(v)}$. The probability that both of these events take place is $\frac{1}{d(u)d(v)}$, which is also the probability of moving from $\tup$ to $\tup$ since $d(\tup) = d(u)d(v)$ since $\mathscr{G}$ is the Cartesian product of $G$. Note that $\mathscr{G}$ is also a non-bipartite graph: $G$ is non-bipartite, so it contains some odd-length cycle. This cycle can be translated into a cycle in $\mathscr{G}$: simply start at the state corresponding to both walks being at some point in the cycle, then follow the transitions corresponding to both walks traveling along the odd cycle until they reach their starting locations. Moreover, $\mathscr{G}$ is a connected graph. Consider any pair of points $\tup$, $\tup$ in $\mathscr{G}$. Since $G$ is connected, there exist paths from $u$ to $w$ and from $v$ to $x$ in $G$. If both paths have the same length, we can translate them into a path in $\mathscr{G}$ in the obvious way. Otherwise, one of the paths is longer than the other, so we will need to lengthen the shorter path. If the difference in path lengths is even, we can simply repeatedly travel back and forth between two adjacent edges to increase the path lengths so they are even. Otherwise, if the difference in path lengths is odd, we take a detour through an odd-length cycle in the graph (which we proved existed); this makes the length difference even, reducing it to the previous case. We can do this for any pair $\tup$, $\tup$, so $\mathscr{G}$ is connected. Now we have shown that two random walks on $G$ can be modeled as a single random walk on a connected non-bipartite graph $\mathscr{G}$. Therefore, as shown in class, the expected cover time of $\mathscr{G}$ is $\bigO{\abs{V(\mathscr{G})}^3}$. Note that the number of vertices in $\mathscr{G}$ is the square of that in $G$. There exist states where both cars are in the same location, so the expected time until a collision is bounded by this time, which is $\bigO{n^6}$. \end{problem} \begin{problem} Consider the following directed graph, which consists of a chain of $n$ vertices with directed edges between adjacent vertices, and directed edges from each vertex back to the first vertex in the chain: \begin{center} \includegraphics[scale=.5]{ps10-4} \end{center} This graph is clearly strongly connected, but its cover time is not polynomial in $n$. Suppose we start at vertex $1$. To reach vertex $n$, we must choose the forward edges at each vertex, rather than the edge back to vertex 1. This occurs with probability $\left(\nicefrac12\right)^n$, since each choice happens with equal probability. Thus, the expected number of tries to reach vertex $n$, and so a bound on the expected cover time, is $\bigO{2^n}$. \end{problem} \begin{problem} Submitted separately. \end{problem} \begin{problem} \begin{subproblem} Lots of interesting topics: hashing, shortest paths, etc. Sampling was not as interesting, but obviously very useful. \end{subproblem} \begin{subproblem} No major complaints about content. Embeddings didn't make much sense to me, but that might have had more to do with how busy I was that week. Math for the linear-programming sampling algorithm was painful, but the algorithm was interesting. \end{subproblem} \begin{subproblem} Seemed like a good broad overview, but I'm not familiar enough with other topics in randomized algorithms to know what else should have been covered. \end{subproblem} \end{problem} \end{pset} \end{document} % LocalWords: colorable