utorok 5. apríla 2016

Programming is thinking!


"In search of a new car, the player picks a door, say 1. The game host then opens one of the other doors, say 3, to reveal a goat and offers to let the player pick door 2 instead of door 1." Taken from wikipedia
A colleague of mine, Lisa DiIorio like saying that writing is thinking. A part of me tends to disagree fiercely, but I still have to find solid evidence that it is not. If I really wanted to argue, I might start proposing writing Vogon poetry or something woefully associative and irrational. On the other hand, I have seen how right she might be. Today Lisa's mantra showed her truth when I tried to solve an old puzzle by ogre-like piece of programming.


I distaste the Monty Hall problem profoundly. My main reason is that it does not figure intuitively. In order to get a reward (a car), you are to guess the correct one of the three doors. As soon as you make your choice (say 1 or 2 here), you are shown that one of the options you have not chosen (3 here) does not get you the reward (a goat is not considered a reward). Should you switch?

I have remembered that I should switch since a student presentation in 2013, though I did not find the argument (proof) easy to reproduce. And it sounded arcane. Similar to the statement that DNA-helicase splits the double stranded DNA – it's name is -ase (analysis), DNA is double-stranded helix ... guess it figures.. I had less enthusiasm for the Monty Hall switching strategy because it lacked even nominal sense. (I did not forget about the proof.)

Thinking about an introduction into probability, Monty Hall came up today. I dared to ask myself – can I look into it properly? I told myself it would be best to write a simulation testing the two alternative strategies: switching vs. not-switching.

The basic architecture of the program is simple: generate N (~1000) random integers between 1 and 3. Do it twice: the first set (array) corresponds to secret locations of the car (Reward), and the other corresponds to the Guesses. Call the strategy function with the two pieces of information and your choice of strategy (not switch or switch) to get your success rate. What does the evaluation (strategy) part function do?

For case of non-switching, it compares corresponding elements of Reward and Guesses and calculates the frequency of such occurrence. By virtue of Law of large numbers this should be close to 1/3.
Let's look at the switching. There are two cases. In the obvious one (A), my original guess was correct, but I dutifully switch to a non-reward option. Bad. In the other case (B), I was wrong, and as I am shown the other incorrect option, I choose the right one.

As I was about to start coding the switching part, the proverbial light-bulb seemed to light up. The probability of the first scenario (A) is 1/3, and it gives me goats. Zero. On the other hand, the second scenario (B) occurs with probability of 2/3, and I always win there. Eureka!

Even though I have a proof, I still run the the program. Winning in 66.75% for a switching 33.19%  for non-switching for runs of 100,000 tries. Job's well done. I suppose I understand the MH puzzle/paradox a bit better.

I guess programming is thinking as well:)

Žiadne komentáre:

Zverejnenie komentára