WIXLIB

Basic Arrival ProcessesChia-Ping ChenProfessorDepartment of Computer Science and EngineeringNational Sun Yat-sen UniversityProbability1/48

OutlineRandom processArrival processBernoulli processPoisson processRandom sum and arrival process2/48Chen PBasic Arrival Processes

Bernoulli Processes3/48Chen PBasic Arrival Processes

random processesLet (Ω, F, P ) be a probability model. A random process defined onΩ, say X, has the following property.X contains random variables, each defined on ΩA random variable of X has an indexXt is the random variable with index tX is discrete-time if the set of index is discreteX is continuous-time if the set of index is continuousAn ω in Ω is mapped to an instance of X called sample sequence or sample function4/48Chen PBasic Arrival Processes

arrival processesLet (Ω, F, P ) be a probability model. An arrival process defined onΩ, say X, has the following property.Every Xt is a Bernoulli random variableXt 1 for an arrival at t and Xt 0 for no arrival at tWe can use arrival processes for 2-state phenomenon.speech activityanomalous sound detectionvirus screening5/48Chen PBasic Arrival Processes

Definition (Bernoulli processes)Let (Ω, F, P ) be a probability model. A Bernoulli process, say X,has the following property.X is a discrete-time arrival processXt indicates whether there is an arrival at epoch tXt ’s are iid Bernoulli random variablesSince every Xt is Ber(p) for some p, we can denote X byBernoulli(p)6/48Chen PBasic Arrival Processes

Example (6.1 Bernoulli process)Let X be a Bernoulli process.Let U be the arrival count of X from time 1 to 5 and V bethe arrival count of X from time 6 to 10. We have U V.Let W be the first odd time index with an arrival of X andY be the first even time index with an arrival of X. We haveW Y.7/48Chen PBasic Arrival Processes

Lemma (binomial arrivals and geometric arrival time)Let X be Bernoulli(p).Let Sn be the arrival count of X from time 1 to time n.Sn Bin(n, p)Let T be the first arrival time of X.T Geo(p)We have Sn X1 · · · Xn where Xi ’s are iid Ber(p). SoSn Bin(n, p)The PDF of T isP (T n) P ((X1 0) · · · (Xn 1 0))P (Xn 1) (1 p)n 1 p8/48Chen PBasic Arrival Processes

fresh-start/memoryless propertyLet X be Bernoulli(p).Let n be a non-negative integer. Let X 0 be the part of Xdiscarding X1 , . . . , Xn , i.e.Xt0 Xn t , t 1, 2, · · ·Then X 0 is Bernoulli(p).Let N be a non-negative integer random variable that is independent of XN 1 , XN 2 , . . . . Let X 00 be part of X discardingX1 , . . . , XN , i.e.Xt00 XN t , t 1, 2, · · ·Then X 00 is Bernoulli(p).9/48Chen PBasic Arrival Processes

Example (6.2)A time-slotted computer executes a priority job with probability p ineach slot, independent of other slots. A slot is busy if the computerexecutes a priority job, idle otherwise. A string of idle slots, flankedby busy slots, is an idle period. A string of busy slots, flankedby idle slots, is a busy period. Let’s look at the random variablesT, B, I, Z as shown in the following figure.10/48Chen PBasic Arrival Processes

T, B, I, ZT is the time of the first idle slot. Since a slot is idle withprobability (1 p), T is Geo(1 p).B is the length of the first busy period. Let X be Bernoulli(p),treating busy slots as arrivals. Let N be the time of the firstbusy slot. The first busy period ends as soon as an idle slot arrives after N . Let X 0 be the part of X discarding X1 , . . . , XN .Then X 0 is Bernoulli(p). Since B equals the time of the firstidle slot of X 0 , it is Geo(1 p).I is the length of the first idle period. This period ends whena busy slot arrives after the first idle slot. So I is Geo(p).Z is the time of the first idle slot after the first busy slot. SinceZ B 1 1 B, we have Z Geo(1 p).11/48Chen PBasic Arrival Processes

Example (6.3)Let X be Bernoulli(p). Let N be the first time that an arrivalof X immediately follows the previous arrival of X. What is theprobability of no arrivals in the next two time slots, i.e.P (XN 1 0 XN 2 0)N is independent of XN 1 , XN 2 , . . . . Let X 0 be the part of Xdiscarding X1 , . . . , XN , i.e.Xt0 XN t , t 1, 2, · · ·Then X 0 is Bernoulli(p). ThusP (XN 1 0 XN 2 0) P (X10 0 X20 0) P (X10 0) P (X20 0) (1 p)212/48Chen PBasic Arrival Processes

Definition (arrival and interarrival times)Let X be an arrival process.The time of an arrival of X is an arrival timeThe time between an arrival and the previous arrival of X isan interarrival timeLet Yk be the time of the kth arrival of X, and Tk be the timebetween the (k 1)th arrival and the kth arrival of X. ThenYk T1 · · · Tk13/48Chen PBasic Arrival Processes

Lemma (geometric interarrival times)Let X be Bernoulli(p) and Tk be the kth interarrival times of X.Then T1 , T2 , · · · are iid Geo(p) random variables.From T1 Y1 and Y1 Geo(p), we haveT1 Geo(p)Let X 0 be X re-started at T1 and Y10 be the first arrival time of X 0 .By the memoryless property, X 0 is Bernoulli(p) and Y10 is Geo(p).From T2 Y10 , we haveT2 Geo(p)By same argument, Tk 1 is the first arrival time of a restarted process of X restarted at N Yk , so Tk 1 is Geo(p).14/48Chen PBasic Arrival Processes

Example (6.4)It has been observed that after a rainy day, the number of daysuntil it rains again is a geometric random variable with parameter p,independent of the past. Find the probability that it rains on boththe 5th and the 8th day of the month.Let X be an arrival process, treating rainy days as arrivals. The iidinter-arrival times Geo(p) implies X is Bernoulli(p). ThusP (X5 1 X8 1) P (X5 1) P (X8 1) p215/48Chen PBasic Arrival Processes

Lemma (Pascal arrival times)Let X be Bernoulli(p) and Yk be the kth arrival time of X.The PMF of Yk can be derivedIt is the Pascal PMF of order k with parameter pEvent (Yk n) occurs if and only if that there are (k 1) arrivalsfrom time 1 to time (n 1) and an arrival at time n. Thus(k 1) arrivals from time 1 to time (n 1)zpYk (n) !} {n 1 k 1p (1 p)n 1 (k 1) k 1 ! n 1 pk (1 p)n k , k 1 0,an arrival at time nz} {pn k, k 1, . . .otherwise16/48Chen PBasic Arrival Processes

Example (6.5)In every minute Lin plays, he commits a foul with probability p. In agame, he plays until he’s fouled out or he plays 30 minutes at most.What is the PMF of his playing time Z in a game?Let X be Bernoulli(p), treating fouls as arrivals. Let Yk be the ktharrival time of X. Then we have Z min(Y6 , 30) and((Z n) HencepZ (n) (Y6 n), 6 n 29(Y6 30), n 30 pY6 (n), 29P1 0,n0 66 n 29pY6 (n0 ),n 30otherwise17/48Chen PBasic Arrival Processes

Definition (split Bernoulli process)Let X be Bernoulli(p) and W , Z be defined as follows: an arrivalof X is an arrival of W with probability q, otherwise it is an arrivalof Z.We have P (Wt 1) P (Xt 1) · q pq, soWt Ber(pq) W Bernoulli(pq)SimilarlyZ Bernoulli(p(1 q))18/48Chen PBasic Arrival Processes

Definition (merge Bernoulli process)Let X be Bernoulli(p), Z be Bernoulli(q) and X Z. Let anarrival of X or an arrival of Z be an arrival of W .We haveP (Wt 1) P ((Xt 1) (Zt 1)) P (Xt 1) P (Zt 1) P ((Xt 1) (Zt 1)) p q pqSo Wt ’s are iid Ber(p q pq), and W is Bernoulli(p q pq).19/48Chen PBasic Arrival Processes

Poisson Processes20/48Chen PBasic Arrival Processes

DefinitionPoisson processLet (Ω, F, P ) be a probability model. A Poissonprocess X defined on Ω has the following property.X is a continuous-time arrival processArrivals in non-overlapping periods are independentArrival process is homogeneous in time21/48Chen PBasic Arrival Processes

Bernoulli arrivals in a small periodLet X be a Poisson process and N (δ) be the arrival count of X ina small period of length 0 δ 1. By assumption, the PMF ofN (δ) is 1 λδ o(δ), k 0P (N (δ) k) λδ o(δ),k 1 o(δ),k 1This is denoted byX Poisson(λ)N (δ) Ber(λδ)22/48Chen PBasic Arrival Processes

arrival rateLet X be Poisson(λ).The expected number of arrivals of X in a small period oflength δ isE[N (δ)] λδ o(δ)The instantaneous rate of arrivals is λlimδ 0 E[N (δ)] λδ23/48Chen PBasic Arrival Processes

Lemma (Poisson arrivals in a period)Let X be Poisson(λ). The arrival count of X in a period of lengthτ is Poi(λτ ).Let N (τ ) be the arrival count in a period of length τ . Partition theperiod into small periods of length δ nτ with n 1. Let Ni bethe arrival count in the ith small period. We have Ni Ber(λδ)and N (τ ) N1 · · · Nn . Hencen N (τ ) Bin(n, λδ) Poi (nλδ) Poi (λτ )24/48Chen PBasic Arrival Processes

Example (6.8)Bill gets e-mails according to Poisson(λ) with λ 0.2 messagesper hour. He checks email every hour. What is the probability of nonew message? 1 new message?Since N (τ ) is Poi (λτ ), we haveN (1) Poi(0.2 1)25/48Chen PBasic Arrival Processes

Example (6.9)Arrivals of customers at a supermarket are modeled by Poisson(λ)with λ 10 customers per minute. Let M (resp. N ) be the numberof the customers arriving between 9:00 and 9:10 (resp. between 9:30and 9:35). What is the PMF of M N ?M is Poi(λτ1 ) Poi(10 · 10), N is Poi(λτ2 ) Poi(10 · 5), andM N . The sum of 2 independent Poisson random variables is aPoisson random variable. Thus(M N ) Poi(100 50)26/48Chen PBasic Arrival Processes

Lemma (exponential first arrival time)Let X be Poisson(λ). The time of the first arrival of X is Exp(λ).Let Y1 be the first arrival time of X and N (t) be the number ofthe arrivals in (0, t). Note (Y1 t) if and only if (N (t) 0). SoP (Y1 t) P (N (t) 0) andP (Y1 t) 1 P (Y1 t) 1 P (N (t) 0)Since N (t) is Poi(λt), we haveP (N (t) k) (λt)k λte , k 0, 1, 2, . . .k!So the CDF of Y1 isFY1 (t) 1 P (N (t) 0) 1 e λtwhich is the CDF of Exp(λ). Therefore, Y1 is Exp(λ).27/48Chen PBasic Arrival Processes

fresh-start/memoryless propertyLet X be Poisson(λ).Let u 0 and X 0 be the part of X discarding X u , i.e.Xt0 Xu t , t 0Then X 0 is Poisson(λ).Let U be a non-negative random variable and be independentof X U . Let X 00 be the part of X discarding X U , i.e.Xt00 XU t , t 0Then X 00 is Poisson(λ).28/48Chen PBasic Arrival Processes

Example (6.10)You and a partner go to the gym to play badminton. You wait untilthe on-court players to finish. Assume that their playing time isExp(λ). Then your waiting time is Exp(λ), regardless of how longthey have been playing.Let X be Poisson(λ) which starts at the same time as the playerson court. Their playing time is Exp(λ), so it is the first arrival timeof X. Let X 0 be the process obtained from restarting X at thesame time as you begin to wait. Then your waiting time is the firstarrival time of X 0 . Since X 0 is Poisson(λ), your waiting time isExp(λ).29/48Chen PBasic Arrival Processes

Example (6.11)When you enter a bank, all 3 tellers are busy serving customers,and there are no other customers in queue. No more customersenter the bank after you. Assume that the service times for thebank customers are iid exponential random variables. What is theprobability that you will be the last customer to leave the bank?1 1? ?4 330/48Chen PBasic Arrival Processes

Lemma (exponential interarrival times)Let X be Poisson(λ) and Tk be the kth interarrival time of X.Then T1 , T2 , · · · are iid Exp(λ) random variables.This follows from the memoryless property.That is, by restarting X at an arrival time, the next arrival timeis Exp(λ) and is an interarrival time of X.An instance of X can be generated as follows: for k 1, 2, . . .sample interarrival timeTk Exp(λ)and set Xt to 1 at arrival timeYk T1 · · · Tk31/48Chen PBasic Arrival Processes

Lemma (Erlang arrival times)Let X be Poisson(λ) and Yk be the kth arrival time of X.The PDF Yk can be derivedIt is the Erlang PDF of order k with parameter λWe have(k 1) arrivals in (0, t)z} {1 arrival in (t, t δ)z} {P (Yk (t, t δ)) P (N (t) k 1) P (N (δ) 1)(λt)k 1 λte (λδ o(δ))(k 1)! FYk (t δ) FYk (t) So the PDF of Yk isfYk (t) limδ 0 λk tk 1 λtFYk (t δ) FYk (t) eδ(k 1)!32/48Chen PBasic Arrival Processes