HIGH_CARD_SIMULATION
Guessing What the Highest Card Is


HIGH_CARD_SIMULATION is a MATLAB program 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 program, 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 GNU LGPL license.

Languages:

HIGH_CARD_SIMULATION is available in a C version and a C++ version and a FORTRAN90 version and a FORTRAN77 version and a MATLAB version.

Related Data and Programs:

BROWNIAN_MOTION_SIMULATION, a MATLAB program which simulates Brownian motion in an M-dimensional region.

COIN_SIMULATION, a MATLAB library which looks at ways of simulating or visualizing the results of many tosses of a fair or biased coin.

DICE_SIMULATION, a MATLAB program which simulates N tosses of M dice, making a histogram of the results.

DUEL_SIMULATION, a MATLAB program which simulates N repetitions of a duel between two players, each of whom has a known firing accuracy.

FAIR_DICE_SIMULATION, a MATLAB program which simulates N tosses of 2 dice, making a histogram of the results.

GAMBLERS_RUIN_SIMULATION, a MATLAB program which simulates the game of gambler's ruin.

HIGH_CARD_PARFOR, a MATLAB program which uses the parfor statement to compute in parallel the statistics for a card game in which you are required to guess the location of the highest card.

ISING_2D_SIMULATION, a MATLAB program which carries out a Monte Carlo simulation of an Ising model, a 2D array of positive and negative charges, each of which is likely to "flip" to be in agreement with neighbors.

LIFE_OPENGL, a C program which uses OpenGL to display the evolution of John Conway's "Game of Life", by Simon Green.

LORENZ_SIMULATION, a MATLAB program which solves the Lorenz equations and displays the solution, for various starting conditions.

MD1, a FORTRAN90 program which carries out a simple molecular dynamics simulation;

MD2, a FORTRAN90 program which carries out a simple molecular dynamics simulation;

MD3, a FORTRAN90 program which carries out a simple molecular dynamics simulation;

MD3GLUE, a FORTRAN90 program which carries out a simple molecular dynamics simulation;

POISSON_SIMULATION, a MATLAB library which simulates a Poisson process in which events randomly occur with an average waiting time of Lambda.

RANDOM_WALK_1D_SIMULATION, a MATLAB program which simulates a random walk in a 1-dimensional region.

RANDOM_WALK_2D_AVOID_SIMULATION, a MATLAB program which simulates a self-avoiding random walk in a 2-dimensional region.

RANDOM_WALK_2D_SIMULATION, a MATLAB program which simulates a random walk in a 2-dimensional region.

RANDOM_WALK_3D_SIMULATION, a MATLAB program which simulates a random walk in a 3-dimensional region.

REACTOR_SIMULATION, a MATLAB program which a simple Monte Carlo simulation of the shielding effect of a slab of a certain thickness in front of a neutron source. This program was provided as an example with the book "Numerical Methods and Software."

ROULETTE_SIMULATION, a MATLAB program which simulates the spinning of a roulette wheel and the evaluation of certain common roulette bets.

SIR_SIMULATION, a MATLAB program which simulates the spread of a disease through a hospital room of M by N beds, using the SIR (Susceptible/Infected/Recovered) model.

SNAKES_AND_LADDERS, MATLAB programs which simulate the game of Snakes and Ladders.

STRING_SIMULATION, a MATLAB program which simulates the behavior of a vibrating string by solving the corresponding initial boundary value problem (IBVP), creating files that can be displayed by gnuplot.

THREE_BODY_SIMULATION, a MATLAB program which simulates the behavior of three planets, constrained to lie in a plane, and moving under the influence of gravity, by Walter Gander and Jiri Hrebicek.

TRAFFIC_SIMULATION, a MATLAB program which simulates the cars waiting to get through a traffic light.

TRUEL_SIMULATION, a MATLAB program which simulates N repetitions of a duel between three players, each of whom has a known firing accuracy.

XISING, a C program which models the variations in ferromagnetism in a material, displaying the results using X Windows.

XWAVES, a C program which simulates the behavior of solutions of certain forms of the wave equation, displaying the results using X Windows.

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:

Examples and Tests:

You can go up one level to the MATLAB source codes.


Last revised on 25 May 2012.