高级算法 (Fall 2023)/Problem Set 2: Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
Zouzongrui (talk | contribs)
Zouzongrui (talk | contribs)
Line 44: Line 44:
In this problem, you will analyze the MCMC sampler over independent sets of fixed size. Given graph <math>G=(V,E)</math> with maximum degree <math>\Delta</math>, let <math>I_k</math> be the set of all independent sets in <math>G</math> of size <math>k</math>. Consider a random walk <math>\{X_i\}_{(i\geq 0)}</math> on <math>I_k</math> defined by the following process:
In this problem, you will analyze the MCMC sampler over independent sets of fixed size. Given graph <math>G=(V,E)</math> with maximum degree <math>\Delta</math>, let <math>I_k</math> be the set of all independent sets in <math>G</math> of size <math>k</math>. Consider a random walk <math>\{X_i\}_{(i\geq 0)}</math> on <math>I_k</math> defined by the following process:


(i) choose a vertex <math>v\in X_t</math> uniformly at random and a vertex <math>w\in V</math> uniformly at random
* choose a vertex <math>v\in X_t</math> uniformly at random and a vertex <math>w\in V</math> uniformly at random


(ii) if <math>w\notin X_t</math> and <math>X_t - \{v\} + \{w\}</math> is independent, <math>X_{t+1} = X_t - \{v\} + \{w\}</math>
* if <math>w\notin X_t</math> and <math>X_t - \{v\} + \{w\}</math> is independent, <math>X_{t+1} = X_t - \{v\} + \{w\}</math>


(iii) otherwise, <math>X_{t+1} = X_t</math>
* otherwise, <math>X_{t+1} = X_t</math>


* Show that the Markov chain <math>\{X_i\}_{(i\geq 0)}</math> is irreducible and aperiodic.
(1) Show that the Markov chain <math>\{X_i\}_{(i\geq 0)}</math> is irreducible and aperiodic.
* Show that the stationary distribution of <math>\{X_i\}_{(i\geq 0)}</math> is the uniform distribution over <math>I_k</math>.
(2) Show that the stationary distribution of <math>\{X_i\}_{(i\geq 0)}</math> is the uniform distribution over <math>I_k</math>.
* Use coupling argument to show that if <math>k\leq \frac{n}{3\Delta + 3}</math>, then the <math>\epsilon</math>-mixing time of <math>\{X_i\}_{(i\geq 0)}</math> is a polynomial in <math>n</math> and <math>\log(1/\epsilon)</math>.
(3) Use coupling argument to show that if <math>k\leq \frac{n}{3\Delta + 3}</math>, then the <math>\epsilon</math>-mixing time of <math>\{X_i\}_{(i\geq 0)}</math> is a polynomial in <math>n</math> and <math>\log(1/\epsilon)</math>.

Revision as of 07:38, 24 November 2023

  • 本次作业每个Problem分值10分,满分80分。
  • 每道题目的解答都要有完整的解题过程,中英文不限。
  • 我们推荐大家使用LaTeX, markdown等对作业进行排版。

Problem 1 (Adjacency matrix)

Let [math]\displaystyle{ A }[/math] be the adjacency matrix of an undirected connected graph [math]\displaystyle{ G }[/math], and [math]\displaystyle{ \alpha_1 }[/math] be its largest eigenvalue.

  • [Lowerbounding [math]\displaystyle{ \alpha_1 }[/math]] We proved [math]\displaystyle{ \alpha_1 \le d_{\mathrm{max}} }[/math] in class. Show that [math]\displaystyle{ \alpha_1 \ge d_{\mathrm{avg}} }[/math] where [math]\displaystyle{ d_{\mathrm{avg}}:=\frac{2|E|}{|V|} }[/math] is the average degree of the graph.
  • [Monotonicity of the spectrum] Let [math]\displaystyle{ A' }[/math] be the adjacency matrix of any subgraph of [math]\displaystyle{ A }[/math] produced by deleting vertices, and let [math]\displaystyle{ \alpha_1' }[/math] be the largest eigenvalue of [math]\displaystyle{ A' }[/math]. Show that [math]\displaystyle{ \alpha'_1\leq \alpha_1 }[/math].
  • [Coloring number] The chromatic number [math]\displaystyle{ \chi(G) }[/math] of a graph is the smallest number of colors needed to color the vertices of [math]\displaystyle{ G }[/math] so that no two adjacent vertices share same color. Prove that [math]\displaystyle{ \chi(G) \le \lfloor \alpha_1 \rfloor +1 }[/math].

Problem 2 (Graph Laplacian)

  • [Spectrum of special graphs] Find eigenvalues of the Laplacian matrices of the following graphs:
    1. The complete graph with [math]\displaystyle{ n }[/math] vertices.
    2. The star graph with [math]\displaystyle{ n }[/math] vertices.
  • [Number of connected points] Let [math]\displaystyle{ G }[/math] be a connected graph, and [math]\displaystyle{ \lambda_1\le \lambda_2 \le \ldots \le \lambda_n }[/math] be the eigenvalues of its normalized Laplacian matrix [math]\displaystyle{ \mathcal{L} }[/math]. Prove that [math]\displaystyle{ \lambda_k = 0 }[/math] if and only if [math]\displaystyle{ G }[/math] has at least [math]\displaystyle{ k }[/math] components.
  • [Lowerbounding [math]\displaystyle{ \lambda_2 }[/math]] Let [math]\displaystyle{ G }[/math] be an undirected graph whose Laplacian is [math]\displaystyle{ L }[/math], with second-smallest eigenvalue [math]\displaystyle{ \lambda_2 }[/math]. We know that if [math]\displaystyle{ G }[/math] is connected then [math]\displaystyle{ \lambda_2\gt 0 }[/math]. Prove that [math]\displaystyle{ \lambda_2 \geq 1/O(rn) \geq 1/O(n^2) }[/math] by analyzing the Rayleigh quotient on all test vectors [math]\displaystyle{ x\perp \mathbf{1} }[/math]. Here, [math]\displaystyle{ r }[/math] is the *diameter* of the graph (i.e. the maximum shortest-path distance between pairs of vertices in the graph). Further, show that when [math]\displaystyle{ G }[/math] is simple and [math]\displaystyle{ d }[/math]-regular, we have [math]\displaystyle{ \lambda_2 \geq d/O(n^2) }[/math].

Problem 3 (Cheeger's inequality)

Problem 4 (Random walk on graph)

Problem 5 (Hitting time, commute time)

Problem 6 (Electrical network)

Problem 7 (Expander mixing lemma)

Problem 8 (MCMC and coupling)

In this problem, you will analyze the MCMC sampler over independent sets of fixed size. Given graph [math]\displaystyle{ G=(V,E) }[/math] with maximum degree [math]\displaystyle{ \Delta }[/math], let [math]\displaystyle{ I_k }[/math] be the set of all independent sets in [math]\displaystyle{ G }[/math] of size [math]\displaystyle{ k }[/math]. Consider a random walk [math]\displaystyle{ \{X_i\}_{(i\geq 0)} }[/math] on [math]\displaystyle{ I_k }[/math] defined by the following process:

  • choose a vertex [math]\displaystyle{ v\in X_t }[/math] uniformly at random and a vertex [math]\displaystyle{ w\in V }[/math] uniformly at random
  • if [math]\displaystyle{ w\notin X_t }[/math] and [math]\displaystyle{ X_t - \{v\} + \{w\} }[/math] is independent, [math]\displaystyle{ X_{t+1} = X_t - \{v\} + \{w\} }[/math]
  • otherwise, [math]\displaystyle{ X_{t+1} = X_t }[/math]

(1) Show that the Markov chain [math]\displaystyle{ \{X_i\}_{(i\geq 0)} }[/math] is irreducible and aperiodic. (2) Show that the stationary distribution of [math]\displaystyle{ \{X_i\}_{(i\geq 0)} }[/math] is the uniform distribution over [math]\displaystyle{ I_k }[/math]. (3) Use coupling argument to show that if [math]\displaystyle{ k\leq \frac{n}{3\Delta + 3} }[/math], then the [math]\displaystyle{ \epsilon }[/math]-mixing time of [math]\displaystyle{ \{X_i\}_{(i\geq 0)} }[/math] is a polynomial in [math]\displaystyle{ n }[/math] and [math]\displaystyle{ \log(1/\epsilon) }[/math].