** Las-Vegas** algorithms, unlike Monte-Carlo, never give
wrong answers. Unlucky coin-flips just make them run longer than
expected. Quick-Sort is a simple example. It is about as fast as
deterministic sorters, but is popular due to its simplicity. It sorts an
array

For easy reference, replace the array entries with their positions
**1,...,n** in the *sorted output* (no effect on the algorithm).
Denote **t(i)** the (random) time **i** is chosen as a pivot.
Then **i** will ever be compared with **j** iff either **t(i)**
or **t(j)** is the smallest among **t(i),...,t(j)**.
This has **2** out of **|j-i|+1** chances. So, the expected number of
comparisons is Note,
that the expectation of the sum of variables is the sum of their expectations
(not true, say, for product).

The above Monte-Carlo and Las-Vegas algorithms require choosing strings *at
random* with uniform distribution. We mentally picture that as flipping a coin.
(Computers use *pseudo-random generators* rather than coins in hope, rarely
supported by proofs, that their outputs have all the statistical properties of
truly random coin flips needed for the analysis of the algorithm.)

- The primality algorithm works for
*all*instances. It tosses the coin itself and can repeat it for a more reliable answer. The HC algorithm only works for*most*instances (with isolated nodes). - In the HC algorithm, we must trust the opponent to follow the presumed random procedure. If he cheats and produces connected graphs often, our analysis breaks down.

Several philosophers dine at a circular table. Before each of them is a plate, and left of each plate is either a knife or a fork arranged so that each diner has a knife on his right and a fork on his left or vice versa. The problem is that neighboring diners must share the utensils: neighbors cannot eat at the same time. How can the philosophers complete the dinner given that all of them must act in the same way without any central organizer? Trying to grab the knives and forks at once may turn them into fighting philosophers. Instead they could each flip a coin, and sit still if it comes up heads, otherwise try to grab the utensils. If two diners try to grab the same utensil, neither succeeds. If they repeat this procedure enough times, most likely each philosopher will eventually get both a knife and fork without interference.

We have no time to actually analyze this and many other scenaria, where randomness is crucial. Instead we will take a look into the concept of Randomness itself.

Wed Aug 21 20:35:42 EDT 1996