View source for Randomized Algorithms (Spring 2010)/Problem Set 6

== 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</math> uniformly at random;
*if <math>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>\pi</math> is a value <math>x</math> for which <math>\pi(x)=x</math>. What is the expected number of fixed points of a permutation chosen uniformly at random from all permutations of <math>[n]</math>.

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

== Problem 4 ==
Suppose <math>n^2</math> jobs are assigned to <math>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>\delta > 0</math> and sufficiently large <math>n</math>, there is a constant <math>\epsilon < 1</math> such that the maximum load exceeds <math>(1 + \delta)n</math> with probability at most <math>n\epsilon^n</math>.

('''Hint''': Use the Chernoff bound)

== 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
* for every <math>i=1,2,\ldots,m</math>, it holds that <math>\sum_{j=1}^nA_{ij}\equiv r_i \pmod k</math>; and
* for every <math>j=1,2,\ldots,n</math>, it holds that <math>\sum_{i=1}^mA_{ij}\equiv c_i \pmod k</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.

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>.