1
$\begingroup$

Given the following markov chain, where T1 is the start state, the labels are shown on the state( 'a' in this case) and p and 1-p are probabilities for that transition happening:

enter image description here

Now, for what values of p is it the case that there is greater than or equal to 0.5 chance of reaching state the labelled a, within a maximum of two steps, from the initial state T1?

So, say p=0.5 then, the transition $(T1 \rightarrow T2)$ will happen with a probability of $1-0.5=0.5$. But with the transitions $(T1 \rightarrow T1 \rightarrow T2)$ will happen with a probability of $p \times (1-p)$ i.e. $=0.5 \times (1-0.5) = 0.25$. So if p=0.5 this will be less than 0.5.

I can't get my head around finding the values for p where the overall probability of reaching label 'a' within a maximum of 2 steps is greater than 0.5. In PCTL this would be written as: $T1 \models P_{\geq 0.5} (F^{\leq 2} a)$

(Sorry for the poor drawing)

$\endgroup$

1 Answer 1

1
$\begingroup$

From what you have said, you need to solve $$(1-p)+p(1-p) \ge \frac12$$ subject to the usual condition for any probability that $0 \le p \le 1$.

This is at worst a quadratic which I will leave for you to solve.

Your example of $p=0.5$ has an error: the probability of reaching state $T_2$ in one step would indeed be $0.5$ and of reaching state $T_2$ exactly on the second step would be $0.25$. So the probability of reaching state $T_2$ in a maximum of two steps would be $0.75 \gt 0.5$.

$\endgroup$
6
  • $\begingroup$ oh so I multiplied where I should've added the probabilities together? $\endgroup$
    – sudo
    Commented Nov 25, 2014 at 21:03
  • 1
    $\begingroup$ Yes: the probability of either of two mutually exclusive events happening is the sum of their individual probabilities. Contrast this with the probability of both of two independent events happening, which is the product of their individual probabilities. $\endgroup$
    – Henry
    Commented Nov 25, 2014 at 21:06
  • $\begingroup$ Yes, that makes perfect sense. I see how I made a mistake there. Thank you for your help. $\endgroup$
    – sudo
    Commented Nov 25, 2014 at 21:08
  • $\begingroup$ Ok at my first attempt, I get $0 \leq p \leq \sqrt{\frac{1}{2}}$ but that doesn't look right? $\endgroup$
    – sudo
    Commented Nov 25, 2014 at 21:31
  • 1
    $\begingroup$ Why not? $\sqrt{\frac12} \approx 0.7071$ and you would prefer $p$ to be small, to increase the chance of leaving $T_1$ $\endgroup$
    – Henry
    Commented Nov 25, 2014 at 21:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .