## Probability of ending up in room N

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

Moonbeam
Posts: 292
Joined: Sat Dec 08, 2007 5:28 pm UTC
Location: UK

### Probability of ending up in room N

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 .......

jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

### Re: Probability of ending up in room N

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.

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

### Re: Probability of ending up in room N

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.

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.

jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

### Re: Probability of ending up in room N

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.

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.