程序代写代做代考 algorithm COMP3600/6466

COMP3600/6466 – Algorithms
Probabilistic Analysis [CLRS sec. C.2, C.3, 5.2]
Hanna Kurniawati
https://cs.anu.edu.au/courses/comp3600/

Probabilistic Analysis
• Analyze the behavior of algorithms when the input
is from a probability distribution
• In general, the objective is to compute the expected properties (e.g., average running time, average space complexity) of an algorithm
• Probabilistic analysis of algorithms can be applied to deterministic and randomized algorithms
• Randomized algorithm will be cover later in this topic

Topics
• Probability Refresher
• Probabilistic Analysis of Deterministic Algorithm • Randomized Algorithm, ex.: RandQuickSort
• Probabilistic Analysis of Randomized Algorithm

Probability Refresher
• Probabilistic Modelling Assumptions:
• Experiments with random outcome
• Which outcome is likely to happen is quantifiable
• Probabilistic modelling consists of 3 components:
• Sample space (S): Set of all possible outcomes.
• Events (𝐄): Subsets of sample space.
• Probability (P): Quantify how likely an event occurs.

Probability Refresher
• Probability: A function that maps events to real numbers satisfying the following 3 axioms:
• Non-negativity: 𝑃 A ≥ 0 for any event 𝐴 ∈ 𝐄
• Normalization: 𝑃 𝑆 = 1
• Additivity of finite / countably infinite events: 𝑃⋃$ 𝐴 =∑$ 𝑃𝐴 𝑂𝑅
!”#! !”# !
𝑃⋃% 𝐴 =∑% 𝑃𝐴 !”#! !”# !
where 𝐴! ∈ 𝐄 are disjoint / mutually exclusive events

Probability Refresher: Example
• Flipping a fair coin, head (H) or tail (T)?
S = {H, T}
𝐄 = {∅, {H}, {T}, {H,T}} and the probabilities are: P{∅} = P{H,T} = 0, P({H}) = P({T}) = 0.5
For compactness of writing, we usually do not list zero probabilities (note: This does not mean they are undefined).
Usually, we write the above as S = {H, T} ; P({H}) = P({T}) = 0.5

Random Variables
• Random variable 𝑋 is a function that maps S to real number
• 2 types of random variable:
• Discrete random variable: Range is finite/countable • Continuous random variable: Range is uncountable
• Example:
• S: Students of COMP3600/6466
• X: The program a student is enrolled in
Suppose the programs are indexed, e.g., BAC: 0, BIT: 1, BSwEng: 2, PHB: 3, MCompSci: 4
X(Jesse) = 3 ; X(Lei) = 0 ; X(Qingtao) = 0 ; ….
• Y: The height of a student in cm (without a cap on #digits behind the decimal point)
Y(Mr M) = 177.23 ; Y(Ms S) = 178.115 ; …

Characterizing Random Variables
• Cumulative distribution function (cdf) 𝐹!(𝑥)=𝑃𝑋≤𝑥 =𝑃 𝑠𝑋𝑠 ≤𝑥,𝑠∈𝑆
• Discrete: Probability mass function (pmf)
𝑓! 𝑥 = 𝑃 𝑋 = 𝑥 = 𝑃 𝑠 𝑋 𝑠 = 𝑥 , 𝑠 ∈ 𝑆
=𝐹! 𝑥 −𝐹! 𝑥−1
• Continuous: Probability density function (pdf) 𝑑 𝐹! ( 𝑥 ) #
𝑓!𝑥= 𝑑𝑥 ;𝑃𝑎≤𝑋≤𝑏=6𝑓!𝑥𝑑𝑥 ”

Compact Characterization of Random Variables
• Expected value: Weighted average of possible values of X, where the weight is the probability
𝐸𝑋=8𝑥𝑃𝑋=𝑥 ∀%
𝐸𝑔(𝑋) =8𝑔(𝑥)𝑃𝑔(𝑋)=𝑥 ∀%
• Useful property: Linearity of expectation 𝐸 𝑎𝑋 + 𝑏 = 𝑎𝐸 𝑋 + 𝑏

Indicator Random Variables
• Convenient to convert between probabilities & expectations
• Suppose we have sample space S and an event 𝐴 in
the (power set of the) sample space S, then:
• The indicator random variable (denoted I 𝐴 ) associated with event 𝐴 is
I𝐴 =01 𝐴𝑜𝑐𝑐𝑢𝑟𝑠
0 𝐴 𝑑𝑜𝑒𝑠 𝑛𝑜𝑡 𝑜𝑐𝑐𝑢𝑟
•Let𝑋&=I𝐴,then𝐸𝑋& =𝑃𝐴
Proof:𝐸𝑋& =𝐸I𝐴 =1.𝑃 𝐴 +0.𝑃𝑆−𝐴 =𝑃 𝐴

Indicator Random Variables: Examples
• Expected number of heads obtained when flipping a fair coin
• S = {H, T} ; P({H}) = P({T}) = 0.5
• 𝑋&=I𝐻 ==1 𝐻𝑜𝑐𝑐𝑢𝑟𝑠 0 𝑇 𝑜𝑐𝑐𝑢𝑟𝑠
𝐸𝑋& =𝐸I𝐻 =1.𝑃 𝐻 +0.𝑃 𝑇 =0.5

Indicator Random Variables: Examples
• Expected number of heads obtained when flipping a
fair coin 𝑛 times?
• Let 𝑋! be the indicator random variable that head occurs in the 𝑖th flip, and 𝑋 be the random variable on the number of heads occurring in 𝑛 flips
• 𝑋! =I 𝐻! =A1 𝐻𝑜𝑐𝑐𝑢𝑟𝑠𝑖𝑛𝑡h𝑒𝑖'(𝑓𝑙𝑖𝑝 0 𝑇 𝑜𝑐𝑐𝑢𝑟𝑠 𝑖𝑛 𝑡h𝑒 𝑖'(𝑓𝑙𝑖𝑝
•𝐸𝑋=𝐸∑$ 𝑋 $ !”# !
= ∑!”# 𝐸[𝑋!]
= ∑$ 0.5 !”#
= 0.5𝑛
(based on linearity of expectation) (based on results in previous slide)

Topics
üProbability Refresher
• Probabilistic Analysis of Deterministic Algorithm • Randomized Algorithm, ex.: RandQuickSort
• Probabilistic Analysis of Randomized Algorithm

InsertionSort(A)
Cost
Times
1
for j = 2 to A.length
c1
n
2
Key = A[j]
c2
n-1
3
i = j-1
c3
n-1
4
While i > 0 and A[i] > key
c4
$
!𝑡! !”#
5
A[i+1] = A[i]
c5
$
! 𝑡! − 1 !”#
6
i = i-1
c6
$
! 𝑡! − 1 !”#
7
A[i+1] = key
c7
n-1
Total: sum of cost*times Note: The total 𝑡* (i.e., total #swaps) is Best case: Θ(𝑛) different for different types of inputs.
Worst case: Θ(𝑛))
But, what’s the average?

Probabilistic Analysis of Deterministic Algorithms w. An Example on Insertion Sort
• Recall Insertion Sort running-time complexity • Best case: Θ(𝑛) àinput already sorted
• Worst case: Θ 𝑛’ àinput sorted in reverse order
• Average case?
• What kind of input leads to “average” case?
• Well, we’re interested not just in one input but, for many inputs
• Need to quantify how likely certain inputs are:
• Assume unique numbers to be sorted and assume all 𝑛! permutations of the numbers are equally likely –aka the input are assumed to be uniformly distributed

Probabilistic Analysis of Deterministic Algorithms w. An Example on Insertion Sort
• A permutation is basically a list of the input numbers in some order, e.g., A: [𝑎(, 𝑎’ , …, 𝑎)]
•Let’scall 𝑖,𝑗 aninversioninAif𝑖<𝑗but𝑎* >𝑎+
• Example: A [20, 5, 10, 8] has 4 inversions, (20, 5) ; (20, 10) ;
(20, 8) ; (10, 8)
• Best case: 0 inversion (sorted in the right order)
• Worst case: 𝑛 = )! = ) )-( (sorted in reverse 2 ‘! )-‘ ! ‘
order)
• The goal of sorting is to remove inversion
• Swapping a pair of number reduces #inversion by exactly 1 • In Insertion Sort, #inversions indicates #swaps

Probabilistic Analysis of Deterministic Algorithms w. An Example on Insertion Sort
• Now, for average case, we need to compute the expected number of inversion in a given input. How?
• First what’s the probability that a pair is an inversion?
• Recall the assumption 2 slides earlier: We assume all 𝑛! permutations equally likely. This means, a given input would be selected uniformly at random from the set of all possible permutations. This in turn means, for a given input (without knowing exactly what the input is), a pair 𝑖, 𝑗 might or might not be an inversion with equal probability (i.e., the probability that the pair is an inversion is 0.5).

Probabilistic Analysis of Deterministic Algorithms w. An Example on Insertion Sort
• Now, how to compute the expected number of inversion in a given input?

Probabilistic Analysis of Deterministic Algorithms w. An Example on Insertion Sort
• To compute the expected number of inversion in a given input
• Let 𝑋 be the number of inversion in a given input
• Let I 𝑆!,* =01 𝑖,𝑗 𝑖𝑠𝑎𝑛𝑖𝑛𝑣𝑒𝑟𝑠𝑖𝑜𝑛 0 𝑜𝑡h𝑒𝑟𝑤𝑖𝑠𝑒
• Then, 𝑋 = ∑$,# ∑$
!”# *”!-#
I 𝑆 !,*
•And𝐸𝑋 =𝐸∑$,#∑$
!”# *”!-#
= ∑$,# ∑$ 𝐸 I 𝑆!,* !”# *”!-#
I𝑆 !,*
= ∑$,# ∑$
!”# *”!-#
=∑$,#∑$
!”# *”!-# )
𝑃 I 𝑆 !,*
= 1
# =# 1+1+⋯+1
=#.$$,# =$$,# ) ) .
) 𝑛 2
= $! =$$,# $,)! )! $,) ! ) $,) !

InsertionSort(A)
Cost
Times
1
for j = 2 to A.length
c1
n
2
Key = A[j]
c2
n-1
3
i = j-1
c3
n-1
4
While i > 0 and A[i] > key
c4
$
Replace with:
c5 $𝑛(𝑛 − 1)
𝑐 +𝑐 +𝑐!𝑡 −1
!𝑡! !”#
!”# +𝑐! 𝑛−1!”#
!4
5
A[i+1] = A[i]
6
i = i-1
c6
$
! 𝑡! − 1 !”#
7
A[i+1] = key
c7
n-1
Total: sum of cost*times Note: The total 𝑡* (i.e., total #swaps) is Best case: Θ(𝑛) different for different types of inputs.
Worst case: Θ(𝑛))
But, what’s the average?

𝑇 𝑛 𝑛(𝑛 − 1)
=𝑐#𝑛+ 𝑐)+𝑐0+𝑐. 𝑛−1 + 𝑐.+𝑐1+𝑐2 4 +𝑐3 𝑛−1
=𝑛) 𝑐.+𝑐1+𝑐2 +𝑛 𝑐#+𝑐)+𝑐0+𝑐.− 𝑐.+𝑐1+𝑐2 +𝑐3 44
− 𝑐)+𝑐0+𝑐.+𝑐3 = 𝑛)𝐶 + 𝑛𝐶4 − 𝐶′′
Where 𝑐. +𝑐1 +𝑐2 𝐶=4
You might want to compare with the worst-case analysis in slide 29 of https://cs.anu.edu.au/c ourses/comp3600/wee k1-introduction- aftClass.pdf
𝐶4=𝑐#+𝑐)+𝑐0+05!− 5″-5# +𝑐3
44 .. 𝐶 =𝑐) +𝑐0 +𝑐. +𝑐3
Therefore, the average running time of insertion sort is Θ(𝑛)). In terms of asymptotic bound, this average case is the same as its worst case, but the coefficient is lower.

Topics
üProbability Refresher
üProbabilistic Analysis of Deterministic Algorithms • Randomized Algorithm, ex.: RandQuickSort
• Probabilistic Analysis of Randomized Algorithm
Next: Randomized Algorithm

Related Posts