Puzzling Stack Exchange is a question and answer site for those who create, solve, and study puzzles. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|improve this question
3  
I would personally have posted this on the math stack exchange. – Jack M Feb 14 at 20:23
up vote 11 down vote accepted

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

The answer is:

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.

share|improve this answer
    
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 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 at 17:30
3  
@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 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 at 6:03
1  
@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 Feb 15 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.

share|improve this answer
    
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 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)

share|improve this answer
    
Seems a bit long and involved for a problem that I solved in my head in about 90 seconds. – Pieter Geerkens Feb 15 at 0:32

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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