A box contains n white and m black balls (m< n). All balls…

A box contains $n$ white and $m$ black balls ($m\lt n$). All balls are drawn one by one without replacement. Let $M(k)$ be the number of black balls and $N(k)$ the number of white balls among the first $k$ drawn. Find the probability $p$ that $M(k)\lt N(k)$ for every $k=1,2,\dots,n+m$.

Explanation of Method

Record the order of colours as a path: a step up for each white ball, a step down for each black ball. All $\binom{n+m}{n}$ colour sequences are equally likely. The condition says the path stays strictly above zero. The first step must go up; after that, we count the paths that touch zero using the reflection principle: reflecting the part of the path before the first touch turns every "bad" path into a path starting from $-1$, and these are easy to count. Subtracting gives the famous ballot theorem: $p=\frac{n-m}{n+m}$.

Step 1: The outcomes

Only the order of colours matters. A colour sequence is determined by the positions of the $n$ white balls among the $n+m$ draws, so there are

\[ \binom{n+m}{n} \]

equally likely sequences (every order of the actual balls is equally likely, and each colour sequence corresponds to the same number $n!\,m!$ of orders).

Step 2: Sequences as paths

Draw a path starting at height $0$: go up by $1$ for a white ball, down by $1$ for a black ball. After $k$ draws the height is $N(k)-M(k)$. The path ends at height $n-m\gt0$.

$0$ W W B W B W number of draws $k$

height after $k$ draws $=N(k)-M(k)$
the path must never touch the dashed line $0$

The draws W, W, B, W, B, W ($n=4$, $m=2$) as a path: up for white, down for black. The condition $M(k)\lt N(k)$ for all $k$ means the path stays strictly above $0$.

The condition "$M(k)\lt N(k)$ for every $k$" means: the path stays strictly above $0$ after the start.

Step 3: The first ball must be white

If the first ball is black, $M(1)=1\gt0=N(1)$. So a good path starts with a step up to height $1$. From there it has $n+m-1$ steps left ($n-1$ up, $m$ down), ends at $n-m$, and must never touch $0$. The number of all paths from height $1$ with these steps is

\[ \binom{n+m-1}{n-1}. \]

Step 4: The reflection principle — counting bad paths

Take a bad path: it starts at height $1$ and touches $0$ somewhere. Reflect the part of the path before its first touch of $0$ (flip up and down steps). The reflected path starts at $-1$ and ends at the same point $n-m$. Conversely, every path from $-1$ to $n-m$ must cross $0$, and reflecting back its part before the first touch gives a bad path. So

\[ \#\{\text{bad paths}\} = \#\{\text{paths from } -1 \text{ to } n-m \text{ in } n+m-1 \text{ steps}\}. \]

A path from $-1$ to $n-m$ rises by $n-m+1$, so with $u$ up and $d$ down steps: $u-d=n-m+1$, $u+d=n+m-1$, giving $u=n$, $d=m-1$. Their number is $\binom{n+m-1}{n}$.

Step 5: Count the good paths

\[ \#\text{good} = \binom{n+m-1}{n-1} - \binom{n+m-1}{n}. \]

Using $\binom{n+m-1}{n-1} = \frac{n}{n+m}\binom{n+m}{n}$ and $\binom{n+m-1}{n} = \frac{m}{n+m}\binom{n+m}{n}$:

\[ \#\text{good} = \frac{n-m}{n+m}\binom{n+m}{n}. \]

Step 6: The probability

\[ \boxed{p = \frac{\#\text{good}}{\binom{n+m}{n}} = \frac{n-m}{n+m}.} \]

Step 7: Check with a small case

$n=3$, $m=1$: the $4$ sequences are BWWW, WBWW, WWBW, WWWB. The first two fail (at $k=1$ or $k=2$ the counts are not in favour of white: WB gives $1=1$). The good ones are WWBW and WWWB: $p=2/4=\tfrac12$, and $\frac{3-1}{3+1}=\frac12$. ✓

Step 8: Why the name "ballot problem"

In an election candidate A gets $n$ votes and candidate B gets $m\lt n$ votes. If the ballots are counted in random order, the probability that A is strictly ahead during the whole count is $\frac{n-m}{n+m}$ (Bertrand, 1887). Example: $60$ to $40$ gives $p = 20/100 = 0.2$.

Result

	Answer
Good sequences	$\binom{n+m-1}{n-1}-\binom{n+m-1}{n}=\frac{n-m}{n+m}\binom{n+m}{n}$
Probability	$p=\dfrac{n-m}{n+m}$ (ballot theorem)