5

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.

Glen_b
  • 257,508
  • 32
  • 553
  • 939
user975917
  • 139
  • 1
  • 8
  • 1
    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](http://hsm.stackexchange.com/) 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) – Glen_b Jul 08 '15 at 01:46

2 Answers2

3

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

Community
  • 1
Tim
  • 108,699
  • 20
  • 212
  • 390
2

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.

paparazzo
  • 433
  • 4
  • 16
  • 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. – meh Dec 28 '16 at 20:52
  • 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. – meh Dec 28 '16 at 21:12
  • @ 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. – meh Dec 28 '16 at 21:19
  • @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. – paparazzo Dec 28 '16 at 21:34
  • 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. – Tim Dec 28 '16 at 22:16