high_card_simulation

high_card_simulation, an Octave code which simulates a game in which you have one chance to select the highest card from a deck.

You are given a deck of DECK_SIZE cards.

Your goal is to select the high card. For convenience, we can assume the cards are a permutation of the integers from 1 to DECK_SIZE, but in fact the user mustn't see such values or else it's obvious which is the largest card. (For a truly difficult problem, we'd have to work harder to disguise the range of values and the likely distribution!)

Your choice is made under the following rules: You may turn over one card at a time. When a card is turned over, you may declare that to be your choice, or else turn over another card. If you have not chosen a card by the end, then your choice is the final card.

If you have no idea what to do, and simply decide in advance to pick a card "at random", that is, for example, you decide to pick the 15th card before having seen any cards, then your probability of winning is 1/DECK_SIZE.

The question is, can you do better than that?

A good strategy is as follows: always look at the first SKIP_NUM cards without choosing them. Then choose the very next card you encounter that is larger than the cards you skipped.

Using this code, you can easily see that skipping 5 cards is much better than picking one at random, skipping 10 is even better, and so on...up to some point, when the benefit begins to disappear. Of course, you can't skip too many cards, and in fact, the results seem to be best for somewhere around 30 to 35 cards skipped. For problems like this, the optimal value is somewhere around 1 / e, where E is the base of the natural logarithm system.

Usage:

high_card_simulation ( deck_size, skip_num, trial_num )

• n is the number of times the dice are thrown.

Licensing:

The computer code and data files described and made available on this web page are distributed under the MIT license

Languages:

high_card_simulation is available in a C version and a C++ version and a Fortran90 version and a MATLAB version and an Octave version and a Python version.

Related Data and codes:

high_card_simulation_test

octave_simulation, an Octave code which uses simulation to study card games, contests, and other processes which have a random element. Usually, the purpose is to try to predict the average behavior of the system over many trials.

Reference:

1. Paul Nahin,
   Digital Dice: Computational Solutions to Practical Probability Problems,
   Princeton University Press, 2008,
   ISBN13: 978-0-691-12698-2,
   LC: QA273.25.N34.

Source Code:

• high_card_probability.m, computes the exact probability that a high card strategy that skips the first K-1 cards and then takes the next card that is higher will actually select the highest card in the whole deck of N cards.
• high_card_simulation.m, the code.
• high_card_shuffle.m, a secondary code, which tries to compute, for small N, a sequence of integers that could be used as the values of the cards in the high card guessing game, in a way that guarantees that the values of the cards seen so far give no clues as to what the maximum card actually is.