DS C8 Randomized Algorithm

What to Randomize?

• Average-case Analysis: The world behaves randomly, randomly generated input solved by traditional algorithm and analysed.

• Randomized Algorithms: The algorithm makes random decisions as the algorithm processes the worst-case input.

Algorithm	Answer it yields
Efficient deterministic algorithms	Always the correct answer	a special case
Efficient randomized algorithms	With high probability be the correct answer
Randomized algorithms	always correct and run efficiently in expectation

Exp: The Hiring Problem

Problem description

We want to hire an office assistant from headhunter, and we interview a different candidate per day for $N$ days.

• Interviewing Cost: $C_i$
• Hiring Cost: $C_h$

Assume $C_i << C_h$.

Naïve Solution

int Hiring ( EventType C[ ], int N ){   
    /* candidate 0 is a least-qualified dummy candidate */
    int Best = 0;
    int BestQ = the quality of candidate 0;
    for ( i=1; i<=N; i++ ) {
        Qi = interview( i ); /* Ci */
        if ( Qi > BestQ ) {
            BestQ = Qi;
            Best = i;
            hire( i );  /* Ch */
        }
    }
    return Best;
}

Worst case

The candidates come in increasing quality order, all will be hired.

What if ramdom order?

Let

$$X_i = \begin{cases}1， if\ {\rm candidate\ i\ is\ hired}\\0, if\ {\rm candidate\ i\ is\ NOT\ hired}\end{cases}$$

Candidate i will be hired if i is the best one of Candidate 1,2,...,i. As any of first $i$ candidates is equally likely to be best-qualified so far,

$$P[X_i = 1] = \frac{1}{i},\quad E[X_i] = \frac{1}{i}$$

Then $X$​, the number of hires,

$$X = \sum_{i = 1}^{N}X_i$$

$$E[X] = E[\sum_{i = 1}^{N}X_i] = \sum_{i = 1}^{N}E[X_i] = \sum_{i = 1}^{N}\frac{1}{i} = \ln N + O(1)$$

The total cost will be

$$O(C_hE[X] + NC_i) = O(C_h\ln N + NC_i)$$

Randomized Algorithm

int RandomizedHiring ( EventType C[ ], int N ){   
    /* candidate 0 is a least-qualified dummy candidate */
    int Best = 0;
    int BestQ = the quality of candidate 0;
    /* The only modification: adding a random shuffle */
    randomly permute the list of candidates;

    for ( i=1; i<=N; i++ ) {
        Qi = interview( i ); /* Ci */
        if ( Qi > BestQ ) {
            BestQ = Qi;
            Best = i;
            hire( i );  /* Ch */
        }
    }

• The random shuffle guarantees the presentation order of the candidates is random.
• But the shuffle takes time!

Randomized Permutation

• Assign each element A[ i ] a random priority P[ i ]
• Sort by P[i]

void PermuteBySorting ( ElemType A[ ], int N )
{
    for ( i=1; i<=N; i++ )
        A[i].P = 1 + rand()%(N3); 
        /* makes it more likely that all priorities are unique */
    Sort A, using P as the sort keys;
}

Online Hiring Algorithm

• interview the first $k$ candidates and mark the best value among then BESTK .
• interview the remaining candidates and hire the first one that better than BESTK.

int OnlineHiring ( EventType C[ ], int N, int k){
    int Best = N;
    int BestQ = - INT_MAX ;
    for ( i=1; i<=k; i++ ) {
        Qi = interview( i );
        if ( Qi > BestQ )   BestQ = Qi;
    }
    for ( i=k+1; i<=N; i++ ) {
        Qi = interview( i );
        if ( Qi > BestQ ) {
            Best = i;
            break;
        }
    }
    return Best;

Given k

Let $S_i$ be subproblem such that the $i^{th}$ candidate is the best. Then the algorithm works if

• $A$: the best one is at position i

  $$P[A] = \frac{1}{N}$$

• $B$: no one at positions k+1 ~ i–1 are hired

  $$P[B] = \frac{k}{i - 1}$$

  Since the best of Candidate 1,2,...,i is in the fist $k$ candidates.

These two are independent.

$$P[S_i] = P[AB] = P[A]P[B] = \frac{k}{N(i-1)}$$

Then

$$P[S] = \sum_{i = k+1}^{N}P[S_i] = \sum_{i = k+1}^{N}\frac{k}{N(i-1)} = \frac{k}{N}\sum_{i = k}^{N-1}\frac{1}{i}$$

And we get

$$\int_k^N\frac{1}{x}{\rm d}x \le\sum_{i = k}^{N-1}\frac{1}{i} \le\int_{k-1}^{N-1}\frac{1}{x}{\rm d}x$$

Hence

$$\frac{k}{N}\int_k^N\frac{1}{x}{\rm d}x \le\frac{k}{N}\sum_{i = k}^{N-1}\frac{1}{i} \le\frac{k}{N}\int_{k-1}^{N-1}\frac{1}{x}{\rm d}x$$

$$\frac{k}{N}\ln\frac{N}{k}\le\frac{k}{N}\sum_{i = k}^{N-1}\frac{1}{i} \le\frac{k}{N}\ln\frac{N-1}{k-1}$$

Let

$$\begin{align*} f(k) &=\frac{k}{N}\ln\frac{N}{k}\\ f'(k) &= \frac{1}{N}\ln\frac{N}{k} + \frac{k}{N}\frac{k}{N}(-\frac{N}{k^2}) = \frac{1}{N}(\ln\frac{N}{k} - 1) \end{align*}$$

Then $f'(k) = 0,k = \frac{N}{e}$

$$f(k)_{max} = f(\frac{N}{e}) = \frac{1}{e}$$

The best $k$ is $\frac{N}{e}$.

Exp: Quick Sort

RECALL

Deterministic Quicksort

• worst-case running time: $O(N^2)$
• average case running time: $O(N\log N)$, assuming every input permutation is equally likely.

Central splitter

Central splitter is the pivot that divides the set so that each side contains at least $\frac{n}{4}$ of $n$ items.

In Modified Quicksort, we always select a central splitter as pivot before recursions.

• central splitter avoids the degeneration to the $O(N^2)$.

Time complexity Analysis

If a pivot is chosen randomly, then

$$P({\rm find\ a\ central\ splitter}) = \frac{1}{2}$$

If we re-choose the pivot if it turns out that the last chosen pivot is not a central splitter, then

$$E(n_{\rm find\ a\ central\ splitter}) = 2$$

It is easy to get that the whole tree makes it to the deepest depth if in every recursion, the pivot split $n$ items into $\frac{n}{4}$ and $\frac{3n}{4}$ items.

Let the subproblem $S$ be of Type j if

$$N(\frac{3}{4})^{j+1} \le |S| \le N(\frac{3}{4})^j$$

and

$$n_{\rm type\ j}\times Size(j) \le N$$

where $n_{\rm type\ j}$ is the number of subproblems of type j, and $Size(j)$ is the size of subproblem of type j. Then $n_{\rm type\ j}\le(\frac{4}{3})^{j+1}$ .

Then

$$E[T_{\rm type\ j}] = O(N(\frac{3}{4})^{j})\times(\frac{4}{3})^{j+1} = O(N)$$

$$N(\frac{3}{4})^j \ge 1$$

then the Number of different types is $\log_{\frac{4}{3}}N$. The total time complexity is

$$T(N) = \log_{\frac{4}{3}}N \times O(N) = O(N\log N)$$