Markov

Question 1

What is the Markovian hypothesis?

Answer 1

The probability of the current state depends only on the previous state, not on the entire history.

Question 2

How is a homogeneous Markov chain parameterized?

Answer 2

By a starting distribution π and a transition matrix A.

Question 3

What does the transition matrix A represent in a Markov chain?

Answer 3

A[i,j] represents the probability of transitioning from state i to state j.

Question 4

How is the probability of a sequence calculated in a Markov chain?

Answer 4

P(x₁, …, xₙ) = πx₁ * ∏ᵢ₌₂ⁿ A[xᵢ₋₁, xᵢ]

Question 5

What does Aᵏ(i,j) represent in a Markov chain?

Answer 5

The probability of going from state i to state j in exactly k steps.

Question 6

What are two key properties of a “well-behaved” Markov chain?

Answer 6

Irreducibility and aperiodicity.

Question 7

What is an irreducible Markov chain?

Answer 7

A chain where it’s possible to get from any state to any other state in a finite number of steps.

Question 8

What is an aperiodic Markov chain?

Answer 8

A chain where there are no closed loops that can only be traversed at fixed intervals.

Question 9

What is the stationary distribution of a Markov chain?

Answer 9

A probability distribution μ that satisfies μ · A = μ.

Question 10

How quickly does a well-behaved Markov chain converge to its stationary distribution?

Answer 10

Exponentially fast.

Question 11

What is a key limitation of Markov chains?

Answer 11

They cannot model long-range effects due to their “short-term memory”.

Question 12

What is an order-k Markov model? What is a drawback of higher-order Markov models?

Answer 12

A model where the current state depends on the k previous states. The number of parameters increases exponentially with the order.

Question 13

Probability of non consecutive events (state A to state B) in Markov chain?

Answer 13

Sum of probabilities of all possible sequences that start with state A and end with state B.

Question 14

How are the parameters of a Markov chain typically estimated?

Answer 14

Using Maximum Likelihood Estimation based on observed state transitions.

Question 15

What is a Hidden Markov Model (HMM)?

Answer 15

Statistical Model used to represent systems that transition between hidden states, while producing observable outputs (emissions). It is used to make inferences about sequential data with short-term dependency and implicit constraints.

Question 16

What are the three main questions addressed with an HMM?

Answer 16

Evaluation (probability of a sequence), Decoding (most probable hidden state allocation), and Estimation (parameter estimation).

Question 17

Parameters of a HMM?

Answer 17

By a starting distribution π and a transition matrix A and Emission probabilities.

Question 18

What is the purpose of the forward algorithm in HMMs?

Answer 18

To compute the probability of an observed sequence and perform filtering in an efficient manner: Sum over all state sequences using a combination of recursion and Dynamic Programming to avoid redundant computations.

Question 19

What is the Viterbi algorithm used for in HMMs?

Answer 19

To find the most likely hidden state sequence. It is also an efficient implementation that uses DP and recursion to keep track of the best path t o each state at each time given the observed emissions. vs. Forward algorithm: It uses max in each recursive step instead of sum and keeps track of best path of hidde nstate.

Question 20

What is the purpose of the forward-backward algorithm?

Answer 20

To compute the posterior probabilities of hidden states given the observed sequence.

Question 21

What is the Baum-Welch algorithm?

Answer 21

It’s an implementation of the EM algorithm for estimating HMM parameters when hidden states are unknown.

Question 22

What is the main advantage of using HMMs over simple mixture models?

Answer 22

HMMs can model dependencies between adjacent positions in a sequence.

Question 23

In the context of HMMs, what is meant by “emission probabilities”?

Answer 23

The probabilities of observing specific outputs given a particular hidden state.

Question 24

How can HMMs be used to model transcription factor binding sites?

Answer 24

By using a background state for non-binding regions and specific states for each position in the binding motif.

Question 25

How does an HMM differ from a simple Markov chain?

Answer 25

An HMM has hidden states that are not directly observable, while all states in a Markov chain are observable.

Question 26

What is meant by “decoding” in the context of HMMs?

Answer 26

Inferring the most likely sequence of hidden states given the observed sequence.

Question 27

What is the main difference between the Viterbi algorithm and the forward-backward algorithm?

Answer 27

Viterbi finds the single most likely state sequence, while forward-backward computes posterior probabilities for each state at each position.