# Randomized Algorithms

Date: February 1, 2001

"Wir müssen wissen, wir werden wissen" (We must know, we shall know)

--- David Hilbert

# Tail Inequalities

## The Chernoff Bound

1. - independent Bernoulli triangles, where and Each is known as a Poisson trials.

2. . .

3. Question: Probability that ? Proof. By Markov inequality, we have: On the other hand, Namely, Let . We know that (since ). Thus,       if we set .      # 4.2 - Routing in a Parallel Computer : A graph of processors. Packets can be sent on edges. : The vertices (i.e., processors) of . , and is a hypercube. Each processes is a binary string .

Question: Given a permutation , how to send the permutation and create minimum delay? How do we sent a packet? We use bit fixing. Namely, the packet from the node, always go to the current adjacent node that have the first different bit as we scan the destination string . For example, packet from going to , would pass through , , .

We assume each edge have a FIFO queue. Here is the algorithm:

(i)
Pick a random intermediate destination from . Packet travels to .

(ii)
Wait till all the packet arrive to their intermediate destination.

(iii)
Packet travels from to its destination .

We analyze only (i) as (iii) follows from the same analysis. - the route taken by in (i).   - 1 if share an edge, 0 otherwise. Total delay for is . Note, that for a fixed , the variables are independent (not however, that are not independent!). , let be the number of routes that pass through . and thus Because of symmetry, the variables have the same distribution for all the edges of . On the other hand, the expected length of a path is , there are routes, and there are edges. We conclude . Thus By the Chernoff inequality Chernoff, we have Since there are packets, we know that with probability all packets arrive to their temporary destination in a delay of most . Sariel Har-Peled 2001-02-01