03 Analysis of Algorithms: Probabilistic Analysis

In this section of the course, we look at the way to use probability to analyze algorithms from the point of view of the worst case analysis.

In order to do this, we will look at:
1. What is the Probability of an Indicator function?
2. How to use the Indicator function to analyze a simple hiring algorithms.
3. How we can enforce the uniform probability property so algorithms based in probability can be simple and efficient.

1. Analysis of Algorithms
Probabilistic Analysis
Andres Mendez-Vazquez
March 16, 2015
1 / 19

2. Outline
1
The Hiring Problem
2
The Hiring Algorithm
3
Paradigm
4
Indicator Random Variable
5
The Randomized Hiring
6
Methods to Enforce Randomization
Permute By Sorting
Permute in Place
2 / 19

3. A Random Process
First
In order to exemplify the usage of the probabilistic analysis, we will use the
Hiring Problem.
Why?
It is clear that hiring a person is a random process.
An Example
Many possible process involving a Expected count in the number of steps
of them.
3 / 19

4. The Hiring Problem
Suppose the following
You are using an employment agency to hire a new oce assistant.
You interview the candidate and must immediately decide whether or
not to hire that person.
Cost
Cost to interview isciper candidate.
Cost to hire ischper candidate.
Assume thatch>ci.
Observation!
You must have somebody working all the time!
You will always hire the best candidate that you interview!
4 / 19

5. Hiring Algorithm
Hire-Assistant(n)
b e s t = 0// c a n d i d a t e dummy
f o r
i n t e r v i e w i
i f
then b e s t = i
h i r e c a n d i d a t e i
COSTGivenncandidates and we hire m of them,O(nci+mch)
5 / 19

6. Paradigm
We have that
We need to nd the maximum or minimum in a sequence by
examining each element and maintaining a current WINNER
The variablemdenotes how many times we change our notion of
which element is currently winning.
Worst Case Analysis
You hire all of n
O(nci+nch) =O(nch)
Why? Because every time we hire somebody, we re somebody.
6 / 19

7. We want to avoid the worst case
How?
Because many times we do not get the worst case
Actually
Many times we get the Average input
This makes
The probability analysis a useful tool to analyze average complexities for
many algorithms
7 / 19

8. Probabilistic Analysis
Uniform Distribution Assumption
1
Assign arankto each candidatei,rank:U! f1;2; :::;ng
2
The possible number of permutations of individuals by the rank isn!
3
Therefore, if we assume that all individuals have the same probability
to have any ranking - Unifrom Distribution Assumption.
4
The input in the hiring problem comes from a uniform distribution.
Essentials of Probability Analysis
You assume a distribution over permutation of elements.
The expectation is over this distribution.
This technique requires that we can make a reasonable
characterization of the input distribution.
8 / 19

9. Indicator Random Variable
Indicator Random Variable
We require to use the indicator random variable to facilitate the use of
probabilistic analysis:
IfAg=
(
0 if A does not ocurr
1 if A does ocurr
:
Using this we have
Lemma 5.1
Given a sample spaceSand an eventAin the sample spaceS, let
XA=IfAg. ThenE[XA] =PrfAg.
9 / 19

10. Analyzing Hiring By Indicator Variable
GivenX
Assume a X, the random variable of the number of times we hire a
person. ThenE[X] =
P
n
x=1
xPrfX=xg
We could analyze the hiring problem by using the indicator function:
Xi=Ifcandidate i is hiredg=
(
1 if candidate i is hired
0 if candidate i is not hired
:
In addition
X=X1+X2+:::+Xn
An because the candidates come randomly (Uniform Assumption), we
have thatE[Xi] =Prfcantidate i is hiredg=
1
i
After all each time, we get a newicandidate is better than the
previous 1 toi1.
10 / 19

11. Analyzing Hiring By Indicator Variable
Finally...
We can calculate
E[X] =E
"
n
X
i=1
Xi
#
=
n
X
i=1
E[X] =
n
X
i=1
1
i
=lnn+O(1):
Final hiring cost isO(chlnn).
11 / 19

12. Hiring Problem
What if
The employment agency sends us a list of allncandidates in advance.
On each day, we randomly choose a candidate from the list to
interview.
Instead of relaying on the candidate being presented to us in a random
order, we take control of the process and enforce a random order.
What makes an algorithm randomized?
An algorithm israndomizedif its behavior is determined in part by
values produced by a random-number generator.
Arandom-number generatoris implemented by a
pseudorandom-number generator, which is a deterministic method
returning numbers that look random and can pass certain statistical
tests.
12 / 19

13. Hiring Algorithm
Randomized-Hire-Assistant(n)
Randomly Permute the l i s t of c a n d i d a t e s
b e s t = 0// c a n d i d a t e dummy
f o r
i n t e r v i e w i
i f
then b e s t = i
h i r e c a n d i d a t e i
Lemma (5.3)
The expected hiring cost of the procedure Randomized-Hiring-Assistant is
O(chlnn)
Proof.
Go to the Blackboard.
13 / 19

14. Methods to Enforce Randomization
Randomly Permute Arrays
1
A=h1;2;3;4i
2
P=h36;3;97;19i
Then, sortB=h2;4;1;3i
Permute-By-Sorting(A)
n = l e n g h t [A]
f o r
do
s o r t A, u s i n g P as s o r t keys
r e t u r n
15 / 19

15. Proving Correctness of Permute-By-Sorting
Lemma 5.4
Procedure Permute-By-Sorting produces a uniform random permutation of
the input, assuming that all priorities are distinct.
Proof:
16 / 19

16. Permute in Place
Randomize-In-Place(A)
n = l e n g h t [A]
f o r
do > A[RANDOM( i , n ) ]
Lemma (5.5)
Procedure Randomize-In-Place computes a unifrom random permutation.
Proof.
Go to the Blackboard.
18 / 19

17. Exercises
5.1-1
5.1-2
5.2-1
5.2-3
5.2-5
5.3-1
5.3-3
5.3-4
19 / 19