Randomized Algorithms (Spring 2010)/Problem Set 6
Consider the following modification of Freivald's algorithm of checking matrix multiplications:
- pick a vector uniformly at random;
- if then return "yes" else return "no";
Give an upper bound on the probability that the algorithm makes mistake.
A fixed point of a permutation is a value for which . What is the expected number of fixed points of a permutation chosen uniformly at random from all permutations of .
After running the power-of-two choices scheme, balls are assigned to bins. Suppose that the expected maximum load (the maximum number of balls in all bins) is exactly . Give an upper bound on the probability that there exists a bin having more than balls.
Suppose jobs are assigned to 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 and sufficiently large , there is a constant such that the maximum load exceeds with probability at most .
(Hint: Use the Chernoff bound)
Let be the set of all table (matrix) whose entries are from , and satisfying
- for every , it holds that ; and
- for every , it holds that ;
where and are parameters.
Suppose that you want to sample a table from uniformly at random. Describe a random walk over , which converges to the stationary distribution which is uniform over .