Wikipedia:Reference desk/Archives/Mathematics/2015 May 15

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

May 15

Markov chain problem

I initialize two entities, A and B, on distinct random nodes of a markov chain. Let f equal either, the number of steps before they meet; or the number of steps + 1/2, if they have switched spaces (if A == previous step B and B == previous step A), whichever comes first. What is the expected value of f? 67.51.100.10 (talk) 04:12, 15 May 2015 (UTC)

I don't really have an answer but since so one else has responded some discussion might be helpful. One thing to consider is that if the chain has more than one "sink" (node with probability 1 of not moving) then there is a positive probability that the A and B will never collide, which would imply that the expected time until they do is infinite. Similarly if there are "sink-cycles" of length more than 2. So perhaps the first question to ask is what is the probability that A and B will ever collide. It shouldn't be hard to compute the probability that A and B will be on the same node at step k, but these probabilities aren't independent so finding the expected first occurrence seems tricky. Perhaps you can do it on a case by case basis by creating a new Markov chain whose nodes correspond to pairs of nodes of the original chain. --RDBury (talk) 09:43, 16 May 2015 (UTC)

Yes, I've also been thinking about this for a bit, and doing some lit searching. I've concluded that your last sentence is the best answer: I'm pretty sure there can't be any truly general rules that would apply to any given Markov chain. In some cases, the paired analysis could be analyzed with standard tools to give a complete answer, in other cases, probably not. SemanticMantis (talk) 23:39, 18 May 2015 (UTC)