# 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