高级算法 (Fall 2016)/Nonconstructive Proof of Lovász Local Lemma and 组合数学 (Fall 2017)/Problem Set 1: Difference between pages

From TCS Wiki
(Difference between pages)
Jump to navigation Jump to search
VisualWikitext
imported>Etone
 
imported>Etone
No edit summary
 
Line 1: Line 1:
== Lovász Local Lemma==
*每道题目的解答都要有<font color="red" size=4>完整的解题过程</font>。中英文不限。
Given a sequence of events <math>A_1,A_2,\ldots,A_n</math>, we use the '''dependency graph''' to describe the dependencies between these events.


{{Theorem
== Problem 1 ==
|Definition|
#有<math>k</math>种不同的明信片，每种明信片有无限多张，寄给<math>n</math>个人，每人一张，有多少种方法？
:Let <math>A_1,A_2,\ldots,A_n</math> be a sequence of events. A graph <math>D=(V,E)</math> on the set of vertices <math>V=\{1,2,\ldots,n\}</math> is called a '''dependency graph''' for the events <math>A_1,\ldots,A_n</math> if for each <math>i</math>, <math>1\le i\le n</math>, the event <math>A_i</math> is mutually independent of all the events <math>\{A_j\mid (i,j)\not\in E\}</math>.
#有<math>k</math>种不同的明信片，每种明信片有无限多张，寄给<math>n</math>个人，每人一张，每个人必须收到不同种类的明信片，有多少种方法？
}}
#有<math>k</math>种不同的明信片，每种明信片有无限多张，寄给<math>n</math>个人，每人收到<math>r</math>张不同的明信片（但不同的人可以收到相同的明信片），有多少种方法？
#只有一种明信片，共有<math>m</math>张，寄给<math>n</math>个人，全部寄完，每个人可以收多张明信片或者不收明信片，有多少种方法？
#有<math>k</math>种不同的明信片，其中第<math>i</math>种明信片有<math>m_i</math>张，寄给<math>n</math>个人，全部寄完，每个人可以收多张明信片或者不收明信片，有多少种方法？


The notion of mutual independence between an event and a set of events is formally defined as follows.
== Problem 2 ==
{{Theorem|Definition|
Find the number of ways to select <math>2n</math> balls from <math>n</math> identical blue balls, <math>n</math> identical red balls and <math>n</math> identical green balls.
:An event <math>A</math> is said to be '''mutually independent''' of events <math>B_1,B_2,\ldots, B_k</math>, if for any disjoint <math>I^+,I^-\subseteq\{1,2,lots,k\}</math>, it holds that
* Give a combinatorial proof for the problem.
::<math>\Pr\left[A\,\,\big{|}\,\, \left(\bigwedge_{i\in I^+}B_i\right) \wedge \left(\bigwedge_{i\in I^-}\overline{B_i}\right)\right]=\Pr[A]</math>.
* Give an algebraic proof for the problem.
}}


;Example
== Problem 3 ==
:Let <math>X_1,X_2,\ldots,X_m</math> be a set of ''mutually independent'' random variables. Each event <math>A_i</math> is a predicate defined on a number of variables among <math>X_1,X_2,\ldots,X_m</math>. Let <math>v(A_i)</math> be the unique smallest set of variables which determine <math>A_i</math>. The dependency graph <math>D=(V,E)</math> is defined by
*一个长度为<math>n</math>的“山峦”是如下由<math>n</math>个"/"和<math>n</math>个"\"组成的，从坐标<math>(0,0)</math>到<math>(0,2n)</math>的折线，但任何时候都不允许低于<math>x</math>轴。例如下图：
:::<math>(i,j)\in E</math> iff <math>v(A_i)\cap v(A_j)\neq \emptyset</math>.


The following lemma, known as the Lovász local lemma, first proved by Erdős and Lovász in 1975, is an extremely powerful tool, as it supplies a way for dealing with rare events.
    /\
  /  \/\/\    /\/\
  /        \/\/    \/\/\
  ----------------------
:长度为<math>n</math>的“山峦”有多少？


{{Theorem
*一个长度为<math>n</math>的“地貌”是由<math>n</math>个"/"和<math>n</math>个"\"组成的，从坐标<math>(0,0)</math>到<math>(0,2n)</math>的折线，允许低于<math>x</math>轴。长度为<math>n</math>的“地貌”有多少？
|Lovász Local Lemma (symmetric case)|
:Let <math>A_1,A_2,\ldots,A_n</math> be a set of events, and assume that the following hold:
:#for all <math>1\le i\le n</math>, <math>\Pr[A_i]\le p</math>;
:#the maximum degree of the dependency graph for the events <math>A_1,A_2,\ldots,A_n</math> is <math>d</math>, and
:::<math>ep(d+1)\le 1</math>.
:Then
::<math>\Pr\left[\bigwedge_{i=1}^n\overline{A_i}\right]>0</math>.
}}


We will prove a general version of the local lemma, where the events <math>A_i</math> are not symmetric. This generalization is due to Spencer.
== Problem 4==
{{Theorem
李雷和韩梅梅竞选学生会主席，韩梅梅获得选票 <math>p</math> 张，李雷获得选票 <math>q</math> 张，<math>p>q</math>。我们将总共的 <math>p+q</math> 张选票一张一张的点数，有多少种选票的排序方式使得在整个点票过程中，韩梅梅的票数一直高于李雷的票数？等价地，假设选票均匀分布的随机排列，以多大概率在整个点票过程中，韩梅梅的票数一直高于李雷的票数。
|Lovász Local Lemma (general case)|
:Let <math>D=(V,E)</math> be the dependency graph of events <math>A_1,A_2,\ldots,A_n</math>. Suppose there exist real numbers <math>x_1,x_2,\ldots, x_n</math> such that <math>0\le x_i<1</math> and for all <math>1\le i\le n</math>,
::<math>\Pr[A_i]\le x_i\prod_{(i,j)\in E}(1-x_j)</math>.
:Then
::<math>\Pr\left[\bigwedge_{i=1}^n\overline{A_i}\right]\ge\prod_{i=1}^n(1-x_i)</math>.
}}


To see that the general LLL implies symmetric LLL, we set <math>x_i=\frac{1}{d+1}</math> for all <math>i=1,2,\ldots,n</math>. Then we have <math>\left(1-\frac{1}{d+1}\right)^d>\frac{1}{\mathrm{e}}</math>.
==Problem 5==
A <math>2\times n</math> rectangle is to be paved with <math>1\times 2</math> identical blocks and <math>2\times 2</math> identical blocks. Let <math>f(n)</math> denote the number of ways that can be done. Find a recurrence relation for <math>f(n)</math>, solve the recurrence relation.


Assume the condition in the symmetric LLL:
== Problem 6 ==
:#for all <math>1\le i\le n</math>, <math>\Pr[A_i]\le p</math>;
* 令<math>s_n</math>表示长度为<math>n</math>，没有2个连续的1的二进制串的数量，即
:#<math>ep(d+1)\le 1</math>;
*:<math>s_n=|\{x\in\{0,1\}^n\mid \forall 1\le i\le n-1, x_ix_{i+1}\neq 11\}|</math>。
then it is easy to verify that for all <math>1\le i\le n</math>,
:求 <math>s_n</math>。
:<math>\Pr[A_i]\le p\le\frac{1}{e(d+1)}<\frac{1}{d+1}\left(1-\frac{1}{d+1}\right)^d\le x_i\prod_{(i,j)\in E}(1-x_j)</math>.
Due to the general LLL, we have
:<math>\Pr\left[\bigwedge_{i=1}^n\overline{A_i}\right]\ge\prod_{i=1}^n(1-x_i)=\left(1-\frac{1}{d+1}\right)^n>0</math>.
This proves the symmetric LLL.


Now we prove the general LLL by the original induction proof.
*令<math>t_n</math>表示长度为<math>n</math>，没有3个连续的1的二进制串的数量，即
{{Proof|
*:<math>t_n=|\{x\in\{0,1\}^n\mid \forall 1\le i\le n-2, x_ix_{i+1}x_{i+2}\neq 111\}|</math>。
First, apply the chain rule. We have
*#给出计算<math>t_n</math>的递归式，并给出足够的初始值。
:<math>\Pr\left[\bigwedge_{i=1}^n\overline{A_i}\right]=\prod_{i=1}^n\Pr\left[\overline{A_i}\mid \bigwedge_{j=1}^{i-1}\overline{A_{j}}\right]=\prod_{i=1}^n\left(1-\Pr\left[{A_i}\mid \bigwedge_{j=1}^{i-1}\overline{A_{j}}\right]\right)</math>.
*#计算<math>t_n</math>的生成函数<math>T(x)=\sum_{n\ge 0}t_n x^n</math>，给出生成函数<math>T(x)</math>的闭合形式。


Next we prove by induction on <math>m</math> that for any set of <math>m</math> events <math>i_1,\ldots,i_m</math>,
注意：只需解生成函数的闭合形式，无需展开。
:<math>\Pr\left[A_{i_1}\mid \bigwedge_{j=2}^m\overline{A_{i_j}}\right]\le x_{i_1}</math>.
The local lemma follows immediately by the above chain rule.


For <math>m=1</math>, this is obvious because
== Problem 7 ==
:<math>\Pr[A_{i_1}]\le x_{i_1}\prod_{(i_1,j)\in E}(1-x_j)\le x_{i_1}</math>.
Let <math>a_n</math> be a sequence of numbers satisfying the recurrence relation:
 
:<math>p a_n+q a_{n-1}+r a_{n-2}=0</math>
For general <math>m</math>, let <math>i_2,\ldots,i_k</math> be the set of vertices adjacent to  <math>i_1</math> in the dependency graph, i.e. event <math>A_{i_1}</math> is mutually independent of <math>A_{i_{k+1}},A_{i_{k+2}},\ldots, A_{i_{m}}</math>.
with initial condition <math>a_0=s</math> and <math>a_1=t</math>, where <math>p,q,r,s,t</math> are constants such that <math>{p}+q+r=0</math>, <math>p\neq 0</math> and <math>s\neq t</math>. Solve the recurrence relation.
 
By conditional probability, we have
:<math>
\Pr\left[A_{i_1}\mid \bigwedge_{j=2}^m\overline{A_{i_j}}\right]
=\frac{\Pr\left[ A_i\wedge \bigwedge_{j=2}^k\overline{A_{i_j}}\mid \bigwedge_{j=k+1}^m\overline{A_{i_j}}\right]}
{\Pr\left[\bigwedge_{j=2}^k\overline{A_{i_j}}\mid \bigwedge_{j=k+1}^m\overline{A_{i_j}}\right]}
</math>.
First, we bound the numerator. Due to that <math>A_{i_1}</math> is mutually independent of <math>A_{i_{k+1}},A_{i_{k+2}},\ldots, A_{i_{m}}</math>, we have
:<math>
\begin{align}
\Pr\left[ A_{i_1}\wedge \bigwedge_{j=2}^k\overline{A_{i_j}}\mid \bigwedge_{j=k+1}^m\overline{A_{i_j}}\right]
&\le\Pr\left[ A_{i_1}\mid \bigwedge_{j=k+1}^m\overline{A_{i_j}}\right]\\
&=\Pr[A_{i_1}]\\
&\le x_{i_1}\prod_{(i_1,j)\in E}(1-x_j).
\end{align}
</math>
 
Next, we bound the denominator. Applying the chain rule, we have
:<math>
\Pr\left[\bigwedge_{j=2}^k\overline{A_{i_j}}\mid \bigwedge_{j=k+1}^m\overline{A_{i_j}}\right]
=\prod_{j=2}^k\Pr\left[\overline{A_{i_j}}\mid \bigwedge_{\ell=j+1}^m\overline{A_{i_\ell}}\right]
</math>
which by the induction hypothesis, is at least
:<math>
\prod_{j=2}^k(1-x_{i_j})=\prod_{\{i_1,i_j\}\in E}(1-x_j)
</math>
where <math>E</math> is the set of edges in the dependency graph.
 
Altogether, we prove the induction hypothesis
:<math>
\Pr\left[A_{i_1}\mid \bigwedge_{j=2}^m\overline{A_{i_j}}\right]
\le\frac{x_{i_1}\prod_{(i_1,j)\in E}(1-x_j)}{\prod_{\{i_1,i_j\}\in E}(1-x_j)}\le x_{i_1}.
</math>
 
Due to the chain rule, it holds that
:<math>
\begin{align}
\Pr\left[\bigwedge_{i=1}^n\overline{A_i}\right]
&=\prod_{i=1}^n\Pr\left[\overline{A_i}\mid \bigwedge_{j=1}^{i-1}\overline{A_{j}}\right]\\
&=\prod_{i=1}^n\left(1-\Pr\left[A_i\mid \bigwedge_{j=1}^{i-1}\overline{A_{j}}\right]\right)\\
&\ge\prod_{i=1}^n\left(1-x_i\right).
\end{align}
</math>
}}

Revision as of 13:14, 17 September 2017

  • 每道题目的解答都要有完整的解题过程。中英文不限。

Problem 1

  1. 有[math]\displaystyle{ k }[/math]种不同的明信片，每种明信片有无限多张，寄给[math]\displaystyle{ n }[/math]个人，每人一张，有多少种方法？
  2. 有[math]\displaystyle{ k }[/math]种不同的明信片，每种明信片有无限多张，寄给[math]\displaystyle{ n }[/math]个人，每人一张，每个人必须收到不同种类的明信片，有多少种方法？
  3. 有[math]\displaystyle{ k }[/math]种不同的明信片，每种明信片有无限多张，寄给[math]\displaystyle{ n }[/math]个人，每人收到[math]\displaystyle{ r }[/math]张不同的明信片（但不同的人可以收到相同的明信片），有多少种方法？
  4. 只有一种明信片，共有[math]\displaystyle{ m }[/math]张，寄给[math]\displaystyle{ n }[/math]个人，全部寄完，每个人可以收多张明信片或者不收明信片，有多少种方法？
  5. 有[math]\displaystyle{ k }[/math]种不同的明信片，其中第[math]\displaystyle{ i }[/math]种明信片有[math]\displaystyle{ m_i }[/math]张，寄给[math]\displaystyle{ n }[/math]个人，全部寄完，每个人可以收多张明信片或者不收明信片，有多少种方法？

Problem 2

Find the number of ways to select [math]\displaystyle{ 2n }[/math] balls from [math]\displaystyle{ n }[/math] identical blue balls, [math]\displaystyle{ n }[/math] identical red balls and [math]\displaystyle{ n }[/math] identical green balls.

  • Give a combinatorial proof for the problem.
  • Give an algebraic proof for the problem.

Problem 3

  • 一个长度为[math]\displaystyle{ n }[/math]的“山峦”是如下由[math]\displaystyle{ n }[/math]个"/"和[math]\displaystyle{ n }[/math]个"\"组成的，从坐标[math]\displaystyle{ (0,0) }[/math]到[math]\displaystyle{ (0,2n) }[/math]的折线，但任何时候都不允许低于[math]\displaystyle{ x }[/math]轴。例如下图：
   /\
  /  \/\/\    /\/\
 /        \/\/    \/\/\
 ----------------------
长度为[math]\displaystyle{ n }[/math]的“山峦”有多少？
  • 一个长度为[math]\displaystyle{ n }[/math]的“地貌”是由[math]\displaystyle{ n }[/math]个"/"和[math]\displaystyle{ n }[/math]个"\"组成的，从坐标[math]\displaystyle{ (0,0) }[/math]到[math]\displaystyle{ (0,2n) }[/math]的折线，允许低于[math]\displaystyle{ x }[/math]轴。长度为[math]\displaystyle{ n }[/math]的“地貌”有多少？

Problem 4

李雷和韩梅梅竞选学生会主席，韩梅梅获得选票 [math]\displaystyle{ p }[/math] 张，李雷获得选票 [math]\displaystyle{ q }[/math] 张，[math]\displaystyle{ p\gt q }[/math]。我们将总共的 [math]\displaystyle{ p+q }[/math] 张选票一张一张的点数，有多少种选票的排序方式使得在整个点票过程中，韩梅梅的票数一直高于李雷的票数？等价地，假设选票均匀分布的随机排列，以多大概率在整个点票过程中，韩梅梅的票数一直高于李雷的票数。

Problem 5

A [math]\displaystyle{ 2\times n }[/math] rectangle is to be paved with [math]\displaystyle{ 1\times 2 }[/math] identical blocks and [math]\displaystyle{ 2\times 2 }[/math] identical blocks. Let [math]\displaystyle{ f(n) }[/math] denote the number of ways that can be done. Find a recurrence relation for [math]\displaystyle{ f(n) }[/math], solve the recurrence relation.

Problem 6

  • 令[math]\displaystyle{ s_n }[/math]表示长度为[math]\displaystyle{ n }[/math]，没有2个连续的1的二进制串的数量，即
    [math]\displaystyle{ s_n=|\{x\in\{0,1\}^n\mid \forall 1\le i\le n-1, x_ix_{i+1}\neq 11\}| }[/math]。
求 [math]\displaystyle{ s_n }[/math]。
  • 令[math]\displaystyle{ t_n }[/math]表示长度为[math]\displaystyle{ n }[/math]，没有3个连续的1的二进制串的数量，即
    [math]\displaystyle{ t_n=|\{x\in\{0,1\}^n\mid \forall 1\le i\le n-2, x_ix_{i+1}x_{i+2}\neq 111\}| }[/math]。
    1. 给出计算[math]\displaystyle{ t_n }[/math]的递归式，并给出足够的初始值。
    2. 计算[math]\displaystyle{ t_n }[/math]的生成函数[math]\displaystyle{ T(x)=\sum_{n\ge 0}t_n x^n }[/math]，给出生成函数[math]\displaystyle{ T(x) }[/math]的闭合形式。

注意：只需解生成函数的闭合形式，无需展开。

Problem 7

Let [math]\displaystyle{ a_n }[/math] be a sequence of numbers satisfying the recurrence relation:

[math]\displaystyle{ p a_n+q a_{n-1}+r a_{n-2}=0 }[/math]

with initial condition [math]\displaystyle{ a_0=s }[/math] and [math]\displaystyle{ a_1=t }[/math], where [math]\displaystyle{ p,q,r,s,t }[/math] are constants such that [math]\displaystyle{ {p}+q+r=0 }[/math], [math]\displaystyle{ p\neq 0 }[/math] and [math]\displaystyle{ s\neq t }[/math]. Solve the recurrence relation.

Retrieved from "https://tcs.nju.edu.cn/wiki/index.php?title=高级算法_(Fall_2016)/Nonconstructive_Proof_of_Lovász_Local_Lemma&oldid=7927"