随机算法 (Fall 2011)/Coupling and 组合数学 (Fall 2011)/Counting and existence: Difference between pages

From TCS Wiki
(Difference between pages)
Jump to navigation Jump to search
VisualWikitext
imported>WikiSysop
(Created page with '=Coupling of Two Distributions= Coupling is a powerful proof technique in probability theory. It allows us to compare two unrelated variables (or processes) by forcing them to sh…')
 
imported>Etone
 
Line 1: Line 1:
=Coupling of Two Distributions=
== Cayley's Formula ==
Coupling is a powerful proof technique in probability theory. It allows us to compare two unrelated variables (or processes) by forcing them to share some randomness.
We now present a theorem of the number of labeled trees on a fixed number of vertices. It is due to [http://en.wikipedia.org/wiki/Arthur_Cayley Cayley] in 1889. The theorem is often referred by the name [http://en.wikipedia.org/wiki/Cayley's_formula Cayley's formula].
{{Theorem|Definition (coupling)|
 
:Let <math>p</math> and <math>q</math> be two probability distributions over <math>\Omega</math>. A probability distribution <math>\mu</math> over <math>\Omega\times\Omega</math> is said to be a '''coupling''' if its marginal distributions are <math>p</math> and <math>q</math>; that is
{{Theorem|Cayley's formula for trees|
::<math>
: There are <math>n^{n-2}</math> different trees on <math>n</math> distinct vertices.
\begin{align}
}}
p(x) &=\sum_{y\in\Omega}\mu(x,y);\\
 
q(x) &=\sum_{y\in\Omega}\mu(y,x).
The theorem has several proofs. Classical methods include the bijection which encodes a tree by a [http://en.wikipedia.org/wiki/Pr%C3%BCfer_sequence Prüfer code], through the [http://en.wikipedia.org/wiki/Kirchhoff's_matrix_tree_theorem Kirchhoff's matrix tree theorem], and by double counting.
\end{align}
 
</math>
===  Prüfer code ===
{{Theorem| Prüfer code (encoder)|
:'''Input''': A tree <math>T</math> of <math>n</math> distinct vertices, labeled by <math>0,1,\ldots,n-1</math>.
:
:let <math>T_1=T</math>;
:for <math>i=1</math> to <math>n-2</math>, do
::let <math>u_i</math> be the leaf in <math>T_i</math> with the smallest label, and <math>v_i</math> be its neighbor;
::let <math>T_{i+1}</math> be the new tree obtained from deleting the leaf <math>u_i</math> from <math>T_i</math>;
:end
:return <math>(v_1,v_2,\ldots,v_{n-2})</math>;
}}
}}


The interesting case is when <math>X</math> and <math>Y</math> are not independent. In particular, we want the probability that <math>X=Y</math> to be as large as possible, yet still maintaining the respective marginal distributions <math>p</math> and <math>q</math>. When <math>p</math> and <math>q</math> are different it is inevitable that <math>X\neq Y</math> with some probability, but how small this probability can be, that is, how well two distributions can be coupled? The following coupling lemma states that this is determined by the total variation distance between the two distributions.


{{Theorem|Lemma (coupling lemma)|
{{Theorem| Prüfer code (decoder)|
:Let <math>p</math> and <math>q</math> be two probability distributions over <math>\Omega</math>.
:'''Input''': A tuple <math>(v_1,v_2,\ldots,v_{n-2})\in[n]^{n-2}</math>.
# For any coupling <math>(X,Y)</math> of <math>p</math> and <math>q</math>, it holds that <math>\Pr[X\neq Y]\ge\|p-q\|_{TV}</math>.
# There exists a coupling <math>(X,Y)</math> of <math>p</math> and <math>q</math> such that <math>\Pr[X\neq Y]=\|p-q\|_{TV}</math>.
}}
}}
{{Proof|
 
;1.  
=== Double counting ===
Suppose <math>(X,Y)</math> follows the distribution <math>\mu</math> over <math>\Omega\times\Omega</math>. Due to the definition of coupling,
We now present a proof of the Cayley's formula by double counting, which is considered by the [http://en.wikipedia.org/wiki/Proofs_from_THE_BOOK Proofs from THE BOOK] "the most beautiful of them all".
:<math>
{{Prooftitle|Proof of Cayley's formula by double counting|
\begin{align}
(Due to Pitman 1999)
p(x) =\sum_{y\in\Omega}\mu(x,y) &\quad\text{and } &q(x) =\sum_{y\in\Omega}\mu(y,x).
 
\end{align}
Let <math>T_n</math> be the number of different trees defined on <math>n</math> distinct vertices.
</math>
 
Then for any <math>z\in\Omega</math>, <math>\mu(z,z)\le\min\{p(z),q(z)\}</math>, thus
A '''rooted tree''' is a tree with a special vertex. That is, one of the <math>n</math> vertices is marked as the "root" of the tree. A rooted tree defines a natural direction of all edges, such that an edge <math>uv</math> of the tree is directed from <math>u</math> to <math>v</math> if <math>u</math> is before <math>v</math> along the unique path from the root.
:<math>
 
\begin{align}
We count the number of different ''sequences'' of directed edges that can be added to an empty graph on <math>n</math> vertices to form from it a ''rooted'' tree. We note that such a sequence can be formed in two ways:
\Pr[X=Y]
# Starting with an unrooted tree, choose one of its vertices as root, and fix an total order of edges to specify the order in which the edges are added.
&=
# Starting from an empty graph, add the edges one by one in steps.
\sum_{z\in\Omega}\mu(z,z)
 
\le\sum_{z\in\Omega}\min\{p(z),q(z)\}.
In the first method, we pick one of the <math>T_n</math> unrooted trees, choose one of the <math>n</math> vertices as the root, and pick one of the <math>(n-1)!</math> total orders of the <math>n-1</math> edges. This gives us <math>T_nn(n-1)!=T_nn!</math> ways.
\end{align}
 
</math>
In the second method, we consider the number of choices in one step, and multiply the numbers of choices in all steps. This is done as follows.
Therefore,
 
:<math>
Given a sequence of ''adding'' <math>n-1</math> edges to an empty graph to form a rooted tree, we reverse this sequence and get a sequence of ''removing'' edges one by one from the final rooted tree until no edge left. We observe that:
\begin{align}
* At first, we remove an edge from the rooted tree. Suppose that the root of the tree is <math>r</math>, and the removed directed edge is <math>(u,v)</math>.  After removing <math>(u,v)</math>, the original rooted tree is disconnected into two rooted trees, one rooted at <math>r</math> and the other rooted at <math>v</math>.
\Pr[X\neq Y]
* After removing <math>k-1</math> edges, there are <math>k</math> rooted trees. In the <math>k</math>th step, a directed edge <math>(u,v)</math> in the current forest is removed and the tree containing <math>(u,v)</math> is disconnected into two trees, one rooted at the old root of that tree, and the other rooted at <math>v</math>.
&\ge
 
1-\sum_{z\in\Omega}\min\{p(z),q(z)\}\\
We now again reverse the above procedure, and consider the sequence of adding directed edges to an empty graph to form a rooted tree.
&=\sum_{z\in\Omega}(p(z)-\min\{p(z),q(z)\})\\
* At first, we have <math>n</math> rooted trees, each of 0 edge (<math>n</math> isolated vertices).
&=\sum_{z\in\Omega\atop p(z)>q(z)}(p(z)-q(z))\\
* After adding <math>n-k</math> edges, there are <math>k</math> rooted trees. Denoting the directed edge added next as <math>(u,v)</math>. As observed above, <math>u</math> can be any one of the <math>n</math> vertices; but <math>v</math> must be the root of one of the <math>k</math> trees, except the tree which contains <math>u</math>. There are <math>n(k-1)</math> choices of such <math>(u,v)</math>.
&=\frac{1}{2}\sum_{z\in\Omega}|p(z)-q(z)|\\
Multiplying the numbers of choices in all steps, the number of sequences of adding directed edges to an empty graph to form a rooted tree is given by
&=\|p-q\|_{TV}.
:<math>\prod_{k=2}^nn(k-1)=n^{n-2}n!</math>.
\end{align}
 
</math>
By the principle of double counting, counting the same thing by different methods yield the same result.
;2.
:<math>T_nn!=n^{n-2}n!</math>,
We can couple <math>X</math> and <math>Y</math> so that for each <math>z\in\Omega</math>, <math>X=Y=z</math> with probability <math>\min\{p(z),q(z)\}</math>. The remaining follows as above.
which gives that <math>T_n=n^{n-2}</math>.
}}
}}


The proof is depicted by the following figure, where the curves are the probability density functions for the two distributions <math>p</math> and <math>q</math>, the colored area is the diference between the two distribution, and the "lower envelope" (the red line) is the <math>\min\{p(x), q(x)\}</math>.
== Existence by Counting ==
=== Shannon's circuit lower bound===
This is a fundamental problem in in Computer Science.


:[[image:Coupling.png|350px]]
A '''boolean function''' is a function in the form <math>f:\{0,1\}^n\rightarrow \{0,1\}</math>.


===Monotonicity of <math>\Delta_x(t)</math>===
[http://en.wikipedia.org/wiki/Boolean_circuit Boolean circuit] is a mathematical model of computation.
Formally, a boolean circuit is a directed acyclic graph. Nodes with indegree zero are input nodes, labeled <math>x_1, x_2, \ldots , x_n</math>. A circuit has a unique node with outdegree zero, called the output node. Every other node is a gate. There are three types of gates: AND, OR (both with indegree two), and NOT (with indegree one).


Consider a Markov chain on state space <math>\Omega</math>. Let <math>\pi</math> be the stationary distribution, and <math>p_x^{(t)}</math> be the distribution after <math>t</math> steps when the initial state is <math>x</math>. Recall that <math>\Delta_x(t)=\|p_x^{(t)}-\pi\|_{TV}</math> is the distance to stationary distribution <math>\pi</math> after <math>t</math> steps, started at state <math>x</math>.
Computations in Turing machines can be simulated by circuits, and any boolean function in '''P''' can be computed by a circuit with polynomially many gates. Thus, if we can find a function in '''NP''' that cannot be computed by any circuit with polynomially many gates, then '''NP'''<math>\neq</math>'''P'''.


We will show that <math>\Delta_x(t)</math> is non-decreasing in <math>t</math>. That is, for a Markov chain, the variation distance to the stationary distribution monotonically decreases as time passes. Although this is rather intuitive at the first glance, the proof is nontrivial. A brute force (algebraic) proof can be obtained by analyze the change to the 1-norm of <math>p_x^{(t)}-\pi</math> by multiplying the transition matrix <math>P</math>. The analysis uses eigen decomposition. We introduce a cleverer proof using coupling.
The following theorem due to Shannon says that functions with exponentially large circuit complexity do exist.


{{Theorem|Proposition|
{{Theorem
:<math>\Delta_x(t)</math> is non-decreasing in <math>t</math>.
|Theorem (Shannon 1949)|
:There is a boolean function <math>f:\{0,1\}^n\rightarrow \{0,1\}</math> with circuit complexity greater than <math>\frac{2^n}{3n}</math>.
}}
}}
{{Proof|
{{Proof|  
Let <math>X_0=x</math> and <math>Y_0</math> follow the stationary distribution <math>\pi</math>. Two chains <math>X_0,X_1,X_2,\ldots</math> and <math>Y_0,Y_1,Y_2,\ldots</math> can be defined by the initial distributions <math>X_0</math> and <math>Y_0</math>. The distributions of <math>X_t</math> and <math>Y_t</math> are <math>p_x^{(t)}</math> and <math>\pi</math>, respectively.
We first count the number of boolean functions <math>f:\{0,1\}^n\rightarrow \{0,1\}</math>. There are <math>2^{2^n}</math> boolean functions <math>f:\{0,1\}^n\rightarrow \{0,1\}</math>.
 
Then we count the number of boolean circuit with fixed number of gates.
Fix an integer <math>t</math>, we count the number of circuits with <math>t</math> gates. By the [http://en.wikipedia.org/wiki/De_Morgan's_laws De Morgan's laws], we can assume that all NOTs are pushed back to the inputs. Each gate has one of the two types (AND or OR), and has two inputs. Each of the inputs to a gate is either a constant 0 or 1, an input variable <math>x_i</math>, an inverted input variable <math>\neg x_i</math>, or the output of another gate; thus, there are at most <math>2+2n+t-1</math> possible gate inputs. It follows that the number of circuits with <math>t</math> gates is at most <math>2^t(t+2n+1)^{2t}</math>.  


For any fixed <math>t</math>, we can couple <math>X_t</math> and <math>Y_t</math> such that <math>\Pr[X\neq Y]=\|p_x^{t}-\pi\|_{TV}=\Delta_x(t)</math>. Due to the Coupling Lemma, such coupling exists. We then define a coupling between <math>X_{t+1}</math> and <math>Y_{t+1}</math> as follows.
If <math>t=2^n/3n</math>, then
* If <math>X_t=Y_t</math>, then <math>X_{t+1}=Y_{t+1}</math> following the transition matrix of the Markov chain.
* Otherwise, do the transitions <math>X_t\rightarrow X_{t+1}</math> and <math>Y_t\rightarrow Y_{t+1}</math> independently, following the transitin matrix.
It is easy to see that the marginal distributions of <math>X_{t+1}</math> and <math>Y_{t+1}</math> both follow the original Markov chain, and
:<math>
:<math>
\Pr[X_{t+1}\neq Y_{t+1}]\le \Pr[X_t\neq Y_{t}].
\frac{2^t(t+2n+1)^{2t}}{2^{2^n}}=o(1)<1,</math>     thus, <math>2^t(t+2n+1)^{2t} < 2^{2^n}.</math>
</math>
 
In conclusion, it holds that
Each boolean circuit computes one boolean function. Therefore, there must exist a boolean function <math>f</math> which cannot be computed by any circuits with <math>2^n/3n</math> gates.
:<math>
\Delta_x(t+1)=\|p_x^{(t+1)}-\pi\|_{TV}\le\Pr[X_{t+1}\neq Y_{t+1}]\le \Pr[X_t\neq Y_{t}]=\Delta_x(t),
</math>
where the first inequality is due to the easy direction of the Coupling Lemma.
}}
}}


=Rapid Mixing by Coupling=
Note that by Shannon's theorem, not only there exists a boolean function with exponentially large circuit complexity, but ''almost all'' boolean functions have exponentially large circuit complexity.
Consider an ergodic (irreducible and aperiodic) Markov chain on state space <math>\Omega</math>. We want to upper bound its mixing time. The coupling technique for bounding the mixing time can be sumerized as follows:
:Consider two random walks starting at state <math>x</math> and <math>y</math> in <math>\Omega</math>. Each individual walk follows the transition rule of the original Markov chain. But the two random walks may be "''coupled''" in some way, that is, may be correlated with each other. A key observation is that for any such coupling, it always holds that
::<math>\Delta(t)
\le\max_{x,y\in\Omega}\Pr[\text{ the two } \mathit{coupled} \text{ random walks started at }x,y\text{ have not met by time }t]
</math>
:where we recall that <math>\Delta(t)=\max_{x\in\Omega}\|p_x^{(t)}-\pi\|_{TV}</math>.


{{Theorem|Definition (coupling of Markov chain)|
=== Double counting ===
:A '''coupling''' of a Markov chain with state space <math>\Omega</math> and transition matrix <math>P</math>, is a Markov chain <math>(X_t,Y_t)</math> with state space <math>\Omega\times\Omega</math>, satisfying
The double counting principle states the following obvious fact: if the elements of a set are counted in two different ways, the answers are the same.
# each of <math>X_t</math> and <math>Y_t</math> viewed in isolation is a faithful copy of the original Markov chain, i.e.
;Handshaking lemma
#:<math>\Pr[X_{t+1}=v\mid X_t=u]=\Pr[Y_{t+1}=v\mid Y_{t}=u]=P(u,v)</math>;
The following lemma is a standard demonstration of double counting.
# once <math>X_t</math> and <math>Y_t</math> reaches the same state, they make identical moves ever since, i.e.
{{Theorem|Handshaking Lemma|
#:<math>X_{t+1}=Y_{t+1}</math> if <math>X_t=Y_t</math>.
:At a party, the number of guests who shake hands an odd number of times is even.
}}
}}


{{Theorem|Lemma (coupling lemma for Markov chains)|
We model this scenario as an undirected graph <math>G(V,E)</math> with <math>|V|=n</math> standing for the <math>n</math> guests. There is an edge <math>uv\in E</math> if <math>u</math> and <math>v</math> shake hands. Let <math>d(v)</math> be the degree of vertex <math>v</math>, which represents the number of times that <math>v</math> shakes hand. The handshaking lemma states that in any undirected graph, the number of vertices whose degrees are odd is even. It is sufficient to show that the sum of odd degrees is even.
:Let <math>(X_t,Y_t)</math> be a coupling of a Markov chain <math>M</math> with state space <math>\Omega</math>. Then <math>\Delta(t)</math> for <math>M</math> is bounded by
 
::<math>\Delta(t)
The handshaking lemma is a direct consequence of the following lemma, which is proved by Euler in his 1736 paper on [http://en.wikipedia.org/wiki/Seven_Bridges_of_K%C3%B6nigsberg Seven Bridges of Königsberg] that began the study of graph theory.
\le\max_{x,y\in\Omega}\Pr[X_t\neq Y_t\mid X_0=x,Y_0=y]</math>.
 
{{Theorem|Lemma (Euler 1736)|
:<math>\sum_{v\in V}d(v)=2|E|</math>
}}
}}
{{Proof|
{{Proof|
Due to the coupling lemma (for probability distributions),
We count the number of '''directed''' edges. A directed edge is an ordered pair <math>(u,v)</math> such that <math>\{u,v\}\in E</math>. There are two ways to count the directed edges.
:<math>
 
\Pr[X_t\neq Y_t\mid X_0=x,Y_0=y]
First, we can enumerate by edges. Pick every edge <math>uv\in E</math> and apply two directions <math>(u,v)</math> and <math>(v,u)</math> to the edge. This gives us <math>2|E|</math> directed edges.
\ge
 
\|p_x^{(t)}-p_y^{(t)}\|_{TV},
On the other hand, we can enumerate by vertices. Pick every vertex <math>v\in V</math> and for each of its <math>d(v)</math> neighbors, say <math>u</math>, generate a directed edge <math>(v,u)</math>. This gives us <math>\sum_{v\in V}d(v)</math> directed edges.
</math>
where <math>p_x^{(t)},p_y^{(t)}</math> are distributions of the Markov chain <math>M</math> at time <math>t</math>, started at states <math>x, y</math>.


Therefore,
It is obvious that the two terms are equal, since we just count the same thing twice with different methods. The lemma follows.
:<math>
\begin{align}
\Delta(t)
&=
\max_{x\in\Omega}\|p_x^{(t)}-\pi\|_{TV}\\
&\le
\max_{x,y\in\Omega}\|p_x^{(t)}-p_y^{(t)}\|_{TV}\\
&\le
\max_{x,y\in\Omega}\Pr[X_t\neq Y_t\mid X_0=x,Y_0=y].
\end{align}
</math>
}}
}}


The handshaking lemma is implied directly by the above lemma, since the sum of even degrees is even.


{{Theorem|Corollary|
== The Pigeonhole Principle ==
:Let <math>(X_t,Y_t)</math> be a coupling of a Markov chain <math>M</math> with state space <math>\Omega</math>. Then <math>\tau(\epsilon)</math> for <math>M</math> is bounded as follows:
The '''pigeonhole principle''' states the following "obvious" fact:
::<math>\max_{x,y\in\Omega}\Pr[X_t\neq Y_t\mid X_0=x,Y_0=y]\le \epsilon\quad\Longrightarrow\quad\tau(\epsilon)\le t</math>.
:''<math>n+1</math> pigeons cannot sit in <math>n</math> holes so that every pigeon is alone in its hole.''
This is one of the oldest '''non-constructive''' principles: it states only the ''existence'' of a pigeonhole with more than one pigeons and says nothing about how to ''find'' such a pigeonhole.
 
The general form of pigeonhole principle, also known as the '''averaging principle''', is stated as follows.
{{Theorem|Generalized pigeonhole principle|
:If a set consisting of more than <math>mn</math> objects is partitioned into <math>n</math> classes, then some class receives more than <math>m</math> objects.
}}
}}


=== Geometric convergence ===
=== Monotonic subsequences ===
Consider a Markov chain on state space <math>\Omega</math>. Let <math>\pi</math> be the stationary distribution, and <math>p_x^{(t)}</math> be the distribution after <math>t</math> steps when the initial state is <math>x</math>. Recall that
Let <math>(a_1,a_2,\ldots,a_n)</math> be a sequence of <math>n</math> distinct real numbers. A '''subsequence''' is a sequence of distinct terms of <math>(a_1,a_2,\ldots,a_n)</math> appearing in the same order in which they appear in <math>(a_1,a_2,\ldots,a_n)</math>. Formally, a subsequence of <math>(a_1,a_2,\ldots,a_n)</math> is an <math>(a_{i_1},a_{i_2},\ldots,a_{i_k})</math>, with <math>i_1<i_2<\cdots<i_k</math>.
*<math>\Delta_x(t)=\|p_x^{(t)}-\pi\|_{TV}</math>;
*<math>\Delta(t)=\max_{x\in\Omega}\Delta_x(t)</math>;
*<math>\tau_x(\epsilon)=\min\{t\mid\Delta_x(t)\le\epsilon\}</math>;
* <math>\tau(\epsilon)=\max_{x\in\Omega}\tau_x(\epsilon)</math>;
*<math>\tau_{\mathrm{mix}}=\tau(1/2\mathrm{e})\,</math>.


We prove that
A sequence <math>(a_1,a_2,\ldots,a_n)</math> is '''increasing''' if <math>a_1<a_2<\cdots<a_n</math>, and '''decreasing''' if <math>a_1>a_2>\cdots>a_n</math>.
{{Theorem|Proposition|
 
# <math>\Delta(k\cdot\tau_{\mathrm{mix}})\le \mathrm{e}^{-k}</math> for any integer <math>k\ge1</math>.
We are interested in the ''longest'' increasing and decreasing subsequences of an <math>a_1<a_2<\cdots<a_n</math>. It is intuitive that the length of both the longest increasing subsequence and the longest decreasing subsequence cannot be small simultaneously. A famous result of Erdős and Szekeres formally justifies this intuition. This is one of the first results in extremal combinatorics, published in the influential 1935 paper of Erdős and Szekeres.
#<math>\tau(\epsilon)\le\tau_{\mathrm{mix}}\cdot\left\lceil\ln\frac{1}{\epsilon}\right\rceil</math>.
 
{{Theorem|Theorem (Erdős-Szekeres 1935)|
:A sequence of more than <math>mn</math> different real numbers must contain either an increasing subsequence of length <math>m+1</math>, or a decreasing subsequence of length <math>n+1</math>.
}}
}}
{{Proof|
{{Proof|(due to Seidenberg 1959)
;1.
Let <math>(a_1,a_2,\ldots,a_{N})</math> be the original sequence of <math>N>mn</math> distinct real numbers. Associate each <math>a_i</math> a pair <math>(x_i,y_i)</math>, defined as:
We denote that <math>\tau=\tau_{\mathrm{mix}}\,</math>. We construct a coupling of the Markov chain as follows. Suppose <math>t=k\tau</math> for some integer <math>k</math>.  
*<math>x_i</math>: the length of the longest ''increasing'' subsequence ''ending'' at <math>a_i</math>;
* If <math>X_t=Y_t</math> then <math>X_{t+i}=Y_{t+i}</math> for <math>i=1,2,\ldots,\tau</math>.
*<math>y_i</math>: the length of the longest ''decreasing'' subsequence ''starting'' at <math>a_i</math>.
* For the case that <math>X_t=u, Y_t=v</math> for some <math>u\neq v</math>, we couple the <math>X_{t+\tau}</math> and <math>Y_{t+\tau}</math> so that <math>\Pr[X_{t+\tau}\neq Y_{t+\tau}\mid X_t=u,Y_t=v]=\|p_u^{(t)}-p_v^{(t)}\|_{TV}</math>. Due to the Coupling Lemma, such coupling does exist.
A key observation is that <math>(x_i,y_i)\neq (x_j,y_j)</math> whenever <math>i\neq j</math>. This is proved as follows:
: '''Case 1:''' If <math>a_i<a_j</math>, then the longest increasing subsequence ending at <math>a_i</math> can be extended by adding on <math>a_j</math>, so <math>x_i<x_j</math>.
: '''Case 2:'''  If <math>a_i>a_j</math>, then the longest decreasing subsequence starting at <math>a_j</math> can be preceded by <math>a_i</math>, so <math>y_i>y_j</math>.
Now we put <math>N</math> "pigeons" <math>a_1,a_2,\ldots,a_N</math> into "pigeonholes" <math>\{1,2,\ldots,N\}\times\{1,2,\ldots,N\}</math>, such that <math>a_i</math> is put into hole <math>(x_i,y_i)</math>, with at most one pigeon per each hole (since different <math>a_i</math> has different <math>(x_i,y_i)</math>).
 
The number of pigeons is <math>N>mn</math>. Due to pigeonhole principle, there must be a pigeon which is outside the region <math>\{1,2,\ldots,m\}\times\{1,2,\ldots,n\}</math>, which implies that there exists an <math>a_i</math> with either <math>x_i>m</math> or <math>y_i>n</math>. Due to our definition of <math>(x_i,y_i)</math>, there must be either an increasing subsequence of length <math>m+1</math>, or a decreasing subsequence of length <math>n+1</math>.
}}
 
=== Dirichlet's approximation ===
Let <math>x</math> be an irrational number. We now want to approximate <math>x</math> be a rational number (a fraction).


For any <math>u,v\in\Omega</math> that <math>u\neq v</math>,
Since every real interval <math>[a,b]</math> with <math>a<b</math> contains infinitely many rational numbers, there must exist rational numbers arbitrarily close to <math>x</math>. The trick is to let the denominator of the fraction sufficiently large.
:<math>\begin{align}
\Pr[X_{t+\tau}\neq Y_{t+\tau}\mid X_t=u,Y_t=v]
&=\|p_u^{(t)}-p_v^{(t)}\|_{TV}\\
&\le \|p_u^{(\tau)}-\pi\|_{TV}+\|p_v^{(\tau)}-\pi\|_{TV}\\
&= \Delta_u(\tau)+\Delta_v(\tau)\\
&\le \frac{1}{\mathrm{e}}.
\end{align}
</math>
Thus <math>\Pr[X_{t+\tau}\neq Y_{t+\tau}\mid X_t\neq Y_t]\le \frac{1}{\mathrm{e}}</math> by the law of total probability. Therefore, for any <math>x,y\in\Omega</math>,
:<math>
\begin{align}
&\quad\, \Pr[X_{t+\tau}\neq Y_{t+\tau}\mid X_0=x,Y_0=y]\\
&=
\Pr[X_{t+\tau}\neq Y_{t+\tau}\mid X_t\neq Y_t]\cdot \Pr[X_{t}\neq Y_{t}\mid X_0=x,Y_0=y]\\
&\le \frac{1}{\mathrm{e}}\Pr[X_{t}\neq Y_{t}\mid X_0=x,Y_0=y].
\end{align}
</math>
Then by induction,
:<math>
\Pr[X_{k\tau}\neq Y_{k\tau}\mid X_0=x,Y_0=y]\le \mathrm{e}^{-k},
</math>
and this holds for any <math>x,y\in\Omega</math>. By the Coupling Lemma for Markov chains, this means <math>\Delta(k\tau_{\mathrm{mix}})=\Delta(k\tau)\le\mathrm{e}^{-k}</math>.


;2.
Suppose however we restrict the rationals we may select to have denominators bounded by <math>n</math>. How closely we can approximate <math>x</math> now?
By the definition of <math>\tau(\epsilon)</math>, the inequality is straightforwardly implied by (1).
}}


=Random Walk on the Hypercube=
The following important theorem is due to Dirichlet and his ''Schubfachprinzip'' ("drawer principle"). The theorem is fundamental in numer theory and real analysis, but the proof is combinatorial.
A <math>n</math>-dimensional [http://en.wikipedia.org/wiki/Hypercube '''hypercube'''] is a graph on vertex set <math>\{0,1\}^n</math>. For any <math>x,y\in\{0,1\}^n</math>, there is an edge between <math>x</math> and <math>y</math> if <math>x</math> and <math>y</math> differ at exact one coordinate (the hamming distance between <math>x</math> and <math>y</math> is 1).


We use coupling to bound the mixing time of the following simple random walk on a hypercube.
{{Theorem|Theorem (Dirichlet 1879)|
{{Theorem|Random Walk on Hypercube|
:Let <math>x</math> be an irrational number. For any natural number <math>n</math>, there is a rational number <math>\frac{p}{q}</math> such that <math>1\le q\le n</math> and
: At each step, for the current state <math>x\in\{0,1\}^n</math>:
::<math>\left|x-\frac{p}{q}\right|<\frac{1}{nq}</math>.
# with probability <math>1/2</math>, do nothing;
# else, pick a coordinate <math>i\in\{1,2,\ldots,n\}</math> uniformly at random and flip the bit <math>x_i</math> (change <math>x_i</math> to <math>1-x_i</math>).
}}
}}
{{Proof|
Let <math>\{x\}=x-\lfloor x\rfloor</math> denote the '''fractional part''' of the real number <math>x</math>. It is obvious that <math>\{x\}\in[0,1)</math> for any real number <math>x</math>.


This is a lazy uniform random walk in an <math>n</math>-dimensional hypercube. It is equivalent to the following random walk.
Consider the <math>n+1</math> numbers <math>\{kx\}</math>, <math>k=1,2,\ldots,n+1</math>. These <math>n+1</math> numbers (pigeons) belong to the following <math>n</math> intervals (pigeonholes):
:<math>\left(0,\frac{1}{n}\right),\left(\frac{1}{n},\frac{2}{n}\right),\ldots,\left(\frac{n-1}{n},1\right)</math>.
Since <math>x</math> is irrational, <math>\{kx\}</math> cannot coincide with any endpoint of the above intervals.


{{Theorem|Random Walk on Hypercube|
By the pigeonhole principle, there exist <math>1\le a<b\le n+1</math>, such that <math>\{ax\},\{bx\}</math> are in the same interval, thus
: At each step, for the current state <math>x\in\{0,1\}^n</math>:
:<math>|\{bx\}-\{ax\}|<\frac{1}{n}</math>.
# pick a coordinate <math>i\in\{1,2,\ldots,n\}</math> uniformly at random and a bit <math>b\in\{0,1\}</math> uniformly at random;
Therefore,
# let <math>x_i=b</math>.
:<math>|(b-a)x-\left(\lfloor bx\rfloor-\lfloor ax\rfloor\right)|<\frac{1}{n}</math>.
Let <math>q=b-a</math> and <math>p=\lfloor bx\rfloor-\lfloor ax\rfloor</math>. We have <math>|qx-p|<\frac{1}{n}</math> and <math>1\le q\le n</math>. Dividing both sides by <math>q</math>, the theorem is proved.
}}
}}


It is easy to see the two random walks are the same. The second form hint us to couple the random choice of <math>i</math> and <math>b</math> in each step. Consider two copies of the random walk <math>X_t</math> and <math>Y_t</math>, started from arbitrary two states <math>X_0</math> and <math>Y_0</math>, the coupling rule is:
== References ==
* At each step, <math>X_t</math> and <math>Y_t</math> choose the same (uniformly random) coordinate <math>i</math> and the same (uniformly random) bit <math>b</math>.
:('''声明:''' 资料受版权保护, 仅用于教学.)
Obviously the two individual random walks are both faithful copies of the original walk.
:('''Disclaimer:''' The following copyrighted materials are meant for educational uses only.)
 
For arbitrary <math>x,y\in\{0,1\}^n</math>, started at <math>X_0=x, Y_0=y</math>, the event <math>X_t=Y_t</math> occurs if everyone of the coordinates on which <math>x</math> and <math>y</math> disagree has been picked at least once. In the worst case, <math>x</math> and <math>y</math> disagree on all <math>n</math> coordinates. The time <math>T</math> that all <math>n</math> coordinates have been picked follows the coupon collector problem collecting <math>n</math> coupons, and we know from the coupon collector problem that for <math>c>0</math>,
:<math>
\Pr[T\ge n\ln n+cn]\le \mathrm{e}^{-c}.
</math>
Thus for any <math>x,y\in\{0,1\}^n</math>, if <math>t\ge n\ln n+cn</math>, then <math>\Pr[X_t\neq Y_t\mid X_0=x,Y_0=y]\le \mathrm{e}^{-c}</math>. Due to the coupling lemma for Markov chains,
:<math>\Delta(n\ln n+cn)\le \mathrm{e}^{-c},</math>
which implies that
:<math>\tau(\epsilon)=n\ln n+n\ln\frac{1}{\epsilon}</math>.
So the random walk achieves a polynomially small variation distance <math>\epsilon=\frac{1}{\mathrm{poly}(n)}</math> to the stationary distribution in time <math>O(n\ln n)</math>.


Note that the number of states (vertices in the <math>n</math>-dimensional hypercube) is <math>2^n</math>. Therefore, the mixing time is exponentially small compared to the size of the state space.
* Aigner and Ziegler. ''Proofs from THE BOOK, 4th Edition.'' Springer-Verlag. [[media:PFTB_chap25.pdf| Chapter 25]] and [[media:PFTB_chap30.pdf| Chapter 30]].
* Alon and Spencer. ''The Probabilistic Method, 3rd Edition.'' Wiley, 2008. [[media:TPM_Chap1.pdf|Chapter 1]], [[media:TPM_Chap2.pdf|Chapter 2]], and [[media:TPM_Chap3.pdf|Chapter 3]].

Revision as of 05:05, 7 October 2011

Cayley's Formula

We now present a theorem of the number of labeled trees on a fixed number of vertices. It is due to Cayley in 1889. The theorem is often referred by the name Cayley's formula.

Cayley's formula for trees
There are [math]\displaystyle{ n^{n-2} }[/math] different trees on [math]\displaystyle{ n }[/math] distinct vertices.

The theorem has several proofs. Classical methods include the bijection which encodes a tree by a Prüfer code, through the Kirchhoff's matrix tree theorem, and by double counting.

Prüfer code

Prüfer code (encoder)
Input: A tree [math]\displaystyle{ T }[/math] of [math]\displaystyle{ n }[/math] distinct vertices, labeled by [math]\displaystyle{ 0,1,\ldots,n-1 }[/math].
let [math]\displaystyle{ T_1=T }[/math];
for [math]\displaystyle{ i=1 }[/math] to [math]\displaystyle{ n-2 }[/math], do
let [math]\displaystyle{ u_i }[/math] be the leaf in [math]\displaystyle{ T_i }[/math] with the smallest label, and [math]\displaystyle{ v_i }[/math] be its neighbor;
let [math]\displaystyle{ T_{i+1} }[/math] be the new tree obtained from deleting the leaf [math]\displaystyle{ u_i }[/math] from [math]\displaystyle{ T_i }[/math];
end
return [math]\displaystyle{ (v_1,v_2,\ldots,v_{n-2}) }[/math];


Prüfer code (decoder)
Input: A tuple [math]\displaystyle{ (v_1,v_2,\ldots,v_{n-2})\in[n]^{n-2} }[/math].

Double counting

We now present a proof of the Cayley's formula by double counting, which is considered by the Proofs from THE BOOK "the most beautiful of them all".

Proof of Cayley's formula by double counting

(Due to Pitman 1999)

Let [math]\displaystyle{ T_n }[/math] be the number of different trees defined on [math]\displaystyle{ n }[/math] distinct vertices.

A rooted tree is a tree with a special vertex. That is, one of the [math]\displaystyle{ n }[/math] vertices is marked as the "root" of the tree. A rooted tree defines a natural direction of all edges, such that an edge [math]\displaystyle{ uv }[/math] of the tree is directed from [math]\displaystyle{ u }[/math] to [math]\displaystyle{ v }[/math] if [math]\displaystyle{ u }[/math] is before [math]\displaystyle{ v }[/math] along the unique path from the root.

We count the number of different sequences of directed edges that can be added to an empty graph on [math]\displaystyle{ n }[/math] vertices to form from it a rooted tree. We note that such a sequence can be formed in two ways:

  1. Starting with an unrooted tree, choose one of its vertices as root, and fix an total order of edges to specify the order in which the edges are added.
  2. Starting from an empty graph, add the edges one by one in steps.

In the first method, we pick one of the [math]\displaystyle{ T_n }[/math] unrooted trees, choose one of the [math]\displaystyle{ n }[/math] vertices as the root, and pick one of the [math]\displaystyle{ (n-1)! }[/math] total orders of the [math]\displaystyle{ n-1 }[/math] edges. This gives us [math]\displaystyle{ T_nn(n-1)!=T_nn! }[/math] ways.

In the second method, we consider the number of choices in one step, and multiply the numbers of choices in all steps. This is done as follows.

Given a sequence of adding [math]\displaystyle{ n-1 }[/math] edges to an empty graph to form a rooted tree, we reverse this sequence and get a sequence of removing edges one by one from the final rooted tree until no edge left. We observe that:

  • At first, we remove an edge from the rooted tree. Suppose that the root of the tree is [math]\displaystyle{ r }[/math], and the removed directed edge is [math]\displaystyle{ (u,v) }[/math]. After removing [math]\displaystyle{ (u,v) }[/math], the original rooted tree is disconnected into two rooted trees, one rooted at [math]\displaystyle{ r }[/math] and the other rooted at [math]\displaystyle{ v }[/math].
  • After removing [math]\displaystyle{ k-1 }[/math] edges, there are [math]\displaystyle{ k }[/math] rooted trees. In the [math]\displaystyle{ k }[/math]th step, a directed edge [math]\displaystyle{ (u,v) }[/math] in the current forest is removed and the tree containing [math]\displaystyle{ (u,v) }[/math] is disconnected into two trees, one rooted at the old root of that tree, and the other rooted at [math]\displaystyle{ v }[/math].

We now again reverse the above procedure, and consider the sequence of adding directed edges to an empty graph to form a rooted tree.

  • At first, we have [math]\displaystyle{ n }[/math] rooted trees, each of 0 edge ([math]\displaystyle{ n }[/math] isolated vertices).
  • After adding [math]\displaystyle{ n-k }[/math] edges, there are [math]\displaystyle{ k }[/math] rooted trees. Denoting the directed edge added next as [math]\displaystyle{ (u,v) }[/math]. As observed above, [math]\displaystyle{ u }[/math] can be any one of the [math]\displaystyle{ n }[/math] vertices; but [math]\displaystyle{ v }[/math] must be the root of one of the [math]\displaystyle{ k }[/math] trees, except the tree which contains [math]\displaystyle{ u }[/math]. There are [math]\displaystyle{ n(k-1) }[/math] choices of such [math]\displaystyle{ (u,v) }[/math].

Multiplying the numbers of choices in all steps, the number of sequences of adding directed edges to an empty graph to form a rooted tree is given by

[math]\displaystyle{ \prod_{k=2}^nn(k-1)=n^{n-2}n! }[/math].

By the principle of double counting, counting the same thing by different methods yield the same result.

[math]\displaystyle{ T_nn!=n^{n-2}n! }[/math],

which gives that [math]\displaystyle{ T_n=n^{n-2} }[/math].

[math]\displaystyle{ \square }[/math]

Existence by Counting

Shannon's circuit lower bound

This is a fundamental problem in in Computer Science.

A boolean function is a function in the form [math]\displaystyle{ f:\{0,1\}^n\rightarrow \{0,1\} }[/math].

Boolean circuit is a mathematical model of computation. Formally, a boolean circuit is a directed acyclic graph. Nodes with indegree zero are input nodes, labeled [math]\displaystyle{ x_1, x_2, \ldots , x_n }[/math]. A circuit has a unique node with outdegree zero, called the output node. Every other node is a gate. There are three types of gates: AND, OR (both with indegree two), and NOT (with indegree one).

Computations in Turing machines can be simulated by circuits, and any boolean function in P can be computed by a circuit with polynomially many gates. Thus, if we can find a function in NP that cannot be computed by any circuit with polynomially many gates, then NP[math]\displaystyle{ \neq }[/math]P.

The following theorem due to Shannon says that functions with exponentially large circuit complexity do exist.

Theorem (Shannon 1949)
There is a boolean function [math]\displaystyle{ f:\{0,1\}^n\rightarrow \{0,1\} }[/math] with circuit complexity greater than [math]\displaystyle{ \frac{2^n}{3n} }[/math].
Proof.

We first count the number of boolean functions [math]\displaystyle{ f:\{0,1\}^n\rightarrow \{0,1\} }[/math]. There are [math]\displaystyle{ 2^{2^n} }[/math] boolean functions [math]\displaystyle{ f:\{0,1\}^n\rightarrow \{0,1\} }[/math].

Then we count the number of boolean circuit with fixed number of gates. Fix an integer [math]\displaystyle{ t }[/math], we count the number of circuits with [math]\displaystyle{ t }[/math] gates. By the De Morgan's laws, we can assume that all NOTs are pushed back to the inputs. Each gate has one of the two types (AND or OR), and has two inputs. Each of the inputs to a gate is either a constant 0 or 1, an input variable [math]\displaystyle{ x_i }[/math], an inverted input variable [math]\displaystyle{ \neg x_i }[/math], or the output of another gate; thus, there are at most [math]\displaystyle{ 2+2n+t-1 }[/math] possible gate inputs. It follows that the number of circuits with [math]\displaystyle{ t }[/math] gates is at most [math]\displaystyle{ 2^t(t+2n+1)^{2t} }[/math].

If [math]\displaystyle{ t=2^n/3n }[/math], then

[math]\displaystyle{ \frac{2^t(t+2n+1)^{2t}}{2^{2^n}}=o(1)\lt 1, }[/math] thus, [math]\displaystyle{ 2^t(t+2n+1)^{2t} \lt 2^{2^n}. }[/math]

Each boolean circuit computes one boolean function. Therefore, there must exist a boolean function [math]\displaystyle{ f }[/math] which cannot be computed by any circuits with [math]\displaystyle{ 2^n/3n }[/math] gates.

[math]\displaystyle{ \square }[/math]

Note that by Shannon's theorem, not only there exists a boolean function with exponentially large circuit complexity, but almost all boolean functions have exponentially large circuit complexity.

Double counting

The double counting principle states the following obvious fact: if the elements of a set are counted in two different ways, the answers are the same.

Handshaking lemma

The following lemma is a standard demonstration of double counting.

Handshaking Lemma
At a party, the number of guests who shake hands an odd number of times is even.

We model this scenario as an undirected graph [math]\displaystyle{ G(V,E) }[/math] with [math]\displaystyle{ |V|=n }[/math] standing for the [math]\displaystyle{ n }[/math] guests. There is an edge [math]\displaystyle{ uv\in E }[/math] if [math]\displaystyle{ u }[/math] and [math]\displaystyle{ v }[/math] shake hands. Let [math]\displaystyle{ d(v) }[/math] be the degree of vertex [math]\displaystyle{ v }[/math], which represents the number of times that [math]\displaystyle{ v }[/math] shakes hand. The handshaking lemma states that in any undirected graph, the number of vertices whose degrees are odd is even. It is sufficient to show that the sum of odd degrees is even.

The handshaking lemma is a direct consequence of the following lemma, which is proved by Euler in his 1736 paper on Seven Bridges of Königsberg that began the study of graph theory.

Lemma (Euler 1736)
[math]\displaystyle{ \sum_{v\in V}d(v)=2|E| }[/math]
Proof.

We count the number of directed edges. A directed edge is an ordered pair [math]\displaystyle{ (u,v) }[/math] such that [math]\displaystyle{ \{u,v\}\in E }[/math]. There are two ways to count the directed edges.

First, we can enumerate by edges. Pick every edge [math]\displaystyle{ uv\in E }[/math] and apply two directions [math]\displaystyle{ (u,v) }[/math] and [math]\displaystyle{ (v,u) }[/math] to the edge. This gives us [math]\displaystyle{ 2|E| }[/math] directed edges.

On the other hand, we can enumerate by vertices. Pick every vertex [math]\displaystyle{ v\in V }[/math] and for each of its [math]\displaystyle{ d(v) }[/math] neighbors, say [math]\displaystyle{ u }[/math], generate a directed edge [math]\displaystyle{ (v,u) }[/math]. This gives us [math]\displaystyle{ \sum_{v\in V}d(v) }[/math] directed edges.

It is obvious that the two terms are equal, since we just count the same thing twice with different methods. The lemma follows.

[math]\displaystyle{ \square }[/math]

The handshaking lemma is implied directly by the above lemma, since the sum of even degrees is even.

The Pigeonhole Principle

The pigeonhole principle states the following "obvious" fact:

[math]\displaystyle{ n+1 }[/math] pigeons cannot sit in [math]\displaystyle{ n }[/math] holes so that every pigeon is alone in its hole.

This is one of the oldest non-constructive principles: it states only the existence of a pigeonhole with more than one pigeons and says nothing about how to find such a pigeonhole.

The general form of pigeonhole principle, also known as the averaging principle, is stated as follows.

Generalized pigeonhole principle
If a set consisting of more than [math]\displaystyle{ mn }[/math] objects is partitioned into [math]\displaystyle{ n }[/math] classes, then some class receives more than [math]\displaystyle{ m }[/math] objects.

Monotonic subsequences

Let [math]\displaystyle{ (a_1,a_2,\ldots,a_n) }[/math] be a sequence of [math]\displaystyle{ n }[/math] distinct real numbers. A subsequence is a sequence of distinct terms of [math]\displaystyle{ (a_1,a_2,\ldots,a_n) }[/math] appearing in the same order in which they appear in [math]\displaystyle{ (a_1,a_2,\ldots,a_n) }[/math]. Formally, a subsequence of [math]\displaystyle{ (a_1,a_2,\ldots,a_n) }[/math] is an [math]\displaystyle{ (a_{i_1},a_{i_2},\ldots,a_{i_k}) }[/math], with [math]\displaystyle{ i_1\lt i_2\lt \cdots\lt i_k }[/math].

A sequence [math]\displaystyle{ (a_1,a_2,\ldots,a_n) }[/math] is increasing if [math]\displaystyle{ a_1\lt a_2\lt \cdots\lt a_n }[/math], and decreasing if [math]\displaystyle{ a_1\gt a_2\gt \cdots\gt a_n }[/math].

We are interested in the longest increasing and decreasing subsequences of an [math]\displaystyle{ a_1\lt a_2\lt \cdots\lt a_n }[/math]. It is intuitive that the length of both the longest increasing subsequence and the longest decreasing subsequence cannot be small simultaneously. A famous result of Erdős and Szekeres formally justifies this intuition. This is one of the first results in extremal combinatorics, published in the influential 1935 paper of Erdős and Szekeres.

Theorem (Erdős-Szekeres 1935)
A sequence of more than [math]\displaystyle{ mn }[/math] different real numbers must contain either an increasing subsequence of length [math]\displaystyle{ m+1 }[/math], or a decreasing subsequence of length [math]\displaystyle{ n+1 }[/math].
Proof.
(due to Seidenberg 1959)

Let [math]\displaystyle{ (a_1,a_2,\ldots,a_{N}) }[/math] be the original sequence of [math]\displaystyle{ N\gt mn }[/math] distinct real numbers. Associate each [math]\displaystyle{ a_i }[/math] a pair [math]\displaystyle{ (x_i,y_i) }[/math], defined as:

  • [math]\displaystyle{ x_i }[/math]: the length of the longest increasing subsequence ending at [math]\displaystyle{ a_i }[/math];
  • [math]\displaystyle{ y_i }[/math]: the length of the longest decreasing subsequence starting at [math]\displaystyle{ a_i }[/math].

A key observation is that [math]\displaystyle{ (x_i,y_i)\neq (x_j,y_j) }[/math] whenever [math]\displaystyle{ i\neq j }[/math]. This is proved as follows:

Case 1: If [math]\displaystyle{ a_i\lt a_j }[/math], then the longest increasing subsequence ending at [math]\displaystyle{ a_i }[/math] can be extended by adding on [math]\displaystyle{ a_j }[/math], so [math]\displaystyle{ x_i\lt x_j }[/math].
Case 2: If [math]\displaystyle{ a_i\gt a_j }[/math], then the longest decreasing subsequence starting at [math]\displaystyle{ a_j }[/math] can be preceded by [math]\displaystyle{ a_i }[/math], so [math]\displaystyle{ y_i\gt y_j }[/math].

Now we put [math]\displaystyle{ N }[/math] "pigeons" [math]\displaystyle{ a_1,a_2,\ldots,a_N }[/math] into "pigeonholes" [math]\displaystyle{ \{1,2,\ldots,N\}\times\{1,2,\ldots,N\} }[/math], such that [math]\displaystyle{ a_i }[/math] is put into hole [math]\displaystyle{ (x_i,y_i) }[/math], with at most one pigeon per each hole (since different [math]\displaystyle{ a_i }[/math] has different [math]\displaystyle{ (x_i,y_i) }[/math]).

The number of pigeons is [math]\displaystyle{ N\gt mn }[/math]. Due to pigeonhole principle, there must be a pigeon which is outside the region [math]\displaystyle{ \{1,2,\ldots,m\}\times\{1,2,\ldots,n\} }[/math], which implies that there exists an [math]\displaystyle{ a_i }[/math] with either [math]\displaystyle{ x_i\gt m }[/math] or [math]\displaystyle{ y_i\gt n }[/math]. Due to our definition of [math]\displaystyle{ (x_i,y_i) }[/math], there must be either an increasing subsequence of length [math]\displaystyle{ m+1 }[/math], or a decreasing subsequence of length [math]\displaystyle{ n+1 }[/math].

[math]\displaystyle{ \square }[/math]

Dirichlet's approximation

Let [math]\displaystyle{ x }[/math] be an irrational number. We now want to approximate [math]\displaystyle{ x }[/math] be a rational number (a fraction).

Since every real interval [math]\displaystyle{ [a,b] }[/math] with [math]\displaystyle{ a\lt b }[/math] contains infinitely many rational numbers, there must exist rational numbers arbitrarily close to [math]\displaystyle{ x }[/math]. The trick is to let the denominator of the fraction sufficiently large.

Suppose however we restrict the rationals we may select to have denominators bounded by [math]\displaystyle{ n }[/math]. How closely we can approximate [math]\displaystyle{ x }[/math] now?

The following important theorem is due to Dirichlet and his Schubfachprinzip ("drawer principle"). The theorem is fundamental in numer theory and real analysis, but the proof is combinatorial.

Theorem (Dirichlet 1879)
Let [math]\displaystyle{ x }[/math] be an irrational number. For any natural number [math]\displaystyle{ n }[/math], there is a rational number [math]\displaystyle{ \frac{p}{q} }[/math] such that [math]\displaystyle{ 1\le q\le n }[/math] and
[math]\displaystyle{ \left|x-\frac{p}{q}\right|\lt \frac{1}{nq} }[/math].
Proof.

Let [math]\displaystyle{ \{x\}=x-\lfloor x\rfloor }[/math] denote the fractional part of the real number [math]\displaystyle{ x }[/math]. It is obvious that [math]\displaystyle{ \{x\}\in[0,1) }[/math] for any real number [math]\displaystyle{ x }[/math].

Consider the [math]\displaystyle{ n+1 }[/math] numbers [math]\displaystyle{ \{kx\} }[/math], [math]\displaystyle{ k=1,2,\ldots,n+1 }[/math]. These [math]\displaystyle{ n+1 }[/math] numbers (pigeons) belong to the following [math]\displaystyle{ n }[/math] intervals (pigeonholes):

[math]\displaystyle{ \left(0,\frac{1}{n}\right),\left(\frac{1}{n},\frac{2}{n}\right),\ldots,\left(\frac{n-1}{n},1\right) }[/math].

Since [math]\displaystyle{ x }[/math] is irrational, [math]\displaystyle{ \{kx\} }[/math] cannot coincide with any endpoint of the above intervals.

By the pigeonhole principle, there exist [math]\displaystyle{ 1\le a\lt b\le n+1 }[/math], such that [math]\displaystyle{ \{ax\},\{bx\} }[/math] are in the same interval, thus

[math]\displaystyle{ |\{bx\}-\{ax\}|\lt \frac{1}{n} }[/math].

Therefore,

[math]\displaystyle{ |(b-a)x-\left(\lfloor bx\rfloor-\lfloor ax\rfloor\right)|\lt \frac{1}{n} }[/math].

Let [math]\displaystyle{ q=b-a }[/math] and [math]\displaystyle{ p=\lfloor bx\rfloor-\lfloor ax\rfloor }[/math]. We have [math]\displaystyle{ |qx-p|\lt \frac{1}{n} }[/math] and [math]\displaystyle{ 1\le q\le n }[/math]. Dividing both sides by [math]\displaystyle{ q }[/math], the theorem is proved.

[math]\displaystyle{ \square }[/math]

References

(声明: 资料受版权保护, 仅用于教学.)
(Disclaimer: The following copyrighted materials are meant for educational uses only.)
Retrieved from "https://tcs.nju.edu.cn/wiki/index.php?title=随机算法_(Fall_2011)/Coupling&oldid=4875"