You need to login before you can make any post submission.

Add New Chapter
## Tutorial

# Randomized Algorithms

## Concept of Expectation

### Expected Value

##### Note:

### Linearity of Expectation

### Probability and Expectation

## Mathematical Background

## Analyzing Randomized Algorithms

## Classification of Randomized Algorithms

## Applications of Randomized Algorithms

An algorithm that uses random numbers to decide what to do next anywhere in its logic is called Randomized Algorithm.

**Examples:**

Uses random number to pick the next pivot (or randomly shuffles the array).*Randomized Quick Sort:*Randomly picks an edge.*Karger’s algorithm:*

A random variable can take any possible value in its range, so it is important to define the **expected value** of any random variable.

Expected value of a discrete random variable is R defined as following:

Suppose R can take value r_{1} with probability p_{1}, value r_{2} with probability p_{2}, and so on, up to value r_{k} with probability p_{k}.

Then the expectation of this random variable R is defined as:

E[R] = r_{1}*p_{1}+ r_{2}*p_{2}+ … r_{k}*p_{k}

**Example:**

Given a fair dice with 6 faces, the dice is thrown n times, find expected value of sum of all results.

- The above way to solve the problem becomes difficult when there are more dice throws.
- If we know about
**linearity of expectation**, then we can quickly solve the above problem for any number of throws.

Let R_{1} and R_{2} be two discrete random variables on some probability space, then expected value of R_{1} + R_{2} is:

E[R_{1}+ R_{2}] = E[R_{1}] + E[R_{2}]

- Some randomized algorithms have deterministic time complexity.
- Example: Implementation of Karger’s algorithm has time complexity as O(E).
- Such algorithms are called
**Monte Carlo Algorithms**and are easier to analyse for worst case.

- On the other hand, time complexity of other randomized algorithms (other than Las Vegas) is dependent on value of random variable.
- Such Randomized algorithms are called
**Las Vegas Algorithms**. - These algorithms are typically analysed for expected worst case.
- To compute expected time taken in worst case, all possible values of the used random variable needs to be considered in worst case and time taken by every possible value needs to be evaluated.
- Average of all evaluated times is the expected worst case time complexity.
- Below facts are generally helpful in analysis os such algorithms.
- Linearity of Expectation
- Expected Number of Trials until Success.

- Such Randomized algorithms are called

Randomized algorithms are classified in two categories:

**Las Vegas Algorithms:**- These algorithms always produce correct or optimum result.
- Time complexity of these algorithms is based on a random value and time complexity is evaluated as expected value.
Randomized QuickSort always sorts an input array and expected worst case time complexity of QuickSort is O(nLogn).*Example:*

**Monte Carlo Algorithms:**- Produce correct or optimum result with some probability.
- These algorithms have deterministic running time and it is generally easier to find out worst case time complexity.
Implementation of Karger’s Algorithm produces minimum cut with probability greater than or equal to 1/n*Example:*^{2}(n is number of vertices) and has worst case time complexity as O(E).Fermet Method for Primality Testing.*Another Example:*

Example to Understand Classification:Consider a binary array where exactly half elements are 0 and half are 1. The task is to find index of any 1.

- Las Vegas algorithm for this task is to keep picking a random element until we find a 1.
- A Monte Carlo algorithm for the same is to keep picking a random element until we either find 1 or we have tried maximum allowed times say k.
- The Las Vegas algorithm always finds an index of 1, but time complexity is determined as expect value. The expected number of trials before success is 2, therefore expected time complexity is O(1).
- The Monte Carlo Algorithm finds a 1 with probability [1 – (1/2)k]. Time complexity of Monte Carlo is O(k) which is deterministic

- Even for sorted array randomized
**quick sort**gives O(nlogn) expected time. - Randomized algorithms have huge applications in
**Cryptography**. **Load Balancing****Number-Theoretic Applications:**Primality Testing**Data Structures:**Hashing, Sorting, Searching, Order Statistics and Computational Geometry.**Algebraic identities:**Polynomial and matrix identity verification. Interactive proof systems.**Mathematical programming:**Faster algorithms for linear programming, Rounding linear program solutions to integer program solutions**Graph algorithms:**Minimum spanning trees, shortest paths, minimum cuts.**Counting and enumeration:**Matrix permanent Counting combinatorial structures.**Parallel and distributed computing:**Deadlock avoidance distributed consensus.**Probabilistic existence proofs:**Show that a combinatorial object arises with non-zero probability among objects drawn from a suitable probability space.**Derandomization:**First devise a randomized algorithm then argue that it can be derandomized to yield a deterministic algorithm.