Robert Scoble, a Technical Evangelist at Microsoft, just came around and interviewed me (and a few other people on our team) for Channel 9 - look for the video to be there in a week or two.
If I'd known I was going to be on TV I would have brushed my hair this morning.
Reams and reams have been written about the Monty Hall problem, but no-one seems to have mentioned a simple fact which, once realised, makes the whole thing seem intuitive.
The Monty Hall show is a (possibly fictional, I'm not sure) TV gameshow. One couple have beaten all the others to the final round with their incredible skill at answering questions on general knowledge and popular culture, and now have a chance to win a Brand New Car. There are three doors. The host explains that earlier, before the couple arrived, a producer on the show rolled a dice. If a 1 or a 4 was rolled, the car was placed behind the red door. If a 2 or a 5 was rolled, it was placed behind the blue door and if a 3 or a 6 was rolled, it was placed behind the yellow door.
The host invites the couple to pick which door they think the car is behind. He then opens one of the other two doors and there's no car behind the door! (He knows where the car is, so he can always arrange for this to happen). Then the host asks the couple if they want to change their mind about which door they think the car is behind. Should they change? Does it make a difference.
Most people's first reaction is that it can't matter. How can it? The car has a one in three chance of being behind each of the doors.
No-one would argue that the car has anything but a probability of 1/3 of being in behind the door the couple picked (say it's the red door). But when the host opens the blue door, magic happens. The probability of the car being behind the blue door suddenly goes to zero. The probability can't vanish (otherwise there would only be a 2/3 probability of there being a car at all) and it can't go to the red door so this ghostly 1/3 probability-of-there-being a car goes to the yellow door. The car now has a 2/3 probability of being behind the yellow door. "Poppycock!" most people would say. Probability isn't this "magic stuff" that can travel between doors. But the correct answer is that the couple should change doors - the car really does have a 2/3 probability of being behind the yellow door.
If you're in doubt, you could simulate the situation with a computer program, run it lots of time for the choices "never change doors" and "always change doors" and see what fraction of the time in each case the couple wins the car. You will find that changing makes you win 2/3 of the time, and sticking 1/3. Or you could enumerate the possibilities:
1/3: Couple picks correct door in the first place. If they change, they lose.
2/3: Couple picks the wrong door. The other wrong door is then eliminated, so if they change, they win.
So changing has a 2/3 probablity of winning. This reasoning sounds like a more plausible argument for changing doors.
The key to this matter, and what makes the whole thing confusing to those who don't realise this, is that probability depends on what you know. If you think about this for a while, it becomes obvious. A fair coin, when tossed, has a 50% probability of landing on heads. However, once the event has happened, the probablity collapses to 0% (if it landed tails up) or 100% (if it landed heads up). Let event A be the tossing of a coin at noon, and success defined by the coin landing heads up. At five seconds to noon the probability of success is 0.5. At five seconds past noon, when everybody can see that the coin landed heads up, the probability of success is 1.0. If the coin is tossed and it rolls under the sofa, then at five seconds past there is still a 50% chance of success. Although the coin has landed, no-one knows what the result is. Probability depends on what you know. If you know nothing about the coin, the probability of success is 0.5.
Suppose a neutral third party is the only one to see the coin, and says "I'm not going to tell you what it says, but I'm going to roll a dice (behind your back, so you can't see it). If it comes up even, I'll say "heads", whatever the coin says. If it comes up odd, I'll say what the coin says. But I won't tell you whether the dice came up odd or even." Suppose this third party then tells says "heads". There's a 50% chance that this was because he rolled an even number and a 50% chance that that's what the coin really said. What is the probability of success now? Well, we can enumerate the possibilities again and notice that of the four equally likely possibilities (Heads+even, Heads+odd, Tails+even, Tails+odd) the only one we've eliminated is Tails+odd, since in that case he would have said "tails". Of the remaining three possibilities (which are still equally likely), two of them involve success so the probability of success is 2/3. We can check this as follows: He says "heads" three out of four times, so the probability of success is (2/3)*(3/4)+0*(1/4)=2/4=1/2 (since we know there is 0 probability of success if he says "tails"). This is the answer we expected.
We conclude that, by cleverness, we can do a "partial collapse" of the probability by finding out a bit of information (if not all of it). In this case the knowledge that the neutral third party said "heads" doesn't give as much information about the state of the coin as seeing the coin itself - it doesn't tell us for definite whether we have heads or not, but it does impart enough information to change the probability.
This is exactly what happens in the Monty Hall problem. The host imparts some information to the couple about which door the car is behind, but not enough to tell for the couple to tell for definite which door the car is behind - just enough to shift the probability in favour of the door which they would choose if they opted to "change". If it was a complete probability collapse (i.e. if he opened any two doors) no-one would be in any doubt as to whether they should change or not. It's just because the probability has only partially collapsed that people get confused.
Justin sent me this email:
I read your paper on "Monte Hall Strikes Back." and absorbed that probability depends on what you know. Following is the question that I made up and is having trouble "partial collapsing" it. Maybe you can help me out with an insight:
There are two doors, door #1 and door #2 behind which two real numbers are written at random. You get a prize if you choose the door with larger real number. At this point, the probability of winning a prize is 1/2. However, you get a chance. You first choose a door, and Monty shows you the number behind that door. What should you do in order to do better than 1/2? Or is it even possible to do better than 1/2?
The answer to the question hinges on how these two real numbers are chosen. If all real numbers are equally likely, you can never do better than 1/2 because for any real number x the size of the set of real numbers smaller than x is exactly the same size as the set of real numbers larger than x (this is easy to prove, just pair them up: for all y>0, pair up x-y with x+y).
Of course, the game can't work like that in the real world because most of the real numbers are extremely large (either positive or negative) and require more atoms than there are in the universe to write down.
Suppose we have a more reasonable probability distribution for 
John de Pillis, a Professor of Mathematics at University of California in Riverside, emailed me to let me know about a graphical "proof" that switching doors (or cups in this case) improves your chances of success. If you're still confused, his diagram might help.
This diagram appears in John's book "777 Mathematical Conversation Starters", published by the Mathematical Association of America.
A new initiative at Microsoft means that everyone (at least in my division, not sure about others) has to spend at least 4 hours a month interacting with customers and partners. It's a good idea in principle but unfortunately I have never actually had occasion to seriously use the tools I write - I've never written any software targetting the .NET Compact Framework other than trivial programs to test my own work. Therefore I'm really not the person to answer the sort of questions my customers ask.
Fortunately I found a loophole - I have to interact with customers, but they don't necessarily have to be my customers. I've started a work blog here which talks about C++ and general programming techniques. I'll continue to post here just as frequently (posting here less frequently would be extremely difficult) and will continue to talk about the same things, as the sort of things I talk about here would probably not be appropriate for my work blog.
We went to one of our favourite strip-mall Italian restaurants on Friday night, and would you believe it? They had run out of spaghetti. Imagine that - an Italian restaurant that had run out of spaghetti. Well we didn't have to. The very concept still boggles my mind.
This is pretty funny, and fairly accurately represents some of my views on the whole Microsoft dividend thing last week.
I finally got my 8253 timer project finished. One minor hurdle that I didn't anticipate is that MESS's abstraction of the host computer's soundcard and its emulated CPU aren't synchronized. The soundcard is supposed to request samples from the emulated CPU at 44.1KHz, but according to the emulated CPU it seems to be doing it slightly faster than that (or the emulated CPU is running slightly slow by the soundcard's standard) so my buffer keeps underrunning.
The way to fix this is to tell the CPU to generate samples at a slightly higher rate (according to its clock) so that the soundcard and the CPU stay in sync. The trouble is, I don't know exactly how much faster the soundcard is than the CPU. Besides which, it seems to fluctuate and the ratio may even be completely different on a different machine.
The next thing I tried was dynamically adjusting the sample rate 60 times a second to the value which was calculated for the previous time-period. The problem with this was that the variations in the sample rate could sometimes be quite large, and the resulting "flutter" of the emulated computer's soundtrack sounded absolutely awful. Also, the buffer might now be slightly less full than optimal (leaving little room for further error) or slightly more full than optimal (causing the soundtrack to "lag" behind the graphics a bit). Clearly the most elegant way to solve this would be to smooth out these variations in such a way that the average sample rate over long time would be correct.
Next, I set up a running total of the "drift" time, and adjusted the sample rate in proportion to this. Of course, this caused the sample rate to oscillate around the correct value - I needed some damping to remove "energy" from the system. A couple of pages of calculations later I had modelled the system with a second order differential equation and solved for the critical damping value. After some tweaking of the buffer length and time-constant values it now works wonderfully - no buffer underruns, no noticable flutter and the graphics and sound are fairly well synchronized.
The only problem now is the aliasing - the 8253 timer in the PC can generate frequencies of up to almost 600KHz, and because of the rather unscientific way I'm downsampling that high-frequency waveform down to 44,100Hz (roughly) all the harmonics too high for the soundcard to play are aliased down to frequencies between 0 and 22,050KHz (roughly) so when you attempt to play a square wave, you get a whole pile of harmonics you weren't expecting and it sounds rather less than perfect. Since the sampling rate drifts up and down, playing a constant high-pitched tone makes all sorts of swooping noises. I wonder if it would be feasable to use a proper finite impulse response filter to downsample while removing all the frequencies that are too high-pitched to play...
For those rare few of you for who are not interested in all this geek stuff, here are some rather spectacular mazes.
Yesterday, I discovered that there is incontrovertible proof that aliens from outer space landed in the U.S. and that this was known by various authorities, right up to President Bill Clinton.
This is not a hoax - everything you are about to read is absolutely true.
The aliens touched down at runway 15 of the Kennedy Space Center in Florida, at 10:54:34am EDT on July 7th, 1995, and came from the (then) largest spacecraft ever observed in orbit around Earth.
The names of the aliens were Vladimir Dezhurov and Gennadiy Strekalov. They were cosmonauts aboard the Russian Mir space station. When the space shuttle Atlantis docked with Mir during mission STS-71 (forming the then largest spacecraft ever in orbit) these two cosmonauts were transferred to Atlantis and brought back to Earth.
U.S. entry visas for Dezurov and Strekalov were forgotten before the launch of the spacecraft that took them to Mia. The U.S. State Department had to ask for a waiver for "aliens from outer space". The INS agreed not to arrest the cosmonauts for illegal entry into the United States.
I had a meeting with my manager's manager today. Managers' managers at Microsoft like to have a chat with their direct reports' direct reports occasionally to make sure they're happy there, that everything is going to plan and to give them a chance to tell them anything they might not want to tell their managers directly.
(By the way, those of you who don't know where to put your apostrophies, or who get the words "their", "they're" and "there" mixed up might want to study the previous paragraph in detail and bookmark this post for future reference. You know who you are.)
Anyway, most of said meeting went very well - I talked about some of the features that I thought it was important that we implement, and justified these with my theories on how the uses of Pocket PCs and Smartphones will change in the future. However, at one point in the conversation I did a terrible thing - a thing of which I am greatly ashamed. I used the word "paradigm". I couldn't help it. Words were coming out of my mouth, and as the thought formed and turned into a sentence I could see that word coming but could do nothing to stop it. The good, decent part of my brain was screaming "find a synomym, quick, you moron" but I couldn't think of one before it was too late and the word was out there in the air like a particularly malodorous flatulation.
Please comment with your suggestions on how I should atone for this atrocity.
One of my ongoing projects is getting old computer games (particularly the old Windmill Software games) to run properly on modern hardware. One technique for doing this that I have recently been experimenting with is emulation - specifically, the Multiple Emulator Super System. This is almost there, as it features cycle-exact emulation of an 8088 processor and hardware-level emulation of a CGA card, thus getting the graphics and speed just right for these old games.
The one place MESS falls down is its emulation of the 8253 Programmable Interval Timer. This small but very important circuit exists almost unchanged in every PC ever made (as well as a number of other computers such as the Telenova Compis, the INDATA DAI, the Sharp MZ-700 and the Tesla PMD-85).
In modern operating systems, the 8253 is used by the task scheduler to interrupt whatever the machine is currently doing so that another program can get a chance at running, but these old games used it for advanced sound effects and "random" number generation. As such, they generally pushed it to the limits of its capabilities, so a very accurate emulation is needed to get these games to work properly.
The 8253 is well documented but unfortunately (though understandably) all the documentation available is written for people who want to program the thing or build a computer a which uses it, rather than for people who want to duplicate its functionality in an emulator. So there are a number of obscure edge-cases like "what happens if you do x, but half way through you do y" which aren't documented. In the interests of accuracy, I want to get these edge cases to work just as they would on the real hardware.
I'm finding myself having to do some real science to figure out the internals of this chip - formulating hypotheses and devising and running experiments to prove or disprove these hypotheses, and gradually constructing a "grand unified theory of the 8253" (if you will). Sometimes it's pretty straightforward, but other times tne observations must be made indirectly. For example, some of these experiments require timing as accurate as a millionth of a second, but this is a fraction of the time it takes to actually read data from or write data to the device in question. So the only way to do these experiments is to fire a whole load of data at the chip ("tuned" to maximize the probability of creating the desired event), record what comes back and then sort through the results (sometimes using statistical methods) to figure out if the edge case that I'm trying to reproduce actually happened, and if so what the result was. If the experiment is run enough times, hopefully the event I'm looking for will actually happen. It's quite a lot like doing high energy particle physics, except I'm searching for logic gates instead of Higgs bosons.
The bathroom sink was draining really slowly, so I decided to remove the U-bend and clean it out. You would not believe the evil things that lurked in there - a foul-smelling black, grey and green sludge held together with human hair. I would have taken a picture of it, but it was so unholy I doubt it would show up in photographs (like vampires in that respect). Hours and a long hot shower later, I still feel dirty.
When people buy houses and make improvements to them, invariably some walls are removed ("We'll knock through here" or "Let's pull this wall down and make this all one big space"). But you never hear of people putting up new walls as part of home improvements ("I think we need a wall here"). So either the average number of walls per house is falling rapidly (clearly an unsustainable situation) or new walls are creeping in from somewhere else. I suspect it is a bit like mould in some houses - "damn, another new wall has sprung up - we'll have to knock through here". I wonder how bad it gets - maybe some people have to keep a sledgehammer by the bed in order to be able to leave the bedroom in the morning.
Anyway, go and play this flash game. It will make you happy.
This pigeon was nesting out on the hallway for a while.
Esmerelda
Greg
Greg sheds his entire winter coat in one night
Greg gets a manicure
Greg in his favourite hiding spot under the skirting of the Christmas tree
Esme has an afternoon snack of Christmas tree
Our heroes enjoy some tasty grass from the lawn.
![P(x <= r<= x+dx) = f(r)dx[/latex]. Then, given the value behind the first door, [latex]x[/latex], you can calculate the probability of [latex]y[/latex] (the number behind the second door) being less than [latex]x[/latex], [latex]\displaystyle P(y < x) = \int_{-\infty}^xf(r)dr = F(x)[/latex], and switch doors if [latex]P(y<x)<\frac{1}{2}[/latex]. Using this strategy you can calculate your probability of winning before knowing x and without even knowing the distribution! [latex]P(win; F(x)>\frac{1}{2}) = F(x)](https://s0.wp.com/latex.php?latex=P%28x+%3C%3D+r%3C%3D+x%2Bdx%29+%3D+f%28r%29dx%26%2391%3B%2Flatex%26%2393%3B.+Then%2C+given+the+value+behind+the+first+door%2C+%26%2391%3Blatex%26%2393%3Bx%26%2391%3B%2Flatex%26%2393%3B%2C+you+can+calculate+the+probability+of+%26%2391%3Blatex%26%2393%3By%26%2391%3B%2Flatex%26%2393%3B+%28the+number+behind+the+second+door%29+being+less+than+%26%2391%3Blatex%26%2393%3Bx%26%2391%3B%2Flatex%26%2393%3B%2C+%26%2391%3Blatex%26%2393%3B%5Cdisplaystyle+P%28y+%3C+x%29+%3D+%5Cint_%7B-%5Cinfty%7D%5Exf%28r%29dr+%3D+F%28x%29%26%2391%3B%2Flatex%26%2393%3B%2C+and+switch+doors+if+%26%2391%3Blatex%26%2393%3BP%28y%3Cx%29%3C%5Cfrac%7B1%7D%7B2%7D%26%2391%3B%2Flatex%26%2393%3B.+Using+this+strategy+you+can+calculate+your+probability+of+winning+before+knowing+x+and+without+even+knowing+the+distribution%21++%26%2391%3Blatex%26%2393%3BP%28win%3B+F%28x%29%3E%5Cfrac%7B1%7D%7B2%7D%29+%3D+F%28x%29&bg=ffffff&fg=000000&s=0 "P(x <= r<= x+dx) = f(r)dx[/latex]. Then, given the value behind the first door, [latex]x[/latex], you can calculate the probability of [latex]y[/latex] (the number behind the second door) being less than [latex]x[/latex], [latex]\displaystyle P(y < x) = \int_{-\infty}^xf(r)dr = F(x)[/latex], and switch doors if [latex]P(y<x)<\frac{1}{2}[/latex]. Using this strategy you can calculate your probability of winning before knowing x and without even knowing the distribution! [latex]P(win; F(x)>\frac{1}{2}) = F(x)")