chapter

Urn Models and Reinforcement Processes Notes for GATE CS

Urn Models and Reinforcement Processes notes for GATE CS: 11 study cards covering concepts, formulas, shortcuts and exam traps, plus solved practice questions

urn models and reinforcement processes notes

Chapter Roadmap: Urn Models and Reinforcement Processes

Your Journey Through Urn Models Current Focus: Polya Urn Reinforcement Processes The reinforcement mechanism and state evolution Exchangeability and why order does not matter Computing probabilities at any step Connection to Beta-Binomial distributions Martingale properties and convergence Why This Matters for GATE Polya Urn models test your understanding of conditional probability in sequential processes, the difference between independent and dependent events, and the long-term behavior of stochastic systems. Master the pattern, and you will recognize it instantly.

The Polya Urn: Rich Get Richer

The Polya Urn: Rich Get Richer Start with r red and b black balls. At each step, draw one ball, note its color, and return it plus one additional ball of the same color . If Red Drawn If Black Drawn Red: r \to r + 1 Black: b \to b + 1 Total: r + b + 1 Total: r + b + 1 Key Insight: Early outcomes get amplified. This is not independent trials — each draw changes the composition of the urn.

State Evolution: Tracking the Urn

State Evolution: Tracking the Urn Initial (Step 0) Red: r, Black: b Total: r + b After n Draws Total: r + b + n If k reds drawn: Red is r + k Probability at Step n + 1 Given k reds in first n draws: P (red at step n + 1) = \frac{r + k}{r + b + n} Markovian Property: The state after n draws is fully described by (n, k) . The future depends only on the current state, not the path taken to reach it.

8 more cards in this chapter

Try a question

Answer it here to see how it works. Nothing is recorded until you sign in.

Question 1

Level 1: Warm-up

In a Polya urn process, the urn initially contains 2 red balls and 3 black balls. Three trials are conducted: in each trial, a ball is drawn at random and returned along with another ball of the same colour. What is the minimum possible number of red balls in the urn after these three trials?

Question 2

Level 1: Warm-up

An urn contains 5 red balls and 3 black balls. In a trial, a ball is drawn at random, its colour is noted, and it is placed back along with another ball of the same colour. The first trial results in a black ball. What is the probability of drawing a red ball in the second trial?

Question 3

Level 1: Warm-up

Consider a Polya urn process starting with r red balls and b black balls. In each trial, a ball is drawn at random and returned along with another ball of the same colour. Which one of the following statements is TRUE?

Question 4

Level 1: Warm-up

An urn initially contains 6 red balls and 3 black balls. In a sequence of two trials, a red ball is drawn in the first trial and a black ball is drawn in the second trial. After each trial, the drawn ball is returned along with another ball of the same colour. What is the number of red balls in the urn after these two trials?

Question 5

Level 1: Warm-up

An urn initially contains 3 red balls and 4 black balls. The Polya urn process is followed for 5 trials: in each trial, a ball is drawn at random, noted, and returned along with another ball of the same colour. What is the maximum possible number of red balls in the urn after these 5 trials?

Question 6

Level 1: Warm-up

Consider the following assertion and reason in the context of a Polya urn process. Assertion (A): If the urn initially contains 4 red balls and 6 black balls, the probability of drawing a red ball on the 10th trial is 0.4. Reason (R): In a Polya urn process, the probability of drawing a red ball on any trial is equal to the initial proportion of red balls, \frac{r}{r + b} . Which one of the following options is correct?

Question 7

Level 1: Warm-up

An urn contains 3 red balls and 5 black balls. In a trial, a ball is randomly drawn from the urn, its colour is noted, and the ball is placed back into the urn along with another ball of the same colour. A ball is drawn in the first trial and is found to be red. What is the probability of drawing a red ball in the second trial?

Question 8

Level 1: Warm-up

An urn contains 5 red balls and 7 black balls. In a trial, a ball is randomly drawn from the urn, its colour is noted, and the ball is placed back into the urn along with another ball of the same colour. What is the probability of drawing a red ball in the first trial?

Question 9

Level 2: Moderate

An urn contains 1 red ball and 1 black ball. A student assumes that the draws in a Polya urn process are independent. Using this assumption, the student finds the minimum number of draws n required such that the probability of all n draws being red is strictly less than 1/11 . What is the actual minimum number of draws required?

Question 10

Level 2: Moderate

An urn contains 3 red balls and 4 black balls. In a trial, a ball is drawn at random, its colour is noted, and it is placed back along with another ball of the same colour. What is the probability that the first draw is red and the second draw is black?

Free preview ends here

Login to view the complete notes

Creating an account is free. You get the rest of this chapter, step-by-step solutions, and a study plan built around the topics you are actually weak at.

Why MastersUp

Personalised first. High quality throughout.

Most platforms hand everyone the same content. Here the content moves with your performance, topic by topic.

Built around you, not around a syllabus PDF

Every answer you give moves your topic-level intelligence rate. The next question, the next revision card and tomorrow's plan all change with it.

Revision that hits your weak spots

We only revise topics you have actually attempted and are still below the safe bar on — never the same chapter on repeat.

Questions calibrated to the real exam

Each question carries a measured toughness. You are served a rung above your current level, so practice keeps stretching you.

Notes written for recall, not for volume

Full lesson cards for first study, curated short-note cards for the last mile — with derivations, traps and exam patterns marked.

One place for everything

Notes, chapter practice, previous-year questions, test series and full-length papers — all feeding one picture of your preparation.

Honest progress

No vanity streaks. Progress here means chapters mastered and accuracy that held up on harder questions.

Unlock the whole course

Full notes and short notes, the complete question bank with worked solutions, mock tests, full-length papers, and an adaptive plan that rebuilds itself as you improve.

View all plans Start free

Urn Models and Reinforcement Processes Notes for GATE CS

Urn Models and Reinforcement Processes notes for GATE CS: 11 study cards covering concepts, formulas, shortcuts and exam traps, plus solved practice questions.

Chapter Roadmap: Urn Models and Reinforcement Processes

Your Journey Through Urn Models

Current Focus: Polya Urn Reinforcement Processes

The reinforcement mechanism and state evolution
Exchangeability and why order does not matter
Computing probabilities at any step
Connection to Beta-Binomial distributions
Martingale properties and convergence

Why This Matters for GATE

Polya Urn models test your understanding of conditional probability in sequential processes, the difference between independent and dependent events, and the long-term behavior of stochastic systems. Master the pattern, and you will recognize it instantly.

The Polya Urn: Rich Get Richer

Start with $r$ red and $b$ black balls. At each step, draw one ball, note its color, and return it plus one additional ball of the same color.

If Red Drawn	If Black Drawn
Red: $r \to r + 1$	Black: $b \to b + 1$
Total: $r + b + 1$	Total: $r + b + 1$

Key Insight: Early outcomes get amplified. This is not independent trials — each draw changes the composition of the urn.

State Evolution: Tracking the Urn

Initial (Step 0)
Red:

r

, Black:

b

Total:

r + b

After $n$ Draws
Total:

r + b + n

k

reds drawn: Red is

r + k

Probability at Step $n + 1$

Given $k$ reds in first $n$ draws:

P (red at step n + 1) = \frac{r + k}{r + b + n}

Markovian Property: The state after $n$ draws is fully described by $(n, k)$ . The future depends only on the current state, not the path taken to reach it.

Exchangeability: Order Does Not Matter

RRB

RBR

BRR

All three sequences have exactly the same probability.

Computing the Probability

For $n$ draws with $k$ reds and $n - k$ blacks:

P (k reds in n draws) = \frac{( k n ) \cdot r ^{(k)} \cdot b ^{(n - k)}}{( r + b ) ^{(n)}}

where $x^{(m)} = x (x + 1) \dots (x + m - 1)$ is the rising factorial. The draws are dependent, yet exchangeable.

Urn Models and Reinforcement Processes: Solved Questions with Step-by-Step Explanations (10 Problems)

Question 1 · Engineering Mathematics MCQ

In a Polya urn process, the urn initially contains 2 red balls and 3 black balls. Three trials are conducted: in each trial, a ball is drawn at random and returned along with another ball of the same colour. What is the minimum possible number of red balls in the urn after these three trials?

A.
1
B.
3
C.
2
D.
5

Correct Answer:

Step-by-Step Solution

Key idea: This is a state-evolution question asking for the minimum red count. The minimum occurs when no red balls are drawn (all draws are black).

Step 1: Initial state: 2 red, 3 black.

Step 2: After 3 trials, 3 balls are added. For minimum red, all 3 draws must be black.

Step 3: When black is drawn, only black balls are added. Red count stays unchanged. Red = 2 + 0 = 2.

Answer: 2

Common traps:

Option A (1): Subtracted 1 from red, thinking red balls are removed when black is drawn.
Option B (3): Added 1 to red, thinking at least one red must be added.
Option D (5): Added all 3 draws to red count (2 + 3 = 5).

Question 2 · Engineering Mathematics MCQ

An urn contains 5 red balls and 3 black balls. In a trial, a ball is drawn at random, its colour is noted, and it is placed back along with another ball of the same colour. The first trial results in a black ball. What is the probability of drawing a red ball in the second trial?

A.
$\frac{5}{8}$
B.
$\frac{6}{9}$
C.
$\frac{5}{7}$
D.
$\frac{5}{9}$

Correct Answer:

Step-by-Step Solution

Key idea: This is a Polya urn state-update question where a black ball is drawn first. We must update both the black count and the total.

Step 1: Initial state: 5 red, 3 black. Total = 8.

Step 2: First draw is black. The black ball is returned along with another black ball. New state: 5 red, 3 + 1 = 4 black. Total = 8 + 1 = 9.

Step 3: Probability of red on second draw = (number of red) / (total) = 5/9.

Answer: $\frac{5}{9}$

Common traps:

Option A ( $\frac{5}{8}$ ): Used the initial probability without updating.
Option B ( $\frac{6}{9}$ ): Added 1 to the red count instead of the black count.
Option C ( $\frac{5}{7}$ ): Subtracted 1 from the total instead of adding 1.

Question 3 · Engineering Mathematics MCQ

Consider a Polya urn process starting with $r$ red balls and $b$ black balls. In each trial, a ball is drawn at random and returned along with another ball of the same colour. Which one of the following statements is TRUE?

A.
The probability of drawing red on the 5th draw is $\frac{r}{r + b + 4}$ .
B.
Each draw is independent of the previous draws.
C.
The probability of drawing red on any draw is always $\frac{r}{r + b}$ .
D.
After $n$ draws, the total number of balls is $r + b + 2 n$ .

Correct Answer:

Step-by-Step Solution

Key idea: This is a statement-truth question testing fundamental properties of the Polya urn process. We check each option against the known properties.

Step 1: Check Option A. The probability of red on the 5th draw is $\frac{r}{r + b}$ by the martingale property, not $\frac{r}{r + b + 4}$ . False.

Step 2: Check Option B. The draws are <b>dependent</b> because each draw changes the urn composition. False.

Step 3: Check Option C. By the martingale property, the probability of red on any draw equals the initial proportion $\frac{r}{r + b}$ . True.

Step 4: Check Option D. After $n$ draws, one ball is added per draw, so total = $r + b + n$ , not $r + b + 2 n$ . False.

Answer: Option C.

Question 4 · Engineering Mathematics MCQ

An urn initially contains 6 red balls and 3 black balls. In a sequence of two trials, a red ball is drawn in the first trial and a black ball is drawn in the second trial. After each trial, the drawn ball is returned along with another ball of the same colour. What is the number of red balls in the urn after these two trials?

A.
6
B.
7
C.
8
D.
5

Correct Answer:

Step-by-Step Solution

Key idea: This is a state-tracking question, recognisable because it specifies the exact sequence of colours drawn and asks for the final count of a specific colour.

Step 1: Initial state: 6 red, 3 black.

Step 2: First trial draws a red ball. The red ball is returned with another red ball. Red count becomes $6 + 1 = 7$ . Black count remains 3.

Step 3: Second trial draws a black ball. The black ball is returned with another black ball. Black count becomes $3 + 1 = 4$ . Red count remains unchanged at 7.

Answer: The number of red balls after the two trials is 7.

Common trap: Option A (6) incorrectly subtracts 1 from the red count when the black ball is drawn, misunderstanding the reinforcement rule.

Question 5 · Engineering Mathematics MCQ

An urn initially contains 3 red balls and 4 black balls. The Polya urn process is followed for 5 trials: in each trial, a ball is drawn at random, noted, and returned along with another ball of the same colour. What is the maximum possible number of red balls in the urn after these 5 trials?

A.
8
B.
7
C.
12
D.
5

Correct Answer:

Step-by-Step Solution

Key idea: This is a state-evolution question asking for the maximum red count after $n$ draws. The maximum occurs when every draw is red.

Step 1: Initial state: 3 red, 4 black. Total = 7.

Step 2: After 5 trials, 5 balls are added (one per trial). Total = 7 + 5 = 12.

Step 3: For maximum red, all 5 draws must be red. Each red draw adds 1 red ball. Red count = 3 + 5 = 8.

Answer: 8

Common traps:

Option B (7): Initial red count, forgetting that red balls are added.
Option C (12): Total balls after 5 draws, not the red count.
Option D (5): Number of draws, not the red count.

Question 6 · Engineering Mathematics MCQ

Consider the following assertion and reason in the context of a Polya urn process.

Assertion (A): If the urn initially contains 4 red balls and 6 black balls, the probability of drawing a red ball on the 10th trial is 0.4.

Reason (R): In a Polya urn process, the probability of drawing a red ball on any trial is equal to the initial proportion of red balls, $\frac{r}{r + b}$ .

Which one of the following options is correct?

A.
A is false but R is true.
B.
A is true but R is false.
C.
Both A and R are true, but R is not the correct explanation of A.
D.
Both A and R are true, and R is the correct explanation of A.

Correct Answer:

Step-by-Step Solution

Key idea: This is an assertion-reason question testing the martingale property. We evaluate A and R separately, then check if R explains A.

Step 1: Evaluate Assertion (A). Initial: $r = 4$ , $b = 6$ . By the martingale property, $P (red on 10th trial) = \frac{r}{r + b} = \frac{4}{10} = 0.4$ . So A is true.

Step 2: Evaluate Reason (R). The statement " $P (red on any trial) = \frac{r}{r + b}$ " is exactly the martingale property. So R is true.

Step 3: Does R explain A? Yes. A is a direct application of R with $r = 4$ , $b = 6$ , and trial number 10. R provides the general principle that makes A true.

Answer: Both A and R are true, and R is the correct explanation of A.

Common trap: Option A might be chosen by a student who computes $\frac{4}{4 + 6 + 9} = \frac{4}{19} \approx 0.21$ , thinking the denominator increases by 9 after 9 previous trials. This is a unit mismatch: confusing the trial number with the denominator update.

Question 7 · Engineering Mathematics MCQ

An urn contains 3 red balls and 5 black balls. In a trial, a ball is randomly drawn from the urn, its colour is noted, and the ball is placed back into the urn along with another ball of the same colour. A ball is drawn in the first trial and is found to be red. What is the probability of drawing a red ball in the second trial?

A.
$\frac{3}{8}$
B.
$\frac{4}{9}$
C.
$\frac{4}{8}$
D.
$\frac{3}{9}$

Correct Answer:

Step-by-Step Solution

Key idea: This is a basic Polya urn state-update question, recognisable because a ball is drawn and returned with another of the same colour.

Step 1: Initial state: 3 red, 5 black. Total = 8.

Step 2: First draw is red. The red ball is returned along with another red ball. New state: 3 + 1 = 4 red, 5 black. Total = 8 + 1 = 9.

Step 3: Probability of red on second draw = (number of red) / (total) = 4/9.

Answer: $\frac{4}{9}$

Common trap: Option A ( $\frac{3}{8}$ ) is the initial probability, obtained by forgetting to update the urn composition. Option C ( $\frac{4}{8}$ ) updates the red count but forgets the total increases. Option D ( $\frac{3}{9}$ ) might come from not returning the drawn ball.

Question 8 · Engineering Mathematics MCQ

An urn contains 5 red balls and 7 black balls. In a trial, a ball is randomly drawn from the urn, its colour is noted, and the ball is placed back into the urn along with another ball of the same colour. What is the probability of drawing a red ball in the first trial?

A.
$\frac{5}{13}$
B.
$\frac{5}{12}$
C.
$\frac{6}{13}$
D.
$\frac{5}{11}$

Correct Answer:

Step-by-Step Solution

Key idea: This is a basic Polya urn setup question, recognisable because it asks for the probability of the very first draw before any reinforcement has occurred.

Step 1: Identify the initial state of the urn. There are 5 red balls and 7 black balls.

Step 2: Calculate the total number of balls initially: $5 + 7 = 12$ .

Step 3: The probability of drawing a red ball on the first trial is the ratio of red balls to the total number of balls: $P (red) = \frac{5}{12}$ .

Answer: $\frac{5}{12}$

Common trap: Option A ( $\frac{5}{13}$ ) incorrectly adds 1 to the total, assuming reinforcement happens before the first draw. The reinforcement only happens after the ball is drawn and noted.

Question 9 · Engineering Mathematics MCQ

An urn contains 1 red ball and 1 black ball. A student assumes that the draws in a Polya urn process are independent. Using this assumption, the student finds the minimum number of draws $n$ required such that the probability of all $n$ draws being red is strictly less than $1/11$ . What is the actual minimum number of draws required?

A.
4
B.
10
C.
12
D.
11

Correct Answer:

Step-by-Step Solution

Key idea: This is a contradiction question testing the exchangeability property, recognisable because it contrasts a false independence assumption with the actual dependent nature of the Polya urn process.

Step 1: Calculate the actual probability of all $n$ draws being red. Using the sequential multiplication rule (or exchangeability formula with $k = n$ ):

$P (all n red) = \frac{1}{2} \times \frac{2}{3} \times \frac{3}{4} \times \dots \times \frac{n}{n + 1} = \frac{1}{n + 1}$ .

Step 2: Set up the inequality for the actual process. We want $\frac{1}{n + 1} < \frac{1}{11}$ .

Step 3: Solve for $n$ . This gives $n + 1 > 11 ⟹ n > 10$ . The minimum integer $n$ is 11.

Answer: 11

Common trap: Option A (4) is the student's incorrect answer, obtained by assuming independence: $(1/2)^{n} < 1/11 ⟹ 2^{n} > 11 ⟹ n = 4$ . This overestimates the probability decay.

Question 10 · Engineering Mathematics MCQ

An urn contains 3 red balls and 4 black balls. In a trial, a ball is drawn at random, its colour is noted, and it is placed back along with another ball of the same colour. What is the probability that the first draw is red and the second draw is black?

A.
$\frac{12}{49}$
B.
$\frac{3}{14}$
C.
$\frac{9}{56}$
D.
$\frac{15}{56}$

Correct Answer:

Step-by-Step Solution

Key idea: This is a sequential probability question in a Polya urn, recognisable because it asks for the joint probability of a specific sequence of draws where the urn composition changes after each draw.

Step 1: Calculate the probability of the first draw being red. Initially, there are 3 red and 4 black balls (total 7). $P (1st Red) = \frac{3}{7}$ .

Step 2: Update the urn state. Since a red ball was drawn and returned with another red ball, the urn now has 4 red and 4 black balls (total 8).

Step 3: Calculate the conditional probability of the second draw being black. $P (2nd Black ∣ 1st Red) = \frac{4}{8} = \frac{1}{2}$ .

Step 4: Multiply the probabilities. $P (1st Red and 2nd Black) = \frac{3}{7} \times \frac{1}{2} = \frac{3}{14}$ .

Answer: $\frac{3}{14}$

Common trap: Option A ( $\frac{12}{49}$ ) is obtained by assuming the draws are independent and multiplying $\frac{3}{7} \times \frac{4}{7}$ . This ignores the reinforcement mechanism.

urn models and reinforcement processes notes

Chapter Roadmap: Urn Models and Reinforcement Processes

Your Journey Through Urn Models

Why This Matters for GATE

The Polya Urn: Rich Get Richer

The Polya Urn: Rich Get Richer

State Evolution: Tracking the Urn

State Evolution: Tracking the Urn

Probability at Step n+1

Try a question

Login to view the complete notes

Personalised first. High quality throughout.

Built around you, not around a syllabus PDF

Revision that hits your weak spots

Questions calibrated to the real exam

Notes written for recall, not for volume

One place for everything

Honest progress

Unlock the whole course

Urn Models and Reinforcement Processes Notes for GATE CS

Chapter Roadmap: Urn Models and Reinforcement Processes

Your Journey Through Urn Models

Why This Matters for GATE

The Polya Urn: Rich Get Richer

The Polya Urn: Rich Get Richer

State Evolution: Tracking the Urn

State Evolution: Tracking the Urn

Probability at Step n+1

Exchangeability: Order Does Not Matter

Exchangeability: Order Does Not Matter

Computing the Probability

Urn Models and Reinforcement Processes: Solved Questions with Step-by-Step Explanations (10 Problems)

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

More notes in this unit

Probability at Step $n + 1$

Probability at Step $n + 1$