Mastering Conditional Probability & Random Walks: 10 Competition-Level Problem Types for Advanced Combinatorics
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.
- Boundary & Absorbing Barrier Inversion: When a path stops upon first arrival at a coordinate, enforce non-absorption conditions strictly on earlier steps.
- Weight Ratio Reduction: If branches share equal power factors, eliminate the common denominator and evaluate the probability using integer weight ratios.
- 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
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.
👉 View Solution & Answer
[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}$.
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
[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}$.
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.
👉 View Solution & Answer
[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}$).
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
[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}$.
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.
👉 View Solution & Answer
[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).
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
[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}$.
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.
👉 View Solution & Answer
[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}$.
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
[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}$.
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.
👉 View Solution & Answer
[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}$.
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
[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.
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.
👉 View Solution & Answer
[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}$.
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
[Solution]
Construct the 3-round sequence tracking coin and die activations based on positive vs non-positive status at each intermediate node.
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.
👉 View Solution & Answer
[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.
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
[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}$.
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$.
👉 View Solution & Answer
[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.
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
[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.
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.
👉 View Solution & Answer
[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}$.
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
[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}$.
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)$.
👉 View Solution & Answer
[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}$.
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
[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
Post a Comment