Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Problem Overview

I am to figure out $v_\pi$ of a certain Markov state.

Given Information

A set of actions, $a$ containing ${up, down, left, right}$

$v_\pi(12), v_\pi(13), v_\pi(14)$ (I am given values for these)

$r(...) = -1$ (all returns are -1, regardless of the transition)

$p(...) = 1$ (each action maps to only one resulting state)

$\pi(a|s) = 1/4$ (the probability of transitioning to any state is 1/4)

$\gamma = 1$ (no discounting is being applied)


Find $v_\pi(15)$, given that transitioning to states $12, 13, 14, 15$ from $15$ is equiprobable.

Relevant Equations

Bellman equation for $v_\pi$

$v_\pi(s)=\sum_a \pi(a|s)\sum_{s'} p(s'|s,a)[r(s,a,s')+\gamma v_\pi(s')]$

A simplified version, given the context of this question, is:

$v_\pi(s)=\sum_a \sum_{s'}(-1 + v_\pi(s'))$

My Approach

I can easily solve this problem where there are only transitions to states $12, 13, 14$ but I'm having a hard time grasping this problem recursively, because at the end of the Bellman equation, when considering the transition to $15$, $v_\pi(s')$ is $v_\pi(15)$.

Therefore, $v_\pi(15)$ depends on $v_\pi(15)$ and leaves me very confused as to how to compute this by hand (I can't just run an insane number of computations until it converges). Should I just do it iteratively until the value doesn't seem to change too much?

Does anyone have any suggestions for me? Help would be greatly appreciated!

share|cite|improve this question
What's $v_{\pi}(15)$? Probability of eventually visiting state 15? – Alex Oct 15 '12 at 1:15
$v_\pi(15)$ is the value of being in a state, considering the values of all states that could possibly be transitioned into from that state. I gave the formula for it in my question. – BraedenP Oct 15 '12 at 1:18
$\gamma=1$ is just a standardizing condition in Kolmogorov forward equation – Alex Oct 15 '12 at 1:24
Hmm, I understand the semantics of the values; I am just unsure of how to solve this, because the $v_\pi(s')$ at the end of the Bellman equation depends on the value I'm trying to calculate. – BraedenP Oct 15 '12 at 1:36
I am trying to find $v_\pi(15)$ and within that inner sum, I am enumerating over state $15$ which requires me to calculate $v_\pi(15)$ in my solution to that very same function. The recursion is messing with my mind lol. – BraedenP Oct 15 '12 at 1:37

I think you should follow the way Kolmogorov forward equations are solved for a birth and death MCs. If rate of growth is $\lambda$ and extinction is $\mu$, then $$ 0=p'_{j}(t)=\mu \pi_{j+1} + \lambda \pi_{j-1} - (\lambda+\mu) \pi_{j} $$ hence $$ \pi_j=\frac{\mu}{\mu+\lambda}\pi_{j+1} + \frac{\lambda}{\mu+\lambda} \pi_{j-1} $$ with the standardizing condition $\sum_{k \geq 0} \pi_k =1$. so you should eng up getting $\pi_0=1-\frac{\lambda}{\mu}$, $\pi_j = \big(\frac{\lambda}{\mu} \big)^j (1-\frac{\lambda}{\mu})$, i.e. Geometric distribution

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.