wu :: forums
« wu :: forums - Markov Chain Visitations »

Welcome, Guest. Please Login or Register.
Oct 10th, 2024, 9:52pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   medium
(Moderators: Eigenray, towr, Grimbal, william wu, ThudnBlunder, Icarus, SMQ)
   Markov Chain Visitations
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Markov Chain Visitations  (Read 2135 times)
william wu
wu::riddles Administrator
*****





   
WWW

Gender: male
Posts: 1291
Markov Chain Visitations  
« on: Feb 4th, 2003, 3:21am »
Quote Quote Modify 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 Pij.  
 
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 Pij, 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 4th, 2003, 7:32am »
Quote Quote Modify Modify

...
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..
...
IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board