wu :: forums - Markov Chain Visitations

wu :: forums « wu :: forums - Markov Chain Visitations » Welcome, Guest. Please Login or Register. Apr 28^th, 2024, 1:25pm
RIDDLES SITE WRITE MATH! Home Help Search Members Login Register

   wu :: forums
   riddles
   medium (Moderators: ThudnBlunder, william wu, Icarus, Eigenray, SMQ, Grimbal, towr)
   Markov Chain Visitations

« Previous topic | Next topic »

Pages: 1

Notify of replies

Send Topic

Author

Topic: Markov Chain Visitations (Read 2125 times)

william wu
wu::riddles Administrator

Gender:

Posts: 1291

Markov Chain Visitations
« on: Feb 4^th, 2003, 3:21am »

Quote

Modify

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 Markov Chain Visitations Markov Chain Visitations Markov Chain Visitations Markov Chain Visitations Markov Chain Visitations Markov Chain Visitations Markov Chain Visitations Markov Chain Visitations Markov Chain Visitations Markov Chain Visitations Markov Chain Visitations Markov Chain Visitations 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'?)

IP Logged

[ wu ] : http://wuriddles.com / http://forums.wuriddles.com

towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender: male

Posts: 13730

Re: Markov Chain Visitations
« Reply #1 on: Feb 4^th, 2003, 7:32am »