Hashing and Randomized Algorithms

Probability

6.1. You are given [math]\displaystyle{ n }[/math] unbiased coins, and perform the following process to generate all heads. Toss all [math]\displaystyle{ n }[/math] coins independently at random onto a table. Each round consists of picking up all the tails-up coins and tossing them onto the table again. You repeat until all coins are heads.

(a) What is the expected number of rounds performed by the process?

(b) What is the expected number of coin tosses performed by the process?

Solution

6.2. Suppose we flip [math]\displaystyle{ n }[/math] coins each of known bias, such that [math]\displaystyle{ p_i }[/math] is the probability of the [math]\displaystyle{ i }[/math]th coin being a head. Present an efficient algorithm to determine the exact probability of getting exactly [math]\displaystyle{ k }[/math] heads given [math]\displaystyle{ p_1, . . . , p_n \in [0, 1] }[/math].

6.3. An inversion of a permutation is a pair of elements that are out of order.

(a) Show that a permutation of [math]\displaystyle{ n }[/math] items has at most [math]\displaystyle{ n(n - 1)/2 }[/math] inversions. Which permutation(s) have exactly n(n - 1)/2 inversions?

(b) Let P be a permutation and [math]\displaystyle{ P^r }[/math] be the reversal of this permutation. Show that [math]\displaystyle{ P }[/math] and [math]\displaystyle{ P^r }[/math] have a total of exactly [math]\displaystyle{ n(n - 1)/2 }[/math] inversions.

(c) Use the previous result to argue that the expected number of inversions in a random permutation is [math]\displaystyle{ n(n - 1)/4 }[/math].

Solution

6.4. A derangement is a permutation [math]\displaystyle{ p }[/math] of [math]\displaystyle{ {1, . . . , n} }[/math] such that no item is in its proper position, that is, [math]\displaystyle{ p_i \neq i }[/math] for all [math]\displaystyle{ 1 \leq i \leq n }[/math]. What is the probability that a random permutation is a derangement?