Markov Flashcards
What is the Markovian hypothesis?
The probability of the current state depends only on the previous state, not on the entire history.
How is a homogeneous Markov chain parameterized?
By a starting distribution π and a transition matrix A.
What does the transition matrix A represent in a Markov chain?
A[i,j] represents the probability of transitioning from state i to state j.
How is the probability of a sequence calculated in a Markov chain?
P(x₁, …, xₙ) = πx₁ * ∏ᵢ₌₂ⁿ A[xᵢ₋₁, xᵢ]
What does Aᵏ(i,j) represent in a Markov chain?
The probability of going from state i to state j in exactly k steps.
What are two key properties of a “well-behaved” Markov chain?
Irreducibility and aperiodicity.
What is an irreducible Markov chain?
A chain where it’s possible to get from any state to any other state in a finite number of steps.
What is an aperiodic Markov chain?
A chain where there are no closed loops that can only be traversed at fixed intervals.
What is the stationary distribution of a Markov chain?
A probability distribution μ that satisfies μ · A = μ.
How quickly does a well-behaved Markov chain converge to its stationary distribution?
Exponentially fast.
What is a key limitation of Markov chains?
They cannot model long-range effects due to their “short-term memory”.
What is an order-k Markov model? What is a drawback of higher-order Markov models?
A model where the current state depends on the k previous states. The number of parameters increases exponentially with the order.
Probability of non consecutive events (state A to state B) in Markov chain?
Sum of probabilities of all possible sequences that start with state A and end with state B.
How are the parameters of a Markov chain typically estimated?
Using Maximum Likelihood Estimation based on observed state transitions.
What is a Hidden Markov Model (HMM)?
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.
What are the three main questions addressed with an HMM?
Evaluation (probability of a sequence), Decoding (most probable hidden state allocation), and Estimation (parameter estimation).
Parameters of a HMM?
By a starting distribution π and a transition matrix A and Emission probabilities.
What is the purpose of the forward algorithm in HMMs?
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.
What is the Viterbi algorithm used for in HMMs?
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.
What is the purpose of the forward-backward algorithm?
To compute the posterior probabilities of hidden states given the observed sequence.
What is the Baum-Welch algorithm?
It’s an implementation of the EM algorithm for estimating HMM parameters when hidden states are unknown.
What is the main advantage of using HMMs over simple mixture models?
HMMs can model dependencies between adjacent positions in a sequence.
In the context of HMMs, what is meant by “emission probabilities”?
The probabilities of observing specific outputs given a particular hidden state.
How can HMMs be used to model transcription factor binding sites?
By using a background state for non-binding regions and specific states for each position in the binding motif.
How does an HMM differ from a simple Markov chain?
An HMM has hidden states that are not directly observable, while all states in a Markov chain are observable.
What is meant by “decoding” in the context of HMMs?
Inferring the most likely sequence of hidden states given the observed sequence.
What is the main difference between the Viterbi algorithm and the forward-backward algorithm?
Viterbi finds the single most likely state sequence, while forward-backward computes posterior probabilities for each state at each position.
