Consider a random walk on a graph in the shape of the capital letter Y, with nodes at A and B at the top, C at the bottom, and O in the center. With probability 1/3, there is a transition from O to A, B, or C that takes 1 time unit to complete. Find the expected time to get to C, starting at A. 7 AnswersI thought this was a geometric series question and came up with the answer of 2, which was clearly wrong. The interviewer tried to help me out, but he and I were using different notation, which we only discovered after 10 minutes of very confusing discussion, in which we both probably thought the other was either insane or stupid. He kept prodding me to "use the symmetry of the situation" (i.e., A and B are basically the same thing), but I wasn't able to see how the symmetry translated into a mathematical result. We moved on without discovering the answer. if no probability is associated with A to O (A to O is a certain thing to happen) then it would be 1+ 1*(1/3) = 4/3. correct me if im wrong All branches go to O with prob 1. So Ec_a = 1 + 1/3 + 2/3Ec_c since the time from b to a is the same by symmetry. Solving we have Ec_a = 4 Show More Responses Since all branches have probability of 1 for traveling to O, we can solve this problem by simple reasoning. The expected number of steps is thus the step to get to O from the branch, which is 1, plus the expected value of the number of steps from O to C, which altogether is 1+ 1/3 +2/3( 1+ 1/3 + 2/3(... = ? We can solve this recursively noting that in the infinite limit x=1+1/3 +2/3(x) Thus x=4, which is the expected number of steps. I've been meaning to post about this for a while now. I don't think 4 is the correct answer. I think the answer is 6. I arrived at it in two ways: (1) Using the straightforward definition of expected value of a discrete random variable and summing the resulting series (which isn't trivial; it's not a simple geometric series, and you have to be a little clever to evaluate it without a computer). (2) Running a Monte Carlo simulation in Python. I can't find the explicit flaw in the arguments given above, but I feel they play too fast and loose with the notion of "expected value" of a random variable. I don't think the recursion argument they offer holds water. The claim that E(T) = 1 + 1/3 + 2/3 E(T) leads to an elegant solution to the problem, but it is all too easy to fool one's self with such "elegant" probabilistic thinking. I would need to see this claim rigorously justified using, e.g., the linearity of the expectation. A further argument - and I'm not sure it's 100% sound; it's kind of hand-wavy - is as follows: the walk will (with certainty) go from A to O. Once there, we are in a binomial experiment with probability of success p (visit to C) 1/3 and probability of failure (visit to either A or B) 2/3. Since the expected value of a binomial random variable is np = n/3, in order to expect ONE success, we have to execute THREE trials. So we should expect our walk to visit A and/or B TWICE before visiting C for the first time. Since each visit to A or B tacks on 2 time units and the visit to C will tack on one, in addition to the 1 time unit we expended in going from A to O, we again obtain E(T) = 1 + 2 + 2 + 1 = 6. If we claim E(T) = 4, on the other hand, we are claiming we should expect only ONE visit to A/B before we observe a visit to C. This appears to contradict the binomial nature of the walk once it gets to O. Again, though, as a pure mathematician, this argument is not nearly as satisfying as just summing the stupid series :) After discussing this problem with a few colleagues today, the flaw in the above arguments concluding that E(T) = 4 has been (I think) spotted. The *correct* recursive formula employing expectations is the following: E(T) = 1 + 1/3 + 2/3 (1 + E(T)). This can be rearranged to give E(T) = 6. Those who posted about this problem previously left off that little "1 + ", which *must* be added because getting back to A (such that we can use E(T) again) deterministically requires 1 time step. |