We are interested in computing the expected meeting time of two passengers randomly riding city buses in Ljubljana. The problem can be modeled using random walks on graphs. A random walk on a weighted digraph is equivalent to a Markov chain, as the transition probability to the next state depends solely on the current state. In this work, we present a theorem that provides the necessary and sufficient conditions for finiteness of the expected meeting time of two independent Markov chains, as well as the explicit formula for the computation of the matrix of expected meeting times. The formula is then tested on synthetic data and compared with simulations of two simultaneous random walks. The problem of the meeting of two passengers is addressed by constructing three network models of the Ljubljana Passenger Transport (LPP), on which we run simulations and implement the calculation of the matrix of expected meeting times.
|
