组合数学 (Fall 2011)/Pólya's theory of counting and 随机算法 (Fall 2011)/Problem set 2: Difference between pages

From TCS Wiki
(Difference between pages)
Jump to navigation Jump to search
VisualWikitext
imported>Etone
 
imported>Etone
 
Line 1: Line 1:
== Groups ==
==Problem 1==
A group <math>(G,\cdot)</math> is set <math>G</math> along with a binary operator <math>\cdot</math> which satisfies the following axioms:
Some known facts:
* closure: <math>\forall g,h\in G, g\cdot h \in G</math>;
* Balls-into-bins: <math>m</math> balls are uniformly and independently thrown to <math>n</math> bins. If <math>m=\Theta(n)</math>, then the maximum load is <math>\Theta\left(\frac{\ln n}{\ln\ln n}\right)</math> with high probability.
* associativity: <math>\forall f,g,h\in G, f\cdot(g\cdot h)=(f\cdot g)\cdot h</math>;
* Power of two choices: <math>m</math> balls are sequentially thrown to <math>n</math> bins. For each ball, uniformly and independently choose random bins <math>i</math> and <math>j</math> (might be the same bin), and throw the ball to the currently less loaded bin among bin <math>i</math> and bin <math>j</math>. Assuming that <math>m=\Theta(n)</math>, after all <math>m</math> balls are thrown to bins, the maximum load is <math>\Theta\left(\ln \ln n\right)</math> with high probability.
* identity: there exists a special element <math>e\in G</math>, called the '''identity''', such that <math>e\cdot g=g</math> for any <math>g\in G</math>;
* inverse: <math>\forall g\in G</math>, there exists an <math>h\in G</math> such that <math>g\cdot h=e</math>, and we denote that <math>h=g^{-1}</math>.


=== Permutation groups===
Questions: Assume <math>n</math> balls and <math>n</math> bins. We throw the <math>n</math> balls sequentially.
# If we throw the first <math>\frac{n}{2}</math> balls uniformly and then throw the rest balls as the way of power-of-two-choices, what is the asymptotic maximum load with high probability?
# For the <math>k</math>th ball, if <math>k</math> is even, we throw the ball to a uniform bin; and if <math>k</math> is odd, we throw the ball as the way of power-of-two-choices. What is the asymptotic maximum load with high probability?


==== Cycle decomposition ====
== Problem 2==
* Generalize the LazySelect algorithm for the general selection problem: finding the <math>k</math>th smallest element in an array. Choose appropriate parameters to do the job.
* Use the Chernoff bounds instead of Chebyshev's inequality in the analysis of the above algorithm and try to use a smaller number of random samples.


=== Group action ===
== Problem 3 ==
{{Theorem|Definition (group action)|
;The Monte Carlo method for computing <math>\mathrm{e}</math>
:A '''group action''' of a group <math>G</math> on a set <math>X</math> is a binary operator:
::<math>\circ:G\times X\rightarrow X</math>
:satisfying:
:* Associativity: <math>(g\cdot h)\circ x=g\circ (h\circ x)</math> for all <math>g,h\in G</math> and <math>x\in X</math>;
:* Identity: <math>e\circ x=x</math> for all <math>x\in X</math>.
}}


== Burnside's Lemma ==
Suppose there are <math>n</math> peoples, each wearing a hat. We collect all their hats and randomly distribute the hats back to them, with each people receiving one hat. We ask for the probability that none of the people receive his/her own hat. We denote this probability by <math>p(n)</math>


=== Orbits ===
Formally, a '''permutation''' is a bijection <math>\pi:[n]\xrightarrow[\text{1-1}]{\text{onto}}[n]</math>. A '''fixed point''' for permutation <math>\pi</math> is an <math>i\in[n]</math> such that <math>\pi[i]=i</math>. Then <math>p(n)</math> is the probability that a uniformly random permutation has no fixed point. Such permutations are called '''derangement'''.
Let <math>G</math> be a permutation group acting on a set <math>X</math>. Let <math>\pi\in G, x\in X</math>.
* The '''invariant set''' of <math>\pi</math>:
::<math>X_\pi=\{x\in X\mid \pi\circ x=x\}</math>.
* The '''stabilizer''' of <math>x</math>:
::<math>G_x=\{\pi\in G\mid \pi\circ x=x\}</math>.
* The '''orbit''' of <math>x</math> under action of <math>G</math>:
::<math>Gx=\{\pi\circ x\mid \pi\in G\}</math>.


We think of <math>X</math> as a set of configurations which we may count up to certain symmetry induced by the group action.
This derangement problem is taught in undergraduate class Combinatorics at Nanjing University. See the [[组合数学 (Fall 2011)/Sieve_methods#Derangements|lecture notes]] for details. By the Principle of Inclusion-Exclusion (容斥原则), we know that <math>p(n)=\sum_{k=0}^n\frac{(-1)^k}{k!}</math>.


=== Counting orbits===
Recall that due to Taylor's expansion <math>\mathrm{e}=\sum_{k=0}^\infty\frac{(-1)^k}{k!}=p(\infty)</math>.


{{Theorem|Lemma|
Now suppose you are given access to a balckbox <math>derange(n)</math> which given as input a number <math>n</math>, samples a uniform and independent permutation <math>\pi</math> of <math>[n]</math>, and returns true if <math>\pi</math> has no fixed point and false if otherwise.
:Let <math>G</math> be a permutation group acting on a set <math>X</math>. For any <math>x\in X</math>,
::<math>|G_x||Gx|=|G|\,</math>.
}}
{{Proof|
Recall that the orbit <math>Gx=\{\pi\circ x\mid \pi\in G\}</math>. Suppose that <math>Gx=\{x_1,x_2,\ldots,x_t\}</math>. Then there exist a set <math>P=\{\pi_1,\pi_2,\ldots,\pi_t\}</math> of permutations such that <math>\pi_i\circ x=x_i\,</math> for <math>i=1,2,\ldots,t</math>. We construct a bijection between <math>G</math> and <math>P\times G_x</math>, which will prove the lemma.


For any <math>\pi\in G</math>, it holds that <math>\pi\circ x=x_i</math> for some <math>x_i</math>, and since <math>\pi_i\circ x=x_i</math>, we have
Develop a randomized algorithm <math>randE(\epsilon,\delta)</math>, whose inputs are <math>0<\epsilon<1</math> and <math>0<\delta<\frac{1}{2}</math>. The returned value of the algorithm should satisfy that
<math>\pi_i\circ x=\pi\circ x</math>, hence
:<math>\Pr[\mathrm{e}-\epsilon\le randE(\epsilon,\delta)\le\mathrm{e}+\epsilon]\ge1-\delta</math>.
:<math>(\pi_i^{-1}\cdot\pi)\circ x=\pi_i^{-1}\circ(\pi\circ x)=\pi_i^{-1}\circ(\pi_i\circ x)=(\pi_i^{-1}\cdot\pi_i)\circ x=e\circ x=x</math>.  
Denote that <math>\sigma=\pi_i^{-1}\cdot \pi</math>. Then
*<math>\pi_i\cdot\sigma=\pi_i\cdot(\pi_i^{-1}\cdot\pi)=\pi</math>, and
*<math>\sigma\circ x=(\pi_i^{-1}\cdot\pi)\circ x=x</math>, which implies that <math>\sigma\in G_x</math>.
Therefore, each <math>\pi\in G</math> corresponds to a unique pair <math>(\pi_i,\sigma)\in P\times G_x</math>. We have a 1-1 mapping from <math>G</math> to <math>P\times G_x</math>.


For every <math>\pi_i\in P</math> and every <math>\sigma\in G_x</math>, <math>\pi=\pi_i\cdot\sigma\in G</math>. We show that this is a 1-1 mapping. Suppose that <math>\pi_i\cdot\sigma=\pi_j\cdot\tau</math> for some <math>\pi_i,\pi_j\in P</math> and <math>\sigma,\tau\in G_x</math>. Then <math>(\pi_i\cdot\sigma)\circ x=\pi_i\circ(\sigma\circ x)=\pi_i\circ x=x_i</math> and <math>(\pi_j\cdot \tau)\circ x=\pi_j\circ(\tau\circ x)=\pi_j\circ x=x_j</math>, which implies <math>x_i=x_j</math> and correspondingly <math>\pi_i=\pi_j</math>. Since <math>\pi_i\cdot\sigma=\pi_j\cdot\tau</math>, <math>\sigma=\tau</math>. Therefore, we show that the mapping is 1-1.
* Your algorithm should call <math>derange(n)</math> as subroutine. Try to make both <math>n</math> and the number of times calling <math>derange(n)</math> as small as possible.
 
* Please given detailed analysis of your algorithm.
In conclusion, there exists a bijection between <math>P\times G_x</math> and <math>G</math>. As a consequence, <math>|Gx||G_x|=|P||G_x|=|P\times G_x|=|G|</math>.
}}
 
{{Theorem|Burnside's Lemma|
:Let <math>G</math> be a permutation group acting on a set <math>X</math>. The number of orbits, denoted <math>|X/G|</math>, is
::<math>|X/G|=\frac{1}{|G|}\sum_{\pi\in G}|X_{\pi}|.</math>
}}
{{Proof|
Let
:<math>A(\pi,x)=\begin{cases}1 & \pi\circ x=x,\\ 0 & \text{otherwise.}\end{cases}</math>
Basically <math>A(\pi,x)</math> indicates whether <math>x</math> is invariant under action of <math>\pi</math>. We can think of <math>A</math> as a matrix indexed by <math>G\times X</math>. An important observation is that the row sums and column sums of <math>A</math> are <math>|X_\pi|</math> and <math>|G_x|</math> respectively, namely,
:<math>|X_\pi|=\sum_{x\in X}A(\pi,x)</math> and <math>|G_x|=\sum_{\pi\in G}A(\pi,x)</math>.
Then a double counting gives that
:<math>\sum_{\pi\in G}|X_\pi|=\sum_{\pi\in G}\sum_{x\in X}A(\pi,x)=\sum_{x\in X}\sum_{\pi\in G}A(\pi,x)=\sum_{x\in X}|G_x|</math>.
 
Due to the above lemma, <math>|G_x|=\frac{|G|}{|Gx|}</math>, thus
:<math>\sum_{x\in X}|G_x|=\sum_{x\in X}\frac{|G|}{|Gx|}=|G|\sum_{x\in X}\frac{1}{|Gx|}</math>.
We may enumerate the <math>x\in X</math> in the sum by first enumerating the orbits and then the elements in each orbit. Suppose there are <math>m</math> orbits <math>X_1,X_2,\ldots,X_m</math>. They forms a partition of <math>X</math>, and for any <math>X_i</math> and every <math>x\in X_i</math>, <math>X_i=Gx</math>. Thus,
:<math>|G|\sum_{x\in X}\frac{1}{|Gx|}=|G|\sum_{i=1}^m\sum_{x\in X_i}\frac{1}{|Gx|}=|G|\sum_{i=1}^m\sum_{x\in X_i}\frac{1}{|X_i|}=|G|\sum_{i=1}^m1=|G|m</math>.
Combining everything together
:<math>\sum_{\pi\in G}|X_\pi|=\sum_{x\in X}|G_x|=|G|\sum_{x\in X}\frac{1}{|Gx|}=|G|m</math>,
which gives us that the number of orbits is
:<math>m=\frac{1}{|G|}\sum_{\pi\in G}|X_\pi|</math>.
}}
 
==Pólya's Theory of Counting ==
=== The cycle index ===
 
=== Pólya's enumeration formula ===
 
=== de Bruijn's generalization===

Revision as of 08:07, 9 October 2011

Problem 1

Some known facts:

  • Balls-into-bins: [math]\displaystyle{ m }[/math] balls are uniformly and independently thrown to [math]\displaystyle{ n }[/math] bins. If [math]\displaystyle{ m=\Theta(n) }[/math], then the maximum load is [math]\displaystyle{ \Theta\left(\frac{\ln n}{\ln\ln n}\right) }[/math] with high probability.
  • Power of two choices: [math]\displaystyle{ m }[/math] balls are sequentially thrown to [math]\displaystyle{ n }[/math] bins. For each ball, uniformly and independently choose random bins [math]\displaystyle{ i }[/math] and [math]\displaystyle{ j }[/math] (might be the same bin), and throw the ball to the currently less loaded bin among bin [math]\displaystyle{ i }[/math] and bin [math]\displaystyle{ j }[/math]. Assuming that [math]\displaystyle{ m=\Theta(n) }[/math], after all [math]\displaystyle{ m }[/math] balls are thrown to bins, the maximum load is [math]\displaystyle{ \Theta\left(\ln \ln n\right) }[/math] with high probability.

Questions: Assume [math]\displaystyle{ n }[/math] balls and [math]\displaystyle{ n }[/math] bins. We throw the [math]\displaystyle{ n }[/math] balls sequentially.

  1. If we throw the first [math]\displaystyle{ \frac{n}{2} }[/math] balls uniformly and then throw the rest balls as the way of power-of-two-choices, what is the asymptotic maximum load with high probability?
  2. For the [math]\displaystyle{ k }[/math]th ball, if [math]\displaystyle{ k }[/math] is even, we throw the ball to a uniform bin; and if [math]\displaystyle{ k }[/math] is odd, we throw the ball as the way of power-of-two-choices. What is the asymptotic maximum load with high probability?

Problem 2

  • Generalize the LazySelect algorithm for the general selection problem: finding the [math]\displaystyle{ k }[/math]th smallest element in an array. Choose appropriate parameters to do the job.
  • Use the Chernoff bounds instead of Chebyshev's inequality in the analysis of the above algorithm and try to use a smaller number of random samples.

Problem 3

The Monte Carlo method for computing [math]\displaystyle{ \mathrm{e} }[/math]

Suppose there are [math]\displaystyle{ n }[/math] peoples, each wearing a hat. We collect all their hats and randomly distribute the hats back to them, with each people receiving one hat. We ask for the probability that none of the people receive his/her own hat. We denote this probability by [math]\displaystyle{ p(n) }[/math]

Formally, a permutation is a bijection [math]\displaystyle{ \pi:[n]\xrightarrow[\text{1-1}]{\text{onto}}[n] }[/math]. A fixed point for permutation [math]\displaystyle{ \pi }[/math] is an [math]\displaystyle{ i\in[n] }[/math] such that [math]\displaystyle{ \pi[i]=i }[/math]. Then [math]\displaystyle{ p(n) }[/math] is the probability that a uniformly random permutation has no fixed point. Such permutations are called derangement.

This derangement problem is taught in undergraduate class Combinatorics at Nanjing University. See the lecture notes for details. By the Principle of Inclusion-Exclusion (容斥原则), we know that [math]\displaystyle{ p(n)=\sum_{k=0}^n\frac{(-1)^k}{k!} }[/math].

Recall that due to Taylor's expansion [math]\displaystyle{ \mathrm{e}=\sum_{k=0}^\infty\frac{(-1)^k}{k!}=p(\infty) }[/math].

Now suppose you are given access to a balckbox [math]\displaystyle{ derange(n) }[/math] which given as input a number [math]\displaystyle{ n }[/math], samples a uniform and independent permutation [math]\displaystyle{ \pi }[/math] of [math]\displaystyle{ [n] }[/math], and returns true if [math]\displaystyle{ \pi }[/math] has no fixed point and false if otherwise.

Develop a randomized algorithm [math]\displaystyle{ randE(\epsilon,\delta) }[/math], whose inputs are [math]\displaystyle{ 0\lt \epsilon\lt 1 }[/math] and [math]\displaystyle{ 0\lt \delta\lt \frac{1}{2} }[/math]. The returned value of the algorithm should satisfy that

[math]\displaystyle{ \Pr[\mathrm{e}-\epsilon\le randE(\epsilon,\delta)\le\mathrm{e}+\epsilon]\ge1-\delta }[/math].
  • Your algorithm should call [math]\displaystyle{ derange(n) }[/math] as subroutine. Try to make both [math]\displaystyle{ n }[/math] and the number of times calling [math]\displaystyle{ derange(n) }[/math] as small as possible.
  • Please given detailed analysis of your algorithm.
Retrieved from "https://tcs.nju.edu.cn/wiki/index.php?title=组合数学_(Fall_2011)/Pólya%27s_theory_of_counting&oldid=5054"