Question

An urn contains \(n\) white and \(m\) black balls that are removed one at a time. If \(n>m\), show that the probability that there are always more white than black balls in the urn (until, of course, the urn is empty) equals ( \(n-m) /(n+m)\). Explain why this probability is equal to the probability that the set of withdrawn balls always contains more white than black balls. (This latter probability is \((n-m) /(n+m)\) by the ballot problem.)

Short answer

We can use the reflection principle from the ballot problem to demonstrate that the probability of always having more white than black balls in an urn with $n$ white and $m$ black balls is equal to \(\frac{n-m}{n+m}\). By adding an extra white ball and translating the urn problem to the ballot problem context, we find that the probability of Alice's votes always exceeding Bob's is also \(\frac{n-m}{n+m}\). The probabilities are equal because both problems involve maintaining a greater count of one type over the other, and the ratio of favorable outcomes to total outcomes is the same in each situation.

Step-by-step solution

Set up the problem

We have an urn containing n white balls and m black balls. We are removing them one by one without replacement. Our goal is to show that the probability of always having more white than black balls left in the urn is equal to (n-m)/(n+m).

Determine the total number of ways to remove balls

There are a total of (n + m) balls in the urn. Since we are removing them one by one, there are (n + m)!/(n!m!) ways to remove the balls.

Count the number of favorable outcomes

Now we must count the number of ways to remove the balls such that there are always more white than black balls left in the urn. We can apply the reflection principle from the ballot problem: If at any stage there are an equal number of white and black balls in the urn, then the sequence of removals from that point onward must be the same as if we had one more white ball and one less black ball initially. Thus, imagine adding an extra white ball to the urn. Now there are n+1 white balls and m black balls, and the desired condition is that there are always more white than black balls in the urn, even when the extra white ball is taken into account. This is exactly the ballot problem.

Apply the ballot problem solution

In the ballot problem context, Alice wins n votes and Bob wins m votes. The probability Alice always has more votes than Bob is (n-m)/(n+m). Translating it back to our urn problem, we see that the probability there are always more white balls than black balls in the urn is also (n-m)/(n+m).

Explain why the probabilities are equal

The probabilities are equal since both problems have the same core idea of keeping a more significant count of one type over the other. In the urn problem, we want the number of white balls to always exceed the black balls. In the set of withdrawn balls, we want the number of white balls to always exceed the black balls as well. Both probabilities represent the ratio of favorable outcomes to the total number of outcomes, which gives insight into why they are equal.

Key concepts

Ballot Problem

The Ballot Problem is a fascinating topic in probability that deals with counting and the logistics of sequences. Let's illustrate it with an example: imagine an election between two candidates, Alice who receives n votes and Bob who receives m votes, with Alice receiving more votes than Bob. The problem asks: what is the probability that throughout the count of votes, Alice always remains ahead of Bob?

The solution involves some clever combinatorial reasoning, specifically using the reflection principle, which we'll explore more in a moment. To answer our question, if Alice wins by n-m votes, the probability that Alice is always ahead is given by the ratio (n-m)/(n+m). This encapsulates the principle of maintaining a lead throughout sequential events, which is directly applicable to other scenarios, such as our urn problem involving white and black balls.

Combinatorics

Combinatorics is the branch of mathematics focused on counting, arrangement, and combination of sets of elements. It plays a vital role in probability as it helps us enumerate possible outcomes and calculate probabilities. For example, in our urn problem, there are n+m balls in total, representing a combination of white and black balls. The number of ways to remove all the balls one at a time is given by the factorial formula (n + m)!/(n!m!), where ! denotes factorial, the product of an integer and all the integers below it down to 1.

• n! represents the number of ways to arrange n white balls.
• m! represents the number of ways to arrange m black balls.
• (n+m)! accounts for the total arrangements of all balls.

This formula from combinatorics enables us to understand the total number of possible sequences in which the balls can be drawn from the urn, forming the denominator in our probability calculation.

Reflection Principle

The Reflection Principle is a clever method used in combinatorial problems to transform complicated counting scenarios into simpler ones. In the context of our urn problem, it's utilized to understand the nature of drawing sequences where one type of ball (white) is continuously more numerous than the other (black).

According to this principle, imagine a scenario where the number of white and black balls are equal at some point. Any continuation of draws from this point can be 'reflected'—as if in a mirror—to create a valid sequence with one extra white ball. This method effectively doubles the number of problematic scenarios to be subtracted from the total, leaving us with the count of sequences where whites always outnumber blacks.

The reflection principle isn't just a trick or shortcut; it's a potent tool that assures we account for all possible scenarios where the condition of 'one more white ball' is met. By applying this principle, as in our urn problem, we can precisely calculate the number of favorable outcomes and thereby determine the probability of always drawing more white balls than black ones from the urn.