Expected Runs in Sampling Without Replacement

This is the solution to the problem posed a couple weeks earlier.

The trick is to realize we can write \[ f(x|N,M) = \sum^{M}_{k=1}\frac{(M)_{k}}{(N)_{k}}x^{k} \tag{1}\] where \((M)_{k} = M(M-1)(\dots)(M-(k-1))\) is the falling factorial. This permits us to rewrite the expected length of a run as \[ \mathbb{E}[L|N,M] = \left.\frac{\mathrm{d}}{\mathrm{d}x}f(x|N,M)\right|_{x=1}. \tag{2} \] But astute readers will recognize Eq (1) is Gauss's hypergeometric function \[ f(x|N,M) = \frac{M}{N}x {}_{2}F_{1}(1, 1-M;1-N;x) \tag{3} \] which permits us to deduce \[ \mathbb{E}[L|N,M] = \frac{M(1+N)}{(1+N-M))(1+N-(M-1))} \] which is the expected run for M red balls in an urn with N balls. This assumes \(M\gt2\), otherwise we can manually compute the expected run trivially.

HOWEVER, we need to normalize the probabilities, since we are considering a slightly different experiment: we are varying the sample size \(n\) from 1 to M (as opposed to varying the portion k of the fixed sample size n balls drawn are of the specified color). That is to say, we need to divide through by \(f(1|N,M)=M/(N+1-M)\) to give us \[ \mathbb{E}[L|N,M] = \frac{(1+N)}{(1+N-(M-1))} \tag{4} \] which, if we fix \(p=M/N\) as both \(M\to\infty\) and \(N\to\infty\), recovers the geometric distribution. [The expected value is approximately \(N/(N-M) = (N - M + M)/(N - M)\) which is \(1 + (M/(N-M)) = 1 + (p/(1-p)) = 1/(1-p)\). Then use the geometric distribution with \(1-p\) for the probability of "success", so we count the number of "failures" with the geometric distribution to coincide with the length of a run in our situation.] (This is an example of a sanity check.)

I suspect there's a way to solve this puzzle elegantly without invoking hypergeometric functions, but this accidentally fell into my lap (literally).

Homework 1. What if we fix \(n\) draws from an urn, sampled without replacement. Suppose this urn contains K red balls, the remainder are white, for a total of N balls. What's the expected first run's length? I.e., if you draw a white, what's the number white balls you expect to draw until you draw a red? And if you first draw a red ball, then what's the number of red balls you expect to draw until drawing a white?

Homework 2. If we consider sampling without replacement from an urn (possibly with balls of multiple colors), then what does the distribution look like on finite sequences of runs of different colors? I.e., specifying a sample as drawing \(n_{1}\) of a color \(c_{1}\), then \(n_{2}\) of \(c_{2}\), then..., such that \(n_{1}+\dots + n_{k}=n\). What does the sample space look like? What's the probability distribution look like?

Problem 17 of Bernoulli's Ars Conjectandi

I'd like to solve Problem 17 of Bernoulli's Ars Conjectandi. I'll summarize the problem as:

A roulette wheel with 38 pockets labelled "1", ..., "8" (with 4 copies of each label), each pocket may hold at most 1 ball, and every pocket is equiprobable for a ball to land in, the player is given 4 balls. If the pocket labels are points, and the player sums the points awarded to them by the pockets the balls land in, what's the expected number of points the player may earn?

Solution

We can work out the frequencies we will find the balls producing k points.

For a single ball, it will land in a pocket labelled w with probability 4/32=1/8.

The second ball has two possibilities: it will land in a pocket also labelled w, or it will land in a pocket with a different label x. There are 31 empty pockets for the second ball to land in for both cases. But when the second ball lands in a w pocket, there are only 3 vacant w-labelled pockets (for a probability of 3/31). On the other hand, there are 4 vacant x-labelled pockets.

We can implement this in R as (similar to James Hanley's solution):

n <- rep(0,32)  # first 3 will remain 0, since points range is 4:32

for (label_1 in 1:8) {
  f1 <- 4; # 4 possibilites of a label_1
  for (label_2 in 1:8) {
    f2 <- f1 * (4 - (label_1 == label_2)); # 3 or 4 possibilities of label_2, depending...
    for (label_3 in 1:8) {
      f3 <- f2 * (4 - (label_3 == label_1) - (label_3 == label_2)); # etc
      for (label_4 in 1:8) {
        f4 <- f3 * (4 - (label_4 == label_1) -
                    (label_4 == label_2) - (label_4 == label_3));
        points <- label_1 + label_2 + label_3 + label_4
        n[points] <- n[points] + f4;
      }  
    }
  }
}

freq <- n[4:32]/24;

expected_value <- sum((4:32)*freq)/sum(freq); # = 18

In this algorithm, we need to divide through by 4! = 24 to avoid double counting. (Think of the case of getting 4 points, i.e., all four balls land in pockets with label "1": there's only one way for this to happen. We don't care how the result comes about [e.g., which ball landed in which particular pocket with label 1], we only care about the final configuration.)

Homework. Bernoulli gives us a "payoff table", rewarding the player with a number of coins depending on the points won. While computing the expected payoff amounts to sum(payoff*freq)/sum(freq), perhaps a better inverse problem is: determine what payoffs will result in the player's expected winnings to be exactly 4, such that if probability of points \(\Pr(p)\lt\Pr(p')\) the payoff \(f(p)\lt f(p')\) (or, \(f\) is monotonically decreasing on the interval [18, 32] and monotonically increasing on the interval [4, 18]).

(Historically, Bernoulli's payoff table was: 120, 100, 30, 24, 18, 10, 6, 6, 6, 5, 3, 3, 3, 2, 2, 3, 3, 3, 3, 4, 4, 6, 8, 12, 16, 24, 25, 32, 180. This is from 4 points up to 32 points.)

Lingering Puzzle

The problem people have with this worked example is, Bernoulli gives a solution for the expected winnings from his table as 4 + 349/3596 (approximately 4.09705228031). If we simulate the table with his winnings, we get a larger value (or smaller value, depending on our random number generator).

It's been a debate: has Bernoulli made a mistake? Professor E computed the expected winnings to be 4 + 153/17980 (about 4.00850945495), much lower than Bernoulli's answer.

An argument in defense of Bernoulli is, if we consider some code to generate the expected winnings:

simulate_wheel <- function(SIMS = 1000000) {
  Total <- 0
  nummi <- c(120, 100, 30, 24, 18, 10, 6, 6, 
             6, 5, 3, 3, 3, 2, 2, 3, 3, 3, 3, 
             4, 4, 6, 8, 12, 16, 24, 25, 32, 180)
  
  pocket_values = rep(1:8,4)
  
  INDICES <- 1:length(pocket_values)
  
  for(sim in 1:SIMS) {
    total_value <- sum(sample(pocket_values, 4, replace = F))
    Total <- Total + nummi[total_value-3]
  }
  
  Total/SIMS
}
simulate_wheel()

This produces a higher-than-expected amount of winnings consistently. (Your mileage may vary, depending on your random number generator.) But the expected sum of the labels for the pockets where the balls landed, we get:

simulate_wheel <- function(SIMS = 1000000) {
  Total <- 0
  
  pocket_values = rep(1:8,4)
  
  INDICES <- 1:length(pocket_values)
  
  for(sim in 1:SIMS) {
    total_value <- sum(sample(pocket_values, 4, replace = F))
    Total <- Total + total_value
  }
  
  Total/SIMS
}
simulate_wheel()

An expected 18 points, agreeing with earlier results.

Puzzle: Did Bernoulli make a mistake? Did our simulations mislead us? What's the real expected winnings according to the table given?

Homework 1. What's the expected winnings if a pocket could hold k balls (for k = 2, 3, 4)?

Runs in a sample

A puzzle to celebrate the 4th of July. This is a bit more open-ended (hence it's a "puzzle", not an "exercise"). Consider an urn, with N balls and an unknown number K of red balls (the remainder are white). We will be sampling without replacement.

First, define a run as drawing one ball after another of the same color.

Puzzle. How can we use the sample of n balls written as a sequence of runs \((k_{1},c_{1})\), ..., \((k_{m},c_{m})\) for a run of length \(k_{i}\) of color \(c_{i}\)? Are there cases where using this data would give less informative inferences than the vanilla inference? (And what's the inferred variance?)

Some exercises might make this all easier.

Exercise 1. Let B be the background information that an urn contains N balls, K of which are red. Is the probability the first k balls drawn are red: \[\Pr(R_{k}\dots R_{1}|B) = \frac{(K-(k-1))(\dots)(K-1)K}{(N-(k-1))(\dots)(N-1)N}\] or should we suppose the run ends when we draw a white ball? I.e., we should examine \(W_{k+1}R_{k}\dots R_{1}\) as a run of k red balls terminated by drawing a white ball? Does the sum of probabilities sum to 1? If not, why not? (And what does it sum to?)

Out of laziness, I sometimes write \(\Pr(n|K,N)\) for a run of n red balls when the urn contains K red balls and N balls in the urn in total.

Exercise 1B. What is \(\Pr(n|K,N+1)\) in terms of   \(\Pr(n-1|K,N)\)? Similarly, what is \(\Pr(n|K+1,N)\) in terms of   \(\Pr(n-1|K,N)\)? Can we relate \(\Pr(n|K+1,N+1)\) and \(\Pr(n|K,N)\)?

Exercise 2. In an urn with N balls (K of which are red), what's the expected length of a run of red balls?

This is rather tricky. Using the solution from exercise 1, the expected value for the length of a run of red balls would be \[\mathbb{E}[L] = \sum_{k=1}^{K}k\Pr(k|K,N)\] where \(L\) is the random variable denoting the length of a run of red balls drawn from the urn (sampled without replacement).

Exercise 3. Consider the "large urn limit", where \(p=K/N\) is fixed as \(N\to\infty\) and \(K\to\infty\). (a) Prove sampling without replacement [the hypergeometric distribution] becomes sampling with replacement [the binomial distribution]. (b) How does the expected length of a run of red balls change?

Could we use exercise 3 as a sanity check on the solution to exercise 2 under appropriate limits?

Exercise 4 (open-ended). Think of at least three ways to test your solutions to exercises 1, 2 and 3(b). [Punishment: if you thought about the \(K=1\) case, think of four more ways to test your solutions.]

Arguably, using the solution of exercise 3 is one check of the solution of exercise 2. Finding two more gives us more confidence in our solution being correct; it is good practice when solving problems and we don't know the solution.

Addendum: The solution will be posted Monday July 13, 2020, at 9:00am PDT.

Further Reading

1. D.M. Bloom, "Probabilities of Clumps in a Binary Sequence (and How to Evaluate Them Without Knowing a Lot)." Mathematics Magazine 69, no.5 (1996) pp. 366–372. (Bloom considers the combinatorics for no-run samples, which is the complement of the situation we're interested in.)
2. I.P. Goulden, and D.M. Jackson, Combinatorial Enumeration. New York: Wiley, 1983.
3. Check your results for a deck of cards (OEIS A086438)

Median Voter Theorem in other Voter Models?

The Economist's Why a left-wing nominee would hurt Democrats explicitly invoked an implicitly assumed proposition in political discourse: the median voter theorem "holds" in US elections.

Briefly put, the median voter theorem states that, if we have an odd number1The assumption of an "odd number" of voters is technically not needed, if we have some way to break the tie, or if (for an even number of voters) we have made sure the 2 median voters agree on how they'll vote. The assumption on the odd number of voters is not strictly necessary, it's just a helpful assumption. of voters who are rational and the vote is about an issue describable by a one-dimensional issue space, then polling the median voter will tell us the outcome of the vote. I won't digress on the assumptions of this theorem or the conditions when it holds too long, the take-away message is the median voter's vote coincides with the result of the vote, so a rational candidate would run as close to the median as possible.

But I draw your attention to the fact that the median voter theorem assumes the voters are rational, in the game theoretic sense of the term.

Puzzle: Does the median voter theorem hold for other voter models?

We can be generous and weaken the median voter theorem statement to be something like There exists a voter, the Median Voter, and the Median Voter's vote "correlates strongly" with the outcome in a first-past-the-post vote with two candidates.

I don't have an answer to this puzzle, nor have I searched the literature hard enough to be satisfied. (There may be some obscure article on this very puzzle, I am unaware of it though.) The answer is famously "no" for ranked-choice voting with multiple candidates, but for incomplete information or alternative voter models...these have not been adequately explored in the literature. I just have accumulated some notes that may be germane to this puzzle.

Aside 1: Half-life of information. It has been noted that the half-life of information, for the average voter, is less than half a week2The conclusion to be drawn from these analyses is clear: memory for campaign messages not only fades but fades quickly, the half-life of the message typically being less than a week., page 315 (bottom of the right column) of Milton Lodge, Marco R. Steenbergen, Shawn Brau, The Responsive Voter: Campaign Information and the Dynamics of Candidate Evaluation. The American Political Science Review, Vol. 89, No. 2. (Jun., 1995), pp. 309-326.. Lets use an exponentially decaying moving average with the half-life set to half a week. (So W = 3.5 ln(2) days.) Specifically, integrating new information Y_n (which occurs at time t_n) into a "stockpile" or "accumulator" S_n obeys the formula: \[ \begin{split} S_n &= \alpha(t_n - t_{n-1}) Y_n + \left[1 - \alpha(t_n - t_{n-1})\right] S_{n-1} \\ &= \left[1 - \exp\left({-\frac{t_n - t_{n-1}}{W}} \right)\right] Y_{n} + S_{n-1}\exp\left({-\frac{t_n - t_{n-1}}{W}} \right) \end{split} \]

For very frequent events, the exponential function becomes approximately linear (since \(t_{n}-t_{n-1}\) is "small").

Remark. We need some way to translate an event, a speech, news coverage, etc., into values for Y_n. Presumably it follows a log-normal distribution. For a one-dimensional issue-space, we could arbitrarily pick positive Y to benefit one candidate, and negative Y to benefit the other. We'd need another random variable, Bernoulli distributed, which controls the sign of Y.

References

• Milton Lodge, Marco R. Steenbergen, Shawn Brau, The Responsive Voter: Campaign Information and the Dynamics of Candidate Evaluation. The American Political Science Review, Vol. 89, No. 2. (Jun., 1995), pp. 309-326.

Puzzles from Bernoulli

I recently stumbled across a fascinating puzzle from Bernoulli's Ars Conjectandi, and then found that part 3 of his book consists of 24 equally exciting worked problems. But I haven't found online the presentation of these problems.

See either Anders Hald's A History of Probability and Statistics and Their Applications before 1750 (2005), especially chapter 15, section 5...or Edith Dudley Sylla's translation The Art of Conjecturing, Together with Letter to a Friend on Sets in Court Tennis (2006).

If I misrepresented any of the problems, leave me a comment! I was rather quick and rushed in assembling the exercises, and I easily could have made mistakes. Also, I am fully aware some of these problems are ambiguous. Try working out every variant you can think of. The whole point (at least, to me) is that these present variations on a theme.

Problem 1. There are two balls in an urn, a "winner" ball and a "loser" ball. There are three players. The first player draws a ball. If it's the "loser" ball, the first player returns it to the urn; and if it's the "winner" ball, the first player wins the game. Should the first player lose, the second player performs the same task, and wins only if drawing the "winner" ball. Should the first and second players both draw the "loser" ball, the third player draws a ball. If the third player draws the "loser" ball, the house wins the game. What is the expected winnings for each player (and the bank)?

Problem 2. A variant of problem 1, each player bets some amount. If no player draws the winning ball, then they divide up the bets equally. (Example: player 1 bets 4 coins, player 2 bets 2 coins, player 3 bets 1 coin; if they all draw the "loser" ball, then each player receives (4 + 2 + 1)/3 coins back.) What is the expected winnings for each player?

Problem 3. Consider a tournament (i.e., a sequence of 2-player games). Two players compete in a game, where there will be only one winner. The winner plays the game against player 3. The winner of the second match plays against player 4. And so on until player 6. If the lots of each player in the games are equal, how do the lots of the later players compare/increase over those of the earlier players?

Problem 4. As a variant of problem 3, the lot of the player who wins the first game is stipulated to be double that of the third player, who plays only in the second game, and so on. Compare the expected winnings for each player.

To be clear, Bernoulli means the relative probability mass of winning the first round are even for both players (each player has 1 favorable outcome for an odds of 1:1, or 50% probability of winning), but the relative probability mass for the winner of the first round to beat player 3 is doubled (the victor of the first match has twice the favorable outcomes as compared to game 1 [i.e., 2 favorable outcomes] whereas player 3 has 1 favorable producing a 2/3 probability favoring the victor of the first game to win the second), and the relative probability mass of the winner of the second round is doubled to determine the odds of winning the third game (so if the victor of the first game also won the second game, this victor has 4 favorable outcomes, but player 4 has 1 favorable outcome, the probability of winning this particular game for the victor of the first two games would be 4/5), and so on.

Problem 5. "This is the third problem of Huygens' Appendix." A wagers against B, that of 40 cards, of which 10 of each color, he will draw 4 of them in a way to have one of each color. (Or, for modern readers, consider a standard playing deck with Jacks, Queens, Kings discarded; A wages that B cannot draw one card from each suit.) What is the probability that A wins the bet? [Alleged solution: One finds in this case that the chance of A is to that of B as 1000 is to 8139.]

Problem 6. "This is the fourth problem of Huygens' Appendix." One takes 12 tokens of which 4 white and 8 black. A wagers against B that among 7 tokens that he will draw from them blindly, there will be found 3 white. One demands the ratio of the chance of A to that of B; i.e., what are the odds A wins? (There is some ambiguity in the historic text; namely, is it exactly 3 white or at least 3 white?)

Face Cards

Problem 7. Let there be a single face card in a pack of n cards, and the first player (of m players) to draw it wins. If no one draws it, and cards remain, then the players continue drawing cards. What is the probability of each player to win? What if n = mk (the number of players divides the number of cards)?

Problem 8. As a variant of Problem 7, what if there were j face cards in the deck and the winner is still the first person to draw a face card? What is the probability for each player to win?

Problem 9. As a variant of Problem 8, what if the players keep drawing cards until the deck is exhausted, and the winner is the player with the most face cards drawn? For ties, the winnings are split among the winners. (Assume each player pays 1 coin to play, for example.) What is the expected winnings for each player?

Problem 10. As an extension to Problem 9, what if we permit any player to sell their position? Specifically Bernoulli considers four players (A, B, C, D) with a deck of 36 cards, of which 16 are face cards. Each player receives cards in rounds until 23 cards have been distributed, A has received 4 face cards, B has 3, C received 2, and D a modest 1 face card, so that there remain 13 cards among which there are 6 face cards. The fourth player D (who is next to receive a card), "seeing that almost all hope of his winning has vanished", wishes to sell his right to one of the others. How much should he sell it for and what are the expectations of the individual players?

Dice Puzzles

Problem 11. Throw a die. Then throw a second die. If they differ, the player wins a point; if they agree, the player loses a point. Then the player throws a third die. If it agrees with any previous die, lose one additional point for each agreement; otherwise, the player wins an additional point added to their running score. Do this for a total of 6 dice. What is the expected score for the player?

Problem 12. Similar to Problem 11, but the dice must be thrown in numerical order. E.g., the first die must be "1" for the player to get a point, otherwise the player loses a point; the second die must be "2" for the player to get a point, otherwise the player loses a point; and so on. What is the expected score for the player?

Problem 13. Three players (A, B, C) have a list of 6 numerals ("1", "2", ..., "6") on a sheet of paper before them. Each of them take turns round-robin. On a player's turn, they roll a die, and if the result is on their sheet of paper, then the player gets to eliminate it from his sheet (scratch off the number) and roll again; but if the player has already eliminated that number, then the next player gets the die. This process continues until someone eliminates all their written numerals. It happens, however, after a while that A has 2 numerals before him, B has 4, and C has 3; it's A's turn to throw. What are probabilities for each player to win? [Bernoulli notes This problem requires more labor and patience than ingenuity.]

Problem 14. There are k players. A given player throws a die, which shows its face to be m. This tells the player to throw m dice and sum the values shown. (We may choose m to be added to the score or not.) The player with the most points wins.

Here's a twist, though: one player may opt to beat a fixed number t of points. This value t is fixed by the rules of the game.

What's the expected winnings for each player if no one opts for the fixed points route? What's the expected winnings for each player if someone chooses to beat a fixed number of points?

Although Bernoulli didn't pitch it, what if there's a "bidding war" competition to determine which player may opt to beat a fixed number of points? Instead of having t be fixed, when one player asks to be the one to beat a fixed number of points, that player must offer a bid ("I want to beat x points"). Each player may pass (and no longer participates in the bidding anymore), or offers a higher bid ("I want to beat y > x points"). This continues until the maximum value of 35 is bid. What strategy works best in this bidding strategy?

Problem 15. As a variant of Problem 14, what if the fixed number of points is the square of the first toss of the die?

Problem 16 (Cinq et Neuf). This is a prototype of craps. Player 1 tosses a pair of dice. Player 1 wins if on his first toss she gets a 3, an 11, or any pair. But player 2 wins if player 1 tosses a 5 or 9.

If player 1's first toss is a 4, 6, 7, 8, or 10, then the game continues (player 1 keeps tossing a pair of dice) until either (a) a 5 or 9 appears [player 2 wins], or (b) player 1 tosses the first value [player 1 wins].

What is the probability of player 1 winning? (Player 2's probability of winning is, by definition, the complement of the probability for player 1 winning.)

Although not asked, what is the expected number of tosses for a given game?

Wheel Games

Problem 17. The player pays 4 coins to toss 4 balls on a roulette-like wheel. The roulette wheel has 32 pockets, each with labels "1", "2", ..., "8". There are four pockets labelled "1"; four pockets labelled "2"; and so on. Each pocket may contain at most 1 ball. The player wins the sum of the pockets's labels (for the pockets containing the balls). What is the expected winnings for the player? [Solution.]

Card Games

Problem 18 (Trijaques). We consider a "toy model" of poker.

We assemble a deck of 28 cards from a standard playing deck, by discarding the cards 2 through 8 for each suit. The values for each card are determined by its face value, but the Jack of Clubs and 9s are wild.

The player will be given 4 cards. The goal is for the player to assemble either a flush (a run of all 4 cards regardless of suit, e.g., "9, 10, J, Q"), or a pair, three of a kind, or four of a kind. The value of a hand is the sum of the value of the cards in the combination. The player with the highest valued hand wins the pot (or it is split among the highest valued hands).

But the sequence of play is as follows: each player is dealt 2 cards face down. Then the players bet. Then each player is dealt 2 cards face up.

What is the expected winnings for each player? What strategies could be considered in the betting process?

Problem 19. Consider a generic game, where one player is the "banker". The banker has an advantage over the other players (i.e., is more probable than any other player to win a given round). But the rules of the game may allow moving the banker role to another player.

Specifically, the banker has probability p of winning a round, and probability q of losing, with p + q = 1 and \(r = p - q > 0\). The banker has probability h of continuing the next round as banker, and probability k of losing the position as banker to another player, with \(t = h - k > 0\). Let a denote the amount won by either the player or the banker, whoever wins the round.

What is the expected winnings for the banker after "many" rounds?

Problem 20 (Capriludium, Bockspiel). At the beginning of the game, each player puts down their bet. Then the banker shuffles the deck, and divides it into equally sized hands. Each player (and the banker) gets a hand. Bernoulli says the player just turns the hand over without organizing it. If the punter [player who is not the banker] has their facing card be of equal or higher value compared to the banker, then the punter wins an amount of money equal to his bet/bid from the banker. Otherwise the player loses their wager to the banker. When the banker loses to all the players in a game, the next player becomes the banker.

After one round, the top cards are not yet discarded. New wagers are first made. Then the top card is discarded (collected by the banker for later shuffling).

If there are N = sf cards in the deck with s suits and f face cards (of value ranging between 1 to f), and suppose there are n players (including the banker) for n = 2, 3, 4.

What is the expected winnings for the banker? What is the expected number of rounds to be played for a given deck? How does it vary on the number of players? What is the probability the banker will remain in their role as banker after one hand? After h hands?

Problem 21 (Basset). The basic formalization is there are 2n cards, of which k are marked "a" and \(2n - k\) marked "b". For example, 2n = 52, and k = 4 (e.g., aces in a standard deck of playing cards). The player draws two cards in succession (no replacement). The possibly outcomes:

• ab = the banker wins 1 point
• ba = the player wins 1 point
• aa = the banker wins 1 point
• bb = toss the cards aside and draw 2 new cards (and consult this table of outcomes again)

What is the expected winnings for the banker after 1 hand? For 1 game (exhausting the whole deck)?

As a variant, we could try using the full rules for Basset, with the bizarre bet multiplying schemes.

Curious Puzzles

Problem 22. There are two players, Titus and Caius. Titus pays Caius one coin for each round where Titus will throw a single die. There are a possible outcomes, of which b favor Titus (Caius pays him one coin) and c favor Caius (where Titus wins nothing). If Titus throws one of the c cases continuously n times in a row, Caius must return all n coins to Titus. What is the expected winnings of Caius and Titus?

Problem 23 (Blinde Würffel, "Blind Dice"). We have 6 dice with a number on only one face, and blanks on the remaining faces. One die has "1" for its non-blank side, another has "2" for its non-blank side, and so on, so each label "1" through "6" may possibly show up. Blank sides are treated as having value 0. Suppose the player rolls all 6 dice, and wins the sum of the values shown. What is the player's expected winnings?

Problem 24. A variant of Problem 23, if the player gets no points, in 5 tosses in a row then the player gets his money back for those 5 tosses. What is the player's expected winnings now?

How many news stories are there?

Recently, an eccentric billionaire bought the Los Angeles Times and sought to make it rival the New York Times as a "newspaper of record". Presumably this means hiring more journalists, but let us ask a simpler question.

Puzzle 1: How many news stories go unreported by both the New York Times and the Los Angeles Times?

We can solve this puzzle using the maximum likelihood estimator for the Hypergeometric Distribution. Think of it like this: on a remote island with some unknown deer population, we go and (without harming the wildlife) tag K deer. A month later, we return, and capture n deer, of which k are tagged. We can estimate the total population of deer N on the island.

Explicitly connecting that analogous problem to our own, we know the "tagged stories" K reported by the New York Times, the "sample stories" n reported by the Los Angeles Times, of which there is the "tagged sample stories" k reported by both newspapers, and we want to estimate how many news stories there are in total N. The maximum likelihood estimator for N is given by \[ \min_{\widehat{N}}\frac{\Pr(\widehat{N},K,n,k)}{\Pr(\widehat{N}-1,K,n,k)}\geq1 \] the smallest N for which the ratio of probabilities is greater than 1. It is not hard to solve this to find \(\widehat{N} = [Kn/k]\) where the brackets indicate we are using the integer part of the number (e.g., [3.2]=3, [4.9]=4).

Now we just need to list the stories which the New York Times reported but the Los Angeles Times did not (giving \(K-k\)), the stories which both papers reported (k), and the total number of stories the Los Angeles Times reported (n). From this, we will estimate how many stories have gone unreported.

To answer this fully, I looked at the front section for each paper for May 28, 2019. The short answer is K = 22 stories in the New York Times, n = 12 stories in the Los Angeles Times, and k = 5 stories in both. We thus may expect there to be N = [264/5] = 52 stories, of which 29 were reported and 23 went unreported by either newspaper. Find below a density plot of the probability for various N, and notice how it is maximized at N = 52 (indicated by a red vertical line):

Solution: Using the maximum likelihood estimate for the hypergeometric distribution, there were a total of N = 52 news stories, 29 were reported by one of the two newspapers, and 23 stories went unreported.

Puzzle 2: Is there a Bayesian estimate for the number of news stories? Or different ways to estimate the total number of news stories?

Puzzle 3: How stable is this estimate for N? If we examine, say, the last week's worth of articles, do we get approximately the same value for N?

Puzzle 4: What if we extend this analysis to include, e.g., the Wall Street Journal, the Washington Post, and others? How stable is N in this case?

Find two tables below, one listing the stories in the international section for both papers, and the second for national stories. Corresponding stories are listed on the same row.

New York Times	Los Angeles Times
She Thought She’d Married a Rich Chinese Farmer. She Hadn’t. (A4)
Attacks by Extremists on Afghan Schools Triple, Report Says (A4)
Romania’s Most Powerful Man Is Sent to Prison for Corruption (A6)
With Trump’s Visit to Japan, Empress Masako Finds a Spotlight (A8)
Trump and Abe’s ‘Unshakable Bond’ Shows Some Cracks in Tokyo (A8)	Trump pushes off war talk on Iran, says ‘regime change’ is not U.S. goal (A1)
Election Puts Europe on the Front Line of the Battle With Populism (A10)	In European vote, far-right surge fails to materialize, but mainstream parties lose support (A2)
European Parliament Elections: 5 Biggest Takeaways (A10)
European Vote Reveals an Ever More Divided France (A11)
18 Schoolchildren Stabbed, and Girl and Man Killed, in Attack in Japan (A11)	Knife-wielding man attacks schoolgirls in Japan, killing 2 (blurb of story on A2)
Sebastian Kurz, Austrian Leader, Is Ousted in No-Confidence Vote (A12)	Ousted by parliament, Austria’s Kurz vows to win back job (A4)
Israel’s Netanyahu Struggles to Form a Government, as Time Runs Short (A12)	Netanyahu running out of time to form government; Israel may face new elections (A2)
White Panda Is Spotted in China for the First Time (A12)
30 Dead and 200 Missing in Congo After Boat Sinks (A12)
	Arrests, killings strike fear in Thailand’s dissidents: ‘The hunting has been accelerated’ (A3)

Matches are based on substantially overlapping subject matters. The only debatable story match is "Trump pushes off war talk on Iran", which is a proper subset of the corresponding New York Times article.

Also note, in the Los Angeles Times, there was a 1000 word blurb about the knife attacks in Japan. Later, on their website, they posted a longer and more detailed article. I decided to count that as a match, which may be debatable.

Sources: Los Angeles Times, New York Times

The national stories in both newspapers, appears to be completely disjoint sets of stories.

New York Times	Los Angeles Times
Trump Administration Hardens Its Attack on Climate Science (A1)
Google’s Shadow Work Force: Temps Who Outnumber Full-Time Employees (A1)
Trump Wants to Wall Off Huawei, but the Digital World Bridles at Barriers (A1)
With His Job Gone, an Autoworker Wonders, ‘What Am I as a Man?’ (A1)
With the 2020 Democratic Field Set, Candidates Begin the Races Within the Race (A1)
Saving Charlie: A Rush to Rescue Stranded Cats and Dogs from Oklahoma Floods (A17)
Fearing Supreme Court Loss, New York Tries to Make Gun Case Vanish (A17)
A Missed Opportunity for the Malpractice System to Improve Health Care (A19)
Why a Hamptons Highway Is a Battleground Over Native American Rights (A22)
	High radiation levels found in giant clams of Marshall Islands near U.S. nuclear dump (A1)
	He made millions as an L.A. investor. Now, he may run for president to fight poverty (A1)
	Want to park in Koreatown? Get ready for a ‘blood sport’ (A1)
	Put your hands together for the World Series of Poker, turning 50 this year (A4)
	Texas lawmakers approve safe gun storage program, quietly going around the NRA (A4)
	Oklahoma’s opiod lawsuit targeting drugmaker goes to trial Tuesday (A7)

Matches are based on substantially overlapping subject matters.

Sources: Los Angeles Times, New York Times

Running for Higher Office: Case Studies

Puzzle: When will a member of the House of Representatives decide to run for Senate over for Governor?

"Political ambition" generically refers to either (1) a politician holding office deciding to run for a higher office, or (2) an individual who does not hold a political position to run for office.

Aldrich and Bianco note that when political ambition is cast in "utility maximization terms" (which I will extend from decision-theoretic framework to include game theoretic ones), it is called a Calculus of Candidacy. This is in analogy to Riker and Ordeshook's term "calculus of voting".1 See W.H. Riker and P.C. Ordeshook, "A theory of the calculus of voting" American Political Science Review 62 (1968) pp. 25–43; or their follow up book An Introduction to Positive Political Theory, Prentice Hall, 1973. As a decision theoretic problem (i.e., ignoring adversaries), it may be cast as maximizing the expected utility: \[EU(a_{k}) = \sum_{j}P_{jk}U(O_{k}) - C_{k}\] where \(a_{k}\) is the strategy of pursuing action \(k\), \(P_{jk}\) is the probability of outcome \(j\) given action \(k\), and \(C_{k}\) is the cost of taking action \(k\). The rational action then chooses the strategy which maximizes the expected utility of its outcome.

But how is this process exactly done? Is there any interaction with "party elites"? Does a person just wake up one day, and announce, "You know what? I think I'll run for governor starting today, because my expected utility of that course is maximized"? And is decision theory the right tool — will potential candidates need to consider potential primary challengers or the potential of defeating an incumbent? Aaron King's doctoral thesis examines these questions on the dynamics surrounding political ambition in greater detail.

This post will gather a few case studies, in preparation for future work trying to set up a game theoretic model for political ambition.

Case Studies

Case Study: Michael Punke and Montana's 2020 Governor Race. The initial decision to run, however, seems to involve some communication with "party elites", as Politico reports about Michael Punke considering a run for Montana's governorship (and the ambitions of Governor Cooney and Mayor Collins):

Punke, who has talked to leading Montana Democrats about his political ambitions but is not talking to donors at this stage, has described himself to potential backers in Montana as "rabidly centrist" and said that if he runs, he would likely focus on issues like health care and workforce development, said one source. He would also use his WTO trade experience as a selling point because some of Montana’s biggest industries are trade-dependent, like exports of agricultural products and copper and even tourism.

[...] The current Democratic governor of Montana, Steve Bullock, is term-limited and is expected to announce a run for president soon. Independent Helena Mayor Wilmot Collins and Democratic Lt. Gov. Mike Cooney are also seen as potential candidates for governor, though Collins said in March he was also considering the Senate race and appears ready to launch a campaign for that office.

The inferences we should draw from this reporting is: (1) there are "party elites" whom Michael Punke is courting prior to entering the race, (2) the considerations of possible opponents are taken into consideration in each actor's calculations.

Curiously, similar processes appear to unfold in the Republican side of the Montana senate race.2 DailyKos's daily election digest reports, MPR's Brian Bakst reports that Bill Guidera, a former executive at 21st Century Fox and News Corp, is considering seeking the GOP nod to take on Democratic Sen. Tina Smith. Guidera, who used to serve as the Minnesota Republican Party's finance chairman, doesn't appear to have said anything publicly yet, but Bakst acquired an email from someone he identified as a longtime friend and quasi-adviser who said that Guidera is thinking about running and holding a fundraiser. Bakst also adds that Guidera has been appearing at local GOP events and doing meet and greets.

We should caution the reader that some sources, e.g., Daily Kos Elections, have used the phrasing of a candidate "seeking the nod from the party" as synonymous for "has entered the primary to be the party's nominee" for an office.3 For an example of this poor abuse of language, DailyKos's daily election digest reports, Former Gov. Bill Haslam confirmed this week that he is still considering seeking the GOP nod to succeed retiring Sen. Lamar Alexander, and he told WBIR that his decision could come as early as next month. To the best of my knowledge, and all the sources I could find, there is no discussions between Governor Haslam and the Tennessee GOP party elites.

Case Study: Bill Weld's 1996 Senate Decision.4This example is inspired from Kenneth A Shepsle's Analyzing Politics, first ed., pages 22–24. First elected in 1991 as governor of Massachusetts, Bill Weld's gubernatorial term came to an end with the November 1994 election. A popular Republican governor in a famously liberal state, Weld remedied the financial debts through a well-executed political squeeze play (thwarting the state legislature from borrowing more money or raising taxes with veto threats), restructuring the state's debts, and taking advantage of Medicaid loopholes to acquire $500Mn from the federal government. The sordid details and play-by-play are well documented in Richard Hogarty's Massachusetts Politics and Public Policy.

Weld was popular inside the state, and outside. It was whispered that party elites were entertaining the idea of Weld as the presidential or vice-presidential candidate in 1996. The governor was inevitably aware of these rumors, since the New York Times's conservative pundit William Safire endorsed such an idea in his 1993 op-ed piece What about Weld, which could be sustained by holding public office. (If you don't know who Mr Safire is, please read Rick Perlstein's Nixonland; it's a wonderful book, and explains only parts of Mr Safire's connections with, and sway among, conservatives and Republican party elite.)

But, things were not so straightforward. Senator Ted Kennedy's term was coming to an end, and Sen Kennedy faced re-election in the November 1994 election as well. Or retirement. In his term, Sen Kennedy faced a number of contraversies ranging from his personal life to his handling of Clarence Thomas's nomination to the supreme court. The GQ's 1990 profile, Ted Kennedy on the Rocks, did little to help. The Boston Globe later reflected, Not surprisingly, many thought the senator would announce that he wasn't running for reelection in 1994, that it was time to get his personal house in order. In fact, Kennedy was already gearing up for the toughest race of his Senate career. The senator announced his intention to run for re-election early in Spring of 1994, entering the race as an especially disadvantaged incumbent.

Governor Weld could either risk challenging the vulnerable Sen Kennedy for the senate seat or run for re-election as governor of Massachusetts. Political observers agreed any race between Kennedy and Weld for the senate would be a toss-up,5For example, The New Republic reported there were more independent voters than registered Democratic voters in 1994. There is a big bloc of voters, as high as 40 percent of the electorate, that is no longer available to Kennedy, a Boston pol who is advising the senator's campaign confided. If anyone runs a minimal campaign, he'll get at least that much of the vote. Such, at least, was the specious reasoning of political operators at the time. but the governor's race would be a lock. Regardless of the choice, Weld needed to hold one of these offices to be considered as presidential (or even vice-presidential) material.

Framed thus, we would expect the decision Weld would make should be to run for re-election as governor in 1994, and enjoy a chance to join the GOP's ticket for the 1996 presidential race.

Well, Weld did run for re-election in 1994, winning 71% of the popular vote. A year afterwards, on November 29, 1995, the governor made his intentions clear to run in 1996 against the junior senator John Kerry after securing the blessings of financial backers and GOP party elites.6The only source I could find documenting this was the Boston Herald's article, Weld expected to launch bid today dated November 29, 1995. Curiously, the article notes, Weld advisers also noted that Weld came to the brink of the presidential race and the 1994 Senate race before bowing out.

Further, that article notes how Weld secured the blessings of Republican donors and party elites: Weld, who was scheduled to be in Manhattan this morning to meet with campaign fund-raisers, reserved a hotel function room in Boston this afternoon in anticipation of announcing his entrance to the race. [...] Today's New York meeting is one last step toward a possible Weld candidacy. New York has been an important factor in the Weld fund-raising equation — accounting for as much as 15 percent of the $6.5 million Weld raised between the 1990 and 1994 gubernatorial elections. While this morning's breakfast was depicted as a critical factor in Weld's decision, a negative outcome is unlikely. Sources close to Weld noted that the people attending the New York event include the governor's two brothers, his sister, and former Harvard classmates. [...] According to sources, Weld has already begun to assemble a fund-raising team, a critical issue since his longtime chief fundraiser, Peter J. Berlandi, has opted for a limited-duty role in the Senate race. According to sources, two Boston attorneys — Weld campaign treasurer Sandy Spaulding and 1992 congressional candidate Michael Crossen — are likely to assume key roles. Sources also said veteran Bay State GOP fundraiser Priscilla Ruzzo, a staffer for the National Republican Senatorial Committee, may be "loaned" to Weld during a startup phase. (LexisNexis saved the article, and I quote from LexisNexis's saved transcript, which may very well be in error.) The Atlantic summed up the elite opinion, Is it the wrong race? Is it the wrong year? Is Kerry the wrong target? The right race, this theory goes, was the last Senate race in Massachusetts. The right year was 1994. The right target was Senator Edward M. Kennedy.

Puzzle. What interactions occurred between election day 1994 and November 25, 1995 which led Weld to prefer challenging Sen Kerry over alternative actions?

Case Study: Claire McCaskill's Senate Run.7This example is inspired from Kenneth A Shepsle's Analyzing Politics, second ed., pages 21–23. Shepsle cites Jeff Goldberg's Central Casting article from The New Yorker, too. Claire McCaskill after graduating law school in 1978 began practicing law until she ran and won a set in Missouri's state House of Representatives. She then ran for Kansas city's county prosecutor in 1988 and won, ran for state auditor (which she viewed as a stepping stone towards governorship) in 1998 and won. Then, in 2004, McCaskill primary challenged the sitting Democratic governor Bob Holden. And won...the nomination. Alas, Roy Blunt (the Republican nominee) prevailed in the governor's race. But McCaskill defeating a sitting governor in the primary was historically unprecedented in Missouri.

But, The New Yorker informs us, In 2006, the two senior Democrats in the Senate, Schumer and Harry Reid, persuaded her to run against a Republican incumbent, Jim Talent. Her timing was good: President Bush’s dismal approval ratings helped the Democrats pick up enough seats to win majorities in both houses of Congress. McCaskill won a narrow victory. (McCaskill claims this as well in her memoir, Plenty Ladylike: A Memoir.)

Observation. "Elder statesmen" of the party [e.g., Reid and Schumer] seemingly count as "party elites" for certain races, like for the Senate.

But in 2014, Sen McCaskill considered running for Governor in 2016 instead of re-election for Senator in 2018. It had been a dream, for Claire McCaskill, to be governor of Missouri, ever since she was in high school. The New Yorker put it this way: By the time McCaskill was in ninth grade, at Hickman High School, in Columbia, she had set her sights on becoming the first female governor of Missouri. Whether this dream was real or imagined, the source or an excuse of, McCaskill's ambition for governorship was evident at the time.7The New York Times reported after the 2018 election, The loss likely marks the end of life in public office for Ms. McCaskill, a singular figure in Missouri politics who began her public career more than three decades ago in a male-dominated State Capitol and outlasted most of her Democratic peers. She has long coveted the state’s governorship, having narrowly lost a bid in 2004, but on Tuesday night, she signaled that she had run her final race, though she said she would be unencumbered in speaking her mind. (emphasis added)

The New Yorker noted about McCaskill's initial run, In 1998, McCaskill ran for state auditor, an office that she saw as a stepping stone to the governorship. And later in that same article, As recently as 2015, she considered returning to Missouri for another try at the governorship. Her mind naturally goes to practical details rather than to big concepts. Her idea of governing is to spend money wisely, punish misbehavior, and give people what they need in order to get through their daily lives.

Whether Sen McCaskill had greater ambitions beyond the governor's mansion remains as unclear as how McCaskill's ambitions evolved over time.

Ultimately, McCaskill sat down and did the calculus sometime in Winter of 2014–2015, and concluded in January 2015 that, for the trajectory McCaskill had in mind, running for re-election in 2018 was more optimal than running for Governor in 2016.8 McCaskill told KCUR in an interview in January 2015, At the end of the day, you have to ask yourself if the job you're thinking about going for is better than the one you have, and can you do more? She reaffirmed this stance with St. Louis Public Radio on January 15, 2015 and with Politico on January 12, 2015.

Puzzle. Did Claire McCaskill plan with Missouri state party elites or her colleagues in the Senate? Or did she arrive at this conclusion on her own?

Conclusion

We have examined a few "case studies" in political ambition. Our case studies have been "broad" rather than "deep": we had a writer aspire for governorship, a governor challenge a sitting senator, a senator with frustrated aspirations for governorship. For completeness, we should also consider a state legislator with ambitions for (1) the House of Representatives, (2) governorship, (3) Senate. But also we should consider individuals with presidential ambitions.

Fowler and McClure's Political Ambition (1989) examines a single congressional district with an open seat, specifically how state legislators determine whether to run for that open seat or not. (This is an example of a "deep" case study which is not "broad".)

We also didn't examine sufficient cases to see if the examples given are a sufficient representative sample. The gender and race of the candidates may impact the dynamics. RL Fox investigated the impact of gender on political ambition.

Although we are critically dependent on newspaper reporting, we have tried to identify a few of the key elements in the decision to run for higher office. The flaw with this approach is obvious: we lack information about "behind the scenes" interactions among key actors. But I'm not a journalist or a political scientist: I don't have the time, energy, or patience to do the investigative dirty work.

Future work could include setting up a game theoretic model of political ambition, further case studies, and possible ways to empirically test various aspects of political ambition or at least determine indicators of political ambition.

References

• John H. Aldrich, William T. Bianco, "A game-theoretic model of party affiliation of candidates and office holders". Mathematical and Computer Modelling 16 (1992) pp. 103–116, doi:10.1016/0895-7177(92)90090-8
• G. Black, "A theory of political ambition: Career choices and the role of structural incentives". American Political Science Review 66 (1972) pp. 144–159
• Scott Gates and Brian D. Humes, Games, Information, and Politics: Applying Game Theoretic Models to Political Science. University of Michigan Press, 1997. See esp. ch. 3.
• Linda Fowler and Robert McClure, Political Ambition: Who Decides to Run for Congress. New Haven, CT: Yale University Press, 1989.
• David Rohde, "Risk-bearing and progressive ambition: The case of members of the United States House of Representatives". American Journal of Political Science 23, 2 (1979) pp. 1–26 [jstor]

"Thick Description" Reading

• Why Would Anyone Ever Want to Run for Congress?, The Atlantic; April 19, 2013
• Who Wants To Be A Senator? Not These High-Profile Democrats, FiveThirtyEight; May 9, 2019
• Richard Hogarty, Massachusetts Politics and Public Policy. University of Massachusetts Press, 2002.
• A Race Too Far?, The Atlantic; August 1996
• Ted Kennedy on the Rocks, GQ; April 15, 2016
• Peter S. Canellos (ed.), Last Lion: The Fall and Rise of Ted Kennedy. Simon & Schuster, 2009.
• Stormin' Mormon, The New Republic; November 7, 1994
• Weld expected to launch bid today, the Boston Herald; November 29, 1995, pg 1.
• Central Casting: The Democrats think about who can win in the midterms-and in 2008, The New Yorker; May 21, 2006
• Claire McCaskill’s Toughest Fight, The New Yorker; October 22, 2018

Initial Decision to Run

• RL Fox, JL Lawless, "Gaining and losing interest in running for public office: The concept of dynamic political ambition". Journal of Politics 73, no. 2 (2011) 443-462. Eprint.
• Aaron S. King, Unfolding Ambition in Senate Primary Elections: Strategic Politicians and the Dynamics of Candidacy Decisions. Lexington Books, 2017. Appears to be a cleaned up version of King's doctoral thesis.
• Jennifer L. Lawless, Becoming a Candidate: Political Ambition and the Decision to Run for Office. Cambridge University Press, 2012.
• Daniel Markham Smith, Succeeding in Politics: Dynasties in Democracies, PhD Thesis at UC San Diego, 2012.

How many days in the year?

Here's a brain teaser: your helpful lab assistant has rounded up a sample of N individuals. One by one, they tell you their birthday. What value of N is needed to determine there are 366 days in the (leap) year? (Or, if you hate leap years, that there are 365 days in the year.)

Variant A: You only know the existence of a day when someone tells you their birthday. So, if the first person says they were born January 2nd, you cannot infer January 1st must exist because "1 < 2".

Variant B: You can infer from January 1st the existence of January 2nd.

Possible acceptable answers include but are not limited to: a probability distribution for getting the correct number (as a function of N), the N which maximizes the likelihood of getting the correct number of days in a year, or the expected value for N.

Variant C: What other ways are there to determine N?

I may post a solution next week to this (or the week after).