5
$\begingroup$

Based on some references I got from another question I learned that:

While convalescing from an illness in 1946, Stan Ulam was playing solitaire. It, then, occurred to him to try to compute the chances that a particular solitaire laid out with 52 cards would come out successfully (Eckhard, 1987).

Interest piqued, I googled on an write up on what Ulam would have done but came up empty handed -- I found countless mentions of this episode but nothing that was step by step.

I found the original paper by Eckhard, here, but again it does not address the application to MCMC

So Question:

Does anyone have a pretty introductory write up on how Ulam applied MCMC to solitaire?

Thanks.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ While this is on-topic here, if you don't get a good response here within a couple of days, you may like to flag your post to try migrating to History of Science and Mathematics SE to see if it fares better there (it's better not to cross post). If you want to do that, you should first check their help for what's on-topic which should give some idea of what they expect in a question (i.e. you may need to edit to make it on topic there; any such changes would need to be made prior to migration) $\endgroup$
    – Glen_b
    Commented Jul 8, 2015 at 1:46

2 Answers 2

Reset to default
3
$\begingroup$

As already said by Paparazzi, the paper is about Monte Carlo method, not Markov Chain Monte Carlo. MCMC is just a part of a broader family of Monte Carlo methods (i.e., informally, using simulation to solve statistical problems).

This is actually described in the referred paper

[...] I was convalescing from an illness and playing solitaires. The question was what are the chances that a Canfield solitaire laid out with 52 cards will come out successfully? After spending a lot of time trying to estimate them by pure combinatorial calculations, I wondered whether a more practical method than "abstract thinking" might not be to lay it out say one hundred times and simply observe and count the number of successful plays. [...]

So it's pure Monte Carlo: he simulated a number of plays and then counted the number of events of interest among the all simulated events. It was obtained using a direct simulation.

Actually MCMC was discovered later with Metropolis algorithm being the first MCMC algorithm as described in A Short History of Markov Chain Monte Carlo: Subjective Recollections from Incomplete Data paper by Robert and Casella (2011).

Improve this answer
$\endgroup$
2
$\begingroup$

But there is no evidence he used Markov chain Monte Carlo. There is no reason to use a probability distribution. You just shuffle the deck and get a random deck - straight up Monte Carlo. See Fisher Yates for random shuffle.

Improve this answer
$\endgroup$
5
  • $\begingroup$ I always thought that Ulam came to Monte Carlo, and not MCMC via the solitaire example. However I believe that Metropolis as in Metropolis-Hasting algo was at Los Alamos with Ulam . There is a wonderful article by Diaconnis called something like "THE MCMC revolution" which has a rather nice example of using MCMC to decode encrypted documents. $\endgroup$
    – meh
    Commented Dec 28, 2016 at 20:52
  • $\begingroup$ I beg to differ. Perhaps OP has asked a question for which the technical answer is "there is no evidence". However, while tangential, I think my comments might be of interest to OP. Feel free to act on your theory and just not reply to this. $\endgroup$
    – meh
    Commented Dec 28, 2016 at 21:12
  • $\begingroup$ @ Paparazzi Did you read my first comment ? It says explicitly, that Ulam used in your words "straight up" Monte Carlo. So my final comment to you is , meh. Feel free to continue posting, I'll read, but I am done. $\endgroup$
    – meh
    Commented Dec 28, 2016 at 21:19
  • $\begingroup$ @aginensky Read my answer. MCMC is an algorithm not a place. If you are getting a shuffles with a probability distribution rather than random it is a crooked house. This is gone not where. $\endgroup$
    – paparazzo
    Commented Dec 28, 2016 at 21:34
  • $\begingroup$ Perhaps you can go into more details or back up your answer with some references? Basically I agree, the paper is about how Ulam discovered Monte Carlo, not MCMC. MCMC is just a part of multiple different Monte Carlo algorithms and methods. $\endgroup$
    – Tim
    Commented Dec 28, 2016 at 22:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.