Ballot Box Probability

A fun, geometric probability problem from Futility Closet that attributes it to W. A. Whitworth, but it is known as Bertrand's ballot problem after J. Bertrand who 'discovered' it eight years later. Yet another example of Stigler's law of eponymy: "No scientific discovery is named after its original discoverer," which, of course, was discovered by another: Robert K. Merton. The problem as explained by Futility Closet:

In 1878 W. A. Whitworth imagined an election between two candidates. A receives m votes, B receives n votes, and A wins (m>n). If the ballots are cast one at a time, what is the probability that A will lead throughout the voting?

The answer, it turns out, is given by the pleasingly simple formula

Howard Grossman offered the proof above in 1946. We start at O, where no votes have been cast. Each vote for A moves us one point east and each vote for B moves us one point north until we arrive at E, the final count, (m, n). If A is to lead throughout the contest, then our path must steer consistently east of the diagonal line OD, which represents a tie score. Any path that starts by going north, through (0,1), must cut OD on its way to E.

If any path does touch OD, let it be at C. The group of such paths can be paired off as p and q, reflections of each other in the line OD that meet at C and continue on a common track to E. This means that the total number of paths that touch OD is twice the number of paths p that start their journey to E by going north. Now, the first segment of any path might be up to m units east or up to n units north, so the proportion of paths that start by going north is n/(m + n), and twice this number is 2n/(m + n). The complementary probability — the probability of a path not touching OD — is (m – n)/(m + n).

(It’s interesting to consider what this means. If m = 2n then p = 1/3 — even if A receives twice as many votes as B, it’s still twice as likely that B ties him at some point as that A leads throughout.)

The technical tool of pairing of reflections is an important technique for computing first return probabilities in the theory of random walks. It is sometimes known as André's Reflection Principle but as shown in this 2008 paper by Marc Renault, although Andre did solve the ballot problem, he used no geometric arguments. This reflection technique can be used to derive the distribution of the Kolmogorov-Smirnov goodness of fit statistic for the difference between two cumulative empirical distribution functions.

More Cumulative Distribution Tabs

This is a recent post from Shorpy.com, a blog of vintage photographs. This image from 1933 shows a woman deftly gluing alphabet tabs on, what appears to be, a dictionary. We've seen earlier how such tabs represent the cumulative distribution function of the first letter of the words in English. The close-up below show the dictionary to the woman's left. The tabs for letter groups run from Z to A from left to right. For our use, we flip it over allowing the alphabet to run properly from A to Z.
The tabs then show relatively few English words beginning with the last letters of the alphabet.

When flipped over, we can see the tabs form cumulative distribution function just as the printed pages showed in our earlier post. More details on these cumulative distribution images can be found in my paper available here.

Law of Large Crowds (Monty Pythony)

A NOVA video about the Wisdom of Crowds. In his paper "Vox Populi" published in Nature, March 7, 1907, Sir Francis Galton investigated this wisdom at a Fat Stock and Poultry Exhibition writing:

In these democratic days, any investigation into the trustworthiness and peculiarities of popular judgments is of interest. The material about to be discussed refers to a small matter, but is much to the point. A weight-judging competition was carried on at the annual show of the West of England Fat Stock and Poultry Exhibition recently held at Plymouth. A fat ox having been selected, competitors bought stamped and numbered cards, for 6d. each, on which to inscribe their respective names, addresses, and estimates of what the ox would weigh after it had been slaughtered and "dressed." Those who guessed most successfully received prizes.

Galton received the 787 cards with the estimates and, then he tabulated results. The actual "dressed" weight of the ox was 1198 lbs. The median of the crowd's guesses was 1207 lbs., so the crowd was off by only 9 pounds out of 1198 or less than 0.8%. This was better than any individual guess, even from the experts. Galton also found the upper quartile (q3) of the guesses to be 1236 and the lower quartile (q1) to be 1162. Thus the inter-quartile range is 74. He modeled the data with a normal distribution and estimated its standard deviation as 1/2 of this inter-quartile range or 37, (he calls this the probable error, p.e.). We could be a bit more accurate by using 3/4 of the inter-quartile range. He notes the skewness of the distribution of guesses, with the lower portion best modeled with a normal distribution with a standard deviation of 45 and the upper portion best modeled with a standard deviation of 29. He graphs horizontally the cumulative distribution function of the fitted normal (solid line) along with the cumulative relative frequencies of the data (dotted line).

His overall finding:

This result is, I think, more creditable to the trust-worthiness of a democratic judgment than might have been expected.

Curve of the fruit length of Oenothera lamarckiana

From the blog Scientific Illustration and Eyeball Mansion showing curves emphasizing the size (length) distribution of the Evening-Primrose (Oenothera lamarckiana). Drawing by botanist and geneticist Hugo de Vries. The top view is a cumulative distribution function flipped by ninety degrees (called by NIST the percent point function). The bottom view shows a larger sketched bell-shaped curve that is just a multiple of the smaller.

Cumulative Distribution Tabs

The image above shows a cumulative distribution function that can be seen and understood with relative ease. This is a side view of the pages of the paperback version of the Oxford Advanced Learners’ Dictionary. Small colored squares for each letter are shown on the edge of each page. These colored squares act as tabs running from the top of the page for letters early in the alphabet to the bottom of the page for those letters that come later. These printed alphabetical marks on the edges of the pages help speed the look up of words and their definitions. This is really one of the first search engines.

When the dictionary is placed on its side, these colored tabs produce a cumulative distribution function for words from the English language. We have a visual and understandable image of a cumulative distribution function. We can quantify this by noting, for example, that 93 pages of this dictionary are devoted to the letter "A", so 93 pages have tabs colored to act as guide tabs to words starting with "A". The last page number of each letter’s tab indicates the number of pages devoted to words that begin with letters occurring, in alphabetical order, before that tab. Let G(x) denote the page number of this last page for each letter x in the set {A,B,C,…,Z}. These are the cumulative counts of pages for words beginning with each letter in the English alphabet. The maximum of G(x), call it M, is just the number of the last page of the dictionary for the letter "Z". Define F(x) to be G(x)/M. Then F(x) represents the cumulative relative frequency of letters of the alphabet. This is the alphabet’s cdf. Learn more from my paper "A Photographic View of Cumulative Distribution Functions" in the Journal of Statistics Education.