## Pick any two cards

Let’s play a game: thoroughly shuffle a standard pack of 52 playing cards.  Now name any two card ranks, e.g., seven and jack.  If a seven and a jack happen to appear next to each other in the deck, you pay me a dollar, otherwise I pay you a dollar.  Should you be willing to play this game?  How likely do you think it is that I will win?

This game is discussed in a Grey Matters blog post, which in turn refers to a “Scam School” video describing the game as a bar trick.  I think it’s interesting because it’s not intuitive– it doesn’t seem very likely at all that an arbitrary pre-selected pair of ranks, just 4 cards each, should appear adjacent in a random shuffle of the 52 total cards in the deck.

But it’s also interesting because it’s not as likely as the Scam School video seems to suggest.  It turns out to be slightly worse than a coin flip, where the probability that two given card ranks appear adjacent is 284622747/585307450, or about 0.486.  Not very useful as a bar bet, I guess.

So, to improve the odds a bit, consider the following slight variation: shuffle the deck, and name any single card rank that is not a face card (i.e., not a jack, queen, or king).  If a card of the named rank appears next to a face card somewhere in the deck, you pay me a dollar.  Now what is the probability that I win?  It turns out this is a much better bet, with a probability of about 0.886 of such an adjacency.

Finally, we don’t have to resort to simulation as in the Grey Matters post.  It’s a nice puzzle to compute the probability in general, where $n=a+b+c$ is the total number of cards in the deck, of which $a$ are of rank A and $b$ are of rank B.  (For example, in the original problem, $n=52$ and $a=b=4$; in the second variant, $a=4$ and $b=12$.)  Then the probability of at least one A/B adjacency is

$1-\frac{1}{{n \choose a,b,c}} \sum_{k=0}^{a-1} {a-1 \choose k} {n-2a+k \choose b} ({c-1 \choose a-k} + 2{c-1 \choose a-k-1} + {c-1 \choose a-k-2})$

the derivation of which I think is a nice puzzle in itself.

## Card shuffling algorithms, good and bad

Introduction

This is motivated by a recent interesting post on the DataGenetics blog about various algorithms for randomly shuffling a list of elements, e.g. a deck of playing cards.  There is a similar article from 2007 at Coding Horror, and I am sure there are others as well.  The gist is that (1) a naive first attempt at implementing a shuffling algorithm is likely to be biased, yielding a non-uniform distribution of possible arrangements; but (2) fortunately, there is an equally simple algorithm that solves the problem efficiently and exactly, known as the Fisher-Yates shuffle.

This is well-trodden ground; my intent here is to expand on that basic story a bit, by digging into some of the mathematics relating these ideas about computer shuffling algorithms to the way we humans shuffle cards, with the result that some of these “broken” naive shuffling algorithms are potentially fixable.

Repeated shuffling

First, how do humans shuffle cards?  There are many different methods, but I will focus here on the riffle shuffle, where the deck is split into two halves, which are then interleaved together.  The randomness arises from the imperfection in:

1. The cut of the deck into two not necessarily equal “halves.”  This can be modeled by cutting at a position selected randomly from a binomial distribution.
2. The interleaving of the two halves, where “clumps” of cards from a single half stay together.  This can be modeled by letting cards fall into a single pile alternately from the two halves, with the probability of the next card to fall being proportional to the current number of cards remaining in the two halves.

Of course, it is not sufficient to perform this shuffle just once.  For one, there are only $2^{52}$ possible permutations resulting from a single riffle shuffle of a standard 52-card poker deck (why?).  This is much less than the $52!$ total possible arrangements.  So all arrangements are not even possible with a single shuffle, let alone equally likely.

However, we can fix this problem by simple repetition– that is, just shuffle multiple times.  With more and more shuffles, eventually all arrangements become possible, and with each additional shuffle, the probability distribution of arrangements more closely approximates a uniform distribution.  Granted, it is an interesting question how many such shuffles are enough.  But in practice it turns out that seven is usually “good enough,” and in principle we can keep shuffling to get as close as desired to a uniform distribution.

So why does this work?  We started with a limited set of $2^{52}$ possible permutations corresponding to a single shuffle, and by repeatedly applying a randomly chosen permutation from that limited set, we were able to arbitrarily closely approximate a uniform distribution over all $52!$ possible permutations.  Under what conditions can we do this?  My goal in this post is to answer this question.

Computer algorithms

On a computer, shuffling can be done more efficiently.  The following Python code implements the Fisher-Yates shuffle of a list of elements, in-place, using a linear number of swaps, with each permutation being exactly equally likely:

import random

def shuffle(deck):
"""Fisher-Yates shuffle."""
for i in range(len(deck) - 1, 0, -1):
j = random.randrange(i + 1)
deck[i], deck[j] = deck[j], deck[i]


(Note that I am ignoring the important issue of integrity of the underlying random number generator, state space size, etc.  For this discussion, let us assume that we can generate random integers uniformly distributed in any given range.)

Compare with the following “naive” algorithm, which is simple to describe– for each position in the deck, swap the card in that position with a randomly chosen card:

import random

def shuffle(deck):
"""Naive shuffling algorithm."""
for i in range(len(deck)):
j = random.randrange(range(len(deck)))
deck[i], deck[j] = deck[j], deck[i]


The problem with this algorithm, as discussed in the earlier linked blog posts, is that it is biased.  That is, the resulting distribution of possible permutations is not uniform; some permutations end up being more likely than others, as shown in the following figure.

Probability distribution of 5!=120 possible permutations after naive shuffle of a 5-card deck.

Each bar represents one of the 5!=120 possible permutations of a 5-card deck, arranged lexicographically from the identity permutation on the left to the “reverse” permutation on the right.  The height of each bar is proportional to the corresponding probability.  The grid line indicates what the probability of each permutation should be (1/120) when the deck is properly shuffled.

Condition 1: Reachability

Another nice visualization of this bias is a heat map, with each color in an n-by-n matrix indicating the probability that a card in position $i$ ends up in position $j$.  To properly shuffle the deck, this probability should be $1/n$ for all $(i,j)$.  The DataGenetics post (near the end, I can’t link directly to the image) as well as Mike Bostock both provide good examples of this.

However, although uniformity of card positions is necessary, it is not sufficient to properly shuffle the deck.  To see why, consider the “shuffle” consisting of simply cutting the deck (and completing the cut) at a uniformly random position.  Each card is equally likely to end up in any given position, so the corresponding heat map would not show any bias.  But there are only $n$ possible cyclic permutations that result, and repetition doesn’t help: we can’t “reach” any additional permutations by repeated cuts.

This “reachability” is the first of two important criteria for a proper shuffling method: the set of permutations from which we can choose for a single shuffle should generate all possible permutations.  That is, it must be possible by repeated shuffles to eventually realize every possible permutation of cards in the deck.

So just cutting the deck fails this condition.  But going back now to the biased naive algorithm above, it does generate all possible permutations… and so it turns out that we can “fix” the bias by repeated applications of shuffle(deck), yielding closer and closer approximations of a perfectly uniform distribution of possible deck arrangements, as shown below:

Probability distribution of permutations after successive naive shuffles.

Condition 2: Spanning cosets

We were able to “fix” the naive shuffling algorithm by applying it repeatedly… but we got slightly lucky in doing so, because this isn’t always possible.  To see why, consider the following even simpler shuffle, consisting of swapping a single randomly selected pair of cards:

import random

def shuffle(deck):
"""Swap a random pair of cards."""
i, j = random.sample(range(len(deck)), 2)
deck[i], deck[j] = deck[j], deck[i]


This obviously requires repeated application, since a single “shuffle” only changes the positions of two cards.  But this simple shuffle does satisfy the reachability condition: every permutation may be represented as a product of transpositions, so with enough random swaps, we can eventually realize every possible permutation.  So at first glance, it certainly seems like this algorithm should work just fine… if rather slowly.

But there is a problem.  Let’s again consider the small, manageable case of just $n=5$ cards, and look at the probability distribution over the $n!=120$ possible permutations as it evolves with each additional call to shuffle(deck)– that is, with each additional random swap of a pair of cards:

Distribution of 5!=120 permutations after successive swaps of random pairs of cards.

At the start, with 0 swaps, all of the probability is concentrated at the identity permutation at the far left.  With more and more swaps, the probability “spreads out” among the rest of the possible permutations.

Can you see the problem?  To make it more vivid, let’s re-arrange the bars in a different order:

The same evolution of probability distributions, but with permutations grouped by parity.

With each successive random swap, the probability distribution does become more and more uniform… but it alternates back and forth between two halves of the set of possible arrangements.  The problem is that permutations have parity.  Although a given permutation can be represented as a product of transpositions in many different ways, the parity (even-ness or odd-ness) of the number of such transpositions is invariant.  Before we begin shuffling, all of the probability is concentrated at the identity permutation, which is even (since it involves zero transpositions).  After the first call to shuffle(deck), the randomly chosen transposition yields an odd permutation (in the right half of the figure); after the second transposition, the resulting product is even; after the third, it jumps back to odd, etc.

This periodic behavior happens because all of the permutations in the generating set– that is, all single transpositions– are odd.  We would have a similar problem if all of the permutations in the generating set were even, except that instead of jumping back and forth as shown above, the distribution would always be confined to the even half of the permutations.

More complex periodic behavior is possible as well.  In general, the second condition needed for a proper shuffle is that the generating set of single shuffles must not all lie in some coset of some subgroup of the symmetry group of all possible permutations.  In the random swap algorithm above, this condition is violated because the set of all single transpositions lies within the single coset of the alternating group.

To summarize, a biased or incomplete shuffle isn’t necessarily hopeless.  It is possible to arbitrarily closely approximate a uniform distribution of permutations of elements of a list by repeated shuffling, as long as (1) every permutation is “reachable,” and (2) the generating set of permutations from a single shuffle do not all lie in the same coset of some subgroup.

Posted in Uncategorized | 2 Comments

## Probabilities in Knockout: solution

This is a very brief follow-up to the previous post about the basketball game Knockout, and the advantage of starting the game at a particular position in line.  Specifically, if we start the game with $n$ equally skilled players, each of whom makes their initial shot (usually from the free throw line) with some fixed probability $p$, and any follow-on rebound shots with probability $q$, then what is the probability of winning the game as a function of starting position?

Using the state transition diagram from last time, let $P_{n,k,s}$ be the probability that, with $n$ players remaining in the game currently in state $s \in \left\{1,2,3,4,5\right\}$, the player in position $k$ (starting from zero) wins.  Then we can translate the state diagram into a corresponding system of equations using the following Mathematica code:

numPlayers = 2;
eq = {
P[1, 0, 1] == 1,
Table[
{
P[n, k, 1] == p P[n, Mod[k - 1, n], 1] + (1 - p) P[n, k, 2],
P[n, k, 2] == p If[k == 0, 0,
P[n - 1, Mod[k - 2, n - 1], 1]] + (1 - p) P[n, k, 3],
P[n, k, 3] == q P[n, Mod[k - 1, n], 4] + (1 - q) P[n, k, 5],
P[n, k, 4] == q P[n, Mod[k - 1, n], 1] + (1 - q) P[n, k, 2],
P[n, k, 5] == q If[k == 0, 0,
P[n - 1, Mod[k - 2, n - 1], 1]] + (1 - q) P[n, k, 3]
},
{n, 2, numPlayers},
{k, 0, n - 1}
]
} // Flatten;


Then we can determine the probabilities of winning for each position in line by solving for $P_{n,k,1}$ for $k=\left\{0,1,...,n-1\right\}$.

Table[
P[numPlayers, k, 1],
{k, 0, numPlayers - 1}
] /. Solve[eq, Cases[eq, _P, {2}]] // First;


Interestingly, in the game with just $n=2$ players, the probability of the first player winning is $1/(3-p)$, independent of $q$, as shown in the following figure.  The second player’s advantage is minimized when the initial shot is easier.

Probability of first player (red) and second player (blue) winning in two-player Knockout, vs. probability of making the initial shot from the free throw line.

With more than two players, the probabilities of winning depend on both $p$ and $q$ in a more complicated way.  If we make the reasonable assumption that rebounds and put-backs are about the same difficulty, say $q=0.8$, no matter from where the initial shot is taken, then we can show similar results for $n=3$ and $n=4$, etc.

Probabilities of winning with 3 players, vs. p (with q=0.8).

Probabilities of winning with 4 players, vs. p (with q=0.8).

As mentioned last time, my intuition suggested that it’s always better to start farther back in line, but the above figures show that’s not necessarily the case, at least if the initial shot is sufficiently difficult– for example, if players start by shooting from the three-point line instead of the free throw line.

Posted in Uncategorized | 2 Comments

## Probabilities in Knockout

Recently, my two youngest nephews have started playing basketball.  Several weeks ago, I taught them– along with my wife– how to play Knockout, a game I remember playing at the various basketball camps I attended as a kid.  The rules are pretty simple:

The $n$ players line up behind the free throw line, with the first two players each having a basketball.  (At camp $n$ was often 80 or so, with the line stretching to the other end of the court, but in this case $n=4$.)  Each player in turn shoots initially from the free throw line.  If he makes it, he passes the ball to the next player and goes to the end of the line.  If he misses, he must recover the ball and shoot again– not necessarily from the free throw line– until he makes it.  If a player ever fails to make a shot before the player behind him makes his shot, he is “knocked out” of the game.  The last player remaining wins.

How fair is this game?  That is, if we assume that all players are equally skilled, how important is your choice of starting position in line?  Intuitively, it seems like it would be better to start nearer the end of the line, with the extent of advantage depending on the assumed difficulty of all shots taken.  As usual, my intuition turned out to be wrong (or at least not entirely correct), which is why I think this is an interesting problem.

Let’s model the game by assuming that each player during his turn makes the initial free throw with probability $p$, and (after a miss) makes any following shot with probability $q$.  (My guess at reasonable values for $p$ are somewhere between 0.4 and 0.6, with $q$ somewhere between 0.7 and 0.9.)  Also, let’s assume that players always alternate shots, so that a player never gets two consecutive opportunities to make his shot without the other player shooting.

To make this more precise, the following figure shows the transitions between the five basic game states, with each node representing a shooting situation $s_i$ for the ordered subset of numbered players currently remaining in the game, with the player to shoot indicated in red.

Transitions between game states in Knockout. The numbered player to shoot is shown in red.

(For reference, a simplified two-player variant of this game was discussed earlier this year at Mind Your Decisions.  However, that game is still not quite Knockout as discussed here, even restricting to $n=2$ players and $p=q$.  For example, if players 1 and 2 both miss, then player 1 makes his following shot, he does not immediately win the game.)

Knockout is relatively easy to simulate, but is a bit more challenging to approach analytically.  Like the dice game Pig discussed earlier this year, the problem is that game states can repeat, so a straightforward recursive or dynamic programming solution won’t work.

So, as usual, to present the problem as a puzzle: in the game of Knockout with just $n=2$ players, as a function of $p$ and $q$, what is the probability that the first player wins?

(Hint: I chose $n=2$ not just because it’s the simplest starting point, but because I think the answer is particularly interesting in that case: the probability does not depend on $q$!)

Posted in Uncategorized | 1 Comment

## Calories in, calories out

Introduction

How do we lose (or gain) weight?  Is it really as simple as “calories in, calories out” (i.e., eat less than you burn), or is what you eat more important than how much?  Is “3500 calories equals one pound” a useful rule of thumb, or just a myth?  I don’t think I would normally find these to be terribly interesting questions, except for the fact that there seems to be a lot of conflicting, confusing, and at times downright misleading information out there.  That can be frustrating, but I suppose it’s not surprising, since there is money to be made in weight loss programs– whether they are effective or not– particularly here in the United States.

Following is a description of my attempt to answer some of these questions, using a relatively simple mathematical model, in an experiment involving daily measurement of weight, caloric intake, and exercise over 75 days.  The results suggest that you can not only measure, but predict future weight loss– or gain– with surprising accuracy.  But they also raise some interesting open questions about how all this relates to the effectiveness of some currently popular diet programs.

The model and the experiment

Here was my basic idea: given just my measured starting weight $w_0$, and a sequence $(c_n)$ of measurements of subsequent daily caloric intake, how accurately could I estimate my resulting final weight, weeks or even months later?

More precisely, consider the sequence $(\hat{w}_n)$ of predicted daily weights given by the following recurrence relation:

$\hat{w}_0 = w_0$

$\hat{w}_{n+1} = \hat{w}_n + \frac{c_n - \alpha \hat{w}_n - 0.63 \hat{w}_n d_n}{3500}$

Intuitively, my weight tomorrow morning $\hat{w}_{n+1}$ should be my weight this morning $\hat{w}_n$, plus the effect of my net intake of calories that day, assuming 3500 calories per pound.  Net calorie intake is modeled with three components:

• $c_n$ is the number of calories consumed.
• $-\alpha\hat{w}_n$ is the number of calories burned due to normal daily activity.  Note that this is a function of current weight, with typical values for $\alpha$ of 12 to 13 calories per pound for men, or 10 to 11 for women; I used 12.5 (more on this later).
• $-0.63 \hat{w}_n d_n$ is the number of additional calories burned while running (my favorite form of exercise), where $d_n$ is the number of miles run that day.  Note that we don’t really have to account for exercise separately like this; especially if duration and intensity don’t change much over time, we could skip this term altogether and just roll up all daily activity into the (larger) value for $\alpha$.

(Aside: I am intentionally sticking with U. S. customary units of pounds, miles, etc., to be consistent with much of the related literature.)

So, at the start of my experiment, my initial weight was $w_0=251.8$ pounds (for reference, I am a little over 6’4″ tall, 40-ish years old).  Over each of the next 75 days, I recorded:

• My actual weight $w_n$, first thing in the morning after rolling out of bed, using a digital scale with a display resolution of 0.1 pound.
• My total calories consumed for the day $c_n$.
• My running mileage for the day $d_n$.

Plugging in $c_n$ and $d_n$ to the recurrence relation above, I computed the sequence of predicted weights $(\hat{w}_n)$, and compared with the sequence of my actual weights $(w_n)$.

Results

The following figure shows the resulting comparison of predicted weight $\hat{w}_n$ (in blue) with measured actual weight $w_n$ (in red).  See the appendix at the end of this post for all of the raw data.

Predicted and actual weight over 75 days.

I was surprised at just how well this worked.  Two and a half months and nearly 30 pounds later, the final predicted weight differed from the actual weight by less than a pound!

There are a couple of useful observations at this point.  First, the “3500 calories per pound” rule of thumb is perfectly valid… as long as it is applied correctly.  Zoë Harcombe, a “qualified nutritionist,” does a great job of demonstrating how to apply it incorrectly:

“Every person who didn’t have that [55-calorie] biscuit every day should have lost 141 pounds over the past 25 years.”

This seems to be a common argument– professor of exercise science Gregory Hand makes a similar but slightly more vivid claim using the same reasoning about a hypothetical dieter, that “if she will lose 1 lb for every 3,500 calorie deficit [my emphasis], our individual will completely disappear from the face of the earth in 300 days.”

The problem in both cases is the incorrect assumption that an initial calorie deficit, due to skipping a biscuit, for example, persists as the same deficit over time, causing a linear reduction in weight.  But that’s not how it works: as weight decreases, calorie expenditure also decreases, so that an initial reduced diet, continued over time, causes an asymptotic reduction in weight.  (In the context of the recurrence relation above, Harcombe and Hand’s calculation effectively replaces the varying $\alpha \hat{w}_n$ in the numerator with the constant $\alpha w_0$.)

Estimating $\alpha$

The second– and, I think, most important– observation is that I arguably “got lucky” with my initial choice of $\alpha=12.5$ calories burned per pound of body weight.  If I had instead chosen 12, or 13, the resulting predictions would not agree nearly as well.  And your value of $\alpha$ is likely not 12.5, but something different.  This seems to be one of the stronger common arguments against calorie-counting: even if you go to the trouble of religiously measuring calories in, you can never know calories out exactly, so why bother?

The Harris-Benedict equation is often used in an attempt to remedy this, by incorporating not only weight, but also height, age, gender, and activity level into a more complex calculation to estimate total daily calorie expenditure.  But I think the problem with this approach is that the more complex formula is merely a regression fit of a population of varying individuals, none of whom are you.  That is, even two different people of exactly the same weight, height, age, gender, and activity level do not necessarily burn calories at the same rate.

But even if you don’t know your personal value of $\alpha$ ahead of time, you can estimate it, by measuring calories in $(c_n)$ and actual weight $(w_n)$ for a few weeks, and then finding the corresponding $\alpha$ that yields a sequence of predicted weights $(\hat{w}_n)$ that best fits the actual weights over that same time period, in a least-squares sense.

The following figure shows how this works: as time progresses along the x-axis, and we collect more and more data points, the y-axis indicates the corresponding best estimate of $\alpha$ so far.

Estimating burn rate (alpha) over time. Early estimates are overwhelmed by the noisy weight measurements.

Here we can see the effect of the noisiness of the measured actual weights; it can take several weeks just to get a reasonably settled estimate.  But keep in mind that we don’t necessarily need to be trying to lose weight during this time.  This estimation approach should still work just as well whether we are losing, maintaining, or even gaining weight.  But once we have a reasonably accurate “personal” value for $\alpha$, then we can predict future weight changes assuming any particular planned diet and exercise schedule.

(One final note: recall the constant 0.63 multiplier in the calculation of calories burned per mile run.  I had hoped that I could estimate this value as well using the same approach… but the measured weights turned out to be simply too noisy.  That is, the variability in the weights outweighs the relatively small contribution of running to the weight loss on any given day.)

Edit: In response to several requests for a more detailed description of a procedure for estimating $\alpha$, I put together a simple Excel spreadsheet demonstrating how it works.  It is already populated with the time series of my recorded weight, calories, and miles from this experiment (see the Appendix below) as an example data set.

Given a particular calories/pound value for $\alpha$, you can see the resulting sequence of predicted weights, as well as the sum of squared differences (SSE) between these predictions and the corresponding actual measured weights.

Or you can estimate $\alpha$ by minimizing SSE.  This can either be done “manually” by simply experimenting with different values of $\alpha$ (12.0 is a good starting point) and observing the resulting SSE, trying to make it as small as possible; or automatically using the Excel Solver Add-In.  The following figure shows the Solver dialog in Excel 2010 with the appropriate settings.

Excel Solver dialog showing the desired settings to estimate alpha minimizing SSE.

Conclusions and open questions

I learned several interesting things from this experiment.  I learned that it is really hard to accurately measure calories consumed, even if you are trying.  (Look at the box and think about this the next time you pour a bowl of cereal, for example.)  I learned that a chicken thigh loses over 40% of its weight from grilling.  And I learned that, somewhat sadly, mathematical curiosity can be an even greater motivation than self-interest in personal health.

A couple of questions occur to me.  First, how robust is this sort of prediction to abrupt changes in diet and/or exercise?  That is, if you suddenly start eating 2500 calories a day when you usually eat 2000, what happens?  What about larger, more radical changes?  I am continuing to collect data in an attempt to answer this, so far with positive results.

Also, how much does the burn rate $\alpha$ vary over the population… and even more interesting, how much control does an individual have over changing his or her own value of $\alpha$?  For example, I intentionally paid zero attention to the composition of fat, carbohydrates, and protein in the calories that I consumed during this experiment.  I ate cereal, eggs, sausage, toast, tuna, steak (tenderloins and ribeyes), cheeseburgers, peanut butter, bananas, pizza, ice cream, chicken, turkey, crab cakes, etc.  There is even one Chipotle burrito in there.

But what if I ate a strict low-carbohydrate, high-fat “keto” diet, for example?  Would this have the effect of increasing $\alpha$, so that even for the same amount of calories consumed, I would lose more weight than if my diet were more balanced?  Or is it simply hard to choke down that much meat and butter, so that I would tend to decrease $c_n$, without any effect on $\alpha$, but with the same end result?  These are interesting questions, and it would be useful to see experiments similar to this one to answer them.

Appendix: Data collection

The following table shows my measured actual weight in pounds over the course of the experiment:

Mon     Tue     Wed     Thu     Fri     Sat     Sun
251.8   251.6   250.6   249.8   248.4   249.8   249.0
250.4   249.0   247.8   246.6   246.6   247.8   246.2
246.6   244.0   244.6   243.6   243.6   244.0   244.8
242.0   240.6   240.4   240.2   240.2   239.4   238.6
238.0   238.0   237.6   238.0   238.0   238.6   238.6
237.4   239.0   237.6   235.8   236.0   235.0   236.0
233.8   232.4   232.6   233.4   233.4   232.0   233.2
232.6   231.6   232.2   232.2   231.2   231.2   229.6
229.6   229.6   230.6   230.4   229.8   228.0   227.4
227.6   226.2   226.4   225.6   225.8   225.8   226.0
228.0   225.8   225.4   224.6   223.8


The following table shows my daily calorie intake:

Mon     Tue     Wed     Thu     Fri     Sat     Sun
1630    1730    1670    1640    2110    2240    1980
1630    1560    1690    1700    2010    1990    2030
1620    1710    1590    1710    2180    2620    2100
1580    1610    1610    1620    1690    2080    1930
1620    1680    1610    1610    1810    2550    2430
1710    1660    1630    1710    1930    2470    1970
1660    1750    1710    1740    2020    2680    2100
1740    1750    1750    1610    1990    2290    1940
1950    1700    1730    1640    1820    2230    2280
1740    1760    1780    1650    1900    2470    1910
1570    1740    1740    1750


And finally, the following table shows the number of miles run on each day:

Mon     Tue     Wed     Thu     Fri     Sat     Sun
2.5     0.0     2.5     0.0     0.0     2.5     0.0
2.5     0.0     2.5     0.0     0.0     2.5     0.0
2.5     0.0     2.5     0.0     0.0     3.0     0.0
2.5     0.0     2.5     0.0     0.0     3.0     0.0
2.5     0.0     3.0     0.0     0.0     3.0     0.0
2.5     0.0     3.0     0.0     0.0     3.0     0.0
3.0     0.0     3.0     0.0     0.0     3.0     0.0
3.0     0.0     3.0     0.0     0.0     3.0     0.0
3.0     0.0     3.0     0.0     0.0     3.5     0.0
3.0     0.0     3.0     0.0     0.0     3.5     0.0
3.0     0.0     3.5     0.0

Posted in Uncategorized | 56 Comments

## No, diversity does not generally trump ability

I am pretty sure that my motivation for this post is simply sufficient annoyance.  I admittedly have a rather harsh view of social “science” in general.  But this particular study seems to have enough visibility and momentum that I think it’s worth calling attention to a recent rebuttal.  Where by “rebuttal” I mean “brutal takedown.”

At issue is a claim by Lu Hong and Scott Page, including empirical evidence from computer simulation and even a mathematical “proof,” that “diversity trumps ability.”  The idea is that when comparing performance of groups of agents working together to solve a problem, groups selected randomly from a “diverse” pool of agents of varying ability can perform better than groups comprised solely of the “best” individuals.

“Diversity” is a fun word.  It’s a magnet for controversy, particularly when, as in this case, it is conveniently poorly defined.  But the notion that diversity might actually provably yield better results is certainly tantalizing, and is worth a close look.

Unfortunately, upon such closer inspection, Abigail Thompson in the recent AMS Notices shows that not only is the mathematics in the paper incorrect, but even when reasonably corrected, the result is essentially just a tautology, with little if any actual “real world” interpretation or application.  And the computer simulation, that ostensibly provides backing empirical evidence, ends up having no relevance to the accompanying mathematical theorem.

The result is that Hong and Page’s central claim enjoys none of the rigorous mathematical justification that distinguished it from most of the literature on diversity research in the first place.  And this is what annoys me: trying to make an overly simple-to-state claim– that is tenuous to begin with– about incredibly complex human behavior, and dressing it up with impressive-sounding mathematics.  Which turns out to be wrong.

References:

1. Hong, L. and Page, S., Groups of diverse problem solvers can outperform groups of high-ability problem solvers, Proc. Nat. Acad. of Sciences, 101(46) 2004 [PDF]

2. Thompson, Abigail, Does Diversity Trump Ability? An Example of the Misuse of Mathematics in the Social Sciences, Notices of the AMS, 61(9) 2014, p. 1024-1030 [PDF]

Posted in Uncategorized | 2 Comments

## The discreet hotel manager

The following puzzle deals with storage and search strategies for querying membership of elements in a table.  Like the light bulb puzzle, it’s an example of a situation where binary search is only optimal in the limiting case.  I will try to present the problem in the same weirdly racy context in which I first encountered it:

You are the manager of a hotel that, once a year, hosts members of a secretive private club in $n=10$ numbered suites on a dedicated floor of the hotel.  There are $m=18$ club members, known to you only by numbers 1 through $m$.  Each year, some subset of 10 of the 18 club members come to the hotel for a weekend, each staying in his own suite.  To preserve secrecy, you assign each man to a suite… but then destroy your records, including the list of the particular members staying that weekend.

It may be necessary to determine whether a particular member is staying at the hotel (say, upon receiving a call from his wife asking if her husband is there).  But the club has asked that in such cases you must only knock on the door of a single suite to find out who is residing there.  For a given subset of 10 club members, how should you assign them to suites, and what is your “single-query” search strategy for determining whether any given club member is staying at your hotel?

This problem is interesting because, for a sufficiently large universe $m$ of possible key values, we can minimize the maximum number of queries needed in a table of size $n$ by storing the $n$ keys in sorted order, and using binary search, requiring $\lceil lg(n+1) \rceil$ queries in the worst case.  But for small $m$, as in this problem, we can do better.  For example, if $m=n$, then we don’t need any queries, since every key is always in the table.  If $m=n+1$, then we can store in a designated position the key immediately preceding (cyclically if necessary) the missing one, requiring just a single query to determine membership.

(Hint: The problem is setup to realize a known tight bound: if $m \leq 2(n-1)$, then there is a strategy requiring just a single query in the worst case.)