Random processes: Poisson process
and Markov chains CompSci 369, 2022
School of Computer Science, University of Auckland
Copyright By PowCoder代写 加微信 powcoder
Last lecture
Intro to simulation (review)
Pseudo RNGs
Sampling from nite discrete distributions
Inversion method for sampling from continous distributions Intro to Random process
the Random walk
This lecture
The Poisson process Markov chains
The Poisson process
Models events that occur independently of each other and randomly in time (or space).
E.g. Genetic mutations, arrival times of customers, radioactive decay, occurrences of earthquakes, industrial accidents, errors in manufacturing processes (e.g. silicon wafers or cloth)
We’ll consider events that occur in time
Events occur at rate (or with intensity )
A Poisson process is a continuous time counting process
is the number of events in the interval .
}0 ≥ t ,)t(N{
)t,0( )t(N λλ
A Poisson process is de ned by the following properties
1 and when .
2 The number of events in any non-overlapping intervals are independent.
3 In any su ciently small time interval the probability of 2 events occurring is 0.
t < s )t(N < )s(N 0 = )0(N
Example of Poisson process
Properties of the Poisson process
Let process have rate .
1 Number of events in an interval of length is Poisson distributed with parameter .
2 Given the number of events in a Poisson process in some interval times of the events are uniform in that interval
3 The times between events --- interarrival-times --- in a Poisson process are exponentially distributed with parameter .
Properties of the Poisson process
deppiks os dna elgna etanimretedni fo si worra htgnel-orez : ,emiTtneve ##
= 1x ,5.1 = 0y ,)]1 - tnevEn:1[emiTtneve ,0(c = 0x(sworra ni gninraW ##
Can see distribution of inter-arrival times is exponential when we plot them: On left, inter-arrival times are time between red lines.
On right, histogram of these times along with exponential density with rate 3.
Simulating the Poisson Process
Properties suggest two ways to simulate a Poisson process with rate on interval :
Either simulate exponential variables with rate until cumulative time exceeds :
)emiTtneve = emit ,tnuoCtneve:1 = tnuoc(nruter
)adbmal = etar ,1(pxEdnar + t = t
]t ,emiTtneve[ = emiTtneve
1 + tnuoCtneve = tnuoCtneve
)T < t( elihw
][ = emiTtneve
0 = tnuoCtneve
)adbmal = etar(pxEdnar = t
Or simulate a Poisson variable with rate to get number of events and then distribute them uniformly across interval .
But: easiest way to simulate a Poisson random variable is simulate a Poisson process with rate for time 1 and count the number of events.
)emiTtneve = emit ,tnuoCtneve:1 = tnuoc(nruter
)emiTtneve(tros = emiTtneve
)tnuoCtneve = rebmun ,T = xam ,0 = nim(mrofinUdnar = emiTtneve
)T * adbmal = etar(nossioPdnar = tnuoCtneve
Splitting Poisson processes
Suppose each event is one of possible types. An event is type with probability , for
Now observe only events of type .
They form a Poisson process with rate .
}k , ... ,1{ ∈ i ip
Looking only at the blue events gives a Poisson process with rate .
5.1 = 57.0 × 2 = eulbpλ
While including only the red events is a Poisson process with rate
5.0 = 52.0×2
Merging Poisson processes
If is a Poisson process with rate and is a Poisson process with rate ,
is a Poisson process with rate .
μ+λ }0 ≥ t,)t(Y+)t(X = )t(Z{ = Z μY
Markov chains
Markov property
The Markov property is about memorylessness: future states depend only on the current state
To propagate a process with the Markov property forward, we need only be told the current state to generate the next state.
Formally, the sequence of random variables is a Markov chain if it has the Markov property
Named after Andrei Andreyevich Markov a Russian mathematician.
x = nX|x = 1+nX(P = )1x = 1X,2x = 2X,...,1−nx = 1−nX,nx = nX|x = 1+nX(P ... ,3X ,2X ,1X
Markov chain example: a simple Weather model
Suppose the weather tomorrow depends only on the weather today.
Weather can either be Sunny or Rainy, S or R for short. State space is
If it is sunny today, tomorrow it is sunny with probability 0.7 and rainy otherwise. If it is rainy today, tomorrow it is rainy with probability 0.6 and sunny otherwise.
Markov chain transition probabilites
Often write as for short. De ne the transition matrix
where th row and th column is probability of moving from state given that currentlyinstate .
Each entry is a probability (so between 0 and 1) and all rows sum to 1: Example: The transition matrix for the weather example given above is
where rows and columns 1 and 2 are indexed by and
1 = jiP j∑
] 6.0 4.0 [ 3.0 7.0
jiP )i = nX|j = 1+nX(rP
Markov chain transition probabilites
The $m$-step transition probability is the probability of going from state to state in exactly steps,
The -step transition matrix is .
Result (Chapman-Kolmogorov equations):
side is just standard matrix multiplication).
(where the right-hand
In particular, . That is, the n-step transition matrix is just the th power of the transition matrix.
nPmP = n+mP
])m(jiP[ = mP
.)m = nX|j = m+nX(rP = )m(jiP
Example: weather transition matrix
The probability that it is raining the day after tomorrow given that it is sunny today is the -entry of the two-step transition matrix :
so the probability that it will rain the in two days given it is sunny today is 0.39
]84.0 25.0[ = 2 P 93.0 16.0
]6.0 4.0[=P 3.0 7.0
Example of process that is NOT Markov
We have rainy and sunny days as before in our simple model but hurricanes are also possible:
A hurricane lasts exactly 7 days and it rains hard every day during a hurricane. Call this state .
This process is not Markov since can only leave state if been there for seven days.
So probabilty of next state depends on not only on current day but also on previous six days.
Markov chain example: music composition
Example taken from , , , and . Garthwaite. Chopin, mazurkas and Markov. Signi cance, 8(4):154-159, 2011. doi:10.1111/j.1740-9713.2011.00519.x
A simple tune An except from Lydia by Fauré (or a full version on youtube).
Make a Markov model considering only the pitches
The transition matrix between pitches is constructed from empirical counts of the observed transitions.
From which we can generate random realisations:
A,G,F,G,F,G,A,B,G, F,G,F,G,A,B,D,E,
B,C,A,F,G,
B$\ at$ ,A,F,G,A,G,A,B,G,A.
Which might be easier to simply listen to: Melody 1, Melody 2, Melody 3
Someone has got a mini industry on youtube doing the same with lyrics. Here's an "AI/DC" song
More sophisticated computer generated composition
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com