*Randomized Selection*algorithm -- Las Vegas version to be more precise. Given a set $S = \{ a_1\,a_2\,a_3\ldots a_n \}$ of keys and an integer $k \in [1,n]$ the

*selection problem*asks to report the $k^{th}$ largest key in the set $S$. Recall that this problem can be solved optimally using $O(n)$ comparison operations using the BFPRT (Blum, Floyd, Pratt, Rivest and Tarjan 1973) algorithm. However a correct implementation of BFPRT algorithm may take a lot of code. On the other hand randomized algorithms for many deterministic algorithms are often simpler to implement. The algorithm chooses a random pivot for partitioning the input and recursively picks on of the partition until the partition (sub problem) size is just one. Following is an implementation of

`in around 25 lines.`

**RandSelect**Our goal here is the analyze the

*and*

**expected run-time***for the problem size converge to*

**expected number of steps***unity*-- more precisely the expected value of the variable

`in the following code. I have purposefully kept the analysis very rigorous to make it accessible to everyone.`

**rand_walk_steps**TL;DR "Expected number of comparisons in

`is $\Theta(n)$ and expected number of`

**RandSelect**`is $\Theta(\log(n))$".`

**rand_walk_steps**// Randomized selection algorithm to pick k^th largest element // in a mutable array. template < typename T > T RandSelect(T *array, size_t n, size_t k) { assert(k > 0 && k <= n); size_t problem_size = n, select = k; // What is the expected value of rand_walk_steps ?? size_t rand_walk_steps = 0; while (problem_size > 1) { size_t i = 0, j = problem_size - 1; size_t ridx = RandArrayIndex(problem_size); const T pivot = array[ridx]; // Partition the sub problem with pivot. while (i <= j) { if (array[i] <= pivot) { i++; } else if (array[j] > pivot) { j--; } else { std::swap(array[i], array[j]); } } problem_size = (i >= select) ? i : problem_size - i; array = (i >= select) ? array : &array[i]; select = (i >= select) ? select : select - i; ++rand_walk_steps; } return array[0]; }

Let $X_i$ be the random variable corresponding to problem size in $i^{th}$ step ($1 \geq i \geq n-1$) in the algorithm -- each step corresponds to one iteration of the outer most

`loop. If the algorithm terminates in $j$ steps then all $X_k$ with $k>j$ are set to $0$.`

**while**$$

\begin{array}{lll}

X_i &=& \text{Random variable for problem size in }i^{th}\text{ iteration of the outer most}\textsf{ while}\text{ loop} \\

X_i && \left\{ \begin{array}{lr} \in [1,X_{i-1}-1] & \textsf{If } X_{i-1} > 1 \\

= 0 & \textsf{Otherwise}

\end{array} \right. \\

X_0 &=& n \,\,\,\,\,\,\, \text{Initial problem size and }\,\,\, E[X_0] = n \\

&& \\

\end{array}

$$

** Lemma-1: ** If $X_{i-1} >1$ Then $E[X_i | X_{i-1}] = \frac{X_{i-1}}{2}$

* Proof: * For a given $X_{i-1} > 1$ the random variable $X_{i}$ is uniformly distributed in the range $[1,X_{i-1}-1]$. Hence the expected value is simply the average $\frac{1 + (X_{i-1}-1)}{2} = \frac{X_{i-1}}{2}$ $\Box$.

** Lemma-2: ** $E[X_i] = \frac{n}{2^i}$

* Proof: *

$$

\begin{array}{llll}

&E[X_i|X_{i-1}] &=& \frac{X_{i-1}}{2}\,\,\,\,\,\text{From Lemma-1}\\

&E[\,E[X_i|X_{i-1}]\,] &=& E[\frac{X_{i-1}}{2}] \\

\Rightarrow & E[X_i] &=& E[\frac{X_{i-1}}{2}] = \frac{E[X_{i-1}]}{2}\,\,\,\,\,\text{for any two random variables } X,Y\,\,E[E[X|Y]] = E[X]\\

&&=&\frac{1}{2}\times E[X_{i-1}] = \frac{1}{2^2}\times E[X_{i-2}] \ldots \,\,\,\,\, \text{Apply recursively} \\

&&\ldots& \\

&&=& \frac{1}{2^i}\times E[X_{i-i}] = \frac{E[X_0]}{2^i} = \frac{n}{2^i} \,\, \Box\\

\end{array}

$$

** Theorem-1: ** Expected number of comparisons done by `RandSelect` is $\Theta(n)$.

* Proof: * The number comparisons done by the algorithm in each iteration is $\leq 3\times X_i$. We at most $2$ comparisons in the inner ` if..else` branch and $1$ comparison to test $i <= j$, so a total of $3$ comparisons in the each iteration of the inner most `while` loop. The loop runs at most $X_i$ times in the $i^{th}$ iteration of the outer most ` while` loop. Finally we need $1$ comparison to test the termination of the `while` loop. Let $T$ be the random variable corresponding the total number of comparisons in the algorithm. So we need to find $E[T]$.

$$

\begin{array}{ll}

&T \leq 3(X_0 + X_1 + X_2 + \ldots X_{n-1}) + 1 & \text{Total number of comparisons in the Algorithm. }\\

&&\\

\Rightarrow& \sum_{i=0}^{n-1} X_i \leq T \leq 3\sum_{i=0}^{n-1} X_{i} + 1 & \\

& \sum_{i=0}^{n-1} E[X_i] \leq E[T] \leq 3\sum_{i=0}^{n-1} E[X_{i}] + 1 & \text{Linearity of expectation.} \\

&&\\

& \sum_{i=0}^{n-1} \frac{n}{2^i} \leq E[T] \leq 3\sum_{i=0}^{n-1} \frac{n}{2^i} + n & \text{Apply Lemma-2.} \\

& 2n\left(1-\frac{1}{2^n}\right) \leq E[T] \leq 6n\left(1-\frac{1}{2^n}\right) +n & \text{Use: } \sum_{i=0}^{n-1}\frac{1}{2^i} = \frac{1-1/2^n}{1-1/2}.\\

&&\\

\Rightarrow &n \leq E[T] < 6n + 1 = 6n +1 & \text{Use: for } n\geq 1\,\,\,,\frac{1}{2} \leq \left(1-\frac{1}{2^n}\right) < 1 \\
&&\\
\Rightarrow & E[T] = \Theta(n)\,\,\Box & \\
\end{array}
$$

We now return the question of the expected number of steps for the problem size to reach unity (i.e. expected number of iterations of the outer most

`while`loop). This is also referred as the expected number of

*recursive*calls in Motwani and Raghavan's book. However the following analysis is much simpler than the application of a calculus based lemma based on random walks in the book. Let $Y_{i}$ be a random variable corresponding to the number of iterations starting with a problem size of $X_{i} > 1$.

$$

\begin{array}{lll}

Y_{i} &:=&\text{random variable for the number of steps with problem size }\,\, X_{i} >1 \\

Y_i &=& 1 + Y_{i+1} \,\,\,\,\,\, \text{(Recursive formulation)}\\

Y = Y_0 &=& \underbrace{1 + 1 + 1 \dots + 1}_{k \text{-times}} + Y_{k} \,\,\,\,\,\, \text{(Expand } k \text{ times)}\\

&& \\

\end{array}

$$

** Theorem-2: ** Expected number of steps for the problem size to reach unity, $E[Y] = \Theta(\log(n))$.

* Proof: *

$$

\begin{array}{ll}

&Y_i \leq X_{i}\,\,\,\, \text{ (Number of steps are at most problem size at } i^{th} \text{ step which is } X_i)\\

& \\

\Rightarrow &E[Y_i] \leq E[X_i] \,\,\,\, \text{( Let } Z = X_i-Y_i\,\,\,\,,\,\,\,\, E[Z] = E[X_i]-E[Y_i] \geq 0 \text{)}\\

&E[Y_i] \leq E[X_i] = \frac{n}{2^i} \,\,\,\, \text{ (Apply Lemma-2)} \\

&Y = Y_0 = \underbrace{1 + 1 + 1 \dots + 1}_{t \text{-times}} + Y_{t} \\

\Rightarrow & E[Y] = \underbrace{E[1] + E[1] \dots + E[1]}_{t \text{-times}} + E[Y_{t}] = t + E[Y_{t}] \\

&E[Y] = t + E[Y_{t}] \leq t + E[X_{t}] \leq t + \frac{n}{2^t} \\

&\\

\Rightarrow &t \leq E[Y] \leq t + \frac{n}{2^t} \,\,\,\, \text{After } t \text{ steps }\\

& \\

&\text{When } t = \log_2(n) \text{ the above inequality becomes the following } \\

& \log_2(n) \leq E[Y] \leq \log_2(n) + \frac{n}{2^{log_2(n)}} = \log_2(n) +1 \\

\Rightarrow & E[Y] =\Theta(log(n)) \,\, \Box \\

\end{array}

$$

This completes our expected analysis of the

`algorithm. The analysis just uses elementary probability theory without relying on a Calculus based random walk theorem in the`

**RandSelect***"Randomized Algorithms"*book by Motwani and Raghavan -- (

**Theorem-1.3**on page-15).

## No comments:

Post a Comment