September 2008 - Posts

A Twist on the Monty Hall Problem
26 September 08 09:56 PM | Scott Mitchell

Steve Smith has posted a couple of interesting probability problem solvers on his blog recently. His most recent one is a twist on the Monty Hall problem. I mentioned the Monty Hall problem and its solution in an earlier blog entry of mine, For Some Probability Problems, Seeing Can Be Believing:

When facing a particularly tough probabilty problem sometimes it helps to sit down and draw out the possible outcomes for the given scenarios. In doing so, things that may otherwise seem very complex boil down to a very apparent solution or explanation.

A great example of simplicity through diagraming is the Monty Hall problem, which goes like this: You are a contestant on the TV game show, Let's Make a Deal and are presented with three doors. Behind one door there is a luxury car. Behind the other two doors there is a poster of a car. The game show host asks you to pick a door. After choosing one, the game show host reveals one of the other doors that has a poster behind it and then asks you if you want to change your door choice to the other unopened door. What is the best strategy?”

The answer is that you should change the door you had selected, because there's a 2/3 probability that the door you did not select houses the luxury car. In other words, there is a 2/3 probability that the door you picked has the remaining poster. The solution seems backwards. It seems paradoxical that the door the host reveals to have a poster of a car could have any influence on your initial selection. But if you sit down and draw out the various probabilities you can see that there's there are more good outcomes if you make the switch than if you hold fast to your initial choice. The following diagram was created by Rick Block; here, instead of a poster of a car you get a goat. Same difference.

Steve's most recent puzzle asks what would happen if instead of a single contestent in the Monty Hall problem there were multiple participants:

I take 3 plain envelopes and put a $100 bill inside one of them, seal them, and give one to you, one to Bob, and one to Carrie, at random. Then I randomly ask one of you to open an envelope - for the sake of argument let's say I choose Carrie. Carrie opens her envelope to reveal that it is empty. Now I offer you the choice to trade envelopes with Bob - should you trade? And now I ask Bob the exact same question. Should he trade?

As written, Steve's problem isn't that interesting. If he is randomly choosing one envelope to open then there is no advantage to be gained by changing or not changing your envelope. Now, if Steve were to reword the problem as follows (as I believe was his intention), then things are a bit more interesting:

I take 3 plain envelopes and put a $100 bill inside one of them. I then let you choose one, and then give the other two to Bob and Carrie. I then open one of the envelopes (Carrie's or Bob's) knowing that it is empty. Now I offer you the choice to trade envelopes with Bob - should you trade? And now I ask Bob the exact same question. Should he trade?

There is a big difference between these two questions. In the first one, everything is random; in the second one, the host (Steve Smith) knowingly opens one of the envelopes that is empty. It's also important that the host is forced to open Bob or Carrie's envelope, and cannot attempt to open yours.

The answer to this problem can be worked out the same way as the traditional Monty Hall problem - by putting pen to paper and drawing out the probability tree, although I used the name Cal instead of Carrie. (See the full size image...)

As you can see, your odds are maximized if you get your hands on your contestant's envelope, while your opponent's best bet is to keep his envelope. Therefore, whoever gets to make the final change is the person with the best odds.

Another tool for determining how a probability puzzle works out is through empirical means. You can oftentimes write a terse program that simulates the problem at hand thousands of times and tallies up the various outcomes. I created such a program in C#.

1 for (int iter = 0; iter < ITERATIONS; iter++)

2 {

3 int moneyPos = rnd.Next(3);

4 int bucketChoice = 2;

5 int openDoor = rnd.Next(2);

6 if (moneyPos == openDoor)

7 openDoor = 1 - openDoor;

8 int oponentsPos = 1 - openDoor;

9

10 bool makeSwap = rnd.Next(2) % 2 == 0;

11 bool otherContestantMakesSwap = rnd.Next(2) % 2 == 0;

12

13 if (makeSwap)

14 {

15 tmp = bucketChoice;

16 bucketChoice = oponentsPos;

17 oponentsPos = tmp;

18 }

19

20 if (otherContestantMakesSwap)

21 {

22 tmp = bucketChoice;

23 bucketChoice = oponentsPos;

24 oponentsPos = tmp;

25 }

26

27 // See if we won

28 if (bucketChoice == moneyPos)

29 {

30 if (makeSwap && otherContestantMakesSwap)

31 numberOfWinningsWhenSwappingAndContestantSwaps++;

32 else if (makeSwap && !otherContestantMakesSwap)

33 numberOfWinningsWhenSwappingAndContestantStays++;

34 else if (!makeSwap && otherContestantMakesSwap)

35 numberOfWinningsWhenStayingAndContesstantSwaps++;

36 else

37 numberOfWinningsWhenStayingAndContesstantStays++;

38 }

39 else if (moneyPos == oponentsPos)

40 {

41 if (makeSwap && otherContestantMakesSwap)

42 numberOfContestantWinsWhenYouSwapAndContestantSwaps++;

43 else if (makeSwap && !otherContestantMakesSwap)

44 numberOfContestantWinsWhenYouSwapAndContestantStays++;

45 else if (!makeSwap && otherContestantMakesSwap)

46 numberOfContestantWinsWhenYouStayAndContestantSwaps++;

47 else

48 numberOfContestantWinsWhenYouStayAndContestantStays++;

49 }

50 }

51

52 // Summarize results

53 Console.WriteLine("Percentage of Wins When Swapping and Contestant Swapping: {0}", Convert.ToDecimal(numberOfWinningsWhenSwappingAndContestantSwaps) / Convert.ToDecimal(ITERATIONS));

54 Console.WriteLine("Percentage of Wins When Swapping and Contestant Stays: {0}", Convert.ToDecimal(numberOfWinningsWhenSwappingAndContestantStays) / Convert.ToDecimal(ITERATIONS));

55 Console.WriteLine("Percentage of Wins When Staying and Contestant Swapping: {0}", Convert.ToDecimal(numberOfWinningsWhenStayingAndContesstantSwaps) / Convert.ToDecimal(ITERATIONS));

56 Console.WriteLine("Percentage of Wins When Staying and Contestant Stays: {0}", Convert.ToDecimal(numberOfWinningsWhenStayingAndContesstantStays) / Convert.ToDecimal(ITERATIONS));

57 Console.WriteLine("");

58 Console.WriteLine("Percentage of Contestant Wins When Swapping and Contestant Swapping: {0}", Convert.ToDecimal(numberOfContestantWinsWhenYouSwapAndContestantSwaps) / Convert.ToDecimal(ITERATIONS));

59 Console.WriteLine("Percentage of Contestant Wins When Swapping and Contestant Stays: {0}", Convert.ToDecimal(numberOfContestantWinsWhenYouSwapAndContestantStays) / Convert.ToDecimal(ITERATIONS));

60 Console.WriteLine("Percentage of Contestant Wins When Staying and Contestant Swapping: {0}", Convert.ToDecimal(numberOfContestantWinsWhenYouStayAndContestantSwaps) / Convert.ToDecimal(ITERATIONS));

61 Console.WriteLine("Percentage of Contestant Wins When Staying and Contestant Stays: {0}", Convert.ToDecimal(numberOfContestantWinsWhenYouStayAndContestantStays) / Convert.ToDecimal(ITERATIONS));

I set ITERATIONS to 50,000 and let 'er rip. The following output confirmed my initial assumptions:

Percentage of Wins When Swapping and Contestant Swapping: 0.08266
Percentage of Wins When Swapping and Contestant Stays: 0.16618
Percentage of Wins When Staying and Contestant Swapping: 0.16482
Percentage of Wins When Staying and Contestant Stays: 0.08318

Percentage of Contestant Wins When Swapping and Contestant Swapping: 0.16754
Percentage of Contestant Wins When Swapping and Contestant Stays: 0.08386
Percentage of Contestant Wins When Staying and Contestant Swapping: 0.08262
Percentage of Contestant Wins When Staying and Contestant Stays: 0.16914

As you can see, your chances of winning are best when you swap and your contestant stays or when you stay and your contestant swaps - namely, when you get your hands on your contestant's envelope. Your contestant, however, does best when he hangs onto his envelope, either by having you both stay or both change.

Filed under:
Transferring Large Files
19 September 08 01:29 PM | Scott Mitchell

Every couple of weeks or so I seem to have a need to transfer (or receive) a relatively large file to another colleague or client. It might be a database zipped up into a 50 MB file, artwork totalling hundreds of megabytes, or various DLLs and source code. Over the course of my career I have used the following techniques for transferring data:

  • E-mail - the most straightforward technique for sharing data. The major con is that many email providers reject attachments over a certain threshold, usually in the 2-10 MB range. Also, e-mail is inherently insecure, making it a non-ideal medium for transferring sensitive data like passwords, credit card numbers, social security numbers, and so on.
  • Upload/Download from a Website - if you have write access to a website you can always upload the data to share and then send a URL to the file(s). The downside here is that you need a website. Security also requires a few extra steps - you need to have some mechanism to only allow the intended recepient from downloading the article.

    Side story: Back in 2002 Microsoft released Web Matrix, which later became Visual Web Developer Express Edition. Prior to announcing the release Microsoft and asp.netPRO Magazine asked me to write an overview of the tool to be included in the asp.netPRO edition that came out right when the product was released officially. There were a group of other ASP.NET folks at the time who also knew about this project and were invited to review my article. I distributed it by putting the article up on a website and provided this group a link to download the article. A couple days later I left for a short vacation during which I did not check e-mail or phone messages.

    The day I left town one of the reviewers leaked the article to Neowin.net, which linked directly to the URL on my website. Shortly after the link was published on Neowin.net I started getting e-mails and phone calls from Scott Guthrie asking me to take down the link. Of course, I did not get these messages until a few days later upon return from my vacation.

    I never did find out who leaked the link/article. I guess it didn't really matter in the end, and it wasn't the article on my server that caused the leak as someone else sent in the link to Neowin.net and they could have just as easily sent the Microsoft Word document. But still, I was rather red-faced when having to explain to the guys at Microsoft why the article was accessible to anyone on the Net and why it took so long to get the article down once it had been compromised.
  • Use a Third-Party Service - there are a plethora of web-based services that are built to allow large files to be transferred between two individuals. Most work by you uploading a file to a site, where it is stored temporarily. You then e-mail the recipient a link to download the attachment. I have used the free service TransferBigFiles.com many times and heartily recommend them. You could also use DropBox and place the file to share in the Public folder. The benefit of this approach is that you don't need a website; however, the security concerns remain. In fact, you might consider the security concerns even (slightly) greater because you are now adding an intermediary into the equation (the folks at TransferBigFiles.com or at DropBox).
  • Physically Deliver the Data - the most secure option is the physically deliver the data - put it on a thumb drive or burn it to a DVD and then mail or hand deliver the data. This approach takes the most work, but is the most secure, especially if you hand deliver the data. And if you are transferring extremely large amounts of data - terrabytes, let's say - this approach would likely be the fastest.

    I used this approach 8 years ago when transferring large amounts of information between myself and a publisher. At the time I only had dial-up access. When the publisher needed to send me several hundred megabytes worth of materials - mostly artwork from previous editions - it was more efficient to mail me a CD. I also had a student in one of my Web Services class, must have been four years ago or so, whose company was running computer simulations that would output several GBs worth of data per test run. To send the day's test data to another facility they would plug in an external hard drive, copy over the data, and then use a mail carrier to overnight deliver the drive. I wonder what techniques they use today.

How do you share large files with others?

Filed under:
Search Your Site Using Google's Custom Search Engine
15 September 08 08:51 AM | Scott Mitchell

Remember when people used to debate what search engine was the best among the bunnch? Do you remember back in the day when Yahoo! differentiated itself from other search engines by having actual human beings catalog, summarize, and rate large swaths of the World Wide Web? Today, search is a commodity. It's ubiquitous. Web surfers expect there to be a search box and expect accurate results returned in the blink of an eye. Because of these expectations, it's now more important than ever that your website offers search. I don't care if the site has only five static web pages that only get updated once in a blue moon, you still need search.

The good news is that Google offers free tools for quickly and easily adding search to your site. With Google's Custom Search Engine (CSE) you can add search to your site within a matter of minutes. All it takes is configuring a few settings and then copying and pasting a snippet or two of HTML and JavaScript into your site. A couple of months ago I used CSE to add search to this blog. You can find the search interface in the upper right hand corner of every page or by visiting the Search page.

To learn how to add a search engine to your site using CSE check out my latest article on DotNetSlackers: Implementing Search in ASP.NET with Google Custom Search.

Site Note: Another technique for making your site more searchable is to create an OpenSearch provider. By adding a simple XML file to your website you can have your site searchable through the search box that's baked into the user interface of browsers like Internet Explorer and Firefox. Learn more about this technique by reading: Helping Visitors Search Your Site By Creating an OpenSearch Provider.

Three's Company, Too
09 September 08 10:24 PM | Scott Mitchell

I try to keep this blog tightly focused on technical issues, but I wanted to share this happy bit of news: on September 1st my wife gave birth to our daughter, Alice Mitchell. Mom & baby are healthy and happy.

If you'd care to read a bit more about this, I've blogged about it on my personal blog, ScottOnLife.com: Then There Were Three.

Filed under:
September's Toolbox Column Online
09 September 08 09:47 AM | Scott Mitchell

My Toolbox column in the September 2008 issue of MSDN Magazine is avaiable online. The September issue examines:

  • LINQPad - A free stand-alone LINQ editor/tester created by Joseph Albahari, author of C# 3.0 in a Nutshell. LINQPad is like SQL Query Analyzer, but for LINQ.
  • Blogs of Note - Rob Waling - Rob is an ASP.NET developer, independent contractor, and micro-ISV. Many blogs examine the latest coding tips and tricks, but Rob's blog is unique in that it focuses more on the business and interpersonal aspects of being a successful developer.
  • Logging Libraries - There are a number of logging libraries available for .NET. This issue of Toolbox looks at two popular libraries: the Enterprise Library and log4net. The Enterprise Library is an open-source collection of application blocks designed by Microsoft's patterns & practices group. It includes a logging application block that can be used to programmatically record status, warning, or error messages to a variety of log stores - the Windows Event Log, XML files, a database, and so on. log4net is another open-source logging library. It is maintained by the Apache Software Foundation and is a port of log4j, a logging library for Java.

There were no book reviews for this column.

Enjoy! - http://msdn.microsoft.com/en-us/magazine/cc793972.aspx

As always, if you have any suggestions for products or books to review for the Toolbox column, please send them to toolsmm@microsoft.com.

Filed under:
More Posts

Archives

My Books

  • Teach Yourself ASP.NET 4 in 24 Hours
  • Teach Yourself ASP.NET 3.5 in 24 Hours
  • Teach Yourself ASP.NET 2.0 in 24 Hours
  • ASP.NET Data Web Controls Kick Start
  • ASP.NET: Tips, Tutorials, and Code
  • Designing Active Server Pages
  • Teach Yourself Active Server Pages 3.0 in 21 Days

I am a Microsoft MVP for ASP.NET.

I am an ASPInsider.