# 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 ${\displaystyle r\in {\color {Red}[k]}^{n}}$ uniformly at random; if ${\displaystyle A(Br)=Cr}$ 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 ${\displaystyle \pi }$ is a value ${\displaystyle x}$ for which ${\displaystyle \pi (x)=x}$. What is the expected number of fixed points of a permutation chosen uniformly at random from all permutations of ${\displaystyle [n]}$.

## Problem 3

After running the power-of-two choices scheme, ${\displaystyle n}$ balls are assigned to ${\displaystyle m=O(n)}$ bins. Suppose that the expected maximum load (the maximum number of balls in all bins) is exactly ${\displaystyle \log \log n}$. Give an upper bound on the probability that there exists a bin having more than ${\displaystyle c\log \log n}$ balls.

## Problem 4

Suppose ${\displaystyle n^{2}}$ jobs are assigned to ${\displaystyle n}$ 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 ${\displaystyle \delta >0}$ and sufficiently large ${\displaystyle n}$, there is a constant ${\displaystyle \epsilon <1}$ such that the maximum load exceeds ${\displaystyle (1+\delta )n}$ with probability at most ${\displaystyle n\epsilon ^{n}}$.

(Hint: Use the Chernoff bound)

## Problem 5

Let ${\displaystyle T}$ be the set of all ${\displaystyle m\times n}$ table (matrix) ${\displaystyle A}$ whose entries are from ${\displaystyle [k]}$, and satisfying

• for every ${\displaystyle i=1,2,\ldots ,m}$, it holds that ${\displaystyle \sum _{j=1}^{n}A_{ij}\equiv r_{i}{\pmod {k}}}$; and
• for every ${\displaystyle j=1,2,\ldots ,n}$, it holds that ${\displaystyle \sum _{i=1}^{m}A_{ij}\equiv c_{i}{\pmod {k}}}$;

where ${\displaystyle r_{i}\in [k],i=1,2,\ldots ,m}$ and ${\displaystyle c_{j}\in [k],j=1,2,\ldots ,n}$ are parameters.

Suppose that you want to sample a table from ${\displaystyle T}$ uniformly at random. Describe a random walk over ${\displaystyle T}$, which converges to the stationary distribution which is uniform over ${\displaystyle T}$.