The Inconvenience of a Law
12.1 THE PROBLEM
In this problem we return to the undocumented resident issue I sketched in the opening of the preface. As you’ll recall, there we developed the following mathematical situation, starting with an urn initially containing b black balls and r red balls. We randomly draw one ball at a time; if it’s black we put it back in the urn, and if it’s red we discard it. We keep doing this until we’ve removed a fraction f of the red balls. We are interested in how many times, on average, each black ball will be drawn before the process terminates. In particular, we are interested in this average number for the cases of f = 0.5, 0.9, and 0.99. Whenever it helps, we’ll use the fact that in America, b is in the hundreds of millions and, while r is smaller, it is still in the millions, too (as I write in December 2011, b and r are about 312 million legal residents and 10 to 15 million undocumented residents, respectively).
12.2 THEORETICAL ANALYSIS
To start, let me remind you of a result we derived in Problem 4, concerning the average number μ of attempts until the first S in a random sequence of S’s and F’s, where p is the probability of an S: μ = 1/p. If we consider drawing a red ball to be an S, then when we start our ball-drawing process we have
and so the average number of drawings until we get the first red ball is
Once that first red ball has been drawn (and discarded), we then have an urn with b black balls and r − 1 red balls, and so the average number of additional drawings until we get the second red ball is 1 + b/(r − 1). We can continue to argue this way until we have reduced the number of red balls to (1 − f)r; to get that final red ball will, on average, require 1 + b/(r − rf) more drawings. (Since both r and b are large numbers we are not going to worry too much about the slight error made in using rf in place of rf + n, where n is a small integer.)
The total number, T, of drawings we make, on average, in reducing the number of red balls from r to r − rf is
where the number of terms in the sum is ≈ rf. Thus,
The average number of times each black ball will be drawn during this reduction process is T/b, and so a formal answer to our question is
where I’ve dropped the (r/b)f term, since (r/b)f Ü 1.
This is a correct answer, but most people would also find it unsatisfying, too; at the least, it represents a lot of numerical work because the partial sums of the harmonic series increase very slowly. Fortunately, with just a bit more work we can get it into a much nicer form.
To a very good approximation, it has been known since the Swiss-born mathematics genius Euler wrote it (in 1781) that, for n ≥ 1,
where γ = 0.577215664 … is Euler’s constant. Even for the very first case of n = 1, the error made by the expression on the right is less than 8%, and it gets even smaller as n increases. Now,
where the first equality follows from the observation that the first two sums on the left are the same, term by term, with the second sum simply the first one in reverse order. So, using Euler’s approximation on the last two sums on the right, we have
Since 1/2r Ü 1, as is 1/2(r − rf), then
This form for the average number of times each black ball is drawn during the process of reducing the number of red balls from r to r − rf is easy to calculate! Notice carefully that there is no dependency on the values of either b or r. This is, I think, totally unexpected. For the values of f = 0.5, 0.9, and 0.99, the average number of times each black ball is drawn is 0.69, 2.3, and 4.6, respectively. Whether or not any of these numbers is “acceptable” in the context of police stopping people at random to find undocumented residents is not a question that can be answered by our analysis. Math gives us the numbers, but people have to make the decision.