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