# Three Cafes Puzzle

Every morning a couple has breakfast at one of three cafes: Amy's, Bob's, or Cindy's.

• After eating at Amy's or Bob's, they flip a coin to see which of the other two cafes they'll go to the next morning.

• However after Cindy's, they always go to Amy's.

Question: Over time, in what ratio do they attend the three cafes?

This is an original problem. I was working on odds for Monopoly boards and first wanted a small degenerate version of the game movement to make sure my methodology was sound.

• I would personally have posted this on the math stack exchange. – Jack M Feb 14 '16 at 20:23

Essentially, this puzzle asks for the steady state behavior of a Markov Chain.

Amy:Bob:Cindy = 4:2:3
In other words Prob[Amy]=4/9 and Prob[Bob]=2/9 and Prob[Cindy]=1/3.

Formally, let us denote the long term probabilities for ending up in Amy, Bob, Cindy respectively by $a,b,c$.

• Then $a=b/2+c$ (as Amy is visited either with probability 1/2 after Bob, or with probability 1 after Cindy).
• Furthermore $b=a/2$ (as Bob is visited with probability 1/2 after Amy).
• Furthermore $c=a/2+b/2$
• And of course $a+b+c=1$.

Solving the resulting equation system yields the above probabilities.

• StackExchange isn't let me mark all correct answers as correct. You seem to be first though so, yes, you obviously have it. Question: I first tried to work out the Monopoly board as a set of simultaneous equations, but since there were no constants I ended up not being able to solve it. After making the toy problem above, I realized I needed the "a+b+c=1" equation, and that in turn made my Monopoly solver work. And yet: your "of course" is a bit facile. How do we know we need this? I had to think for 30 minutes and I'm sure it was blind luck I ever thought of it. – Swiss Frank Feb 14 '16 at 17:28
• @Swiss Frank: The first three equations are linearly dependent. The third equation is implied by the other two, as it is just picking up the remaining probabilities (that have not been assigned in the first two equations). Hence the system is underdetermined, and we need the fourth equation. The same holds true in gerneral, in all Markov chains. – Gamow Feb 14 '16 at 17:30
• @SwissFrank Another way to look at it is that "a+b+c=1" is the formalization of the statement "Every morning a couple has breakfast at one of three cafes: Amy's, Bob's, or Cindy's." The probability of being at any cafe on a given day is 1 i.e., there never a day you don't go to some cafe. – David Conrad Feb 14 '16 at 18:36
• Sure, I know why the third formula simply derives from the first two, and what the magic a+b+c=1 means. But why exactly is it an "of course?" For me the first three equations were totally obvious but I had to think for a half hour before coming up with the last one. – Swiss Frank Feb 15 '16 at 6:03
• @SwissFrank Strictly speaking, "of course" [ ;-) ] you don't need the constraint that $a+b+c=1$ since you asked for the ratio and that's perfectly expressible (as 2:3:4) without it. Adding that final constraint has the effect of normalising / expressing as attendance probabilities. – Oliphaunt - reinstate Monica Feb 15 '16 at 8:44

In a steady state, they go to Amy's, Bob's, and Cindy's with probability $a$, $b$, $c$ respectively. For this to be true, the probability of each cafe must be $a$, $b$, $c$ the next day as well. Therefore $$a=0.5b+c\\b=0.5a\\c=0.5a+0.5b$$These equations (along with the fact that $a+b+c=1$) can be solved to find that $a=\frac{4}{9}$, $b=\frac{2}{9}$, $c=\frac{1}{3}$.

A more formal way to do this (find the steady state of a Markov process) would be to make a transition matrix and then find the eigenvector with eigenvalue 1, which represents the steady state. People have done this for Monopoly, for example here, here, and here.

• Correct! But I can only select one answer as correct, so I went with the ealier. Still you did it exactly as I did. Yes, there's prior practice on the Monopoly problem... but the goal was to solve it, not to have the solution. A surprising number of public solutions don't quite agree. I've also found agreeing versions that had the same oversight so independent verification isn't proof of accuracy. – Swiss Frank Feb 14 '16 at 17:35

Let's call them A, B and C respectively.

After A: With 1/2 probability B, 1/2 C.

After B: With 1/2 probability C, 1/2 A.

After C: The probability of going to A is 1.

Letting the probabilities of going to A, B and C be $P_A,P_B,P_C$ we get:

$P_A=P_B/2 + P_C$
$P_B=P_A/2$
$P_C=P_A/2 + P_B/2$

$P_A=P_A/4 + P_A/2 + P_A/4$
$P_B=P_A/2$
$P_C=P_A/2 + P_A/4$

$1=9P_A/4$

$P_A=4/9$ (A to be visited 4/9 of the time)
$P_B=2/9$ (B to be visited 2/9 of the time)
$P_C=3/9$ (C to be visited 3/9 of the time)

• Seems a bit long and involved for a problem that I solved in my head in about 90 seconds. – Pieter Geerkens Feb 15 '16 at 0:32