Gilbert–Shannon–Reeds model

Key takeaways

Gilbert–Shannon–Reeds model belongs to science; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect Gilbert–Shannon–Reeds model to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Gilbert–Shannon–Reeds model from memory before moving on to harder problems.

Reference excerpt

In the mathematics of shuffling playing cards, the Gilbert–Shannon–Reeds model is a probability distribution on riffle shuffle permutations. It forms the basis for a recommendation that a deck of cards should be riffled seven times in order to thoroughly randomize it. It is named after the work of Edgar Gilbert, Claude Shannon, and J. Reeds, reported in a 1955 technical report by Gilbert and in a 1981 unpublished manuscript of Reeds.

Description A riffle shuffle permutation of a sequence of elements is obtained by partitioning the elements into two contiguous subsequences, and then arbitrarily interleaving the two subsequences. For instance, this describes many common ways of shuffling a deck of playing cards, by cutting the deck into two piles of cards that are then riffled together. The Gilbert–Shannon–Reeds model assigns a probability to each of these permutations. In this way, it describes the probability of obtaining each permutation, when a shuffle is performed at random. The model may be defined in several equivalent ways, describing alternative ways of performing this random shuffle:

Most similarly to the way humans shuffle cards, the Gilbert–Shannon–Reeds model describes the probabilities obtained from a certain mathematical model of randomly cutting and then riffling a deck of cards. First, the deck is cut into two packets. If there are a total of n {\displaystyle n} cards, then the probability of selecting k {\displaystyle k} cards in the first deck and n − k {\displaystyle n-k} in the second deck is defined as ( n k ) / 2 n {\displaystyle {\tbinom {n}{k}}/2^{n}} . Then, one card at a time is repeatedly moved from the bottom of one of the packets to the top of the shuffled deck, such that if x {\displaystyle x} cards remain in one packet and y {\displaystyle y} cards remain in the other packet, then the probability of choosing a card from the first packet is x / ( x + y ) {\displaystyle x/(x+y)} and the probability of choosing a card from the second packet is y / ( x + y ) {\displaystyle y/(x+y)} . A second, alternative description can be based on a property of the model, that it generates a permutation of the initial deck in which each card is equally likely to have come from the first or the second packet. To generate a random permutation according to this model, begin by flipping a fair coin n {\displaystyle n} times, to determine for each position of the shuffled deck whether it comes from the first packet or the second packet. Then split into two packets whose sizes are the number of tails and the number of heads flipped, and use the same coin flip sequence to determine from which packet to pull each card of the shuffled deck. A third alternative description is more abstract, but lends itself better to mathematical analysis. Generate a set of n {\displaystyle n} values from the uniform continuous distribution on the unit interval, and place them in sorted order. Then the doubling map x ↦ 2 x ( mod 1 ) {\displaystyle x\mapsto 2x{\pmod {1}}} from the theory of dynamical systems maps this system of points to a permutation of the points in which the permuted ordering obeys the Gilbert–Shannon–Reeds model, and the positions of the new points are again uniformly random. Among all of the possible riffle shuffle permutations of a card deck, the Gilbert–Shannon–Reeds model gives almost all riffles equal probability, 1 / 2 n {\displaystyle 1/2^{n}} , of occurring. However, there is one exception, the identity permutation, which has a greater probability ( n + 1 ) / 2 n {\displaystyle (n+1)/2^{n}} of occurring. Thus, for instance, for a standard 52-card deck of cards, a shuffle that does not change the ordering of the cards at all is 53 times more likely than any other individual permutation.

Inverse The inverse permutation of a random riffle may be generated directly. To do so, start with a deck of n cards and then repeatedly deal off the bottom card of the deck onto one of two piles, choosing randomly with equal probability which of the two piles to deal each card onto. Then, when all cards have been dealt, stack the two piles back together.

… excerpt ends here. Continue reading the full article.

Worked examples

Example 1 — a first encounter with Gilbert–Shannon–Reeds model

Start with the simplest possible case. Write down what Gilbert–Shannon–Reeds model claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In science, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Gilbert–Shannon–Reeds model before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Gilbert–Shannon–Reeds model ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Gilbert–Shannon–Reeds model

In research: Gilbert–Shannon–Reeds model appears in science research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses Gilbert–Shannon–Reeds model in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: Gilbert–Shannon–Reeds model is common in secondary-school and first-year university syllabi. It links to neighbouring topics Card shuffling, Stochastic models, so understanding it makes those chapters shorter.
In everyday life: Look for Gilbert–Shannon–Reeds model outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

How to study Gilbert–Shannon–Reeds model in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Gilbert–Shannon–Reeds model means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain Gilbert–Shannon–Reeds model out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Gilbert–Shannon–Reeds model in simple terms?

In the mathematics of shuffling playing cards, the Gilbert–Shannon–Reeds model is a probability distribution on riffle shuffle permutations. It forms the basis for a recommendation that a deck of cards should be riffled seven times in order to thoroughly randomize it.

Why does Gilbert–Shannon–Reeds model matter?

Because it connects several science ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Gilbert–Shannon–Reeds model?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Gilbert–Shannon–Reeds model.