Markov Chain Flashcards
What is a finite–space Markov Chain?
One where there is a difference there are discrete values or states” that the Markov chain can take”
What is a unigram, bigram, trigram and a 4–gram?
Unigram – each term in the chain is random
Bigram – each term distribution depends only on the previous term
Trigram – each term depends on the previous 2 terms
4–gram – each term depends on the previous 3 terms
What is a Transition Matrix?
A matrix which has all the probabilities of transitioning to each state in every row
i.e. row 1 corresponds to the 1st state probabilities of moving to another state.
After n passes of time, what is the transition matrix?
The original transition matrix (for one passing of time) to the power of n
What is a limiting distribution?
One that satisfies That there is a constant transition matrix at all times
What is true for every limiting distribution?
That a limiting distribution is also stationary distribution
What must be satisfied in order to be a stationary distribution?
As the time leap tends to infinity, the transition matrix tends to a uniform matrix (it is equally likely to be in any of the states)
What is true for every NxN transition matrix, P?
1 is always an eigenvalue
This is proved through definition of eigenvalue and the sum of all rows adding to 1
When is a process not regular ergodic for a stationary distribution?
Two stationary distributions
The stationary distribution depends on the initial condition
When can two states from a markov chain be said to communicate with each other?
When there is a path between the two states (both ways)
What is a recurrent set?
A set where all members communicate with each other.
It is impossible to move outside the set
What is a transient state?
One outside of a recurrent set
If we start on this state, eventually the state will be left and never returned to.
What is an irreducible Markov chain?
One where all states communicate with each other
What is the waiting time to get to a state?
the sum of:
All probabilities of entering state multiplied by 1/(1 + waiting time of that state)
What is the period of a state k?
The greatest common divisor of the set of probabilities of returning to the state k from the state k.
When is a state periodic?
When a state has a period of 1
When is a Markov chain aperiodic?
When all states are aperiodic
If a chain is irreducible and aperiodic, what is it also?
It is also regular ergodic and will have a limiting distribution
How many eigenvalues of the transition matrix are there for a Markov chain with periodicity k?
K eigenvalues
What are the magnitudes of the eigenvalues?
All have magnitude 1
When is a distribution detailed balance with a transition matrix P.
πjPj,k = πkPk,j
What is a birth–death process?
One where a number of items increase and decrease at a set rate?
What n(t) for a birth–death process?
The number of items at a time instance t
For a change in time dt (t+dt), what is the probability of having n items when only birth is considered?
in blue is probability of no birth. In red is probability of a birth
What is the difference between continuous and discrete time?
Discrete time there is a transition matrix
In continuous time there’s the transition rate matrix, Q
What is the transition rate matrix Q like?
dx(t)/dt = x(t)Q,
xn(t) = Pn(t),
The sum of all probability of each number sums to 1
Each row of Q sums to 0 (probability mass conserved)
What is the probability of a certain number of items when death rate is introduced?
Blue is probability of nothing occurring
Red is a birth occurring
Green is a death occurring
How can Brownian Motion be described?
As a random walk where each step is taken at a certain interval that tends to 0
What is used in Brownian Motion?
Density of items rather than number
Items leave area (lowering density)
Or enter area (increasing density)
What is used to investigate Brownian Motion?
Taylor Series Expansion to both changes in time and position f(x,t)
What is the result?
the diffusion equation
What are the three properties of a one–dimensional Wiener Process?
independence: paths between to points are independent of anything before that path
Stationarity: The distribution of a path is independent of the length of the path
continuity: Wt is a continuous function
Gaussianity: Wt is a gaussian
What is the cross correlation between two different functions at points t and s?
2αmin(t,s)
What is a simple extension to the Wiener Process?
Adding a drift term
What are Monte–Carlo Methods?
A general class of approaches that rely on random samples
Often used when analytical approaches fail
used to estimate complicated integrals
Essentially uses histogram methods
Rather than histograms, what can be done?
Sampling from a weighted function w(x)
What should be minimised in Monto–Carlo methods?
The number of samples
The variance (standard deviation)
What can be done to get a better set of samples or when we cant sample from p(x) so must use another pdf?
importance sampling
What is the equation for importance sampling?
p(x)/q(x) is the importance of the drawn sample
With biased sampling how does q(x) affect results?
The closer q(x) is to H(x) the better the bias does at reducing Variance
What is rejection sampling?
Drawing a box
Sampling uniformly from a box
rejecting samples that don’t fall under a curve
What is the problem with rejection sampling?
Very wasteful
Curse of dimensionality
What is the Metropolis–Hastings Algorithm?
Using Markov chain theory to draw samples from a distribution p(x)
When is a sample accepted?
when it is less than the previous sample with some probability alpha
