# Randomized Algorithms (Spring 2010)/Problem Set 6

## Problem 1

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

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