0
$\begingroup$

I am trying to understand why Random Walks' and Random Jumps', on a graph, transition matrix are also stochastic matrix.

A stochastic matrix is a matrix the values of each row add up to 1 and no value is < 0.

  • 0
    What about if you include a Random Walk that can also have jumps? Where these jumps have a certain probability also. What I mean by this is lets say your at A now you have some probability to go from A to B, because of random walk, BUT now you also have another probability to jump from A to C! How would that be a stochastic matrix compared to the original of random walking alone.2011-12-12

1 Answers 1

1

The $(i,j)$th entry of the transition matrix is the probability that on any given step, starting from vertex $i$, you will pass to vertex $j$. So the sum of the values in the $i$th row represents the probability that, on a given step, you will pass to vertex 1, or to vertex 2, or to vertex 3, etc. -- this probability is 1, since you must end up at one of the vertices. The entries are nonnegative since probabilities are numbers between 0 and 1 (inclusive).

  • 0
    @Loik: do you mean with jumps a transition between vertices which are connected more than with one edge?2011-12-12