Probability of ending up in room N

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

User avatar
Moonbeam
Posts: 278
Joined: Sat Dec 08, 2007 5:28 pm UTC
Location: UK

Probability of ending up in room N

Postby Moonbeam » Wed Dec 30, 2015 10:00 am UTC

I've just "dreamt" this up, so if it's unsolvable (or even too easy) .... go easy on me please :)

So you check into a plush hotel and pay your $40 for 1 night's stay.
You are then told you've been allocated room 1 (which is a bit of a bummer. as the rooms get better as the room number increases), but he'll let you a play a game, for free, which gives you a chance to upgrade to room 2, or poss 3 or better .....

He flips a fair coin and you call heads or tails .... if you win you're upgraded to room 2 and the game ends ... it's a straight 1 in 2 chance of winning.

If you lose, you now have the chance of upgrading to room 3. same as before but your odds of upgrading are now 1 in 3 ... so he rolls a 3 sided die (??) or whatever, just so long as you have exactly 1 in 3 chance of winning. If you win you're upgraded to room 3 and the game ends .... if you lose, you have the chance to upgrade to room 4 with a 1 in 4 chance of winning .... ad infinitum ....

What are your odds of ending up in room N

As the game progresses and your odds shorten with each room, is it possible to never get an upgrade, even though there are an infinite number of rooms??

What if the odds were changed, so that your odds of room 2 are 1 in 2; odds of room 3 are 2 in 3; odds of room 4 are 3 in 4 .... i.e. your odds of each individual room are now (N-1)/N instead of 1/N .... what are your odds of getting room N now ??

I would assume that you would eventually get a room in this scenario, as the odds increase with each room .......

User avatar
jaap
Posts: 2075
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Probability of ending up in room N

Postby jaap » Wed Dec 30, 2015 10:27 am UTC

Moonbeam wrote:I've just "dreamt" this up, so if it's unsolvable (or even too easy) .... go easy on me please :)

So you check into a plush hotel and pay your $40 for 1 night's stay.
You are then told you've been allocated room 1 (which is a bit of a bummer. as the rooms get better as the room number increases), but he'll let you a play a game, for free, which gives you a chance to upgrade to room 2, or poss 3 or better .....

He flips a fair coin and you call heads or tails .... if you win you're upgraded to room 2 and the game ends ... it's a straight 1 in 2 chance of winning.

If you lose, you now have the chance of upgrading to room 3. same as before but your odds of upgrading are now 1 in 3 ... so he rolls a 3 sided die (??) or whatever, just so long as you have exactly 1 in 3 chance of winning. If you win you're upgraded to room 3 and the game ends .... if you lose, you have the chance to upgrade to room 4 with a 1 in 4 chance of winning .... ad infinitum ....

What are your odds of ending up in room N

Spoiler:
To get room N, you must lose on the first N-1 rounds, and then win room N.

If you win round n with probability 1/n, lose with probability (n-1)/n, you get:
Room 2: 1/2
Room 3: 1/2*1/3 = 1/6
Room 4: 1/2*2/3*1/4 = 1/12
Room 5: 1/2*2/3*3/4*1/5 = 1/20
...
Room N: 1/(N(N-1))

Moonbeam wrote:As the game progresses and your odds shorten with each room, is it possible to never get an upgrade, even though there are an infinite number of rooms??

What if the odds were changed, so that your odds of room 2 are 1 in 2; odds of room 3 are 2 in 3; odds of room 4 are 3 in 4 .... i.e. your odds of each individual room are now (N-1)/N instead of 1/N .... what are your odds of getting room N now ??

Spoiler:
If you win round n with probability (n-1)/n, lose with probability 1/n, you get:

Room 2: 1/2
Room 3: 1/2*2/3 = 1/3
Room 4: 1/2*1/3*3/4 = 1/8
Room 5: 1/2*1/3*1/4*4/5 = 1/30
Room 6: 1/2*1/3*1/4*1/5*5/6 = 1/144
...
Room N: (N-1)/N!

Moonbeam wrote:As the game progresses and your odds shorten with each room, is it possible to never get an upgrade, even though there are an infinite number of rooms??

Not really. You also have an infinite number of rounds to play, and each round has a non-zero chance of success. While it is theoretically possible to lose an infinite number of times, the probability of that happening is zero. You are almost surely going to win some round.

User avatar
measure
Posts: 123
Joined: Sat Apr 04, 2015 4:31 pm UTC
Location: Time-traveling kayak

Re: Probability of ending up in room N

Postby measure » Wed Dec 30, 2015 11:50 pm UTC

jaap wrote:Not really. You also have an infinite number of rounds to play, and each round has a non-zero chance of success. While it is theoretically possible to lose an infinite number of times, the probability of that happening is zero. You are almost surely going to win some round.


What about this scenario then?

The first upgrade (to room 2) has a 1/2 chance of success, the second has a 1/4, the third, 1/8, and the nth, 1/(2^n).

This still has an infinite number of rounds and each round still has a non-zero chance of termination, but now consider a group (arbitrarily large) of people playing this game:
After the first round 1/2 of them will have terminated in room 2 leaving 1/2 still playing.
After the second round 1/4 of those remaining (1/8 of the total) will have terminated in room 3 leaving 3/8 remaining.
After the third round 1/8 of the remainder (3/64 of the total) are removed leaving 21/64 remaining.
After the fourth round 1/16 or the remainder (21/1024 of the total) are removed leaving 315/1024 remaining.
The fraction of the original group that remain each round forms the sequence: 1/2, 3/8, 21/64, 315/1024, 9765
/32768, ... , A005329(n)/A006125(n + 1)

This sequence appears to converge at a value of about 0.288788, which suggests that about 29% of people who start this game will never finish despite unending non-zero chances. Is this right? I'm not sure how to verify that this series actually converges.

User avatar
jaap
Posts: 2075
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Probability of ending up in room N

Postby jaap » Thu Dec 31, 2015 6:50 am UTC

measure wrote:
jaap wrote:Not really. You also have an infinite number of rounds to play, and each round has a non-zero chance of success. While it is theoretically possible to lose an infinite number of times, the probability of that happening is zero. You are almost surely going to win some round.


What about this scenario then?

The first upgrade (to room 2) has a 1/2 chance of success, the second has a 1/4, the third, 1/8, and the nth, 1/(2^n).

This still has an infinite number of rounds and each round still has a non-zero chance of termination, but now consider a group (arbitrarily large) of people playing this game:
After the first round 1/2 of them will have terminated in room 2 leaving 1/2 still playing.
After the second round 1/4 of those remaining (1/8 of the total) will have terminated in room 3 leaving 3/8 remaining.
After the third round 1/8 of the remainder (3/64 of the total) are removed leaving 21/64 remaining.
After the fourth round 1/16 or the remainder (21/1024 of the total) are removed leaving 315/1024 remaining.
The fraction of the original group that remain each round forms the sequence: 1/2, 3/8, 21/64, 315/1024, 9765
/32768, ... , A005329(n)/A006125(n + 1)

This sequence appears to converge at a value of about 0.288788, which suggests that about 29% of people who start this game will never finish despite unending non-zero chances. Is this right? I'm not sure how to verify that this series actually converges.

I think you're right. I hadn't realised that was possible. In that case I'd better prove that everyone gets a room in the two cases in the OP.
First scenario:
Spoiler:
The probability of getting room N is 1/((N(N-1)) = 1(N-1)-1/N
The partial sum of the series, i.e. the probability of getting one of the rooms 1...k, is then:
(1/1-1/2) + (1/2-1/3) + (1/3-1/4) + .... + (1/(k-1)-1/k) =
1/1 + (-1/2 + 1/2) + (-1/3 + 1/3) + .... + (-1/(k-1) + 1/(k-1)) - 1/k = 1-1/k
This obviously converges to 1 as k goes to infinity, so the probability of getting one of the infinite number of rooms really is 1.

Second scenario:
Spoiler:
The probability of getting room N is (N-1)/N!
The partial sum of the series, i.e. the probability of getting one of the rooms 1...k, is then:
1/2! + 2/3! + ... (k-1)/k! = 1 - 1/k!
This is less obvious but can be proved by induction, from the fact that 1 - 1/k! = 1 - 1/(k-1)! + (k-1)/k!

Again, this obviously converges to 1 as k goes to infinity, so the probability of getting one of the infinite number of rooms really is 1.


Return to “Logic Puzzles”

Who is online

Users browsing this forum: No registered users and 7 guests