Markov Chain

Question 1

What is a finite–space Markov Chain?

Answer 1

One where there is a difference there are discrete values or states” that the Markov chain can take”

Question 2

What is a unigram, bigram, trigram and a 4–gram?

Answer 2

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

Question 3

What is a Transition Matrix?

Answer 3

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.

Question 4

After n passes of time, what is the transition matrix?

Answer 4

The original transition matrix (for one passing of time) to the power of n

Question 5

What is a limiting distribution?

Answer 5

One that satisfies That there is a constant transition matrix at all times

Question 6

What is true for every limiting distribution?

Answer 6

That a limiting distribution is also stationary distribution

Question 7

What must be satisfied in order to be a stationary distribution?

Answer 7

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)

Question 8

What is true for every NxN transition matrix, P?

Answer 8

1 is always an eigenvalue

This is proved through definition of eigenvalue and the sum of all rows adding to 1

Question 9

When is a process not regular ergodic for a stationary distribution?

Answer 9

Two stationary distributions

The stationary distribution depends on the initial condition

Question 10

When can two states from a markov chain be said to communicate with each other?

Answer 10

When there is a path between the two states (both ways)

Question 11

What is a recurrent set?

Answer 11

A set where all members communicate with each other.

It is impossible to move outside the set

Question 12

What is a transient state?

Answer 12

One outside of a recurrent set

If we start on this state, eventually the state will be left and never returned to.

Question 13

What is an irreducible Markov chain?

Answer 13

One where all states communicate with each other

Question 14

What is the waiting time to get to a state?

Answer 14

the sum of:

All probabilities of entering state multiplied by 1/(1 + waiting time of that state)

Question 15

What is the period of a state k?

Answer 15

The greatest common divisor of the set of probabilities of returning to the state k from the state k.

Question 16

When is a state periodic?

Answer 16

When a state has a period of 1

Question 17

When is a Markov chain aperiodic?

Answer 17

When all states are aperiodic

Question 18

If a chain is irreducible and aperiodic, what is it also?

Answer 18

It is also regular ergodic and will have a limiting distribution

Question 19

How many eigenvalues of the transition matrix are there for a Markov chain with periodicity k?

Answer 19

K eigenvalues

Question 20

What are the magnitudes of the eigenvalues?

Answer 20

All have magnitude 1

Question 21

When is a distribution detailed balance with a transition matrix P.

Answer 21

πjPj,k = πkPk,j

Question 22

What is a birth–death process?

Answer 22

One where a number of items increase and decrease at a set rate?

Question 23

What n(t) for a birth–death process?

Answer 23

The number of items at a time instance t

Question 24

For a change in time dt (t+dt), what is the probability of having n items when only birth is considered?

Answer 24

in blue is probability of no birth. In red is probability of a birth

Question 25

What is the difference between continuous and discrete time?

Answer 25

Discrete time there is a transition matrix

In continuous time there’s the transition rate matrix, Q

Question 26

What is the transition rate matrix Q like?

Answer 26

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)

Question 27

What is the probability of a certain number of items when death rate is introduced?

Answer 27

Blue is probability of nothing occurring

Red is a birth occurring

Green is a death occurring

Question 28

How can Brownian Motion be described?

Answer 28

As a random walk where each step is taken at a certain interval that tends to 0

Question 29

What is used in Brownian Motion?

Answer 29

Density of items rather than number

Items leave area (lowering density)

Or enter area (increasing density)

Question 30

What is used to investigate Brownian Motion?

Answer 30

Taylor Series Expansion to both changes in time and position f(x,t)

Question 31

What is the result?

Answer 31

the diffusion equation

Question 32

What are the three properties of a one–dimensional Wiener Process?

Answer 32

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

Question 33

What is the cross correlation between two different functions at points t and s?

Answer 33

2αmin(t,s)

Question 34

What is a simple extension to the Wiener Process?

Answer 34

Adding a drift term

Question 35

What are Monte–Carlo Methods?

Answer 35

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

Question 36

Rather than histograms, what can be done?

Answer 36

Sampling from a weighted function w(x)

Question 37

What should be minimised in Monto–Carlo methods?

Answer 37

The number of samples

The variance (standard deviation)

Question 38

What can be done to get a better set of samples or when we cant sample from p(x) so must use another pdf?

Answer 38

importance sampling

Question 39

What is the equation for importance sampling?

Answer 39

p(x)/q(x) is the importance of the drawn sample

Question 40

With biased sampling how does q(x) affect results?

Answer 40

The closer q(x) is to H(x) the better the bias does at reducing Variance

Question 41

What is rejection sampling?

Answer 41

Drawing a box

Sampling uniformly from a box

rejecting samples that don’t fall under a curve

Question 42

What is the problem with rejection sampling?

Answer 42

Very wasteful

Curse of dimensionality

Question 43

What is the Metropolis–Hastings Algorithm?

Answer 43

Using Markov chain theory to draw samples from a distribution p(x)

Question 44

When is a sample accepted?

Answer 44

when it is less than the previous sample with some probability alpha