Randomized Algorithms (Spring 2010)/Problem Set 6

From EtoneWiki
Jump to: navigation, search

Problem 1

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.

Problem 2

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 .

Problem 3

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.

Problem 4

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)

Problem 5

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 .