随机算法 (Spring 2014)/Problem Set 1 and 组合数学 (Spring 2014)/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:
== Problem 1 ==
== Problem 1==
(Due to J. von Neumann.)
Prove the following identity:
*<math>\sum_{k=1}^n k{n\choose k}= n2^{n-1}</math>.


# Suppose you are given a coin for which the probability of HEADS, say <math>p</math>, is <i>unknown</i>. How can you use this coin to generate unbiased (i.e., <math>\Pr[\mbox{HEADS}]=\Pr[\mbox{TAILS}]=1/2</math>) coin-flips? Give a scheme for which the expected number of flips of the biased coin for extracting one unbiased coin-flip is no more than <math>1/(p(1-p))</math>.
(Hint: Use double counting.)
# Devise an extension of the scheme that extracts the largest possible number of independent, unbiased coin-flips from a given number of flips of the biased coin.


== Problem 2 ==
== Problem 2 ==
(Due to D.E. Knuth and A. C-C. Yao.)
(Erdős-Spencer 1974)


# Suppose you are provided with a source of unbiased random bits. Explain how you will use this to generate uniform samples from the set <math>S=\{0,\dots,n-1\}</math>. Determine the expected number of random bits required by your sampling algorithm.
Let <math>n</math> coins of weights 0 and 1 be given. We are also given a scale with which we may weigh any subset of the coins. Our goal is to determine the weights of coins (that is, to known which coins are 0 and which are 1) with the minimal number of weighings.  
# What is the <i>worst-case</i>  number of random bits required by your sampling algorithm? Consider the case when <math>n</math> is a power of <math>2</math>, as well as the case when it is not.
# Solve (1) and (2) when, instead of unbiased random bits, you are required to use as the source of randomness uniform random samples from the set <math>\{0,\dots,p-1\}</math>; consider the case when <math>n</math> is a power of <math>p</math>, as well as the case when it is not.


== Problem 3 ==
This problem can be formalized as follows: A collection <math>S_1,S_1,\ldots,S_m\subseteq [n]</math> is called '''determining''' if an arbitrary subset <math>T\subseteq[n]</math> can be uniquely determined by the cardinalities <math>|S_i\cap T|, 1\le i\le m</math>.
We play the following game:


Start with <math>n</math> people, each with 2 hands. None of these hands hold each other.  At each round, uniformly pick 2 free hands and let these two hands hold together. Repeat this until no free hands left.
* Prove that if there is a determining collection <math>S_1,S_1,\ldots,S_m\subseteq [n]</math>, then there is a way to determine the weights of <math>n</math> coins with <math>m</math> weighings.
* Use pigeonhole principle to show that if a collection <math>S_1,S_1,\ldots,S_m\subseteq [n]</math> is determining, then it must hold that <math>m\ge \frac{n}{\log_2(n+1)}</math>.


* What is the expected number of cycles made by people holding hands with each other at the end of the game? (One person with left hand holding right hand is also counted as a cycle.)
(This gives a lower bound for the number of weighings required to determine the weights of <math>n</math> coins.)


== Problem 4 ==


In <i>Balls-and-Bins</i> model, we throw <math>n</math> balls independently and uniformly at random into <math>n</math> bins, then the maximum load is <math>\Theta(\frac{\ln n}{\ln\ln n})</math> with high probability.
== Problem 3 ==


The <i>two-choice paradigm</i> is another way to throw <math>n</math> balls into <math>n</math> bins: each ball is thrown into the least loaded of 2 bins chosen independently and uniformly at random and breaks the tie arbitrarily. The maximum load of two-choice paradigm is <math>\Theta(\ln\ln n)</math> with high probability, which is exponentially less than the previous one. This phenomenon is called the <i>power of two choices</i>.
A set of vertices <math>D\subseteq V</math> of graph <math>G(V,E)</math> is a [http://en.wikipedia.org/wiki/Dominating_set ''dominating set''] if for every <math>v\in V</math>, it holds that <math>v\in D</math> or <math>v</math> is adjacent to a vertex in <math>D</math>. The problem of computing minimum dominating set is NP-hard.  


Now consider the following three paradigms:
* Prove that for every <math>d</math>-regular graph with <math>n</math> vertices, there exists a dominating set with size at most <math>\frac{n(1+\ln(d+1))}{d+1}</math>.


# The first <math>n/2</math> balls are thrown into bins independently and uniformly at random. The remaining <math>n/2</math> balls are thrown into bins using two-choice paradigm.
* Try to obtain an upper bound for the size of dominating set using Lovász Local Lemma. Is it better or worse than previous one?
# The first <math>n/2</math> balls are thrown into bins using two-choice paradigm. The remaining <math>n/2</math> balls are thrown into bins independently and uniformly at random.
# Assume all <math>n</math> balls are in a sequence. For every <math>1\le i\le n</math>, if <math>i</math> is odd, we throw <math>i</math>th ball into bins independently and uniformly at random, otherwise, we throw it into bins using two-choice paradigm.


What is the maximum load with high probability in each of three paradigms. You need to give an asymptotically tight bound (i.e. <math>\Theta(\cdot)</math>).
== Problem 4 ==
Let <math>H(W,F)</math> be a graph and <math>n>|W|</math> be an integer. It is known that for some graph <math>G(V,E)</math> such that <math>|V|=n</math>, <math>|E|=m</math>, <math>G</math> does not contain <math>H</math> as a subgraph. Prove that for <math>k>\frac{n^2\ln n}{m}</math>, there is an edge <math>k</math>-coloring for <math>K_n</math> that <math>K_n</math> contains no monochromatic <math>H</math>.
 
Remark: Let <math>E=\binom{V}{2}</math> be the edge set of <math>K_n</math>. "An edge <math>k</math>-coloring for <math>K_n</math>" is a mapping <math>f:E\to[k]</math>.


== Problem 5 ==
== Problem 5 ==


Consider a sequence of <math>n</math> flips of an unbiased coin. Let <math>H_i</math> denote the absolute value of the excess of the number of HEADS over the number of TAILS seen in the first <math>i</math> flips. Define <math>H=\max_i H_i</math>. Show that <math>\mathbf{E}[H_i]=\Theta(\sqrt{i})</math>, and that <math>\mathbf{E}[H]=\Theta(\sqrt{n})</math>.
Let <math>G(V,E)</math> be a cycle of length <math>k\cdot n</math> and let <math>V=V_1\cup V_2\cup\dots V_n</math> be a partition of its <math>k\cdot n</math> vertices into <math>n</math> pairwise disjoint subsets, each of cardinality <math>k</math>.  
 
For <math>k\ge 11</math>, show that there must be an independent set of <math>G</math> containing precisely one vertex from each <math>V_i</math>.
 
== Bonus Problem ==


Consider the following experiment, which proceeds in a sequence of <i>rounds</i>. For the first round, we have <math>n</math> balls, which are thrown independently and uniformly at random into <math>n</math> bins. After round <math>i</math>, for <math>i\ge 1</math>, we discard every ball that fell into a bin by itself in round <math>i</math> (i.e., we discard a ball if and only if there is no other balls that fell into the same bin). The remaining balls are retained for round <math>i+1</math>, in which they are thrown independently and uniformly at random into the <math>n</math> bins. Show that there is a constant <math>c</math> such that with probability <math>1-o(1)</math>, the number of rounds is at most <math>c\ln\ln n</math>.
Hint: you can use Lovász Local Lemma.

Revision as of 11:26, 9 April 2014

Problem 1

Prove the following identity:

  • [math]\displaystyle{ \sum_{k=1}^n k{n\choose k}= n2^{n-1} }[/math].

(Hint: Use double counting.)

Problem 2

(Erdős-Spencer 1974)

Let [math]\displaystyle{ n }[/math] coins of weights 0 and 1 be given. We are also given a scale with which we may weigh any subset of the coins. Our goal is to determine the weights of coins (that is, to known which coins are 0 and which are 1) with the minimal number of weighings.

This problem can be formalized as follows: A collection [math]\displaystyle{ S_1,S_1,\ldots,S_m\subseteq [n] }[/math] is called determining if an arbitrary subset [math]\displaystyle{ T\subseteq[n] }[/math] can be uniquely determined by the cardinalities [math]\displaystyle{ |S_i\cap T|, 1\le i\le m }[/math].

  • Prove that if there is a determining collection [math]\displaystyle{ S_1,S_1,\ldots,S_m\subseteq [n] }[/math], then there is a way to determine the weights of [math]\displaystyle{ n }[/math] coins with [math]\displaystyle{ m }[/math] weighings.
  • Use pigeonhole principle to show that if a collection [math]\displaystyle{ S_1,S_1,\ldots,S_m\subseteq [n] }[/math] is determining, then it must hold that [math]\displaystyle{ m\ge \frac{n}{\log_2(n+1)} }[/math].

(This gives a lower bound for the number of weighings required to determine the weights of [math]\displaystyle{ n }[/math] coins.)


Problem 3

A set of vertices [math]\displaystyle{ D\subseteq V }[/math] of graph [math]\displaystyle{ G(V,E) }[/math] is a dominating set if for every [math]\displaystyle{ v\in V }[/math], it holds that [math]\displaystyle{ v\in D }[/math] or [math]\displaystyle{ v }[/math] is adjacent to a vertex in [math]\displaystyle{ D }[/math]. The problem of computing minimum dominating set is NP-hard.

  • Prove that for every [math]\displaystyle{ d }[/math]-regular graph with [math]\displaystyle{ n }[/math] vertices, there exists a dominating set with size at most [math]\displaystyle{ \frac{n(1+\ln(d+1))}{d+1} }[/math].
  • Try to obtain an upper bound for the size of dominating set using Lovász Local Lemma. Is it better or worse than previous one?

Problem 4

Let [math]\displaystyle{ H(W,F) }[/math] be a graph and [math]\displaystyle{ n\gt |W| }[/math] be an integer. It is known that for some graph [math]\displaystyle{ G(V,E) }[/math] such that [math]\displaystyle{ |V|=n }[/math], [math]\displaystyle{ |E|=m }[/math], [math]\displaystyle{ G }[/math] does not contain [math]\displaystyle{ H }[/math] as a subgraph. Prove that for [math]\displaystyle{ k\gt \frac{n^2\ln n}{m} }[/math], there is an edge [math]\displaystyle{ k }[/math]-coloring for [math]\displaystyle{ K_n }[/math] that [math]\displaystyle{ K_n }[/math] contains no monochromatic [math]\displaystyle{ H }[/math].

Remark: Let [math]\displaystyle{ E=\binom{V}{2} }[/math] be the edge set of [math]\displaystyle{ K_n }[/math]. "An edge [math]\displaystyle{ k }[/math]-coloring for [math]\displaystyle{ K_n }[/math]" is a mapping [math]\displaystyle{ f:E\to[k] }[/math].

Problem 5

Let [math]\displaystyle{ G(V,E) }[/math] be a cycle of length [math]\displaystyle{ k\cdot n }[/math] and let [math]\displaystyle{ V=V_1\cup V_2\cup\dots V_n }[/math] be a partition of its [math]\displaystyle{ k\cdot n }[/math] vertices into [math]\displaystyle{ n }[/math] pairwise disjoint subsets, each of cardinality [math]\displaystyle{ k }[/math]. For [math]\displaystyle{ k\ge 11 }[/math], show that there must be an independent set of [math]\displaystyle{ G }[/math] containing precisely one vertex from each [math]\displaystyle{ V_i }[/math].

Hint: you can use Lovász Local Lemma.

Retrieved from "https://tcs.nju.edu.cn/wiki/index.php?title=随机算法_(Spring_2014)/Problem_Set_1&oldid=6026"