There is a bathroom in your office building that has only one toilet. There is a small sign stuck to the outside of the door that you can slide from “Vacant” to “Occupied” so that no one else will try the door handle (theoretically) when you are inside. Unfortunately, people often forget to slide the sign to “Occupied” when entering, and they often forget to slide it to “Vacant” when exiting.
Assume that 1/3 of bathroom users don’t notice the sign upon entering or exiting. Therefore, whatever the sign reads before their visit, it still reads the same thing during and after their visit. Another 1/3 of the users notice the sign upon entering and make sure that it says “Occupied” as they enter. However, they forget to slide it to “Vacant” when they exit. The remaining 1/3 of the users are very conscientious: They make sure the sign reads “Occupied” when they enter, and then they slide it to “Vacant” when they exit. Finally, assume that the bathroom is occupied exactly half of the time, all day, every day.
Two questions about this workplace situation:
1. If you go to the bathroom and see that the sign on the door reads “Occupied,” what is the probability that the bathroom is actually occupied?
2. If the sign reads “Vacant,” what is the probability that the bathroom actually is vacant?
Extra credit: What happens as the percentage of conscientious bathroom users changes?
This problem can be solved using Bayes’ Rule but you can also use Markov chains. I like Markov chains so that’s what we’ll do!
The first step is to define what are states and transition probabilities are. This is the tricky part; we might be tempted to think that because the bathroom can be either occupied or not, and the sign in front can either read “Vacant” or “Occupied”, that there should be four states (one for each possible pair).
However, this is not the case. The reason is because the transition probabilities are not independent of one another. Consider the state “bathroom is occupied and the sign says it’s occupied”. We must distinguish between the cases where the person occupying the bathroom is conscientious (they will definitely slide the sign to “Vacant” when they leave) or not (they will leave the sign as “Occupied” after they leave).
We must therefore add additional states to our Markov chain that correspond to the different ways in which the bathroom can be occupied. To keep things general, let’s assume the fraction of oblivious, forgetful, and conscientious users are $p$, $q$, and $r$, respectively. Therefore $0\le p,q,r \le 1$ and $p+q+r=1$. A diagram of the Markov chain:
If $\{x_k\}$ denotes the probability of being in state $k$ in the diagram, the stationary distribution satisfies the equation:
\[
\begin{bmatrix}
0 & 0 & 1 & 1 & 0 & 0 \\
0 & 0 & 0 & 0 & 1 & 1 \\
p & 0 & 0 & 0 & 0 & 0 \\
r & r & 0 & 0 & 0 & 0 \\
q & q & 0 & 0 & 0 & 0 \\
0 & p & 0 & 0 & 0 & 0
\end{bmatrix}
\begin{bmatrix}
x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \\ x_6
\end{bmatrix}
=
\begin{bmatrix}
x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \\ x_6
\end{bmatrix}
\]
Solving these equations, we obtain:
\begin{align}
x_1 &= \frac{r}{2 (q+r)}, & x_2 &= \frac{q}{2 (q+r)}, & x_3 &= \frac{p r}{2 (q+r)}, \\
x_4 &= \frac{r}{2}, & x_5 &= \frac{q}{2}, & x_6 &= \frac{pq}{2 (q+r)}
\end{align}
We can now compute the probabilities we’re after:
\begin{align}
\mathbb{P}(\text{Vacant}\mid \text{says “Vacant”})
&= \frac{x_1}{x_1+x_3} = \frac{1}{1+p}\\
\mathbb{P}(\text{Occupied}\mid \text{says “Occupied”})
&= \frac{x_4+x_5+x_6}{x_2+x_4+x_5+x_6} = \frac{r+q-pr}{r+2q-pr}
\end{align}
When $p=q=r=\frac{1}{3}$ (equal fraction of conscientious, forgetful, and oblivious users), we obtain:
\begin{align}
\mathbb{P}(V\mid V) &= \frac{3}{4}, &
\mathbb{P}(O\mid O) &= \frac{5}{8}
\end{align}
Bonus: different probabilities
We have the analytic expressions above for what happens as a function of $p,q,r$… so now it remains to visualize it somehow. One possibility is to set two of them equal and just make a plot. For example, if we only vary the percentage of conscientious users ($r$) and set the other two to be equal, i.e. $p=q=\frac{1-r}{2}$. We then obtain:
\begin{align}
\mathbb{P}(V\mid V) &= \frac{2}{3-r}, &
\mathbb{P}(O\mid O) &= \frac{r^2+1}{r^2-r+2}
\end{align}We can also plot these probabilities as a function of $r$:
If we want to see what happens as we vary the percentages of $p,q,r$ all at once, we can visualize the result using a ternary density plot. Here, we plot values in a triangle; the fraction of each type of bathroom user is determined by the length of the altitude to the opposite side of the triangle and the color indicates the probability. Here are the plots:
You can read off the appropriate percentages by looking at the tick marks. For example, the lower-left corner corresponds to everybody being conscientious, the bottom (horizontal) side of the triangle corresponds to nobody being oblivious, and as you move from left to right you increase the fraction of forgetful users while simultaneously decreasing the fraction of conscientious users. The center of the triangle corresponds to $p=q=r=\tfrac{1}{3}$, and so on.
One additional comment: you’ll notice the point at the top of the triangle (100% oblivious users) is missing. This is because this probability doesn’t make sense. When all users are oblivious, the sign will never change. So if it starts at “Vacant”, it will stay at “Vacant” forever.
Something seems off with the bottom ternary plot? The left side of the triangle means that when q is zero, (O|”O”) is always equal to 0.5, but by equation it is (r-pr)/(r-pr) or 1, which is not 0.5. Also, the right side, with constant 1, for r of zero, should be (O|”O”) equal to q/2q, which is 0.5. Maybe some axes got switched? I am new to ternary plots, so please forgive me if I am just reading them incorrectly. Also, could you just check the top plot, too, even though I think it is correct?
Also, I find it interesting that the last assumption given of “the bathroom is half occupied, half vacant” never entered explicitly into your calculations. How would the solution have changed had the bathroom been 90% vacant, 10% occupied? It seems to me that maybe since you only transition to vacant from occupied, and occupied from vacant, this accounts for the assumption. You would have had some “internal state transitions” for vacant remaining vacant and occupied moving to occupied if it weren’t 50-50.
Also, I am very happy you have resumed riddling. I am guessing your summer recess is over. Bummer. At least you still get summer recesses!
Thank you for the comment. Indeed I had mislabeled the ternary plots. I fixed it; should be correct now!
I’m honored you returned to tackle my bathroom problem. The Markov chain approach never occurred to me, but I’m relieved that you got the same answers I did using a Bayesian approach!
Dave, Laurent,
I think you’re giving a slightly incorrect solution. This riddle was also posted on five38 website. Below I’m posting an explanation, which I have posted to five38 as well, but it’s still unfortunately left in unanswered state. I looked at Dave’s solution and found a problem that causes the discrepancy. In his solution Dave used incomplete event space and hence got a different result. Below I provide 2 solutions and small python simulation program that yields results that very well
converge to provided below closed form solutions. First solution is my original approach based on Bayes theorem and uses characteristic equation to solve recurrence of conditional probabilities associated with unconscientious bathroom visitors following each other. To reconcile result with Dave Moran’s solution I used exactly the same conditional probability framework that Dave used, but provided complete event space and got the correct result that matches computer simulation. I will appreciate if you could review these solutions with Dave and possibly provide a public errata or prove that my solution approach and associated computer simulation are not correct.
Thank you in advance for your time and efforts,
Vadim Tsozik.
####Solution# 1 (Bayes theorem based) ####
if
p(b|o) – is probability that bathroom is busy if sign reads “Occupied”,
p(o) – probability that sign reads “Occupied” (irregardless whether bathroom empty or not).
p(o|b) – probability that sign reads “Occupied” if bathroom is busy
p(b) – probability that bathroom is busy,
then according to Bayes theorem we have:
p(b|o) * p(o) = p(o|b) * p(b), so
p(b|o) = p(o|b) * p(b) / p(o) (1), where
provided that:
p(b) = 1/2 – probability that bathroom is busy (non-empty),
p(c) = 1/3 – probability that we deal with conscientious people
p(s) = 1/3 – probability that we deal with semi-conscientious people
p(u) = 1/3 – probability that we deal with unconscientious people
we have:
p(o) = p(c) * p(b) + p(s) + p(u) * p(o) (2), solving we get p(o) = 1/2
Note that sign could read occupied only if:
1) conscientious people entered, but not exited the bathroom,
2) irregardless whether half-conscientious people entered or exited the bathroom,
3) irregardless whether unconscientious people entered or exited the bathroom as long as sign read occupied,
p(o|b) – probability that sign reads occupied when bathroom is actually busy,
p(o|b) = p(c) + p(s) + p(u) * p(0) (3), solving we get p(o|b) = 11/12
Note that sign will always read occupied when conscientious and semi-conscientious people inside and when sign read occupied just before unconscientious people entered the bathroom,
Plugging results from (2) and (3) into (1) gives us:
p(b|o) = 11/12 * ½ / ¾ = 11/18 = 0.6(1) or ~61.11% as per computer simulation below.
As for probability that bathroom is empty if vacant sign is observed – p(e|v)
Again from Bayes theorem we have:
p(e|v) * p(v) = p(v|e) * p(e), where
p(e|v) – probability that bathroom is empty if sign reads “Vacant”,
p(v) – probability that bathroom sign reads “Vacant” (irregardless whether bathroom is empty or not)
p(v|e) – probability that sign reads “Vacant” if bathroom is empty,
p(e|v) = p(v|e) * p(e) / p(v) (4)
Since we already know value of p(o)=3/4 and sign may display only “Occupied” or “Vacant” we can compute p(v) as complement of p(o):
p(v) = 1 – p(o) = 1/4
Sign will read “Vacant” if bathroom is empty only after conscientious exited it or unconscientious people left bathroom leaving the sign in “Vacant” state, so:
p(v|e) = p(c) + p(u) * p(v) = 5/12
Plugging results into (4) yields:
p(e|v) = 5/12 * 1/2 / (1/4) = 5/6 = 0.8(3) or ~83.33% again computer simulation below converges to this value.
#### Solution# 1 (Dave’s approach, conditional probabilities) ####
Let’s consider an entire event space that leads to sign display “Occupied”:
P(1) = 1/2 * 1/3 = 1/6 – conscientious (C) user is in the bathroom at the moment (1/2 probability that bathroom is occupied, 1/3 – probability that C is in the bathroom if it’s occupied).
P(2) = 1/2 * 1/3 = 1/6 – semi-conscientious (S) user is in the bathroom at the moment (1/2 probability that bathroom is occupied, 1/3 – probability that S is in the bathroom if it’s occupied).
P(3) – Probability that unconscientious (U) user is in the bathroom at the moment and when he entered the bathroom sign read “Occupied”.
P(3) – is a sum of infinite series of probabilities of one or more Us visited bathroom and observed sign displayed “Occupied” on the entrance and last U is in the bathroom now. I will describe first members of these series below
P(3.1) = (1/2 * 1/3) * (1/2 * 1/3 + 1/3) = 1/2 * 1/3 * 1/2 – Probability that U is now in the bathroom (1/2 * 1/3) and before U entered the bathroom sign read “Occupied”:
(1/2 * 1/3 + 1/3) = 1/2 – Note that sign reads occupied only if S visited just prior U or C has entered the bathroom just before U and is in the bathroom now.
This 1/2 – is essentially the same probability of having user visiting the bathroom who is not U, but was S (see Dave’s explanation).
P(3.2) = (1/2 * 1/3 * 1/3) * (1/2 * 1/3 + 1/3) = 1/2 * (1/3)^2 * 1/2 – Probability that U entered the bathroom and is currently there following another U who observed sign reading “Occupied” entering the bathroom.
P(3.3) = (1/2 * 1/3 * 1/3 * 1/3) * (1/2 * 1/3 + 1/3) = 1/2 * (1/3)^3 * 1/2 – Probability that U entered the bathroom and is currently there following another U who followed yet another U visit. That yet another U observed sign reading “Occupied” entering the bathroom.
…
P(3.inf) = 1/2 * (1/3)^inf * 1/2 -> 0 – Probability that U entered the bathroom and is currently there following infinite number of U visits where very first U in that sequence observed sign reading “Occupied” or sign read “Occupied” before very first U visited the bathroom.
So adding probabilities of these mutually independent events we have:
P(3) = P(3.1) + P(3.2) + P(3.3) + … + P(3.inf) = 1/2 * 1/3 * 1/2 + 1/2 * (1/3)^2 * 1/2 + 1/2 * (1/3)^3 * 1/2 + … + 1/2 * (1/3)^inf * 1/2 = (1/2 * 1/3 * 1/2) * (1 + 1/3 + (1/3)^2 + … + (1/3)^inf) = (1/12) * S,
S – is a sum of infinite power series (see http://mathworld.wolfram.com/PowerSeries.html or https://en.wikipedia.org/wiki/Power_series for details).
S = (1 + (1/3)^inf) / (1 – 1/3) = 1 / (1 – 1/3) = 3/2 as (1/3)^inf -> 0
So P(3) = (1/12) * S = 1/12 * 3/2 = 1/8
Now
P(4) = 1/2 * 1/3 = 1/6 – is probability that S just left the bathroom and didn’t flip sign to “Vacant” (1/2 probability that bathroom is empty, 1/3 – probability that S was in the bathroom before if it’s empty now).
P(5) – is probability that U just exited the bathroom leaving it empty, but when he entered it sign read “Occupied”. This is very similar to P(3) except we need to change occupancy probability to probability that bathroom is not occupied at the moment,
since its value is identical to value of probability that bathroom is occupied at the moment, i.e. 1 – 1/2 = 1/2 we will have the same value for P(5) as for P(3) following the same reasoning as for P(3) computing the sum of infinite series of probabilities related to
prior U visitors. So
P(5) = (1/2 * 1/3 * 1/2) * 3/2 = 1/12 * 3/2 = 1/8
Finally probability that bathroom sign reads occupied when someone is really in the bathroom:
PO = (P(1) + P(2) + P(3)) / (P(1) + P(2) + P(3) + P(4) + P(5))
P(1) + P(2) + P(3) = 1/6 + 1/6 + 1/8 = (4 + 4 + 3)/24 = 11/24
P(1) + P(2) + P(3) + P(4) + P(5) = 11/24 + 1/6 + 1/8 = (11 + 4 + 3) / 24 = 18/24
PO = 11/24 / (18/24) = 11/18 = 0.6(1) or ~61.11% as per computer simulation below.
Now let’s reconcile sign reads “Vacant” when bathroom is empty case.
In this case complete sample space consists of the following events and associated probabilities for the sign to read “Vacant”:
P(6) = 1/2 * 1/3 = 1/6 – Probability that bathroom is empty and C was the one who there before.
P(7) – the bathroom is occupied by U who entered it when sign read “Vacant”
As with P(3) in the “Occupied” case there’s sub sample space here:
P(7.1) = 1/2 * 1/3 *1/3 * 1/2 – Probability that U has just left the bathroom and sign read “Vacant” when he entered it because C has left bathroom and flip sign to “Vacant”, where 1/2 – is the probability that bathroom is empty now, 1/3 – probability that it was U who visited it last,
(1/3 * 1/2) – probability that C was in the bathroom and exited before U, so when U entered sign read “Vacant”
P(7.2) = 1/2 * 1/3 *1/3 * 1/3 * 1/2 – Probability that U has just left the bathroom following another U visit who happened to enter the bathroom just after C left that bathroom flipping sign to “Vacant”,
P(7.2) = 1/2 * 1/3 *1/3 * 1/3 * 1/3 * 1/2 – Probability that U has just left the bathroom following another U visit following yet another U visit who happened to enter the bathroom just after C left that bathroom flipping sign to “Vacant”,
P(7) as also sum of infinite series of probabilities of the events such as above.
P(7) = P(7.1) + P(7.2) + P(7.3) + … + P(7.inf) = 1/2 * 1/3 *1/3 * 1/2 + 1/2 * 1/3 * 1/3 * 1/3 * 1/2 + 1/2 * 1/3 * (1/3)^2 * 1/3 * 1/2 + … + 1/2 * 1/3 * (1/3)^inf * 1/3 * 1/2
As P(7.inf) = 1/2 * 1/3 *(1/3)^inf * 1/3 * 1/2 -> 0 we know that the sum of this infinite power series also converges to a constant value.
Using formula for the sum of geometric progression for 1/3 fraction, which is 0 < 1/3 0:
Hide original message
P(7) = (1/2 * 1/3 * 1/3 * 1/2) * (1 + 1/3 + (1/3)^2 + … + (1/3)^inf) = 1/36 * (3/2) = 1/24
P(8) – Probability of U is in the bathroom at the moment and sign reads “Vacant”. These is computed similarly to P(7), except occupancy probability is inverted to probability of bathroom being empty at the moment, since it has the same value as its complement, i.e. 1 – 1/2 = 1/2
P(8) will be equal to P(7),
P(8) = (1/2 * 1/3 * 1/3 * 1/2) * (3/2) = 1/36 * 3/2 = 1/24
Finally probability that bathroom is empty when sign reads “Vacant”:
PV = (P(6) + P(7)) / (P(6) + P(7) + P(8))
(P(6) + P(7)) = 1/6 + 1/24 = (4 + 1)/24 = 5/24
(P(6) + P(7) + P(8)) = 5/24 + 1/24 = 6/24
PV = 5/24 / (6/24) = 5/6 = 0.8(3) or ~83.33% again computer simulation below converges to this value.
##### Bonus Question ####
with p(c) changing in either direction will bring modest effect to p(b|o) as it’s in both numerator and denominator of (1) via (2) and (3), obviously p(b|o) = 1, if p(c) = 1 and p(b|o) = 1/2 if p(c) = 0.
#### Computer simulation program with the results (written in Python) ####
Running simulation python code below prints:
p(b|o) – probability that bathroom is busy if sign reads “Occupied”
p(e|v) – probability that bathroom is empty if sign reads “Vacant”
p(o) – probability that sign reads “Occupied” (irregardless whether bathroom empty or not).
p(b|o) = 0.610485817924 , p(e|v) = 0.831819837271 , p(o) = 0.750137
###################################################################
import random
import time
def main():
random.seed(time.time())
bo = 0.
nbv = 0.
o = 0.
v = 0.
st = 0
for _ in range(1000000):
gr = random.randint(1,3)
bu = random.randint(0,1)
#print gr, bu, ‘\r’,
if gr == 2:
st = 1
elif gr == 3:
if bu > 0:
st = 1
else:
st = 0
if st > 0:
if bu > 0:
bo += 1.
o += 1.
else:
if bu 0 and v > 0:
print ‘p(b|o) = ‘,bo / o,’, p(e|v) = ‘,nbv / v,’, p(o) = ‘,o / (o + v)
if __name__ == ‘__main__’:
main()
Is the bottom triangle correct? Is the left upright for 0% forgetful? Then the bathroom should always be occupied when the sign says “Occupied”. The right upright should be the one that has 50%, since it represents 0% conscientious.
Also, how was the assumption that the bathroom was occupied half the time used in the solution? If the bathroom was occupied 75% of the time, how would that be incorporated into the Markov chain?
Thanks for catching that — I had mislabeled the plots; I fixed it now.
Good question about the occupancy rate. In my model, the Markov chain alternates at every step between a “red” (occupied) and a “green” (vacant) state. This is where I implicitly built in the assumption that the bathroom is occupied half the time and vacant half the time. If you wanted to change this probability, you would simply weigh the outgoing edges. e.g. you could change the probability of going back from red to green (which is always 1 in my chain) to some other number say $\alpha$, and then add a self-loop with probability $1-\alpha$ that you’ll stay in the red state. As you change $\alpha$, you change the amount of time spent in red vs green. This technique can be used to model even more complicated constraints such as “forgetful users spend twice as long on average in the bathroom as conscientious users”.
I was happy to get the correct answers without using my feeble abilities in matrices and Markovs. I just drew 6 “average” timeline permutations, with each being occupied by A, B, and C in different orders, each followed by a time of vacancy, and all of these in one of two states – Sign O / Sign V, based on the previous state (the first state determined by occupant, or in A’s case, one of each).
A B C
OOOOOV
VVOOOV
C A B
OVVVOO
OVVVOO
etc.
Then I just counted ‘occupied’s versus ‘O’s, and ‘vacant’s versus ‘V’s.