Randomized Algorithms (Spring 2010)/The probabilistic method: Difference between revisions
imported>WikiSysop |
imported>WikiSysop |
||
Line 32: | Line 32: | ||
:Given a set family <math>\mathcal{F}\subseteq{S\choose k}</math>, where <math>m=|\mathcal{F}|</math> and <math>n=|S|</math>, <math>\mathcal{F}</math> has a blocking set of size <math>\left\lceil\frac{n\ln m}{k}\right\rceil</math>. | :Given a set family <math>\mathcal{F}\subseteq{S\choose k}</math>, where <math>m=|\mathcal{F}|</math> and <math>n=|S|</math>, <math>\mathcal{F}</math> has a blocking set of size <math>\left\lceil\frac{n\ln m}{k}\right\rceil</math>. | ||
|} | |} | ||
'''Proof:''' | |||
Let <math>\tau=\left\lceil\frac{n\ln m}{k}\right\rceil</math>. Let <math>T</math> be a set chosen uniformly at random from <math>{S\choose \tau}</math>. We show that <math>T</math> is a blocking set of <math>\mathcal{F}</math> with a probability >0. | |||
Fix any <math>A\in\mathcal{F}</math>. Recall that <math>\mathcal{F}\subseteq{S\choose k}</math>, thus <math>|A|=k</math>. And | |||
:<math> | |||
\begin{align} | |||
\Pr[A\cap T=\emptyset] | |||
&= | |||
\frac{\left|{S-T\choose \tau}\right|}{\left|{S\choose \tau}\right|}\\ | |||
&= | |||
\frac{{n-k\choose \tau}}{{n\choose\tau}}\\ | |||
&= | |||
\frac{(n-k)\cdot(n-k-1)\cdots(n-k-\tau+1)}{n\cdot(n-1)\cdots(n-\tau+1)}\\ | |||
&< | |||
\left(1-\frac{k}{n}\right)^{\tau}\\ | |||
&\le | |||
\exp\left(-\frac{k\tau}{n}\right)\\ | |||
&\le | |||
\frac{1}{m}. | |||
\end{align} | |||
</math> | |||
By the union bound, the probability that there exists an <math>A\in\mathcal{F}</math> that misses <math>T</math> | |||
:<math> | |||
\Pr[\exists A\in\mathcal{F}, A\cap T=\emptyset]\le m\Pr[A\cap T=\emptyset]<m\cdot\frac{1}{m}=1. | |||
</math> | |||
Thus, the probability that <math>T</math> is a blocking set | |||
:<math> | |||
\Pr[\forall A\in\mathcal{F}, A\cap T\neq\emptyset]>0. | |||
</math> | |||
=== Linearity of expectation === | === Linearity of expectation === |
Revision as of 09:36, 16 April 2010
The Basic Idea
Counting or sampling
- Ramsey number
Theorem
|
- Circuit complexity
Theorem (Shannon)
|
- Blocking number
Let [math]\displaystyle{ S }[/math] be a set. Let [math]\displaystyle{ 2^{S}=\{A\mid A\subseteq S\} }[/math] be the power set of [math]\displaystyle{ S }[/math], and let [math]\displaystyle{ {S\choose k}=\{A\mid A\subseteq S\mbox{ and }|A|=k\} }[/math] be the [math]\displaystyle{ k }[/math]-uniform of [math]\displaystyle{ S }[/math].
We call [math]\displaystyle{ \mathcal{F} }[/math] a set family (or a set system) with ground set [math]\displaystyle{ S }[/math] if [math]\displaystyle{ \mathcal{F}\subseteq 2^{S} }[/math]. The members of [math]\displaystyle{ \mathcal{F} }[/math] are subsets of [math]\displaystyle{ S }[/math].
Given a set family [math]\displaystyle{ \mathcal{F} }[/math] with ground set [math]\displaystyle{ S }[/math], a set [math]\displaystyle{ T\subseteq S }[/math] is a blocking set of [math]\displaystyle{ \mathcal{F} }[/math] if all [math]\displaystyle{ A\in\mathcal{F} }[/math] have [math]\displaystyle{ A\cap T\neq \emptyset }[/math], i.e. [math]\displaystyle{ T }[/math] intersects (blocks) all member set of [math]\displaystyle{ \mathcal{F} }[/math].
Theorem
|
Proof: Let [math]\displaystyle{ \tau=\left\lceil\frac{n\ln m}{k}\right\rceil }[/math]. Let [math]\displaystyle{ T }[/math] be a set chosen uniformly at random from [math]\displaystyle{ {S\choose \tau} }[/math]. We show that [math]\displaystyle{ T }[/math] is a blocking set of [math]\displaystyle{ \mathcal{F} }[/math] with a probability >0.
Fix any [math]\displaystyle{ A\in\mathcal{F} }[/math]. Recall that [math]\displaystyle{ \mathcal{F}\subseteq{S\choose k} }[/math], thus [math]\displaystyle{ |A|=k }[/math]. And
- [math]\displaystyle{ \begin{align} \Pr[A\cap T=\emptyset] &= \frac{\left|{S-T\choose \tau}\right|}{\left|{S\choose \tau}\right|}\\ &= \frac{{n-k\choose \tau}}{{n\choose\tau}}\\ &= \frac{(n-k)\cdot(n-k-1)\cdots(n-k-\tau+1)}{n\cdot(n-1)\cdots(n-\tau+1)}\\ &\lt \left(1-\frac{k}{n}\right)^{\tau}\\ &\le \exp\left(-\frac{k\tau}{n}\right)\\ &\le \frac{1}{m}. \end{align} }[/math]
By the union bound, the probability that there exists an [math]\displaystyle{ A\in\mathcal{F} }[/math] that misses [math]\displaystyle{ T }[/math]
- [math]\displaystyle{ \Pr[\exists A\in\mathcal{F}, A\cap T=\emptyset]\le m\Pr[A\cap T=\emptyset]\lt m\cdot\frac{1}{m}=1. }[/math]
Thus, the probability that [math]\displaystyle{ T }[/math] is a blocking set
- [math]\displaystyle{ \Pr[\forall A\in\mathcal{F}, A\cap T\neq\emptyset]\gt 0. }[/math]
Linearity of expectation
Theorem
|
Theorem
|