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 )
where

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:


Last revised on 16 November 2022.