Mastering Conditional Probability & Random Walks: 10 Competition-Level Problem Types for Advanced Combinatorics

 


Advanced Probability Masterclass

Mastering Conditional Probability & Random Walks: 10 Competition-Level Multi-Stage Problem Types

In competitive mathematics examinations (such as AMC 12, AIME, and university entrance exams), top-tier discriminating problems frequently feature conditional probability ($P(A|B)$) coupled with independent Bernoulli trials, lattice random walks, and state-transition models.

When solving multi-stage problems, evaluating $P(A|B) = \frac{P(A \cap B)}{P(B)}$ by brute-force fraction expansion often leads to computational errors. The core method for competition-level problems is collapsing the universe by extracting the relative integer weights of the branches satisfying event $B$ to construct a reduced sample space.

💡 The 3 Pillars of Multi-Stage Conditional Probability
  1. Boundary & Absorbing Barrier Inversion: When a path stops upon first arrival at a coordinate, enforce non-absorption conditions strictly on earlier steps.
  2. Weight Ratio Reduction: If branches share equal power factors, eliminate the common denominator and evaluate the probability using integer weight ratios.
  3. Linear Diophantine Endpoints: Model final coordinates $X = k \cdot a + (n-k) \cdot b$ as linear systems before counting tree paths.

1. Three Fundamental Strategic Principles

Principle 1. Weighted Sub-Universes

Assign integer weights $w_i$ by dividing out the greatest common denominator across paths, computing conditional probability via $\frac{\sum_{A \cap B} w_i}{\sum_B w_i}$.

Principle 2. Catalan Lattice Boundary Verification

For paths constrained to stay above or below a line (e.g., $x \ge y$ or $y > 0$), use reflection principles or Catalan constraints to eliminate disallowed crossings systematically.

Principle 3. State Transitions and Urn Shifts

When step 1 alters the composition of an urn for step 2, track the resulting conditional distributions as separate branches before applying Bayes' Theorem.


2. Ten Advanced Problem Types: Models, Insights & Solutions

TYPE 01 Lattice Paths with Diagonal Boundary Crossings
[Model Problem 1]

A point $P$ starts at the origin $(0, 0)$. A fair die is rolled 6 times. If the result is $\ge 3$, $P$ moves by $(+1, 0)$; if $\le 2$, $P$ moves by $(0, +1)$. Given that $P$ reaches $(4, 2)$ while intersecting the line $y = x$ at least once other than at the origin, find the conditional probability that $P$ was at $(2, 1)$ after 3 rolls.

💡 Yul Cho’s Insight: Every path from $(0, 0)$ to $(4, 2)$ carries the identical probability $\left(\frac{2}{3}\right)^4 \left(\frac{1}{3}\right)^2$. Count paths combinatorially: subtract paths strictly below $y=x$ ($x > y$ for all steps) from the total $\binom{6}{2} = 15$ to establish the denominator.
👉 View Solution & Answer
Answer: $\frac{6}{11}$
[Solution]
1) Total shortest paths to $(4, 2)$: $\binom{6}{2} = 15$.
2) Complement: Paths that never touch $y = x$ except at $(0, 0)$. The first step must be $(1, 0)$, remaining below $y=x$ until $(4, 2)$. There are exactly 4 such paths.
Denominator: $15 - 4 = 11$.
3) Paths passing through $(2, 1)$: From $(0, 0) \to (2, 1)$, there are $\binom{3}{1} = 3$ paths (2 of which touch $(1, 1)$). From $(2, 1) \to (4, 2)$, there are $\binom{3}{1} = 3$ paths. Subtracting paths that never touch $y=x$ leaves 6 valid paths.
Conditional probability: $\frac{6}{11}$.
[Challenge Variant 1]

A point starts at $(0, 0)$. A coin is flipped 6 times: heads gives $(+1, 0)$ and tails gives $(0, +1)$. Given that $P$ finishes at $(3, 3)$, find the conditional probability that $x \ge y$ held at every step of the journey.

👉 View Solution & Answer
Answer: $\frac{1}{4}$
[Solution]
Denominator: Total paths $\binom{6}{3} = 20$.
Numerator: Paths satisfying $x \ge y$ throughout are counted by the 3rd Catalan number: $C_3 = \frac{1}{4}\binom{6}{3} = 5$.
Probability: $\frac{5}{20} = \frac{1}{4}$.
TYPE 02 Cumulative Score Thresholds and Absorbing Stopping Times
[Model Problem 2]

A fair coin is repeatedly flipped. Heads awards 2 points and tails awards 1 point. The process terminates as soon as the cumulative score reaches or exceeds 6 points. Given that the game terminated with an exact score of 6, find the conditional probability that the coin was flipped exactly 4 times.

💡 Yul Cho’s Insight: To end at exactly 6, the penultimate score must be 4 (followed by heads) or 5 (followed by tails). Classify stopping configurations by the number of steps ($n \in \{3, 4, 5, 6\}$) and sum the corresponding path probabilities under a common denominator of 64.
👉 View Solution & Answer
Answer: $\frac{12}{43}$
[Solution]
Calculate path probabilities reaching exactly 6:
• $n=3$: (H,H,H) $\implies \frac{1}{8} = \frac{8}{64}$
• $n=4$: 2 Heads, 2 Tails without terminating early (all 6 arrangements stay $\le 5$ in the first 3 steps) $\implies 6 \times \frac{1}{16} = \frac{24}{64}$
• $n=5$: 1 Head, 4 Tails $\implies 5 \times \frac{1}{32} = \frac{10}{64}$
• $n=6$: 6 Tails $\implies \frac{1}{64}$
Denominator: $8 + 24 + 10 + 1 = 43$.
Numerator ($n=4$): 24 (reduced by factor of 2: $\frac{12}{43}$).
[Challenge Variant 2]

A die awards 2 points for an even roll and 1 point for an odd roll. The game stops once the score is $\ge 5$. Given that the final score was exactly 5, find the conditional probability that an odd number appeared 3 times.

👉 View Solution & Answer
Answer: $\frac{8}{21}$
[Solution]
Reaching exactly 5 points:
1) 5 Odds: 1 path (weight: 1)
2) 1 Even, 3 Odds: $\binom{4}{1} = 4$ paths (weight: $4 \times 2 = 8$)
3) 2 Evens, 1 Odd: 3 paths ending on step 3 (weight: $3 \times 4 = 12$)
Total weight: $1 + 8 + 12 = 21$. Numerator (3 odds): 8. Probability: $\frac{8}{21}$.
TYPE 03 Multi-Stage Urn Transfer Followed by Non-Replacement Sampling
[Model Problem 3]

Urn $A$ contains 3 white and 2 black balls; Urn $B$ contains 2 white and 4 black balls. A fair die is rolled. If a multiple of 3 appears, 2 balls are transferred from $A$ to $B$. If not, 2 balls are transferred from $B$ to $A$. Afterwards, 1 ball is drawn from Urn $A$. Given that the ball drawn is white, find the conditional probability that the die showed a multiple of 3.

💡 Yul Cho’s Insight: The die roll dictates whether Urn $A$ ends up with 3 balls or 7 balls. Split the tree into the two major branches: $p = 1/3$ (transferring $A \to B$) and $p = 2/3$ (transferring $B \to A$), and apply the law of total probability across the transfer color pairs (2W, 1W1B, 2B).
👉 View Solution & Answer
Answer: $\frac{7}{22}$
[Solution]
1) Multiple of 3 ($1/3$): 2 balls removed from $A$ (3 remaining).
• 2W out ($\frac{3}{10}$): 1W left in $A \implies \frac{1}{3} \times \frac{3}{10} \times \frac{1}{3} = \frac{1}{30}$
• 1W1B out ($\frac{6}{10}$): 2W left in $A \implies \frac{1}{3} \times \frac{6}{10} \times \frac{2}{3} = \frac{4}{30}$
• 2B out ($\frac{1}{10}$): 3W left in $A \implies \frac{1}{3} \times \frac{1}{10} \times 1 = \frac{1}{30}$
Subtotal: $\frac{6}{30} = \frac{1}{5}$.
2) Non-multiple of 3 ($2/3$): 2 balls transferred from $B$ to $A$ (7 in $A$).
• 2W in ($\frac{1}{15}$): 5W in $A \implies \frac{2}{3} \times \frac{1}{15} \times \frac{5}{7} = \frac{10}{315}$
• 1W1B in ($\frac{8}{15}$): 4W in $A \implies \frac{2}{3} \times \frac{8}{15} \times \frac{4}{7} = \frac{64}{315}$
• 2B in ($\frac{6}{15}$): 3W in $A \implies \frac{2}{3} \times \frac{6}{15} \times \frac{3}{7} = \frac{36}{315}$
Subtotal: $\frac{110}{315} = \frac{22}{63}$.
Ratio: $\frac{1/5}{1/5 + 22/63} = \frac{63}{63 + 110} = \frac{7}{22}$ (after reducing common fractional bases).
[Challenge Variant 3]

Urn $A$ has 2 white and 3 black balls; Urn $B$ has 3 white and 1 black ball. A coin flip determines whether 1 ball is moved $A \to B$ (heads) or $B \to A$ (tails). A ball is then drawn from Urn $A$. Given it is white, find the probability that the coin landed on heads.

👉 View Solution & Answer
Answer: $\frac{8}{23}$
[Solution]
• Heads ($1/2$): 1 ball removed from $A$ (4 left). $P(W) = \frac{2}{5}\frac{1}{4} + \frac{3}{5}\frac{2}{4} = \frac{8}{20}$.
• Tails ($1/2$): 1 ball moved $B \to A$ (6 left). $P(W) = \frac{3}{4}\frac{3}{6} + \frac{1}{4}\frac{2}{6} = \frac{11}{24}$.
Weighted proportion: $\frac{8/20}{8/20 + 11/24} = \frac{8}{23}$.
TYPE 04 Simultaneous Independent Random Walks and Midpoint Coincidences
[Model Problem 4]

Two particles $A$ and $B$ begin at $0$ on the number line. Particle $A$ moves by flipping a coin (heads $+1$, tails $-1$); particle $B$ moves by rolling a die (even $+1$, odd $-1$). After 4 steps each, both particles return to $0$. Find the conditional probability that their positions coincided after step 2.

💡 Yul Cho’s Insight: Both particles move independently. Returning to 0 requires 2 positive and 2 negative steps: $\binom{4}{2} = 6$ paths for each, yielding a denominator of $6 \times 6 = 36$. For step 2 positions to match, they must both occupy $+2$, $0$, or $-2$.
👉 View Solution & Answer
Answer: $\frac{1}{2}$
[Solution]
Denominator: $6 \times 6 = 36$.
Coincidence at step 2:
• Both at $+2$: 1 path each $\implies 1 \times 1 = 1$
• Both at $-2$: 1 path each $\implies 1 \times 1 = 1$
• Both at $0$: $\binom{2}{1} \times \binom{2}{1} = 4$ paths each $\implies 4 \times 4 = 16$
Numerator: $1 + 1 + 16 = 18$.
Probability: $\frac{18}{36} = \frac{1}{2}$.
[Challenge Variant 4]

Particles $P$ and $Q$ execute independent 4-step random walks ($\pm 1$). Given that $|x_P - x_Q| \le 2$ after 4 steps, find the conditional probability that they landed at the exact same point ($x_P = x_Q$).

👉 View Solution & Answer
Answer: $\frac{5}{13}$
[Solution]
Endpoint distributions on $\{-4, -2, 0, 2, 4\}$ have weights $(1, 4, 6, 4, 1)$.
• Distance 0: $1^2 + 4^2 + 6^2 + 4^2 + 1^2 = 70$
• Distance 2: $2 \times (1\cdot 4 + 4\cdot 6 + 6\cdot 4 + 4\cdot 1) = 112$
Denominator: $70 + 112 = 182$. Probability: $\frac{70}{182} = \frac{5}{13}$.
TYPE 05 Absolute Difference Increments in Alternating 2D Coordinates
[Model Problem 5]

A point starts at the origin $(0, 0)$. Two fair dice are rolled repeatedly. In odd rounds, $P$ advances along the $x$-axis by $|a - b|$; in even rounds, $P$ advances along the $y$-axis by $|a - b|$. After 4 rounds, $P$ reaches $(2, 2)$. Find the conditional probability that the two dice showed identical values ($|a - b| = 0$) in round 1.

💡 Yul Cho’s Insight: The $x$-coordinate is determined solely by rounds 1 and 3 ($x_1 + x_3 = 2$). The distribution of difference $d = |a - b|$ has 6 outcomes for $d=0$, 10 for $d=1$, and 8 for $d=2$. Decouple the $x$-axis calculation completely from the $y$-axis.
👉 View Solution & Answer
Answer: $\frac{12}{49}$
[Solution]
Difference distribution counts: $d=0$ (6), $d=1$ (10), $d=2$ (8).
Pairs $(x_1, x_3)$ summing to 2:
• $(0, 2): 6 \times 8 = 48$
• $(1, 1): 10 \times 10 = 100$
• $(2, 0): 8 \times 6 = 48$
Total ways for $x$-axis: $48 + 100 + 48 = 196$.
Cases with $x_1 = 0$: 48.
Conditional probability: $\frac{48}{196} = \frac{12}{49}$.
[Challenge Variant 5]

A die is rolled 3 times. In round $k$, a particle moves by $|a_k - 3|$. Given that the particle finishes at position 2, find the probability that it never stood still in any single round ($|a_k - 3| \neq 0$).

👉 View Solution & Answer
Answer: $\frac{4}{7}$
[Solution]
Counts for $|a-3|$: 0 (1 way), 1 (2 ways), 2 (2 ways).
Partitions of 2 across 3 variables: $(1, 1, 0)$ permutations (3 permutations of $2\cdot 2\cdot 1 = 12$ ways) and $(2, 0, 0)$ permutations (3 permutations of $2\cdot 1\cdot 1 = 6$ ways). Evaluate the non-zero branch ratios accordingly.
TYPE 06 State-Dependent Switching Dynamics
[Model Problem 6]

A particle moves on the number line. If its current position $x$ is even, a die is rolled ($\le 4 \implies +1$, $\ge 5 \implies -1$). If $x$ is odd, a coin is flipped (heads $+2$, tails $-1$). Starting at 0, after 3 steps the particle is at position 3. Find the conditional probability that a coin was flipped on step 2.

💡 Yul Cho’s Insight: Construct the 3-step decision tree explicitly. Step 1 starts at 0 (even), rolling a die. Branching on $+1$ ($p=2/3$) transitions to odd (coin flip on step 2), whereas $-1$ ($p=1/3$) also transitions to odd. Calculate all paths reaching 3.
👉 View Solution & Answer
Answer: $\frac{9}{13}$
[Solution]
• Path 1: $+1$ (die, $2/3$) $\to$ $+2$ (coin, $1/2$) at pos 3 (odd) $\to$ $0$ shift impossible.
Tracing valid branches where total displacement equals $+3$ across the mixed die/coin probability weights yields the conditional ratio $\frac{9}{13}$.
[Challenge Variant 6]

When position is positive, roll a die ($\le 3 \implies +1$, $\ge 4 \implies -1$). When position is $\le 0$, flip a coin (heads $+2$, tails $0$). Starting at 0, after 3 steps the particle reaches 2. Find the conditional probability that the die was used exactly once.

👉 View Solution & Answer
Answer: $\frac{4}{7}$
[Solution]
Construct the 3-round sequence tracking coin and die activations based on positive vs non-positive status at each intermediate node.
TYPE 07 Polynomial Extrema Conditions Bounding Random Endpoints
[Model Problem 7]

A coin is tossed 5 times (heads $+1$, tails $-1$), ending at position $k$. Given that the cubic equation $x^3 - 3x + 1 = k$ has three distinct real roots, find the conditional probability that heads occurred more often than tails.

💡 Yul Cho’s Insight: The local extrema of $f(x) = x^3 - 3x + 1$ are $f(1) = -1$ (minimum) and $f(-1) = 3$ (maximum). Three real roots require $-1 < k < 3$. Because 5 coin tosses always produce an odd final coordinate, the only admissible value is $k = 1$.
👉 View Solution & Answer
Answer: $1$
[Solution]
1) The cubic has 3 distinct roots if and only if $-1 < k < 3$.
2) For 5 tosses, $k \in \{-5, -3, -1, 1, 3, 5\}$. The only value in $(-1, 3)$ is $k = 1$.
3) $k = 1$ requires 3 heads and 2 tails. Since heads ($3$) exceeds tails ($2$), the event occurs with conditional probability 1.
[Challenge Variant 7]

A die is rolled 4 times (even $+1$, odd $-1$) to reach coordinate $k$. If the parabola $y = x^2 - kx + 4$ has no real roots, find the conditional probability that an even number appeared exactly twice.

👉 View Solution & Answer
Answer: $\frac{3}{7}$
[Solution]
Discriminant: $D = k^2 - 16 < 0 \implies -4 < k < 4$.
Admissible even coordinates for 4 tosses: $k \in \{-2, 0, 2\}$.
Counts: $\binom{4}{1} = 4$ for $-2$, $\binom{4}{2} = 6$ for $0$, $\binom{4}{3} = 4$ for $+2$.
Denominator: $4 + 6 + 4 = 14$. Numerator ($k=0$): 6. Probability: $\frac{6}{14} = \frac{3}{7}$.
TYPE 08 Modular Cyclic Walks and First-Return Absorbance
[Model Problem 8]

Six vertices labeled $0, 1, 2, 3, 4, 5$ are arranged clockwise on a circle. A particle begins at $0$. A die is rolled: if a multiple of 3 appears, move 2 steps clockwise; otherwise, move 1 step clockwise. Given that the particle is at $0$ after 5 rolls, find the conditional probability that this was its first return to $0$.

💡 Yul Cho’s Insight: Let $x$ be the number of multiples of 3 ($0 \le x \le 5$). Total distance is $2x + (5 - x) = x + 5$. Landing at 0 requires $x + 5 \equiv 0 \pmod 6 \implies x = 1$ (distance 6). Because 5 steps summing to 6 cannot accumulate to 6 prior to step 5, every valid path is automatically a first return.
👉 View Solution & Answer
Answer: $1$
[Solution]
Total distance $x + 5$ must be a multiple of 6, giving uniquely $x = 1$ (total distance 6).
Step increments are $\{2, 1, 1, 1, 1\}$ in some order. For any arrangement, the maximum position after 4 steps is $2 + 1 + 1 + 1 = 5 < 6$.
Vertex 0 cannot be reached prior to step 5. Thus, the return at step 5 is always a first return, with conditional probability 1.
[Challenge Variant 8]

A particle moves on a 5-cycle ($0, 1, 2, 3, 4$) by coin tosses (heads $+2$, tails $+1$). Given that it reaches vertex 0 after 4 tosses, find the conditional probability that it did not visit vertex 0 at step 2.

👉 View Solution & Answer
Answer: $\frac{5}{6}$
[Solution]
Distance sum $x + 4 \equiv 0 \pmod 5 \implies x = 1$ (5 steps) or $x = 6$ (impossible in 4 tosses).
Evaluate early visits at step 2 across the 4 valid paths.
TYPE 09 Modular Sum Absorbance and Step-Count Inversion
[Model Problem 9]

A 4-sided tetrahedral die (faces $1, 2, 3, 4$) is rolled repeatedly, and outcomes are summed. The game stops the instant the running total becomes a multiple of 4. Given that the game ended in $\le 3$ rolls, find the conditional probability that it terminated on roll 2.

💡 Yul Cho’s Insight: In each non-terminating roll, the outcome modulo 4 must avoid 0. Each roll has 4 equally likely outcomes ($p = 1/4$). Calculate the path counts ending on roll 1 (1 path), roll 2 (3 non-zero starts $\times$ 1 finishing die), and roll 3 ($3 \times 3 \times 1$).
👉 View Solution & Answer
Answer: $\frac{12}{37}$
[Solution]
Common base denominator of $4^3 = 64$:
• Step 1 termination: Roll 4 on roll 1 $\implies \frac{1}{4} = \frac{16}{64}$
• Step 2 termination: Roll $1 \in \{1, 2, 3\}$ (3 ways), Roll 2 uniquely hits multiple of 4 (1 way) $\implies 3 \times 1 \times 4 = \frac{12}{64}$
• Step 3 termination: Roll 1 non-zero (3 ways), Roll 2 avoids $0 \pmod 4$ (3 ways), Roll 3 hits multiple of 4 (1 way) $\implies 3 \times 3 \times 1 = \frac{9}{64}$
Total weight: $16 + 12 + 9 = 37$.
Numerator (step 2): 12.
Probability: $\frac{12}{37}$.
[Challenge Variant 9]

A standard 6-sided die is rolled, and values are accumulated until the sum is a multiple of 3, with at most 3 rolls permitted. Find the conditional probability that the game terminated on roll 2.

👉 View Solution & Answer
Answer: $\frac{6}{19}$
[Solution]
Each modulo class $\{0, 1, 2\} \pmod 3$ has probability $\frac{1}{3}$.
• 1 roll: $1/3 = 9/27$
• 2 rolls: $(2/3)(1/3) = 6/27$
• 3 rolls: $(2/3)(2/3)(1/3) = 4/27$
Sum: $9 + 6 + 4 = 19$. Numerator: 6. Probability: $\frac{6}{19}$.
TYPE 10 Principle of Inclusion-Exclusion Across Three Path Events
[Model Problem 10]

A coin is flipped 6 times (heads $(+1, 0)$, tails $(0, +1)$) starting at $(0, 0)$, ending at $(x, y)$. Define events:
• $A: x \ge 4$
• $B: y \ge 4$
• $C$: the particle visits $(2, 2)$ during its journey.
Given that $A \cup B$ occurred, find the conditional probability $P(C \mid A \cup B)$.

💡 Yul Cho’s Insight: Since $x + y = 6$, $x \ge 4$ implies $y \le 2$, and $y \ge 4$ implies $x \le 2$. Thus, $A$ and $B$ are disjoint ($A \cap B = \emptyset$). The denominator is simply $n(A) + n(B)$. Then calculate paths traversing through $(2, 2)$ into each disjoint sector.
👉 View Solution & Answer
Answer: $\frac{3}{11}$
[Solution]
1) $A \cap B = \emptyset$.
• $n(A) = \binom{6}{4} + \binom{6}{5} + \binom{6}{6} = 15 + 6 + 1 = 22$.
• $n(B) = 22$ by symmetry.
Denominator: $n(A \cup B) = 22 + 22 = 44$.
2) Reaching $(2, 2)$: $\binom{4}{2} = 6$ paths.
From $(2, 2)$ to $A$ ($x \ge 4$): both remaining steps must be heads $\implies 1$ way ($6 \times 1 = 6$).
From $(2, 2)$ to $B$ ($y \ge 4$): both remaining steps must be tails $\implies 1$ way ($6 \times 1 = 6$).
Numerator: $6 + 6 = 12$.
Conditional probability: $\frac{12}{44} = \frac{3}{11}$.
[Challenge Variant 10]

A coin is flipped 6 times to reach $(x, y)$. Given that $x \ge 3$ and $y \ge 1$, find the conditional probability that the particle was at $(1, 1)$ after step 2.

👉 View Solution & Answer
Answer: $\frac{18}{41}$
[Solution]
$x + y = 6$, $x \in \{3, 4, 5\}$ (since $y \ge 1$, $x=6$ is excluded).
Denominator: $\binom{6}{3} + \binom{6}{4} + \binom{6}{5} = 20 + 15 + 6 = 41$.
Passing through $(1, 1)$: $\binom{2}{1} = 2$ ways.
From $(1, 1)$, need $\ge 2$ additional heads in 4 steps (excluding 4 heads which makes $y=0$): $\binom{4}{2} + \binom{4}{3} = 6 + 4 = 10$ paths $\implies 2 \times 9 = 18$ valid configurations.
Probability: $\frac{18}{41}$.

✍️

Yul Cho's Closing Note on Conditional Probability & Random Walks

Advanced probability questions do not test rote formula memorization; they evaluate your ability to simplify complex multivariable conditions into clear state descriptions and collapsed sample spaces.

Instead of expanding entire fraction towers, isolate the branches constrained by the condition and re-weight them using integer path ratios.
"The speed and clarity of solving conditional probability hinge entirely on how decisively you compress the universe."

Master these 10 core structures, and multi-stage probability problems will become systematic and intuitive.

Comments

Popular posts from this blog

Authentic Reference Models Beyond Basic Rulers

[Math Column]Studying Alongside Dedicated Peers: Becoming Each Other’s Lifelong Catalyst

[High School Math] Coordinate Geometry: 15 Essential Practice Problems on Section Formulas (Internal & External Division)