Some Extremal Markov Chains

Some Extremal Markov Chains By J. E. MAZO (Manuscript received March 10, 1982) Using a Markov chain model for the motion of a particle through a V-node network, we consider the quantities ny, which are the average number of steps taken by the particle in traveling from an originating node, i, to a destination node, j. A figure-of-merit, N, for the entire network is introduced by averaging nij over i and j. We investigate which networks minimize or maximize N, either when no restriction is placed on the Markov chain, or when we restrict it so that it corresponds to random routing. By the latter we mean that at each node the particle "selects at random" lines from an undirected network graph. We show that for random routing, the complete graph has N = (V -- 1) and is the minimizing graph. The maximizing graph is unknown, but we establish that the worst behavior of N increases at least with the cube of the number of vertices, but no worse than the 3.5 power. Properties of the class of graphs known as barbells are useful here. The minimizing unrestricted chain corresponds to placing the nodes on a circle and proceeding unidirectionally from one node to the next. Here, N = V/2. I. INTRODUCTION AND RESULTS Our work is set against the background of the Markov chain model for the movement of a "particle" or "message" through a network of V nodes. Thus, suppose a particle originates at node i and is destined for node j ^ i. The particle wanders through the network toward its destination via a Markov chain, going to node n from node m with probability/w The quantity pmn is the (m, n) element of the transition matrix P of the Markov chain whose states correspond to the nodes of the network.