What is a Markov Chain?

S3-SA3-0434

Grade Level:

Class 9

AI/ML, Data Science, Physics, Economics, Cryptography, Computer Science, Engineering

Definition

What is it?

A Markov Chain is a mathematical model that describes a sequence of events where the probability of each future event depends only on the current state, and not on the sequence of events that preceded it. Think of it as a 'memoryless' process where only the present matters for predicting the future.

Simple Example

Quick Example

Imagine you are predicting if it will rain tomorrow. If it's raining today, there's an 80% chance it will rain tomorrow and a 20% chance it will be sunny. If it's sunny today, there's a 30% chance of rain tomorrow and a 70% chance of sun. The prediction for tomorrow only cares about today's weather, not what happened last week.

Worked Example

Step-by-Step

Let's say a student's mood can be 'Happy' (H) or 'Sad' (S). --- STEP 1: If the student is Happy today, there's a 70% chance they'll be Happy tomorrow and 30% chance they'll be Sad. --- STEP 2: If the student is Sad today, there's a 40% chance they'll be Happy tomorrow and 60% chance they'll be Sad. --- STEP 3: We can write these as probabilities: P(H tomorrow | H today) = 0.7, P(S tomorrow | H today) = 0.3, P(H tomorrow | S today) = 0.4, P(S tomorrow | S today) = 0.6. --- STEP 4: If the student is Happy today, what is the probability they will be Sad after two days? --- STEP 5: To be Sad after two days, starting Happy today, there are two paths: Path 1: H -> H -> S. Probability = P(H tomorrow | H today) * P(S after 2 days | H tomorrow) = 0.7 * 0.3 = 0.21. --- STEP 6: Path 2: H -> S -> S. Probability = P(S tomorrow | H today) * P(S after 2 days | S tomorrow) = 0.3 * 0.6 = 0.18. --- STEP 7: Total probability = Probability(Path 1) + Probability(Path 2) = 0.21 + 0.18 = 0.39. --- ANSWER: If the student is Happy today, there is a 39% chance they will be Sad after two days.

Why It Matters

Markov Chains are super useful in AI/ML for things like predicting stock prices or weather patterns. In computer science, they help design efficient algorithms and understand network traffic. Understanding them can open doors to careers in data science, software engineering, and even physics research, helping you build smarter systems.

Common Mistakes

MISTAKE: Thinking the past history of states matters for the next transition. | CORRECTION: Remember the 'memoryless' property; only the current state affects the probabilities of future states.

MISTAKE: Confusing probabilities of being in a state with probabilities of transitioning between states. | CORRECTION: Always use conditional probabilities, P(next state | current state), for transitions.

MISTAKE: Assuming the probabilities of transitions always stay the same over time. | CORRECTION: While often true in basic examples, in advanced applications, transition probabilities can sometimes change, making it a 'non-stationary' Markov Chain.

Practice Questions

Try It Yourself

QUESTION: A fan's team can either 'Win' (W) or 'Lose' (L) a match. If they win today, they have a 60% chance to win tomorrow. If they lose today, they have a 70% chance to lose tomorrow. If they won today, what is the probability they lose tomorrow? | ANSWER: 40% (100% - 60% win chance = 40% lose chance)

QUESTION: Using the cricket team example from Q1, if the team won today, what is the probability they win the day after tomorrow? (Show working) | ANSWER: There are two paths: W -> W -> W (0.6 * 0.6 = 0.36) and W -> L -> W (0.4 * 0.3 = 0.12). Total probability = 0.36 + 0.12 = 0.48 or 48%.

QUESTION: A small village has two tea stalls, Stall A and Stall B. Each day, 80% of customers who went to Stall A yesterday return to Stall A, while 20% switch to Stall B. From Stall B, 70% return to Stall B, and 30% switch to Stall A. If 100 people went to Stall A today, how many are expected to go to Stall A the day after tomorrow? | ANSWER: Let's track probabilities. If 100 people went to Stall A today: Tomorrow: Stall A = 100 * 0.8 = 80 people. Stall B = 100 * 0.2 = 20 people. Day after tomorrow (from those 80 at A): 80 * 0.8 (stay at A) = 64. 80 * 0.2 (switch to B) = 16. Day after tomorrow (from those 20 at B): 20 * 0.3 (switch to A) = 6. 20 * 0.7 (stay at B) = 14. Total at Stall A the day after tomorrow = 64 + 6 = 70 people. So, 70 people.

MCQ

Quick Quiz

Which of the following best describes the 'memoryless' property of a Markov Chain?

The chain remembers all past states.

The probability of the next state depends only on the current state.

The chain has no states.

The future is entirely random and unpredictable.

The Correct Answer Is:

Option B correctly defines the memoryless property: the next state's probability is solely determined by the current state, not by any previous history. Options A, C, and D are incorrect as they contradict the fundamental definition of a Markov Chain.

Real World Connection

In the Real World

Markov Chains are used by companies like Google to predict the next word you might type on your phone or in a search query, based on the words you've already typed. They also power recommendation systems on platforms like Netflix or Amazon, suggesting products or movies based on your current viewing or shopping habits, not your entire past history.

Key Vocabulary

Key Terms

STATE: A specific condition or situation in the system, like 'sunny' or 'raining' | TRANSITION: Moving from one state to another | PROBABILITY: The likelihood of an event occurring | MEMORYLESS PROPERTY: The future depends only on the present state, not the past | TRANSITION MATRIX: A table showing all probabilities of moving between states

What's Next

What to Learn Next

Great job understanding Markov Chains! Next, you can explore 'Transition Matrices,' which are a powerful way to represent and calculate probabilities in Markov Chains more easily. This will help you solve more complex prediction problems and see how these chains are used in real-world computer science.