-1
$\begingroup$

Let's say you have a Hilbert's grand hotel full occupancy. Assign each occupant a new room select randomly without regard to whether the room is assigned to someone. i.e. empty rooms, multiple occupancies etc are all allowed.

what are the chances that any given room is vacant?

I get $1/e$ the limit of $((x-1)/x)^x$ as x -> ∞.

but

if each member of an infinite set has a > 0 chance of doing something then that thing should happen and happen an infinite number of times making a 0 chance of having an empty room or even a room with < infinite members.

So what gives?

$\endgroup$

closed as unclear what you're asking by GEdgar, user147263, John B, Leucippus, Daniel W. Farlow May 21 '16 at 1:32

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 8
    $\begingroup$ How do you select a room randomly if there are an infinite number of rooms? Surely you're not selecting uniformly randomly? $\endgroup$ – Alex R. May 20 '16 at 17:35
  • $\begingroup$ is the impossibility of a uniform distribution on the set of real numbers where the "paradox" comes in? $\endgroup$ – King-Ink May 20 '16 at 17:44
  • 1
    $\begingroup$ This might be meaningful with a distribution such as this: Move the occupant of room n to room 1 to f(n), where f(n) > n. You might also investigate the length of chains of collisions. $\endgroup$ – marty cohen May 20 '16 at 18:10
  • 1
    $\begingroup$ @DavidC.Ullrich: I don't think there's an error in the calculations. The limit $\frac1{\mathrm e}=\lim_{x\to\infty}\left(\frac{x-1}x\right)^x$ is the correct limit of probability of a given room remaining empty in the finite case in which each of $x$ occupants in $x$ rooms uniformly randomly chooses a new room. There's no paradox since this doesn't correspond to any limiting distribution. $\endgroup$ – joriki May 20 '16 at 18:12
  • 1
    $\begingroup$ @DavidC.Ullrich: I was responding to your comment "The paradox arises from some error in your calculations, which we can't spot without seeing them." I agree that there's an error of the form you describe in your last comment. But I still don't think there's an error in the calculations that we can't spot for lack of seeing them. A correct calculation is being misinterpreted, and all information that we need to spot that error is in the post. $\endgroup$ – joriki May 20 '16 at 18:24
2
$\begingroup$

The limit you took doesn't correspond to any limiting distribution. For each $x$, each occupant is assigned one of the rooms with the same probability $\frac1x$. But infinitely many occupants cannot be assigned rooms with the same probability "$\frac1\infty$".

Here's a distribution for the infinite case, though: Inhabitant $n$ takes one of the rooms $1$ through $n$ with equal probability $\frac1n$. Then room $k$ remains empty with probability

$$ \prod_{n=k}^\infty\left(1-\frac1n\right)\;. $$

This infinite product diverges to zero, so all rooms are almost surely occupied.

If you use the same probabilities in the finite case with $x$ occupants, then for fixed $k$ the probability for room $k$ to remain empty will go to $0$ as $x\to\infty$.

$\endgroup$
  • $\begingroup$ Each factor should be $1-(1/n)$ $\endgroup$ – Empy2 May 20 '16 at 18:00
  • $\begingroup$ @Michael: Thanks; fixed. $\endgroup$ – joriki May 20 '16 at 18:00
  • $\begingroup$ So for any hotel with a large finite number of rooms about 1/e of those rooms will empty but in an infinitely large hotel all the rooms will be full? $\endgroup$ – King-Ink May 20 '16 at 18:20
  • $\begingroup$ @King-Ink: Which distributions are you talking about? $\endgroup$ – joriki May 20 '16 at 18:20
  • $\begingroup$ got it. a since a uniform distribution is not possible in the case of infinite rooms the chance of an empty room is dependent on the distribution I choose for the room change. i.e. if the room changes were based on room number + a random integer between -1,000,000 and 1,000,000 uniformly distributed (allowing negative room numbers) I would get a different answer. $\endgroup$ – King-Ink May 20 '16 at 18:27
1
$\begingroup$

Related to joriki's answer,
if Inhabitant $n$ goes to a room between $1$ and $n\log n$, each room is also almost surely occupied, but if they go to a room between $1$ and $n^2$, the probability is less than $1$.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.