We would like to choose a random walk as a Markov process on this graph: for every vertex i and its outgoing edge to j , choose probability S i j of the walker randomly using this edge after visiting i . Formally, find a stochastic matrix S (containing the transition probabilities of a Markov chain) such that