Randomized Algorithms

---

Rand: “Mirror, mirror, hanging on Alek’s wall (no I don’t actually have a mirror that would be kinda creppy / narscisistic, you get the point, maybe read this as”webcam, webcam…“) who is the fastest sorting algorithm of them all”

Alek: “Ummm, Probably quicksort”

Rand: “But it has worst case performance like \(O(n^2)\) !!! That’s so trash. What about mergesort?”

Alek: “Actually it turns out that with high probability in n quicksort is super fast, in particular \(O(n \log n)\), and actually in particular way better than mergesort because the expectation of the number of comparisons that it makes is like \(2n \log n\) which is a super good constant”

Rand: “hmmm, that sounds pretty good. tell me more.”

Alek: “OK, and as an added bonus I’ll refrain from my entropy joke”

---

What is a randomized algorithm?

In this post I’m going to discuss algorithms that use randomness. Randomness plays a crucial role in many algorithms. For example, randomness is used in

• Getting a good fast heuristic approximate solution to a problem
• Cryptography: randomness is the key to security
• Analyzing algorithms that deterministically get the right answer, but use randomness to get there. With such an algorithm it is often desirable to show that the algorithm is fast “with high probability”

Analysis of “probably fast” algorithms

Quicksort is the prototypical example (in my opinion) of a randomized algorithm that is fast “with high probability”.

I’d like to analyze the running time of quicksort using something called a concentration bound, but first I’ll quickly talk about some basic probability theory.

Probability background

I define some basic concepts:

begin remark For this post, only discrete probability is of interest (stay tuned for a post on measure theory and continuous probability at some point in time!) Thus, we take \(\mathcal{F}= \mathcal{P}(\Omega)\) (the powerset). Also the state space will always be a (finite) subset of \(\mathbb{R}\) in this post. end remark

Bounds

Now that I have defined probability, I will demonstrate some bounds on probabilities.

This is kind of useful on its own, but there are some really cool coroloaries: concentration bounds.

Note: this is really nice, it says that there is a really good chance that the outcome of a random experiment will be pretty close it’s mean (i.e. the random variable is “tightly concentrated around its mean”).

This is nice, but for certain types of random variables you can actually give a much stronger concentration bound. In particular,

Rand: “Holly cow, that was gnarly, was that really relevant to quicksort?” Alek: “yeah we can analyze quicksort now”

Applying Chernoff Bound to Quicksort

First let me review the quicksort algorithm:

• Pick a pivot randomly (this is key!)
• Partition the array relative to the pivot
• Recurse on the subarray of elements less than the pivot, and recurse on the subarray of elements greater than the pivot

Here is an implementation of this algorithm in C++

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int partition(int* A, int n, int pivot){
  int low = 0; int high = n-1;
  while (low < high){
    while(A[low] <= pivot && low < high){
      low++;
    }
    while(A[high] > pivot && low < high){
      high--;
    }
    int tmp = A[low];
    A[low] = A[high];
    A[high] = tmp;
  }
  if(A[low] <= pivot && low < n){
    low++;
  }
  return low;
}

// Note: I assume that the elements of A are all distinct in this simplisitc implementation of quicksort, it is easy to modify this code to work for arrays that can have duplicate elements 
void quicksort(int* A, int n){
  if(n>1){
    int pivot = A[rand()%n]; // randomly select the pivot
    int splitIndex = partition(A, n, pivot);
    quicksort(A, splitIndex);
    quicksort(A+splitIndex, n-splitIndex);
  }
}

int main(){
    srand(time(NULL)); // set seed for rng
    int n = 100;
    int* A = (int*)malloc(sizeof(int)*n);
    for (int i = 0; i < n; ++i) {
        A[i] = rand();
    }
    quicksort(A, n);
}

Let \(X_i\) be the random variable which has value 1 if the rank of the pivot is in the middle, i.e. in \([n/4, 3n/4]\) Then \(X_i\) is bernouli with \(p=1/2\). If you flip \(\log n\) coins then whp the number of heads is tightly concentrated around half thus you basically just need \(2n\log n\) comparisons for quicksort whp.

More formally, let \(\epsilon > 0\) be constant, and say we have \(2\log n\) fair coins. Then the chernoff bound gives

\[Pr[|\sum_{i=1}^{2\log n} X_i - \log n| > \epsilon \log n] \le 2 e^{- (1/3)\epsilon^2\log n} = 2 n^{-\epsilon^2/3}. \] In fact we really only need

\[Pr[\sum_{i}^{2\log n} X_i > (1+\epsilon)\log n] < n^{-\epsilon^2/3}.\] This is awesome, i.e. high probability. To guarantee that we get more than \(\log_{4/3} n\) heads (which is what we need), we set \(\epsilon = \frac{1}{\ln (4/3)} - 1 \approx 2.5\) Then we get that the result happens with probability approximately \(1/n^2\).

Lowerbound on comparison based sorting

It turns out that, as you might have known, the algorithm had to be in \(\Omega(n \log n)\), because all comparison based sorting algorithms are. Here is a proof: Consider a binary tree with \(n!\) leaves. Then it has depth \(\log n!\). By Stirling’s approximation this is like \(n \log \frac{n}{e} = \Omega(n \log n)\). With comparison based sorting algorithms every comparison moves you a level in this tree, and you have to get to a leaf starting from the root. Hence the lower bound.

Note that there are other types of sorting algorithms, e.g. counting sort, radix sort (these exploit the fact that the arrays they need to sort have a small discrete set of possible values in them).