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