高级算法 (Fall 2019)/Probability Basics and 组合数学 (Fall 2019): Difference between pages

From TCS Wiki
(Difference between pages)
Jump to navigation Jump to search
VisualWikitext
imported>Etone
(Created page with "=Probability Space= The axiom foundation of probability theory is laid by [http://en.wikipedia.org/wiki/Andrey_Kolmogorov Kolmogorov], one of the greatest mathematician of the...")
 
imported>Etone
 
Line 1: Line 1:
=Probability Space=
{{Infobox
The axiom foundation of probability theory is laid by [http://en.wikipedia.org/wiki/Andrey_Kolmogorov Kolmogorov], one of the greatest mathematician of the 20th century, who advanced various very different fields of mathematics.
|name        = Infobox
|bodystyle    =
|title        = <font size=3>组合数学  <br>
Combinatorics</font>
|titlestyle  =


{{Theorem|Definition (Probability Space)|
|image        =  
A '''probability space''' is a triple <math>(\Omega,\Sigma,\Pr)</math>.
|imagestyle  =  
*<math>\Omega</math> is a set, called the '''sample space'''.
|caption      =  
*<math>\Sigma\subseteq 2^{\Omega}</math> is the set of all '''events''', satisfying:
|captionstyle =  
*:(K1). <math>\Omega\in\Sigma</math> and <math>\emptyset\in\Sigma</math>. (Existence of the ''certain'' event and the ''impossible'' event)
|headerstyle = background:#ccf;
*:(K2). If <math>A,B\in\Sigma</math>, then <math>A\cap B, A\cup B, A-B\in\Sigma</math>. (Intersection, union, and difference of two events are events).
|labelstyle  = background:#ddf;
* A '''probability measure''' <math>\Pr:\Sigma\rightarrow\mathbb{R}</math> is a function that maps each event to a nonnegative real number, satisfying
|datastyle    =  
*:(K3). <math>\Pr(\Omega)=1</math>.
*:(K4). For any ''disjoint'' events  <math>A</math> and <math>B</math> (which means <math>A\cap B=\emptyset</math>), it holds that <math>\Pr(A\cup B)=\Pr(A)+\Pr(B)</math>.
*:(K5*). For a decreasing sequence of events <math>A_1\supset A_2\supset \cdots\supset A_n\supset\cdots</math> of events with <math>\bigcap_n A_n=\emptyset</math>, it holds that <math>\lim_{n\rightarrow \infty}\Pr(A_n)=0</math>.
}}
 
;Remark
* In general, the set <math>\Omega</math> may be continuous, but we only consider '''discrete''' probability in this lecture, thus we assume that <math>\Omega</math> is either finite or countably infinite.
* Sometimes it is convenient to assume <math>\Sigma=2^{\Omega}</math>, i.e. the events enumerates all subsets of <math>\Omega</math>. But in general, a probability space is well-defined by any <math>\Sigma</math> satisfying (K1) and (K2). Such <math>\Sigma</math> is called a <math>\sigma</math>-algebra defined on <math>\Omega</math>.
* The last axiom (K5*) is redundant if <math>\Sigma</math> is finite, thus it is only essential when there are infinitely many events. The role of axiom (K5*) in probability theory is like [http://en.wikipedia.org/wiki/Zorn's_lemma Zorn's Lemma] (or equivalently the [http://en.wikipedia.org/wiki/Axiom_of_choice Axiom of Choice]) in axiomatic set theory.
 
Useful laws for probability can be deduced from the ''axioms'' (K1)-(K5).
{{Theorem|Proposition|
# Let <math>\bar{A}=\Omega\setminus A</math>. It holds that <math>\Pr(\bar{A})=1-\Pr(A)</math>.
# If <math>A\subseteq B</math> then <math>\Pr(A)\le\Pr(B)</math>.
}}
{{Proof|
# The events <math>\bar{A}</math> and <math>A</math> are disjoint and <math>\bar{A}\cup A=\Omega</math>. Due to Axiom (K4) and (K3), <math>\Pr(\bar{A})+\Pr(A)=\Pr(\Omega)=1</math>.
# The events <math>A</math> and <math>B\setminus A</math> are disjoint and <math>A\cup(B\setminus A)=B</math> since <math>A\subseteq B</math>. Due to Axiom (K4), <math>\Pr(A)+\Pr(B\setminus A)=\Pr(B)</math>, thus <math>\Pr(A)\le\Pr(B)</math>.
}}
 
;Notation
An event <math>A\subseteq\Omega</math> can be represented as <math>A=\{a\in\Omega\mid \mathcal{E}(a)\}</math> with a predicate <math>\mathcal{E}</math>.
 
The predicate notation of probability is
:<math>\Pr[\mathcal{E}]=\Pr(\{a\in\Omega\mid \mathcal{E}(a)\})</math>.
We use the two notations interchangeably.
 
==Union bound==
A very useful inequality in probability is the '''Boole's inequality''', mostly known by its nickname '''union bound'''.
{{Theorem
|Theorem (union bound)|
:Let <math>A_1, A_2, \ldots, A_n</math> be <math>n</math> events. Then
::<math>\begin{align}
\Pr\left(\bigcup_{1\le i\le n}A_i\right)
&\le
\sum_{i=1}^n\Pr(A_i).
\end{align}</math>
}}
{{Proof|
Let <math>B_1=A_1</math> and for <math>i>1</math>, let <math>B_i=A_i\setminus \left(\bigcup_{j<i}A_j\right)</math>.
We have <math>\bigcup_{1\le i\le n} A_i=\bigcup_{1\le i\le n} B_i</math>.
 
On the other hand, <math>B_1,B_2,\ldots,B_n</math> are disjoint, which implies by the axiom of probability space that
:<math>\Pr\left(\bigcup_{1\le i\le n}A_i\right)=\Pr\left(\bigcup_{1\le i\le n}B_i\right)=\sum_{i=1}^n\Pr(B_i)</math>.
Also note that <math>B_i\subseteq A_i</math> for all <math>1\le i\le n</math>,  thus <math>\Pr(B_i)\le \Pr(A_i)</math> for all <math>1\le i\le n</math>. The theorem follows.
}}
 
The union bound is a special case of the '''Boole-Bonferroni inequality'''.
{{Theorem
|Theorem (Boole-Bonferroni inequality)|
:Let <math>A_1, A_2, \ldots, A_n</math> be <math>n</math> events. For <math>1\le k\le n</math>, define <math>S_k=\sum_{i_1<i_2<\cdots<i_k}\Pr\left(\bigcap_{j=1}^k A_{i_j}\right)</math>.
 
:Then for '''''odd''''' <math>m</math> in <math>\{1,2,\ldots, n\}</math>:
::<math>\Pr\left(\bigcup_{1\le i\le n}A_i\right)\le \sum_{k=1}^m (-1)^{k-1} S_k</math>;
:and for '''''even''''' <math>m</math> in <math>\{1,2,\ldots, n\}</math>:
::<math>\Pr\left(\bigcup_{1\le i\le n}A_i\right)\ge \sum_{k=1}^m (-1)^{k-1} S_k</math>.
}}
The inequality follows from the well-known '''inclusion-exclusion principle''', stated as follows, as well as the fact that the quantity <math>S_k</math> is ''unimodal'' in <math>k</math>.
{{Theorem
|Principle of Inclusion-Exclusion|
:Let <math>A_1, A_2, \ldots, A_n</math> be <math>n</math> events. Then
::<math>\Pr\left(\bigcup_{1\le i\le n}A_i\right)=\sum_{k=1}^n (-1)^{k-1} S_k,</math>
:where <math>S_k=\sum_{i_1<i_2<\cdots<i_k}\Pr\left(\bigcap_{j=1}^k A_{i_j}\right)</math>.
}}
 
= Conditional Probability =
In probability theory, the word "condition" is a verb. "Conditioning on the event ..." means that it is assumed that the event occurs.
 
{{Theorem
|Definition (conditional probability)|
:The '''conditional probability''' that event <math>A</math> occurs given that event <math>B</math> occurs is
::<math>
\Pr[A\mid B]=\frac{\Pr[A\wedge B]}{\Pr[B]}.
</math>
}}
 
The conditional probability is well-defined only if <math>\Pr[B]\neq0</math>.
 
== Law of total probability ==
The following fact is known as the law of total probability. It computes the probability by averaging over all possible cases.
{{Theorem
|Theorem (law of total probability)|
:Let <math>B_1,B_2,\ldots,B_n</math> be ''mutually disjoint'' events, and <math>\bigcup_{i=1}^n B_i=\Omega</math> is the sample space.
:Then for any event <math>A</math>,
::<math>
\Pr[A]=\sum_{i=1}^n\Pr[A\wedge B_i]=\sum_{i=1}^n\Pr[A\mid B_i]\cdot\Pr[B_i].
</math>
}}
{{Proof| Since <math>B_1,B_2,\ldots, B_n</math> are mutually disjoint and <math>\bigvee_{i=1}^n B_i=\Omega</math>, events <math>A\wedge B_1, A\wedge B_2,\ldots, A\wedge B_n</math> are also mutually disjoint, and <math>A=\bigcup_{i=1}^n\left(A\cap B_i\right)</math>. Then the additivity of disjoint events, we have
:<math>
\Pr[A]=\sum_{i=1}^n\Pr[A\wedge B_i]=\sum_{i=1}^n\Pr[A\mid B_i]\cdot\Pr[B_i].
</math>
}}
 
The law of total probability provides us a standard tool for breaking a probability into sub-cases. Sometimes this will help the analysis.
 
== "The Chain Rule" ==
By the definition of conditional probability, <math>\Pr[A\mid B]=\frac{\Pr[A\wedge B]}{\Pr[B]}</math>. Thus, <math>\Pr[A\wedge B] =\Pr[B]\cdot\Pr[A\mid B]</math>. This hints us that we can compute the probability of the AND of events by conditional probabilities. Formally, we have the following theorem:
{{Theorem|Theorem|
:Let <math>A_1, A_2, \ldots, A_n</math>  be any <math>n</math> events. Then
::<math>\begin{align}
\Pr\left[\bigwedge_{i=1}^n A_i\right]
&=
\prod_{k=1}^n\Pr\left[A_k \mid \bigwedge_{i<k} A_i\right].
\end{align}</math>
}}
{{Proof|It holds that <math>\Pr[A\wedge B] =\Pr[B]\cdot\Pr[A\mid B]</math>. Thus, let <math>A=A_n</math> and <math>B=A_1\wedge A_2\wedge\cdots\wedge A_{n-1}</math>, then
:<math>\begin{align}
\Pr[A_1\wedge A_2\wedge\cdots\wedge A_n]
&=
\Pr[A_1\wedge A_2\wedge\cdots\wedge A_{n-1}]\cdot\Pr\left[A_n\mid \bigwedge_{i<n}A_i\right].
\end{align}
</math>
Recursively applying this equation to <math>\Pr[A_1\wedge A_2\wedge\cdots\wedge A_{n-1}]</math> until there is only <math>A_1</math> left, the theorem is proved.
}}


=Random Variable=
|header1 =Instructor
{{Theorem|Definition (random variable)|
|label1  =
:A random variable <math>X</math> on a sample space <math>\Omega</math> is a real-valued function <math>X:\Omega\rightarrow\mathbb{R}</math>. A random variable X is called a '''discrete''' random variable if its range is finite or countably infinite.
|data1  =
|header2 =  
|label2  =
|data2  = 尹一通
|header3 =
|label3  = Email
|data3  = yitong.yin@gmail.com  yinyt@nju.edu.cn 
|header4 =
|label4= office
|data4= 计算机系 804
|header5 = Class
|label5  =
|data5  =
|header6 =
|label6  = Class meetings
|data6  = Wednesday, 2pm-4pm <br> 仙I-319
|header7 =
|label7  = Place
|data7  =
|header8 =
|label8  = Office hours
|data8  = Wednesday, 4pm-6pm <br>计算机系 804
|header9 = Textbook
|label9  =
|data9  =
|header10 =
|label10  =
|data10  = [[File:LW-combinatorics.jpeg|border|100px]]
|header11 =
|label11  =
|data11  = van Lint and Wilson. <br> ''A course in Combinatorics, 2nd ed.'', <br> Cambridge Univ Press, 2001.
|header12 =
|label12  =
|data12  = [[File:Jukna_book.jpg|border|100px]]
|header13 =
|label13  =
|data13  = Jukna. ''Extremal Combinatorics: <br> With Applications in Computer Science,<br>2nd ed.'', Springer, 2011.
|belowstyle = background:#ddf;
|below =
}}
}}


For a random variable <math>X</math> and a real value <math>x\in\mathbb{R}</math>, we write "<math>X=x</math>" for the event <math>\{a\in\Omega\mid X(a)=x\}</math>, and denote the probability of the event by
This is the webpage for the ''Combinatorics'' class of fall 2019. Students who take this class should check this page periodically for content updates and new announcements.  
:<math>\Pr[X=x]=\Pr(\{a\in\Omega\mid X(a)=x\})</math>.
 
The independence can also be defined for variables:
{{Theorem
|Definition (Independent variables)|
:Two random variables <math>X</math> and <math>Y</math> are '''independent''' if and only if
::<math>
\Pr[(X=x)\wedge(Y=y)]=\Pr[X=x]\cdot\Pr[Y=y]
</math>
:for all values <math>x</math> and <math>y</math>. Random variables <math>X_1, X_2, \ldots, X_n</math> are '''mutually independent''' if and only if, for any subset <math>I\subseteq\{1,2,\ldots,n\}</math> and any values <math>x_i</math>, where <math>i\in I</math>,
::<math>\begin{align}
\Pr\left[\bigwedge_{i\in I}(X_i=x_i)\right]
&=
\prod_{i\in I}\Pr[X_i=x_i].
\end{align}</math>
}}


Note that in probability theory, the "mutual independence" is <font color="red">not</font> equivalent with "pair-wise independence", which we will learn in the future.
= Announcement =
TBA


= Linearity of Expectation =
= Course info =
Let <math>X</math> be a discrete '''random variable'''. The expectation of <math>X</math> is defined as follows.
* '''Instructor ''': 尹一通 ([http://tcs.nju.edu.cn/yinyt/ homepage])
{{Theorem
:*email: yinyt@nju.edu.cn,
|Definition (Expectation)|
:*office: 804
:The '''expectation''' of a discrete random variable <math>X</math>, denoted by <math>\mathbf{E}[X]</math>, is given by
* '''Class meeting''': Wednesday, 2pm-4pm, 仙I-319.
::<math>\begin{align}
* '''Office hour''': Wednesday, 4pm-6pm, 计算机系 804.
\mathbf{E}[X] &= \sum_{x}x\Pr[X=x],
\end{align}</math>
:where the summation is over all values <math>x</math> in the range of <math>X</math>.
}}


Perhaps the most useful property of expectation is its '''linearity'''.
= Syllabus =


{{Theorem
=== 先修课程 Prerequisites ===
|Theorem (Linearity of Expectations)|
* 离散数学（Discrete Mathematics）
:For any discrete random variables <math>X_1, X_2, \ldots, X_n</math>, and any real constants <math>a_1, a_2, \ldots, a_n</math>,
* 线性代数（Linear Algebra）
::<math>\begin{align}
* 概率论（Probability Theory）
\mathbf{E}\left[\sum_{i=1}^n a_iX_i\right] &= \sum_{i=1}^n a_i\cdot\mathbf{E}[X_i].
\end{align}</math>
}}
{{Proof| By the definition of the expectations, it is easy to verify that (try to prove by yourself):
for any discrete random variables <math>X</math> and <math>Y</math>, and any real constant <math>c</math>,
* <math>\mathbf{E}[X+Y]=\mathbf{E}[X]+\mathbf{E}[Y]</math>;
* <math>\mathbf{E}[cX]=c\mathbf{E}[X]</math>.
The theorem follows by induction.
}}
The linearity of expectation gives an easy way to compute the expectation of a random variable if the variable can be written as a sum.


;Example
=== Course materials ===
: Supposed that we have a biased coin that the probability of HEADs is <math>p</math>. Flipping the coin for n times, what is the expectation of number of HEADs?
* [[组合数学 (Fall 2019)/Course materials|<font size=3>教材和参考书清单</font>]]
: It looks straightforward that it must be np, but how can we prove it? Surely we can apply the definition of expectation to compute the expectation with brute force. A more convenient way is by the linearity of expectations: Let <math>X_i</math> indicate whether the <math>i</math>-th flip is HEADs. Then <math>\mathbf{E}[X_i]=1\cdot p+0\cdot(1-p)=p</math>, and the total number of HEADs after n flips is <math>X=\sum_{i=1}^{n}X_i</math>. Applying the linearity of expectation, the expected number of HEADs is:
::<math>\mathbf{E}[X]=\mathbf{E}\left[\sum_{i=1}^{n}X_i\right]=\sum_{i=1}^{n}\mathbf{E}[X_i]=np</math>.


The real power of the linearity of expectations is that it does not require the random variables to be independent, thus can be applied to any set of random variables. For example:
=== 成绩 Grades ===
:<math>\mathbf{E}\left[\alpha X+\beta X^2+\gamma X^3\right] = \alpha\cdot\mathbf{E}[X]+\beta\cdot\mathbf{E}\left[X^2\right]+\gamma\cdot\mathbf{E}\left[X^3\right].</math>
* 课程成绩：本课程将会有若干次作业和一次期末考试。最终成绩将由平时作业成绩 (≥ 60%) 和期末考试成绩 (≤ 40%) 综合得出。
* 迟交：如果有特殊的理由，无法按时完成作业，请提前联系授课老师，给出正当理由。否则迟交的作业将不被接受。


However, do not exaggerate this power!
=== <font color=red> 学术诚信 Academic Integrity </font>===
* For an arbitrary function <math>f</math> (not necessarily linear), the equation <math>\mathbf{E}[f(X)]=f(\mathbf{E}[X])</math> does <font color="red">not</font> hold generally.
学术诚信是所有从事学术活动的学生和学者最基本的职业道德底线，本课程将不遗余力的维护学术诚信规范，违反这一底线的行为将不会被容忍。
* For variances, the equation <math>var(X+Y)=var(X)+var(Y)</math> does <font color="red">not</font> hold without further assumption of the independence of <math>X</math> and <math>Y</math>.


==Conditional Expectation ==
作业完成的原则：署你名字的工作必须是你个人的贡献。在完成作业的过程中，允许讨论，前提是讨论的所有参与者均处于同等完成度。但关键想法的执行、以及作业文本的写作必须独立完成，并在作业中致谢（acknowledge）所有参与讨论的人。不允许其他任何形式的合作——尤其是与已经完成作业的同学“讨论”。


Conditional expectation can be accordingly defined:
本课程将对剽窃行为采取零容忍的态度。在完成作业过程中，对他人工作（出版物、互联网资料、其他人的作业等）直接的文本抄袭和对关键思想、关键元素的抄袭，按照 [http://www.acm.org/publications/policies/plagiarism_policy ACM Policy on Plagiarism]的解释，都将视为剽窃。剽窃者成绩将被取消。如果发现互相抄袭行为，<font color=red> 抄袭和被抄袭双方的成绩都将被取消</font>。因此请主动防止自己的作业被他人抄袭。
{{Theorem
|Definition (conditional expectation)|
:For random variables <math>X</math> and <math>Y</math>,
::<math>
\mathbf{E}[X\mid Y=y]=\sum_{x}x\Pr[X=x\mid Y=y],
</math>
:where the summation is taken over the range of <math>X</math>.
}}


There is also a '''law of total expectation'''.
学术诚信影响学生个人的品行，也关乎整个教育系统的正常运转。为了一点分数而做出学术不端的行为，不仅使自己沦为一个欺骗者，也使他人的诚实努力失去意义。让我们一起努力维护一个诚信的环境。
{{Theorem
|Theorem (law of total expectation)|
:Let <math>X</math> and <math>Y</math> be two random variables. Then
::<math>
\mathbf{E}[X]=\sum_{y}\mathbf{E}[X\mid Y=y]\cdot\Pr[Y=y].
</math>
}}


= <math>k</math>-wise  independence =
= Assignments =
Recall the definition of independence between events:
TBA
{{Theorem
|Definition (Independent events)|
:Events <math>\mathcal{E}_1, \mathcal{E}_2, \ldots, \mathcal{E}_n</math> are '''mutually independent''' if, for any subset <math>I\subseteq\{1,2,\ldots,n\}</math>,
::<math>\begin{align}
\Pr\left[\bigwedge_{i\in I}\mathcal{E}_i\right]
&=
\prod_{i\in I}\Pr[\mathcal{E}_i].
\end{align}</math>
}}
Similarly, we can define independence between random variables:
{{Theorem
|Definition (Independent variables)|
:Random variables <math>X_1, X_2, \ldots, X_n</math> are '''mutually independent''' if, for any subset <math>I\subseteq\{1,2,\ldots,n\}</math> and any values <math>x_i</math>, where <math>i\in I</math>,
::<math>\begin{align}
\Pr\left[\bigwedge_{i\in I}(X_i=x_i)\right]
&=
\prod_{i\in I}\Pr[X_i=x_i].
\end{align}</math>
}}
 
Mutual independence is an ideal condition of independence. The limited notion of independence is usually defined by the '''k-wise independence'''.
{{Theorem
|Definition (k-wise Independenc)|
:1. Events <math>\mathcal{E}_1, \mathcal{E}_2, \ldots, \mathcal{E}_n</math> are '''k-wise independent''' if, for any subset <math>I\subseteq\{1,2,\ldots,n\}</math>  with <math>|I|\le k</math>
:::<math>\begin{align}
\Pr\left[\bigwedge_{i\in I}\mathcal{E}_i\right]
&=
\prod_{i\in I}\Pr[\mathcal{E}_i].
\end{align}</math>
:2. Random variables <math>X_1, X_2, \ldots, X_n</math> are '''k-wise independent''' if, for any subset <math>I\subseteq\{1,2,\ldots,n\}</math> with <math>|I|\le k</math> and any values <math>x_i</math>, where <math>i\in I</math>,
:::<math>\begin{align}
\Pr\left[\bigwedge_{i\in I}(X_i=x_i)\right]
&=
\prod_{i\in I}\Pr[X_i=x_i].
\end{align}</math>
}}
 
A very common case is pairwise independence, i.e. the 2-wise independence.
{{Theorem
|Definition (pairwise Independent random variables)|
:Random variables <math>X_1, X_2, \ldots, X_n</math> are '''pairwise independent''' if, for any <math>X_i,X_j</math> where <math>i\neq j</math> and any values <math>a,b</math>
:::<math>\begin{align}
\Pr\left[X_i=a\wedge X_j=b\right]
&=
\Pr[X_i=a]\cdot\Pr[X_j=b].
\end{align}</math>
}}
 
Note that the definition of k-wise independence is hereditary:
* If <math>X_1, X_2, \ldots, X_n</math> are k-wise independent, then they are also <math>\ell</math>-wise independent for any <math>\ell<k</math>.
* If <math>X_1, X_2, \ldots, X_n</math> are NOT k-wise independent, then they cannot be <math>\ell</math>-wise independent for any <math>\ell>k</math>.
 
== Pairwise Independent Bits ==
Suppose we have <math>m</math> mutually independent and uniform random bits <math>X_1,\ldots, X_m</math>. We are going to extract <math>n=2^m-1</math> pairwise independent bits from these <math>m</math> mutually independent bits.
 
Enumerate all the nonempty subsets of <math>\{1,2,\ldots,m\}</math> in some order. Let <math>S_j</math>  be the <math>j</math>th subset. Let
:<math>
Y_j=\bigoplus_{i\in S_j} X_i,
</math>
where <math>\oplus</math> is the exclusive-or, whose truth table is as follows.
:{|cellpadding="4" border="1"
|-
|<math>a</math>
|<math>b</math>
|<math>a</math><math>\oplus</math><math>b</math>
|-
| 0 || 0 ||align="center"| 0
|-
| 0 || 1 ||align="center"| 1
|-
| 1 || 0 ||align="center"| 1
|-
| 1 || 1 ||align="center"| 0
|}
 
There are <math>n=2^m-1</math> such <math>Y_j</math>, because there are <math>2^m-1</math> nonempty subsets of <math>\{1,2,\ldots,m\}</math>. An equivalent definition of <math>Y_j</math> is
:<math>Y_j=\left(\sum_{i\in S_j}X_i\right)\bmod 2</math>.
Sometimes, <math>Y_j</math> is called the '''parity''' of the bits in <math>S_j</math>.
 
We claim that <math>Y_j</math> are pairwise independent and uniform.
 
{{Theorem
|Theorem|
:For any <math>Y_j</math> and any <math>b\in\{0,1\}</math>,
::<math>\begin{align}
\Pr\left[Y_j=b\right]
&=
\frac{1}{2}.
\end{align}</math>
:For any <math>Y_j,Y_\ell</math> that <math>j\neq\ell</math> and any <math>a,b\in\{0,1\}</math>,
::<math>\begin{align}
\Pr\left[Y_j=a\wedge Y_\ell=b\right]
&=
\frac{1}{4}.
\end{align}</math>
}}


The proof is left for your exercise.
= Lecture Notes =
# [[组合数学 (Fall 2019)/Basic enumeration|Basic enumeration | 基本计数]]
# Generating functions | 生成函数
# Pólya's theory of counting | Pólya计数法
# Sieve methods | 筛法
# Cayley's formula | Cayley公式
# Existence problems | 存在性问题
# The probabilistic method | 概率法
# Extremal graph theory | 极值图论
# Extremal set theory | 极值集合论
# Ramsey theory | Ramsey理论
# Matching theory | 匹配论


Therefore, we extract exponentially many pairwise independent uniform random bits from a sequence of mutually independent uniform random bits.
= Resources =
* [http://math.mit.edu/~fox/MAT307.html Combinatorics course] by Jacob Fox (now at Stanford) taught at MIT and Princeton.
* [https://www.math.ucla.edu/~pak/lectures/Math-Videos/comb-videos.htm Collection of Combinatorics Videos]


Note that <math>Y_j</math> are not 3-wise independent. For example, consider the subsets <math>S_1=\{1\},S_2=\{2\},S_3=\{1,2\}</math> and the corresponding random bits <math>Y_1,Y_2,Y_3</math>. Any two of <math>Y_1,Y_2,Y_3</math> would decide the value of the third one.
= Concepts =
* [http://en.wikipedia.org/wiki/Binomial_coefficient Binomial coefficient]
* [http://en.wikipedia.org/wiki/Twelvefold_way The twelvefold way]
* [http://en.wikipedia.org/wiki/Composition_(number_theory) Composition of a number]
* [http://en.wikipedia.org/wiki/Multiset#Formal_definition Multiset]
* [http://en.wikipedia.org/wiki/Combination#Number_of_combinations_with_repetition Combinations with repetition], [http://en.wikipedia.org/wiki/Multiset#Counting_multisets <math>k</math>-multisets on a set]
* [http://en.wikipedia.org/wiki/Multinomial_theorem#Multinomial_coefficients Multinomial coefficients]
* [http://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind Stirling number of the second kind]
* [http://en.wikipedia.org/wiki/Partition_(number_theory) Partition of a number]
** [http://en.wikipedia.org/wiki/Young_tableau Young tableau]
* [http://en.wikipedia.org/wiki/Fibonacci_number Fibonacci number]
* [http://en.wikipedia.org/wiki/Catalan_number Catalan number]
* [http://en.wikipedia.org/wiki/Generating_function Generating function] and [http://en.wikipedia.org/wiki/Formal_power_series formal power series]
* [http://en.wikipedia.org/wiki/Binomial_series Newton's formula]
* [https://en.wikipedia.org/wiki/Burnside%27s_lemma Burnside's lemma]
**[https://en.wikipedia.org/wiki/Group_action group action] and [https://en.wikipedia.org/wiki/Group_action#Orbits_and_stabilizers orbits]
* [https://en.wikipedia.org/wiki/Permutation#Cycle_notation Cycle decomposition] of permutation
* [https://en.wikipedia.org/wiki/Pólya_enumeration_theorem Pólya enumeration theorem]
* [http://en.wikipedia.org/wiki/Inclusion-exclusion_principle The principle of inclusion-exclusion] (and more generally the [http://en.wikipedia.org/wiki/Sieve_theory sieve method])
* [http://en.wikipedia.org/wiki/M%C3%B6bius_inversion_formula Möbius inversion formula]
* [http://en.wikipedia.org/wiki/Derangement Derangement], and [http://en.wikipedia.org/wiki/M%C3%A9nage_problem Problème des ménages]
* [http://en.wikipedia.org/wiki/Ryser%27s_formula#Ryser_formula Ryser's formula]
* [http://en.wikipedia.org/wiki/Euler_totient Euler totient function]
* [http://en.wikipedia.org/wiki/Cayley_formula Cayley's formula]
** [http://en.wikipedia.org/wiki/Prüfer_sequence Prüfer code for trees]
** [http://en.wikipedia.org/wiki/Kirchhoff%27s_matrix_tree_theorem Kirchhoff's matrix-tree theorem]
* [http://en.wikipedia.org/wiki/Double_counting_(proof_technique) Double counting] and the [http://en.wikipedia.org/wiki/Handshaking_lemma handshaking lemma]
* [http://en.wikipedia.org/wiki/Sperner's_lemma Sperner's lemma] and [http://en.wikipedia.org/wiki/Brouwer_fixed_point_theorem Brouwer fixed point theorem]
* [http://en.wikipedia.org/wiki/Pigeonhole_principle Pigeonhole principle]
:* [http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Szekeres_theorem Erdős–Szekeres theorem]
:* [http://en.wikipedia.org/wiki/Dirichlet's_approximation_theorem Dirichlet's approximation theorem]
* [http://en.wikipedia.org/wiki/Probabilistic_method The Probabilistic Method]
* [http://en.wikipedia.org/wiki/Lov%C3%A1sz_local_lemma Lovász local lemma]
* [http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model Erdős–Rényi model for random graphs]
* [http://en.wikipedia.org/wiki/Extremal_graph_theory Extremal graph theory]
* [http://en.wikipedia.org/wiki/Turan_theorem Turán's theorem], [http://en.wikipedia.org/wiki/Tur%C3%A1n_graph Turán graph]
* Two analytic inequalities:
:*[http://en.wikipedia.org/wiki/Cauchy%E2%80%93Schwarz_inequality Cauchy–Schwarz inequality]
:* the [http://en.wikipedia.org/wiki/Inequality_of_arithmetic_and_geometric_means inequality of arithmetic and geometric means]
* [http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Stone_theorem Erdős–Stone theorem] (fundamental theorem of extremal graph theory)
* [https://en.wikipedia.org/wiki/Sunflower_(mathematics) Sunflower lemma and conjecture]
* [http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Ko%E2%80%93Rado_theorem Erdős–Ko–Rado theorem]
* [http://en.wikipedia.org/wiki/Sperner_family Sperner system]
* [https://en.wikipedia.org/wiki/Sauer–Shelah_lemma Sauer's lemma] and [https://en.wikipedia.org/wiki/VC_dimension VC dimension]
* [https://en.wikipedia.org/wiki/Kruskal–Katona_theorem Kruskal–Katona theorem]
* [http://en.wikipedia.org/wiki/Ramsey_theory Ramsey theory]
:*[http://en.wikipedia.org/wiki/Ramsey's_theorem Ramsey's theorem]
:*[http://en.wikipedia.org/wiki/Happy_Ending_problem Happy Ending problem]
* [https://en.wikipedia.org/wiki/Hall%27s_marriage_theorem Hall's theorem ] (the marriage theorem)
:* [https://en.wikipedia.org/wiki/Doubly_stochastic_matrix Birkhoff–Von Neumann theorem]
* [http://en.wikipedia.org/wiki/K%C3%B6nig's_theorem_(graph_theory) König-Egerváry theorem]
* [http://en.wikipedia.org/wiki/Dilworth's_theorem Dilworth's theorem]
:* [http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Szekeres_theorem Erdős–Szekeres theorem]
* The  [http://en.wikipedia.org/wiki/Max-flow_min-cut_theorem Max-Flow Min-Cut Theorem]
:* [https://en.wikipedia.org/wiki/Menger%27s_theorem Menger's theorem]
:* [http://en.wikipedia.org/wiki/Maximum_flow_problem Maximum flow]

Revision as of 01:42, 2 September 2019

组合数学
Combinatorics
Instructor
尹一通
Email yitong.yin@gmail.com yinyt@nju.edu.cn
office 计算机系 804
Class
Class meetings Wednesday, 2pm-4pm
仙I-319
Office hours Wednesday, 4pm-6pm
计算机系 804
Textbook
van Lint and Wilson.
A course in Combinatorics, 2nd ed.,
Cambridge Univ Press, 2001.
Jukna. Extremal Combinatorics:
With Applications in Computer Science,
2nd ed., Springer, 2011.
v · d · e

This is the webpage for the Combinatorics class of fall 2019. Students who take this class should check this page periodically for content updates and new announcements.

Announcement

TBA

Course info

  • email: yinyt@nju.edu.cn,
  • office: 804
  • Class meeting: Wednesday, 2pm-4pm, 仙I-319.
  • Office hour: Wednesday, 4pm-6pm, 计算机系 804.

Syllabus

先修课程 Prerequisites

  • 离散数学（Discrete Mathematics）
  • 线性代数（Linear Algebra）
  • 概率论（Probability Theory）

Course materials

成绩 Grades

  • 课程成绩：本课程将会有若干次作业和一次期末考试。最终成绩将由平时作业成绩 (≥ 60%) 和期末考试成绩 (≤ 40%) 综合得出。
  • 迟交：如果有特殊的理由，无法按时完成作业，请提前联系授课老师，给出正当理由。否则迟交的作业将不被接受。

学术诚信 Academic Integrity

学术诚信是所有从事学术活动的学生和学者最基本的职业道德底线，本课程将不遗余力的维护学术诚信规范，违反这一底线的行为将不会被容忍。

作业完成的原则：署你名字的工作必须是你个人的贡献。在完成作业的过程中，允许讨论，前提是讨论的所有参与者均处于同等完成度。但关键想法的执行、以及作业文本的写作必须独立完成，并在作业中致谢（acknowledge）所有参与讨论的人。不允许其他任何形式的合作——尤其是与已经完成作业的同学“讨论”。

本课程将对剽窃行为采取零容忍的态度。在完成作业过程中，对他人工作（出版物、互联网资料、其他人的作业等）直接的文本抄袭和对关键思想、关键元素的抄袭，按照 ACM Policy on Plagiarism的解释，都将视为剽窃。剽窃者成绩将被取消。如果发现互相抄袭行为， 抄袭和被抄袭双方的成绩都将被取消。因此请主动防止自己的作业被他人抄袭。

学术诚信影响学生个人的品行，也关乎整个教育系统的正常运转。为了一点分数而做出学术不端的行为，不仅使自己沦为一个欺骗者，也使他人的诚实努力失去意义。让我们一起努力维护一个诚信的环境。

Assignments

TBA

Lecture Notes

  1. Basic enumeration | 基本计数
  2. Generating functions | 生成函数
  3. Pólya's theory of counting | Pólya计数法
  4. Sieve methods | 筛法
  5. Cayley's formula | Cayley公式
  6. Existence problems | 存在性问题
  7. The probabilistic method | 概率法
  8. Extremal graph theory | 极值图论
  9. Extremal set theory | 极值集合论
  10. Ramsey theory | Ramsey理论
  11. Matching theory | 匹配论

Resources

Concepts

Retrieved from "https://tcs.nju.edu.cn/wiki/index.php?title=高级算法_(Fall_2019)/Probability_Basics&oldid=8519"