Is it true that All Markov chains eventually reach a steady state.?

Only irreducible, aperiodic Markov chains with finite state spaces are guaranteed to converge to a unique stationary distribution.

Is it true that The future state depends on all past states.?

In a Markov chain, the future state depends *only* on the current state (the Markov property).

Markov Chains: A Comprehensive Cheat Sheet

Markov chains are mathematical systems that transition from one state to another based on probabilities. They are fundamental in modeling systems where future states depend only on the current state, not past events.

Core Principles

A stochastic process is a collection of random variables, often indexed by time.
A Markov process (or chain) has the 'memoryless' property: the future state depends only on the present state, not on the sequence of events that preceded it.
States can be discrete or continuous, and time can be discrete or continuous, leading to four main types of Markov chains.
The transition matrix (P) contains probabilities of moving from one state to another.
Stationary distribution (π) represents the long-term probabilities of being in each state.
Key concepts include recurrence, transience, irreducibility, and periodicity of states.

Action Steps

Identify the states of the system.
Determine the transition probabilities between states.
Construct the transition matrix.
Calculate the stationary distribution (if it exists).
Analyze state properties (recurrent, transient, irreducible, periodic).

Formulas

$P(X_{n+1}=j | X_n=i) = P_{ij}$
$P(X_n=j) = \sum_{i} P(X_{n-1}=i) P_{ij}$
$\pi_j = \sum_{i} \pi_i P_{ij}$
$P(t) = P(0) e^{Qt}$ (for continuous-time Markov chains)
$P_{ij}(t) = e^{-\lambda t} \frac{(\lambda t)^{j-i}}{(j-i)!}$ (for Poisson process)

Key Terms

Stochastic Process: A collection of random variables, often indexed by time.
Markov Property: The future state depends only on the current state, not on past states.
State: A possible condition or value of the system.
Transition Probability: The probability of moving from one state to another.
Transition Matrix: A matrix containing all transition probabilities.
Stationary Distribution: The long-term probability distribution of states.
Recurrent State: A state that is eventually returned to with probability 1.
Transient State: A state that is eventually left with probability 1.
Irreducible Chain: A chain where all states can reach each other.
Aperiodic Chain: A chain where states can be returned to at any time (no fixed period).
Sojourn Time: The time spent in a state before transitioning.
Time Reversibility: A property where the process behaves the same forwards and backwards in time.

Pro Tips

For discrete-time, finite-state Markov chains, the stationary distribution often exists if the chain is irreducible and aperiodic.
For continuous-time Markov chains, the existence of a stationary distribution depends on the rates and the structure of the state space.
Understanding the 'global balance equations' is crucial for solving for stationary distributions in continuous-time chains.
Time reversibility simplifies analysis by allowing the process to be viewed forwards or backwards in time.
The embedded Markov chain is a powerful tool for analyzing continuous-time processes.

Pitfalls to Avoid

Assuming a chain is irreducible or aperiodic when it is not.
Incorrectly calculating transition probabilities.
Confusing discrete-time and continuous-time models.
Misinterpreting the meaning of stationary distribution (it's a long-term average, not a guarantee).
Forgetting the condition $\lambda < \mu$ for the existence of a stable M/M/1 queue.

Myth vs Reality

All Markov chains eventually reach a steady state.: Only irreducible, aperiodic Markov chains with finite state spaces are guaranteed to converge to a unique stationary distribution.
The future state depends on all past states.: In a Markov chain, the future state depends *only* on the current state (the Markov property).

Real World Examples

Customer arrival and service in a queue (e.g., call center, supermarket).: Modeling waiting times, queue lengths, and system utilization (M/M/1 queues).
Weather patterns (e.g., sunny, cloudy, rainy days).: Predicting future weather based on current conditions.
Web page navigation (e.g., Google's PageRank algorithm).: Determining the importance of web pages based on link structure.
Inventory management and machine breakdowns.: Optimizing stock levels and predicting maintenance needs.

Statistics

Average number of customers in M/M/1 queue (L): $\lambda / (\mu - \lambda)$
Average waiting time in M/M/1 queue (W): $\lambda / (\mu (\mu - \lambda))$

Timeline

Early 20th Century: Andrey Markov develops the theory of Markov chains.
Mid-20th Century: Applications emerge in physics, engineering, and operations research.
Late 20th Century - Present: Widespread use in computer science (algorithms, machine learning), finance, biology, and more.

People

Andrey Markov: Pioneer of Markov chain theory.
A. K. Erlang: Early work on queuing theory, related to Markov processes.