wu :: forums « wu :: forums - Markov Chain Visitations » Welcome, Guest. Please Login or Register. Apr 20th, 2024, 12:14pm RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    medium (Moderators: Grimbal, william wu, towr, Icarus, ThudnBlunder, Eigenray, SMQ)    Markov Chain Visitations « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: Markov Chain Visitations  (Read 2123 times)
william wu

Gender:
Posts: 1291
 Markov Chain Visitations   « on: Feb 4th, 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 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:
Posts: 13730
 Re: Markov Chain Visitations   « Reply #1 on: Feb 4th, 2003, 7:32am » Quote 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 Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy => medium   - hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »