21 Distributions for Inter-Arrival Times and Item Counts PDF

Preview

Summary

Mersenne Twister...

Description

Inter-Arrival Time Distributions & Item Selection Distributions • • • • •

Bernoulli Geometric Exponential Binomial Poisson

– Single Time Step – Discrete Time Steps – Continuous Time – Count of successes/choices – Count of (rare) successes/choices for large number of trial / items

1

Bernoulli Distribution • Basic distribution upon which most others used for simulations are built • The outcome of a single binary event • p is the probability of the event occurring

• R Code • Code 1:

runif(n) < p

• Code 2:

rbinom(n,1,p)

Bernoulli Distribution • Many distributions are compositions of basic binary events • For a single time step: arrived / not arrived • For a single item • searched for: found / not found • selected: chosen / not chosen • For tests: success / failure • For coin flips: heads / tails

Geometric Distribution In R: rgeom(n, p) • Number of trials until the first success • Discrete function • Mean = 1/p Variance = (1 – p)/p2 • Ex: How many times do I need to roll

a 6 sided die before I roll a 6? P = 1/6 • • • •

Could roll it on the first roll, or the second or the third May never roll it (but very very very … unlikely) To generate random numbers use: rgeom(n, 1/6) Expected number of rolls is 1/p = 1/(1/6) = 6

Geometric Distribution m(n, p) • Number • Discre • Mean • Ex: How

a • • • •

Could May n To ge Geometric Distribution Expec

1/6 the third kely) /6)

Geometric Distribution and Inter-Arrival Times • Single unit time step: arrived / not arrived • Bernoulli Distribution with probability of arrival = p

• Question: How many unit time steps to an arrival? • Answer: can derive probability for time step t e.g. t = 4 • • • •

t=1 t=2 t=3 t=4

not arrived not arrived not arrived arrived

(1 – p) (1 – p)2 (1 – p)3 p (1 – p)3

Geometric Distribution and Inter-Arrival Times • Single unit time step: arrived / not arrived • Bernoulli Distribution with probability of arrival = p

• Question: How many unit time steps to an arrival? • Answer: ca So Geometric Distribution! ep t e.g. t = 4 • • • •

t=1 t=2 t=3 t=4

not arrived not arrived not arrived arrived

(1 – p) (1 – p)2 (1 – p)3 p (1 – p)3

Geometric Distribution and Inter-Arrival Times • Single unit time step: arrived / not arrived • Bernoulli Distribution with probability of arrival = p

• Question: How many unit time steps to an arrival? • Answer: can derive probability for time step t

Simple Assumptions:

1. An arrival can come at any time (each “unit time” is independent of each other) 2. arrival probability is the same at each unit time • t=4

arrived

p (1 – p)3

Geometric Distribution and Inter-Arrival Times • Single

d

• Questio • Answe e.g. t = • • • •

t t t t

of arrival = p P(T = t)

• B

n arrival? step t

t Geometric Distribution Geop(t) = p (1 – p)t

From IAT as a Geometric Dist. to IAT as an Exponential Dist. • Let “unit time” get smaller and smaller • until continuous • extra assumption: • probability that arrival occurs is proportional to the unit time • so as unit time decreases, prob of arrival during that time decreases too

Geometric distribution

pf(t) = p (1 − p )t

From IAT as a Geometric Dist. to IAT as an Exponential Dist. • Let “unit time” get smaller and smaller • until continuous • extra assumption: • probability that arrival occurs is proportional to the unit time • so as unit time decreases, prob of arrival during that time decreases too

Geometric distribution

pf(t) = (1 − e− λ ) e− λt simple change of base

by letting λ = − ln(1− p)

From IAT as a Geometric Dist. to IAT as an Exponential Dist. • Let “unit time” get smaller and smaller • until continuous • extra assumption: • probability that arrival occurs is proportional to the unit time • so as unit time decreases, prob of arrival during that time decreases too

Geometric distribution

pf(t) = (1 − e− λ ) e− λt change in form - same equation

by letting λ = − ln(1− p)

From IAT as a Geometric Dist. to IAT as an Exponential Dist. • Let “unit time” get smaller and smaller • until continuous • extra assumption: • probability that arrival occurs is proportional to the unit time • so as unit time decreases, prob of arrival during that time decreases too

Geometric distribution

pf(t) = (1 − e− λ ) e− λt still uses same discrete unit time

by letting λ = − ln(1− p)

From IAT as a Geometric Dist. to IAT as an Exponential Dist. • Let “unit time” get smaller and smaller • Allows for continuous inter-arrival times • extra assumption: • probability that arrival occurs is proportional to the unit time • so as unit time decreases, prob of arrival during that time decreases too

Geometric distribution

pf(t) = (1 − e− λ ) e− λt

Exponential distribution

→ unit time → 0

pdf(t) = λ e− λt

From IAT as a Geometric Dist. to IAT as an Exponential Dist. • Let “u

mes P(T = t)

• Allo • extra • pr is • so pr

ller

too t

Geometric d Exponential Distribution

pf(t) = (1 − e ) e

→ unit time → 0

al distribution

pdf(t) = λ e− λt

Exponential Distribution exp λ (t) = λ e− λt • Continuous variant of Geometric • Length of time until first success Mean = E(T) = 1/λ

Variance = V(T) = 1/λ2

What Exponentially Distributed IATs Mean • Arrivals typically come sooner rather than later • However probability that IAT = 0 is zero • An arrival typically comes within a

characteristic time frame • • •

But no upper bound Time frame defined by the rate λ Not uniformly distributed over that characteristic time!

λ and “Characteristic Time” • The rate λ controls (but does not equal) • the expected amount of time

that elapses between customers • i.e. the expected IAT

• The rate is defined as the the number of customers that arrives per “unit time” • unit time is defined differently than before • means base unit of measurement (sec, min, hr ...) • not “the time interval where a customer either arrives or doesn’t arrive”

λ and “Characteristic Time” • From the properties of Exponential Distributions

E(T ) = 1 / λ • In other words

the "average" IAT = 1 / λ • e.g. if a customer arrives on average every 5 minutes

λ = 1/ 5

and

E(IAT ) = 1 / λ = 5

Calculating Exp Distr Rate Directly • Eg: On average, 2 customers arrive every 5 minutes •

λ = 2/5 cust. per min = 0.4 cust. per min

• Code in R: rexp(n, 2/5) • Expected time for an arrival = 1/λ = 5/2 min = 2.5 min • i.e a customer arrives on average every 2.5 minutes

Converting to Base Time Units • Choose a time unit and stick to it • Will depend on what you are simulating • Typical choices: • microseconds (chip designs) • milliseconds (program designs) • seconds • minutes (stores, games, “human time”) • hours • days • years (evolution simulations)

Converting to Base Time Units • Example: On average, 120 customers arrive daily • Convert to hours • 120 customers per day / 12 hours per day λ = 10 customers per hour • Code in R: rexp(n, 10) • Expected time for an arrival = 1/λ = 1/10 hr = 0.1 hr • Convert to minutes • 10 customers per hour / 60 minutes per hour λ = 1/6 customer per minute = 0.1667 customers per min • Code in R: rexp(n, 1/6) • Expected time for an arrival = 1/λ = 1/(1/6) min = 6 min

Calculating Exp Distr Rate Using an Average IAT • Mean of the Exp. Distr E(T ) = 1 / λ

⇒

λ = 1 / E(T )

Calculating Exp Distr Rate Using an Average IAT • Mean of the Exp. Distr E(T ) = 1 / λ

⇒

λ = 1 / E(T )

• Eg: On average, time between customers = 2.5 min •

λ = 1 / 2.5 customers per minute = 0.4 = 2/5

• Code in R:

rexp(n, 2/5)

• Expected time for an arrival = 1/λ = 5/2 min = 2.5 min • i.e a customer arrives on average every 2.5 minutes

Common Probability Distributions

1 Bn=10, p=1/2 (x) = 10 2 0.300

⎛ 10⎞ ⋅⎜ ⎟ ⎝ x⎠

• Binomial Distribution • Discrete • Probability associated with a binomial random variable • Binomial random variable

0.250

0.200

•

Counts binomial (two state) events

Probability Function

0.150

⎛ n⎞ Bn, p (x) = ⎜ ⎟ p x (1 − p)n−x ⎝ x⎠

0.100

0.050

0.000 0

1

2

3

4

5

X=x

6

7

8

9

10

Common Probability Distributions

1 ⎛ 10 ⎞ (10−x ) Bn=10 , p=1/4 (x) = 10 ⎜ ⎟ 3 • Binomial Distribution 4 ⎝ x⎠

0.300000

• Discrete • Probability associated with a binomial random variable • Binomial random variable

0.250000

0.200000

•

Counts binomial (two state) events

Probability Function

0.150000

⎛ n⎞ Bn, p (x) = ⎜ ⎟ p x (1 − p)n−x ⎝ x⎠

0.100000

0.050000

0.000000 0

1

2

3

4

5

X=x

6

7

8

9

10

Common Probability Distributions

1 ⎛ 10 ⎞ (10−x ) Bn=10 , p=1/4 (x) = 10 ⎜ ⎟ 3 • Binomial Distribution 4 ⎝ x⎠

0.300000

• Discrete • Probability associated with a binomial random variable • Binomial random variable

0.250000

0.200000

•

Counts binomial (two state) events

Probability Function

0.150000

⎛ n⎞ Bn, p (x) = ⎜ ⎟ p x (1 − p)n−x ⎝ x⎠

0.100000

0.050000

0.000000 0

1

2

3

4

5

X=x

6

7

8

9

10

mean! = np var! = np (1 – p)

Poisson Distribution • The number of events occurring in a fixed

interval of time assuming events occur • •

at a known average rate independently of the time since the last event

• Infinite (but still discrete) • Equivalent to the Binomial distribution with large n and small p (i.e. many trials with low probability)

mean = variance = λ

1 λx Poisλ (x) = λ ⋅ e x!

Poisson Distribution • The

ed

• •

at in

x

inter

• Infin • Eq an

mean

nt h large n bility)

x Poisson Distribution

λx x!

Modelling the Number of Items Selected by a Customer • Assume the chance (overall) of selecting one item over another is the same from item to item • Each item is either selected / not-selected • Bernoulli trial (heads / tails coin flip) • Number of selected items therefore binomially distributed

• If number of items (n) to select from is large in comparison to the number of items that a customer will select • probability of selection (p) is small • therefore the number of selections

will approximately have a Poisson distribution...