Something about probablility

This is a discussion on Something about probablility within the A Brief History of Cprogramming.com forums, part of the Community Boards category; Naturally I would accept a computer program as evidence. Would be odd to say no. However we will have to ...

  1. #61
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,487
    Naturally I would accept a computer program as evidence. Would be odd to say no. However we will have to agree on the algorithm and this whole thing gave me a terrible headache. I'll check macgyver's later.

    over and out.
    The programmer’s wife tells him: “Run to the store and pick up a loaf of bread. If they have eggs, get a dozen.”
    The programmer comes home with 12 loaves of bread.


    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  2. #62
    Deathray Engineer MacGyver's Avatar
    Join Date
    Mar 2007
    Posts
    3,211
    Quote Originally Posted by laserlight View Post
    EDIT:
    Heh, MacGyver already wrote one, apparently.
    Not a very good one, I'm afraid. I suspect there may be issues with it, plus it's not suited for receiving lots of data.

    I can try rewriting another one later for that purpose, but someone will probably beat me to it.

  3. #63
    Registered User
    Join Date
    Oct 2001
    Posts
    2,129
    No matter what happens, the host will remove one of the donkeys. So then it's 50/50.

    Does anybody care to try to disprove this?

  4. #64
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218
    Ok, my last attempt to explain it:

    There is a 2/3 probablility of winning by switching from the outset. Your odds don't change once you select the first door. This is because, at the start there will allways be a 2/3 probability that one of the doors you do not chose to begin with will have the money in it.

    First off these are all possibilities of what can be behind the doors:
    Code:
           Host  |     You
    donkey    donkey |  money
    money     donkey | donkey
    donkey    money  | donkey
    It needs to be understood that the host has to remove a donkey from the following possibilities:
    Code:
    donkey, donkey
    money, donkey
    donkey, money
    This means that there are three possibilities as to what the host can have behind the final door:
    Code:
    donkey
    money
    money
    The door you picked initially also has three possibilities to the outcome, but they are the same as from the start:
    Code:
    money
    donkey
    donkey
    Now compare the possibilities of what the host can have against what your original door can have:
    Code:
    Host  |  You
    donkey| money
    money | donkey
    money | donkey
    This is because the donkey that the host removes only affects the probability that one of his doors have money behind it, it has no effect on the door you picked. Therefore there is a predetermined 2/3 probability that by switching you will win the money.
    Last edited by mike_g; 03-08-2008 at 05:24 PM.

  5. #65
    Registered User
    Join Date
    Jan 2005
    Posts
    7,328
    >> Does anybody care to try to disprove this?
    I don't know about "proof", but unfortunately it is wrong.

    As I mentioned earlier, the host's choice of what to open depends on your original choice of your door, so you cannot start over with a new probability just because a door has been removed.

    If the host opened a door at random and it ended up being a donkey, then the chance would be 50-50. But the host doesn't open a door at random. The host opens the door based on your choice and his knowledge of what is behind the doors.

  6. #66
    Registered User
    Join Date
    Jan 2005
    Posts
    7,328
    You can also think about this alternative scenario. There are 50 doors. You pick 1. The host opens 48 doors that he knows all have donkeys. Should you switch?

  7. #67
    Deathray Engineer MacGyver's Avatar
    Join Date
    Mar 2007
    Posts
    3,211
    Think I messed up my original program.

    Try this one:

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    
    int doRound(void);
    int getRandomDoor(void);
    
    int doRound(void)
    {
    	int iRightDoor, iGuess;
    	
    	iRightDoor = getRandomDoor();
    	iGuess = getRandomDoor();
    	
    	return (iRightDoor!=iGuess);
    }
    
    int getRandomDoor(void)
    {
    	return rand() &#37; 3;
    }
    
    int main(int argc, char *argv[])
    {
    	int i, times = 100, iSwitch = 0, iStay = 0;
    	
    	srand(time(NULL));
    	if(argc > 1)
    	{
    		times = (int)strtol(argv[1], NULL, 10);
    	}
    	for(i=0;i<times;i++)
    	{
    		if(doRound())
    		{
    			iSwitch++;
    		}
    		else iStay++;
    	}
    	printf("Switching was appropriate %d times\n", iSwitch);
    	printf("Staying   was appropriate %d times\n", iStay);
    	
    	return 0;
    }
    My output for 4 iterations:

    Code:
    Switching was appropriate 69 times
    Staying   was appropriate 31 times
    
    Switching was appropriate 70 times
    Staying   was appropriate 30 times
    
    Switching was appropriate 65 times
    Staying   was appropriate 35 times
    
    Switching was appropriate 65 times
    Staying   was appropriate 35 times
    Provided there are no bugs, I think this could be submitted as evidence that Daved, CornedBee et al are correct, especially since the difference is about 2:1... ie. 66% chance in getting it right to make a switch.

  8. #68
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,487
    Quote Originally Posted by Daved View Post
    If the host opened a door at random and it ended up being a donkey, then the chance would be 50-50. But the host doesn't open a door at random. The host opens the door based on your choice and his knowledge of what is behind the doors.
    I need to dissect this because I believe herein lies the crux of the problem.

    > If the host opened a door at random and it ended up being a donkey, then the chance would be 50-50.

    Take notice of this statement: If it happened to be a donkey, the chance would be 50-50.

    >
    The host opens the door based on your choice and his knowledge of what is behind the doors.

    So he knows what door he can open to show the contestant a donkey. He does this all the time, no matter my choice. He can always open a door to a donkey.

    So, what you think will be the odds?... 50:50, because that's exactly what the host does: If it happened to be a donkey, the chance would be 50-50.
    The programmer’s wife tells him: “Run to the store and pick up a loaf of bread. If they have eggs, get a dozen.”
    The programmer comes home with 12 loaves of bread.


    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  9. #69
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    Here's another simulation that runs when your browser loads. It also has an informal explanation of why 2/3 for a switch is correct.

    http://edp.org/monty.htm

  10. #70
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    Quote Originally Posted by robwhit View Post
    No matter what happens, the host will remove one of the donkeys. So then it's 50/50.

    Does anybody care to try to disprove this?
    I gave a proof sketch in my last post. The intuition is this:

    P(chosen-door) = 1/3
    P(host-door) = 0

    Thus,
    P(remaining-door) = 2/3.

  11. #71
    Registered User
    Join Date
    Oct 2001
    Posts
    2,129
    dammit.

  12. #72
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,794
    Perhaps you would like to read:
    Ask Dr. Math: FAQ: The Monty Hall Problem
    Wolfram MathWorld: Monty Hall Problem

    For a walkthrough simulation:
    Let's Make a Deal
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  13. #73
    Registered User
    Join Date
    Oct 2001
    Posts
    2,129
    If the donkeys and the money were placed behind the doors after the host made his/her choice, I would have been right.

  14. #74
    Registered User
    Join Date
    Jan 2005
    Posts
    7,328
    >> because that's exactly what the host does: If it happened to be a donkey, the chance would be 50-50.

    There's a difference. If the host chooses a door at random, then there is a 1/3 chance he opens the door with the money. But if the host chooses a door on purpose, then that 1/3 chance disappears.

    Let's say this happens 30 times. We'll label the doors as such:

    Door A: money
    Door B: donkey
    Door C: donkey

    So out of 30 times, 10 times the contestant chooses Door A, 10 times the contestant chooses Door B and 10 times the contestant chooses Door C.

    Contestant chooses Door A, host opens Door B five times and Door C five times, all ten times a switch is bad.
    Contestant chooses Door B, host opens Door C all ten times (because he can't open door A), switch is good all ten times.
    Contestant chooses Door C, host opens Door B all ten times (because he can't open door A), switch is good all ten times.

    So the switch is good 20 out of 30 times.


    Let's do the same thing when the host doesn't know where the money is.

    Contestant chooses Door A, host opens Door B five times and Door C five times, all ten times a switch is bad.
    Contestant chooses Door B, host opens Door A five times and Door C five times, switch is good five times, and five times we ignore (because the original problem assumes the host opened a door with a donkey).
    Contestant chooses Door C, host opens Door A five times and Door B five times, switch is good five times, and five times we ignore (because the original problem assumes the host opened a door with a donkey).

    That's 10 times switch is bad, 10 times switch is good, and 10 times that are ignored because the problem assumes the host opens a door with a donkey.


    See the difference?
    Last edited by Daved; 03-08-2008 at 07:16 PM.

  15. #75
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,487
    Yup. I can see it now. It's an amazing paradox. Very invigorating. Also took a look at the links and on wikipedia.

    It's a pleasure to see how wrong I am. This one is definitely going to my notebook.

    Thanks a lot for the patience through the ordeal of trying to make see the light
    The programmer’s wife tells him: “Run to the store and pick up a loaf of bread. If they have eggs, get a dozen.”
    The programmer comes home with 12 loaves of bread.


    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

Page 5 of 8 FirstFirst 12345678 LastLast
Popular pages Recent additions subscribe to a feed

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21