Models & Algorithms

for Internet Computing

Lecture 4: MORE APPLICATIONS WITH
PROBABILISTIC ANALYSIS
Agenda
• Review: Coupon Collector’s problem and
Packet Sampling
• Analysis of Quick-Sort
• Birthday Paradox and applications
• The Bins and Balls Model

Probability for Computing 3

Coupon Collector Problem
• Problem: Suppose that each box of cereal contains one
of n different coupons. Once you obtain one of every
type of coupon, you can send in for a prize.

• Question: How many boxes of cereal must you buy

before obtaining at least one of every type of coupon.

• Let X be the number of boxes bought until at least one

of every type of coupon is obtained.

• E[X] = nH(n) = nlnn

Probability for Computing 4

Application: Packet Sampling
• Sampling packets on a router with probability p
• The number of packets transmitted after the last sampled
packet until and including the next sampled packet is
geometrically distributed.

• From the point of destination host, determining all

the routers on the path is like a coupon collector’s
problem.

• If there’s n routers, then the expected number of

packets arrived before destination host knows all of
the routers on the path = nln(n).

Probability for Computing 5

DoS attack

Probability for Computing 6

IP traceback
• Marking and
Reconstruction
• Node append vs.
node sampling

Probability for Computing 7

Node apend
D
A1 A2
A3

R5 D R6 R6 R7

D R6 R3 R3 R4

D R6 R3 R2 R2

D R6 R3 R2 R1 R1
V D R6 R3 R2 R1
Probability for Computing 8
 Node Sampling
A A
A
1 2
3
1 D R7
R R R
5 6 7

R R
3 4

R p=0.51 R2 x=0.2 < p

2

R 1 D R2
1

Probability for Computing 9

Expected Run-Time of
QuickSort

Probability for Computing 10

Analysis
• Worst-case: n2.
• Depends on how we choose the pivot.
• Good pivot (divide the list in two nearly equal
length sub-lists) vs. Bad pivot.
• In case of good pivot -> nlg(n). [by solving
recurrence]

• If we choose pivot point randomly, we will

have a randomized version of QuickSort.

Probability for Computing 11

Analysis
• Xij be a random variable that
• Takes value 1 if yi and yj are compared with each other
• 0 if they are not compared.

• E[X] = ∑∑E[Xij]
• E[Xij] = 2/ (j-i+1)
• Consider when the set Yij={yi, yi+1, …, yj} is “touched” by a
pivot the first time. If this pivot is either yi or yj then the
two will be compared, otherwise Never – a (S1,S2) split

• Using k = j-i+1, we can compute E[X] = 2nln(n)

Probability for Computing 12
Detail analysis

Probability for Computing 13

Birthday “Paradox”

What is the probability that

two persons in a room of
30 have the same
birthday?

Probability for Computing 14

Birthday Paradox

• Ways to assign k different birthdays

without duplicates:
N = 365 * 364 * ... * (365 – k + 1)
= 365! / (365 – k)!
• Ways to assign k different birthdays with
possible duplicates:
D = 365 * 365 * ... * 365 = 365k

Probability for Computing 15

Birthday “Paradox”
Assuming real birthdays assigned randomly:
N/D = probability there are no duplicates
1 - N/D = probability there is a duplicate

= 1 – 365! / ((365 – k)!(365)k )

Probability for Computing 16

Generalizing Birthdays 17

P(n, k) = 1 – n!/(n-k)!nk

Given k random selections from n possible

values, P(n, k) gives the probability that there is
at least 1 duplicate.

Probability for Computing 17

Birthday Probabilities
P( two match) = 1 – P(all are different)
P(2 chosen from N are different)
= 1 – 1/N
P(3 are all different)
= (1 – 1/N)(1 – 2/N)
P(k trials are all different)
= (1 – 1/N)(1 – 2/N) ... (1 – (k – 1)/N)
ln (P)
= ln (1 – 1/N) + ln (1 – 2/N) + ... ln (1 – (k – 1)/N)

Probability for Computing 18

Happy Birthday Bob!

ln (P) = ln (1 – 1/N) + ... + ln (1 – (k – 1)/N)

For 0 < x < 1: ln (1 – x)  x
ln (P)  – (1/N + 2/N + ... + (k – 1)/N)
Gauss says:
1 + 2 + 3 + 4 + ... + (k – 1) + k = ½ k (k + 1)
So,
ln (P)  -½ (k-1) k/N
P  e-½(k-1)k / N
Probability of match  1 – e-½ (k-1)k / N

Probability for Computing 19

Applying Birthdays

P(n, k) > 1 – e-k*(k-1)/2n

For n = 365, k = 20:
P(365, 20) > 1 – e-20*(19)/2*365
P(365, 20) > .4058
For n = 264, k = 232: P (264, 232) > .39
For n = 264, k = 233: P (264, 233) > .86
For n = 264, k = 234: P (264, 234) > .9996
Application: Digital Signatures
Probability for Computing 20
Digital Signature Scheme: Using
Hash Functions
• A hash function H maps a message of variable
length n bits to a fingerprint of fixed length m
bits, with m < n.
• This hash value is also called a digest (of the
original message).
• Since n>m, there exist many X which are map to the
same digest  collision.
DS schemes with hash
functions
H(X) Concatenation
X H DA

C .
X DA(H(X))

Signature Generator
EA

.
X DA(H(X)) + 0 – Accept
1 – Reject

Signature Verifier
Main properties
Given a hash function H: X →Y
• Long message  short, fixed-length hash
• One-way property: given y Y
it is computationally infeasible to find a value xX
s.t. H(x) = y
• Collision resistance (collision-free)
it is computationally infeasible to find any two
distinct values x’, x  X s.t. H(x’) = H(x)
• This property prevent against signature forgery
Collisions
• Avoiding collisions is theoretically impossible
• Dirichlet principle: n+1 rabbits into n cages  at
least 2 rabbits go to the same cage
• This suggest exhaustive search: try |Y|+1
messages then must find a collision (H:XY)
• In practice
• Choose |Y| large enough so exhaustive search is
computational infeasible.
• |Y| not too large or long signature and slow process
• However, collision-freeness is still hard
Birthday attack
• Can hash values be of 64 bits?
• Look good, initially, since a space of size 264 is too
large to do exhaustive search or compute that
many hash values
• However a birthday attack can easily break a DS
with a 64-bit hash function
• In fact, the attacker only need to create a bunch of 232
messages and then launch the attack with reasonably
high probability for success.
How is the attack
• Goal: given H, find x, x’ such that H(x)=H(x’)
• Algorithm:
• pick a random set S of q values in X
• for each xS, computes hx=H(x)
• if hx=hx’ for some x’≠x then collision found: (x,x’), else
fail
• The average success probability is
= 1-exp(q(q-1)/2|Y|)
• Suppose Y has size 2m, choose q ≈2m/2 then  is almost
0.5!
Balls into Bins
• We have m balls that are thrown into n bins,
with the location of each ball chosen
independently and uniformly at random from n
possibilities.
• What does the distribution of the balls into the
bins look like
• “Birthday paradox” question: is there a bin with at
least 2 balls
• How many of the bins are empty?
• How many balls are in the fullest bin?
Answers to these questions give solutions to
many problems in the design and analysis of
algorithms Probability for Computing 27
The maximum load
• When n balls are thrown independently and uniformly
at random into n bins, the probability that the maximum
load is more than 3 lnn/lnlnn is at most 1/n for n
sufficiently large.
• By Union bound, Pr [bin 1 receives  M balls] 
• Note that:

• Now, using Union bound again, Pr [ a bin that receives  M

balls] is at most

which is  1/n
Probability for Computing 28
Application: Bucket Sort
• A sorting algorithm that
breaks the (nlogn) lower
bound under certain input
assumption
• Bucket sort works as follows:
• Set up an array of initially
empty "buckets."
• Scatter: Go over the original
array, putting each object in its
bucket.
• Sort each non-empty bucket. A set of n =2m integers,
• Gather: Visit the buckets in randomly chosen from
order and put all elements back [0,2k),km, can be sorted
into the original array. in expected time O(n)
Probability for Computing  Why:29will analyze later!
The Poisson Distribution
• Consider m balls, n bins
• Pr [ a given bin is empty] =
• Let Xj is a indicator r.v. that is 1 if bin j empty, 0 otherwise
• Let X be a r.v. that represents # empty bins

• Generalizing this argument, Pr [a given bin has r balls] =

• Approximately,

• So:

Probability for Computing 30

Limit of the Binomial Distribution

Probability for Computing 31

Thank you for​
your attentions!​