Randomized Algorithms (Spring 2010)/Problem Set 6: Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
imported>WikiSysop
Created page with '== Problem 1 == Consider the following modification of Freivald's algorithm of checking matrix multiplications: {{Theorem|Algorithm| *pick a vector <math>r \in{\color{Red}[k]}^n<…'
 
imported>WikiSysop
Line 20: Line 20:
== Problem 5 ==
== Problem 5 ==
Let <math>T</math> be the set of all <math>m\times n</math> table (matrix) <math>A</math> whose entries are from <math>[k]</math>, and satisfying
Let <math>T</math> be the set of all <math>m\times n</math> table (matrix) <math>A</math> whose entries are from <math>[k]</math>, and satisfying
* for every <math>i=1,2,\ldots,m</math>, <math>\left(\sum_{j=1}^nA_{ij}\right)\bmod k=r_i</math>; and
* for every <math>i=1,2,\ldots,m</math>, it holds that <math>\left(\sum_{j=1}^nA_{ij}\right)\bmod k=r_i</math>; and
* for every <math>j=1,2,\ldots,n</math>, <math>\left(\sum_{i=1}^mA_{ij}\right)\bmod k=c_j</math>;
* for every <math>j=1,2,\ldots,n</math>, it holds that <math>\left(\sum_{i=1}^mA_{ij}\right)\bmod k=c_j</math>;
where <math>r_i\in[k], i=1,2,\ldots,m</math> and <math>c_j\in[k],j=1,2,\ldots,n</math> are parameters.
where <math>r_i\in[k], i=1,2,\ldots,m</math> and <math>c_j\in[k],j=1,2,\ldots,n</math> are parameters.


Suppose that you want to sample a table from <math>T</math> uniformly at random.
Suppose that you want to sample a table from <math>T</math> uniformly at random.
Describe a random walk over <math>T</math>, which converges to the stationary distribution which is uniform over <math>T</math>.
Describe a random walk over <math>T</math>, which converges to the stationary distribution which is uniform over <math>T</math>.

Revision as of 01:22, 29 June 2010

Problem 1

Consider the following modification of Freivald's algorithm of checking matrix multiplications:

Algorithm
  • pick a vector [math]\displaystyle{ r \in{\color{Red}[k]}^n }[/math] uniformly at random;
  • if [math]\displaystyle{ A(Br) = Cr }[/math] then return "yes" else return "no";

Give an upper bound on the probability that the algorithm makes mistake.

Problem 2

A fixed point of a permutation [math]\displaystyle{ \pi }[/math] is a value [math]\displaystyle{ x }[/math] for which [math]\displaystyle{ \pi(x)=x }[/math]. What is the expected number of fixed points of a permutation chosen uniformly at random from all permutations of [math]\displaystyle{ [n] }[/math].

Problem 3

After running the power-of-two choices scheme, [math]\displaystyle{ n }[/math] balls are assigned to [math]\displaystyle{ m=O(n) }[/math] bins. Suppose that the expected maximum load (the maximum number of balls in all bins) is exactly [math]\displaystyle{ \log\log n }[/math]. Give an upper bound on the probability that there exists a bin having more than [math]\displaystyle{ c\log\log n }[/math] balls.

Problem 4

Suppose [math]\displaystyle{ n^2 }[/math] jobs are assigned to [math]\displaystyle{ n }[/math] machines with each job choosing a machine independently and uniformly at random. Let the load on a machine be the number of jobs assigned to it. Show that for any fixed [math]\displaystyle{ \delta \gt 0 }[/math] and sufficiently large [math]\displaystyle{ n }[/math], there is a constant [math]\displaystyle{ \epsilon \lt 1 }[/math] such that the maximum load exceeds [math]\displaystyle{ (1 + \delta)n }[/math] with probability at most [math]\displaystyle{ n\epsilon^n }[/math].

(Hint: Use the Chernoff bound)

Problem 5

Let [math]\displaystyle{ T }[/math] be the set of all [math]\displaystyle{ m\times n }[/math] table (matrix) [math]\displaystyle{ A }[/math] whose entries are from [math]\displaystyle{ [k] }[/math], and satisfying

  • for every [math]\displaystyle{ i=1,2,\ldots,m }[/math], it holds that [math]\displaystyle{ \left(\sum_{j=1}^nA_{ij}\right)\bmod k=r_i }[/math]; and
  • for every [math]\displaystyle{ j=1,2,\ldots,n }[/math], it holds that [math]\displaystyle{ \left(\sum_{i=1}^mA_{ij}\right)\bmod k=c_j }[/math];

where [math]\displaystyle{ r_i\in[k], i=1,2,\ldots,m }[/math] and [math]\displaystyle{ c_j\in[k],j=1,2,\ldots,n }[/math] are parameters.

Suppose that you want to sample a table from [math]\displaystyle{ T }[/math] uniformly at random. Describe a random walk over [math]\displaystyle{ T }[/math], which converges to the stationary distribution which is uniform over [math]\displaystyle{ T }[/math].