wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Markov Chain Visitations
        
(Message started by: william wu on Feb 4^th, 2003, 3:21am)

Title: Markov Chain Visitations
Post by william wu on Feb 4^th, 2003, 3:21am

A problem I was discussing with a friend a few hours ago; thought you guys might be interested. I think it's originally from topcoder.com. The solution algorithm may seem surprisingly simple.

Markov Chain Visitations

You are given a Markov Chain M, defined by a set of states S and a transition probability matrix P_ij.

Write an algorithm that computes the average number of times you will visit a certain subset of states S', if you move k steps starting from an initial state v.

(In other words, if you start at v and start walking k steps according to the probabilities given by P_ij, on average how many times will you hit a vertex in the set S'?)

Title: Re: Markov Chain Visitations
Post by towr on Feb 4^th, 2003, 7:32am

...[hide]
From what I remember from the last time I used them, it might be the sum of all incoming probabilities (given that all transitions together sum to one) for every state in the subset.
Assuming v is random..
[/hide]...