Andrew's Blog     All posts     Feed     About


Quote: Maud Ray Kent

Paraphrasing from Macrae’s biography of J. von Neumann:

In 1940 the Germans captured Denmark plus Niels Bohr. A cable arrived in Britain from Otto Frisch’s aunt in Sweden saying, “Met Niels and [wife] Margarethe recently. Both well but unhappy about events. Please inform Cockroft [British nuclear scientist] and Maud Ray Kent”.

Who or what was “Maud Ray Kent”? The British decided it was an anagram for “radyum taken” and thus gave warning that the Germans were moving fast to develop an A-bomb. Perhaps that was the reason the Nazis had occupied Bohr’s Copenhagen, and were capturing Norway and its heavy water too? Someone suggested that Maud might actually stand for “Military Application: Uranium Disintegration”. The British nuclear program commenced under the name “MAUD Committee”, as a tribute to the brilliant anagram.

Down in her home in Kent, Miss Maud Ray, the English governess to Bohr’s children, remained uncontacted because nobody had heard of her.

Classic probability puzzles and their solutions

Envelope paradox

Problem: You are given two blank envelopes which each contain money. One envelope contains twice as much as the other. You may choose an envelope and keep the money it contains. After choosing, you have the option to switch for the other envelope. Should you switch?

Pitfall: Clearly there is no reason to switch (or not to switch) since the envelopes are blank and at no point do you learn anything new about their contents. However, the following argument seems to show you actually should switch. Let \(X\) be the amount of money in the envelope chosen originally. The other envelope contains an amount of either \(2X\) or \(X/2\), each with probability \(1/2\). Thus the expected value of the other envelope is

\[\frac{1}{2} (2X) + \frac{1}{2} (X/2) = \frac{5}{4} X > X.\]

…so you should switch?

Solution: Whenever things get tricky, it’s best to be as formal and methodical as possible. What do we actually mean by \(X\)? We’re taking \(X\) to be the amount of money in the envelope we choose originally. That means \(X\) is a random variable whose value depends on the random choice of the original envelope. It’s true that \(X\) is equally likely to be either the smaller or larger amount. Let these be \(x\) and \(2x\). Then we need to find the expected value of the other envelope. Let the value of the other envelope be \(X'\). Implicitly we are finding the expected value of \(X'\) by conditioning on the value of \(X\). There are two possibilities, and in each case we know what we get:

\[\begin{align*} \mathbb{E}(X') &= \mathbb{P}(X' > X)\mathbb{E}(X' | X' > X) + \mathbb{P}(X' < X)\mathbb{E}(X' | X' < X) \\ &= \frac{1}{2}\mathbb{E}(X' | X' > X) + \frac{1}{2}\mathbb{E}(X' | X' < X) \end{align*}\]

Note that depending on whether \(X' > X\) or \(X' < X\) the value of \(X\) is different. If \(X' > X\), then \(X = x\) and \(X' = 2X = 2x\), and if \(X' < X\), then \(X = 2x\) and \(X' = X/2 = x\). So,

\[\begin{align*} \frac{1}{2}\mathbb{E}(X' | X' > X) + \frac{1}{2}\mathbb{E}(X' | X' < X) &= \frac{1}{2}\mathbb{E}(X' | X'=2X) \\ &\qquad {} + \frac{1}{2}\mathbb{E}(X' | X'=X/2) \\ &= \frac{1}{2}2x + \frac{1}{2}x \\ &= \frac{3}{2}x \\ &= \mathbb{E}(X). \end{align*}\]

Comparing with the pitfall solution, the key difference is that we cannot use the same symbol \(X\) in two cases if our assumption about the value of \(X\) is different in each case. Tricky!

Monty Hall problem

Problem: In the TV game show Let’s Make a Deal, you get to win a prize by opening one of three doors. Behind one door is a car and behind the others are goats. You pick a door, say #1, and without opening #1 the host Monty Hall intentionally shows you that a goat is behind another door, say #3, and gives you the chance to change to #2. Should you change doors?

Pitfall: You have the choice between two doors, one with a car, the other with a goat. Reasoning by symmetry, the probability of each configuration is \(1/2\), so there is no point switching.

Solution: It’s true that we know there are two possible configurations at this point, but that’s not all we know. We also know that #2 was not a door chosen by Monty as a door with a goat. This gives us an extra clue that #2 might have the car.

Again, the best way to deal with tricky problems is being as rigorous as possible. Let’s explicitly set up a probability model as follows. Let \(C \in \{1,2,3\}\) be the random variable for the door with the car. Let \(S_3\) be the event that Monty chooses #3 to show a goat. Then we can write down the following conditional probabilities.

\[\begin{align*} \mathbb{P}(S_3|C=1)&=\frac{1}{2} \\ \mathbb{P}(S_3|C=2)&=1 \\ \mathbb{P}(S_3|C=3)&=0. \end{align*}\]

These are all we need to compute \(\mathbb{P}(C=2|S_3)\), which is the probability of winning if we switch. Using Bayes’s rule, we have

\[\begin{align*} \mathbb{P}(C=2|S_3) &= \frac{\mathbb{P}(S_3|C=2)\mathbb{P}(C=2)}{\mathbb{P}(S_3)} \\ &=\frac{\mathbb{P}(S_3|C=2)\mathbb{P}(C=2)}{ \sum_{i=1}^3 \mathbb{P}(S_3|C=i)\mathbb{P}(C=i)} \\ &=\frac{\mathbb{P}(S_3|C=2)}{ \mathbb{P}(S_3|C=1)+\mathbb{P}(S_3|C=2)+\mathbb{P}(S_3|C=3)} \\ &=\frac{1}{\frac12+1+0} =\frac23 > \frac{1}{2}. \end{align*}\]

Feminist bank teller question

Problem: Linda is 31 years old, single, outspoken, and very bright. She majored in philosophy. As a student, she was deeply concerned with issues of discrimination and social justice, and also participated in anti-nuclear demonstrations.

Which is more probable?

  1. Linda is a bank teller.
  2. Linda is a bank teller and is active in the feminist movement.

Pitfall: The description makes it very plausible that Linda is active in the feminist movement, therefore #2 is more likely than #1.

Solution: This is an example of the conjunction fallacy. Let \(B\) be the event Linda is a bank teller, and let \(F\) be the event that Linda is active in the feminist movement. Then we can immediately say \(\mathbb{P}(B) \geq \mathbb{P}(F \cap B)\) since \(F \cap B \subseteq B\). And so #2 cannot be more probable than #1.

In general, if more details are added, we cannot become more confident in a claim. This goes against a bias we have to consider situations more plausible if they are specific and vivid. For more on cognitive biases and heuristics, see Thinking, Fast and Slow, but also see the mistakes in that book caused by cognitive biases and heuristics.

Base rate neglect

Problem: A certain disease affects 1 in 1000 people. A medical diagnostic test for the disease has 95% accuracy, i.e. 95% of the time it gives the correct diagnosis (whether you’re diseased or not). Suppose you take the test and it reads positive, what is the probability that you have the disease?

Pitfall: Since the diagnostic has 95% accuracy, then in my case I can conclude that the probability I have the disease is 95%.

Solution: Let \(D\) be the event I have the disease, and let \(P\) be the event I receive a positive diagnosis. We seek \(\mathbb{P}(D|P)\). Bayes’s rule gives

\[\begin{align*} \mathbb{P}(D|P) &= \frac{\mathbb{P}(P|D)\mathbb{P}(D)}{\mathbb{P}(P)} \\ &= \frac{\mathbb{P}(P|D)\mathbb{P}(D)}{\mathbb{P}(P|D)\mathbb{P}(D) + \mathbb{P}(P|\neg D)\mathbb{P}(\neg D)} \\ &= \frac{(0.95)(0.001)}{(0.95)(0.001) + (0.05)(0.999)} \\ &= 0.019 = 1.9\%. \end{align*}\]

So the probability I have the disease is actually very small, even though I got a positive test. This is another case of not using all the information we have. The 95% accuracy needs to be combined with the very low probability that anyone has the disease. Problems of this type have been given to doctors and medical students who often fail to find the solution.

Birthday paradox

Problem: In a group of 23 people, what is the probability that at least 2 of them have the same birthday?

Pitfall: The probability must be small since there are only 23 people and 365 possible birthdays.

Solution: Let \(N\) be the event no 2 people have the same birthday. The total number of assignments from people to birthdays is \(365^{23}\). The total number of assignments from people to birthdays with no repeats is \(365 \cdot 364 \cdot \,\cdots\, \cdot 343\) since there are 365 possibilities for the first person’s birthday, which leaves 364 possibilities for the next, and so on. But

\[\mathbb{P}(N) = \frac{365^{23}}{365 \cdot 364 \cdot\, \cdots\, \cdot 343} = 0.492703.\]

Then the probability that 2 people share a birthday is \(1-0.492703=0.507297\). So the probability isn’t small; in fact it’s greater than \(1/2\)! It’s true that any given pair of people are unlikely to share a birthday, but as the size of the group grows, the probability that all pairs do not share a birthday becomes small. There are \(\binom{23}{2} = 253\) different pairs of people in a group of 23.

What's the probability of the Riemann Hypothesis?

Usually when we talk about probabilities, we have certain given information, which takes the form of a \(\sigma\)-algebra of possible events, and there is also a probability function that assigns values to each event. The rationality of a probability function is judged based on the relationships between events. For example if \(A \subseteq B\) then we must have \(P(A) \leq P(B)\). But as long as these relationships are satisfied (giving a proper probability measure), the probabilities could be anything. As such, we do not judge subjective probabilities based on whether they’re actually accurate or not, just whether they are consistent with each other.

Now, imagine if information isn’t the limiting factor in our uncertainty, but rather it’s our lack of mathematical knowledge. A statement like the Riemann Hypothesis (RH) is unknown even though it is entirely determined by the axiom system we use, leaving aside issues of completeness. Here there’s no given \(\sigma\)-algebra and in fact the relationships between RH and other statements may themselves be difficult to determine.

A more realistic view is that we have limited computational resources, we want to solve an intractible problem, and we’ll settle for the best approximation we can get. Thus a probability function is seen as a kind of approximation algorithm. With this algorithmic language, however, we aren’t able to give a very good answer for single propositions like RH. If RH is the entire set of inputs, the optimal approximation is the exact truth value, because it takes a trivial amount of computational resources to output the constant 1 or 0. If the set of inputs is infinite, then the particular input corresponding to RH makes no difference in an asymptotic analysis. For more elaboration on this theme, see this paper.

In traditional Bayesianism there is a seemingly ineradicable source of subjectivity from the choice of prefix Turing machine used to define Solomonoff’s prior. Any one input can be assigned a wide range of probabilities. Perhaps we are left with an analogous but different kind of subjectivity for mathematical probabilities.

Andrew Critch (Above: Andrew Critch thinking about this in Berkeley.)

The Fundamental Theorem of Asset Pricing is Bayesianism

If uncertainties encode bet preferences as represented by probabilities, Bayesianism is a collection of Dutch book arguments proving that probabilities must be consistent with each other (defining a probability measure) to be rational. Weisberg has an excellent paper that explains the details. On the other hand, the Fundamental Theorem of Asset Pricing proves that for prices to be arbitrage-free, they must be conditional expectations. Details on the relevant results are found in “The Mathematics of Arbitrage”, by Delbaen and Schachermayer. Having a consistent probability function has been shown to be equivalent to minimizing a proper scoring rule. And conditional expectations have been shown to minimize Bregman divergences. Et cetera. The correspondance between these theories is alluded to by Nau.

Data from Canadian 700MHz and 2500MHz spectrum auctions

The 700MHz (2014) and 2500MHz (2015) spectrum auctions generated revenues of 5,270,636,002 CAD from 302 licenses and 755,371,001 CAD from 97 licenses. Both auctions used a combinatorial clock auction (CCA) format involving an ascending clock phase followed by a sealed-bid supplementary stage where bids could be made on packages of products. Final prices were determined using Vickrey pricing with a core-adjustment. An activity rule was used which required bidders to make bids or lose eligibility to bid in later clock rounds, along with a revealed preference rule which allows the eligibility limit to be exceeded as long as consistency checks are satisfied. For full details on the auction formats see the official documentation (700MHz rules, 700MHz additional details, 2500MHz rules); and the record of bids placed is here for 700MHz and here for 2500MHz.

Bid consistency

The revealed preference rule prevents some inconsistent behavior but not all. By “truthful”, we mean bids that are true indications of subjective value, and by “consistent” we mean bids that are indications of some fixed set of valuations, possibly not the bidder’s actual valuations.

The following table gives the values of Afriat’s critical cost efficiency index (CCEI) for the 700MHz auction. Recall that for a CCEI value \(x\), if \(x < 1\) there is at least some intransitivity in preferences (i.e. inconsistent bidding) and \(1-x\) can be interpreted as the fraction of expenditure wasted making inefficient choices (see this by S. Kariv for more).

Bidder CCEI (clock rounds) CCEI (clock and supp. rounds)
Bell 0.930 0.417
Bragg 0.880 0.420
Feenix 1 1
MTS 0.996 0.627
Novus 1 1
Rogers 0.998 0.742
SaskTel 1 1
TBayTel 1 1
Telus 0.970 0.488
Videotron 0.879 0.560

Kroemer et al. conclude for the 700MHz auction, “the numbers suggest that bidders deviated substantially from straightforward bidding” in the clock rounds. But “it is not unreasonable to believe that bidders tried to bid up to their true valuation in the supplementary stage” because of higher bid amounts compared to the clock rounds.

The next table gives CCEI values for the 2500MHz auction. We extend the definition of CCEI to apply to supplementary bids as in Kroemer’s paper.

Bidder CCEI (clock rounds) CCEI (clock and supp. rounds)
Bell 0.913 0.712
Bragg 0.920 0.530
Corridor 1 1
MTS 1 1
Rogers 1 1
SSi Micro 1 1
TBayTel 1 1
Telus 0.997 0.996
Videotron 1 1
WIND 1 1
Xplornet 1 0.578

Kroemer et al. (Sec. 5.2) also point out that the total number of bids submitted in the 700MHz auction was much smaller than the number of possible bids, which probably indicates untruthful bidding since an omitted package must have valuation less than or equal to its (low) opening price. The same observation holds for the 2500MHz auction. More exactly, the auction formats enforced a limit on the number of packages bidders were allowed to submit, which was in the hundreds, and bidders generally did not reach the limit.

Ideally, we would determine whether the bids made are consistent with a non-truthful strategy incorporating gaming and/or coordination. The papers Janssen and Karamychev - “Raising Rivals’ Cost in Multi-unit Auctions” and Janssen and Kasberger - “On the Clock of the Combinatorial Auction” derive Bayesian Nash equilibria under gaming preferences and conclude that GARP is not violated in equilibrium gaming strategies. We note that the assumptions in these game models do not include all features of the CCAs under consideration e.g. discrete products, many bidders, public aggregate excess demand, revealed preference rule, initial EP limit, supplementary package limit, 50% mid-auction deposits.

Bids, budgets, and final prices

Bidders may have a notion of a budget – the maximum they are willing to spend. But how should this correspond to the maximum they should bid? In general, bidders may end up paying the exact amount of their highest bid, but looking at the data we see bid prices and final prices can be very different in practice. The following tables show figures from both auctions that illustrate this difference. All prices are given in CAD.

700MHz auction: highest bid placed. Average ratio: 0.192. Max ratio: 0.766.

Bidder Max bid (\(M\)) Allocation stage final price (\(p\)) Ratio (\(p/M\)) Final clock bid
Bell 3,999,999,000 565,705,517 0.141 1,366,867,000
Bragg 141,894,000 20,298,000 0.143 38,814,000
Feenix 60,650,000 284,000 0.005 346,000
MTS 73,067,000 8,772,072 0.120 10,853,000
Novus 112,359,000 0 0 0
Rogers 4,299,949,000 3,291,738,000 0.766 3,931,268,000
Sasktel 75,000,000 7,556,929 0.101 11,927,000
TbayTel 7,683,000 0 0 0
Telus 3,750,000,000 1,142,953,484 0.305 1,313,035,000
Videotron 677,524,000 233,328,000 0.344 468,530,000


700MHz auction: (highest) bid placed on package eventually won. Average ratio: 0.447. Max ratio: 0.766.

Bidder Max bid on won package (\(W\)) Allocation stage final price (\(p\)) Ratio (\(p/W\)) Allocation stage Vickrey price
Bell 2,583,868,000 565,705,517 0.219 565,705,000
Bragg 51,000,000 20,298,000 0.398 20,298,000
Feenix 425,000 284,000 0.668 284,000
MTS 40,000,000 8,772,072 0.219 3,198,000
Novus N/A 0 N/A 0
Rogers 4,299,949,000 3,291,738,000 0.766 3,291,738,000
Sasktel 62,400,000 7,556,929 0.121 2,755,000
TbayTel N/A 0 N/A 0
Telus 1,607,300,000 1,142,953,484 0.711 1,142,953,000
Videotron 490,000,000 233,328,000 0.476 233,328,000


2500MHz auction: highest bid placed. Average ratio: 0.135. Max ratio: 0.277.

Bidder Max bid (\(M\)) Allocation stage final price (\(p\)) Ratio (\(p/M\)) Final clock bid
Bell 542,746,000 28,730,000 0.053 76,214,000
Bragg 35,935,000 4,821,021 0.134 12,091,000
Corridor 9,300,000 2,299,000 0.247 N/A
MTS 13,609,000 2,242,000 0.165 2,609,000
Rogers 304,109,000 24,049,546 0.079 52,343,000
SSi Micro 851,000 0 0 0
TBayTel 12,001,000 1,731,000 0.144 1,731,000
Telus 1,771,723,000 478,819,000 0.270 1,038,472,000
Videotron 749,128,000 66,552,980 0.089 231,851,000
WIND 22,609,000 0 0 0
Xplornet 91,974,000 25,472,454 0.277 57,839,000


2500MHz auction: (highest) bid placed on package eventually won. Average ratio: 0.235. Max ratio: 0.410.

Bidder Max bid on won package (\(W\)) Allocation stage final price (\(p\)) Ratio (\(p/W\)) Allocation stage Vickrey price
Bell 536,563,000 28,730,000 0.054 28,730,000
Bragg 19,000,000 4,821,021 0.254 3,536,000
Corridor 6,440,000 2,299,000 0.357 2,299,000
MTS 11,000,000 2,242,000 0.204 2,242,000
Rogers OR 24,049,546 N/A 21,252,000
SSi Micro N/A 0 N/A 0
TBayTel 12,001,000 1,731,000 0.144 1,731,000
Telus 1,771,723,000 478,819,000 0.270 478,819,000
Videotron 358,477,000 66,552,980 0.186 61,092,000
WIND N/A 0 N/A 0
Xplornet 62,200,000 25,472,454 0.410 22,917,000

Across both auctions, we see that bidders paid an average of 16% of their maximum bid placed, where each bidder is equally weighted.

Misc. notes

Researchers design approximation algorithms for winner and price determination in auctions (in e.g. this paper) because exact optimization can be intractable as the number of bids grows, at least in the worst case. However, in these recent auction instances, theoretical intractability did not present a problem because the solution was computable in a small amount of time. The 2500MHz allocation stage involved 2,239 bids and a GLPK-powered solver finds the winners and final prices in a couple minutes on a standard computer. Simulations involving well over 30,000 random bids still take a feasible amount of time.

In the 2500MHz auction, there were 4 pairs of package submissions where the lower-priced package had strictly higher quantities of products. In this case the lower-priced package is superfluous. This table shows the packages, submitted by Bell.

  Price of larger package (CAD) Price of smaller package (CAD) Number of products difference
1 535,917,000 536,214,000 3
2 536,628,000 536,645,000 3
3 536,401,000 536,545,000 3
4 536,434,000 536,563,000 3

Acknowledgement: Thanks to Z. Gao for pointers.

Link of the day: Journal of Craptology

http://www.anagram.com/jcrap/


The prestigious Journal of Craptology is an open-access publication in the area of cryptology.