##### Department of Mathematics,

University of California San Diego

****************************

### Math 269 - Combinatorics

## Franklin Kenter

#### Department of Computational and Applied Mathematics Rice University

## Concentration of the Stationary Distribution on General Random Directed Graphs

##### Abstract:

We consider a random model for directed graphs whereby an arc is placed from one vertex to another with a prescribed probability $p_{ij}$ which may vary from arc to arc. Using perturbation bounds as well as Chernoff inequalities, we show that the stationary distribution of a Markov process on a random graph is concentratednear that of the â€œexpectedâ€ process under mild conditions. These conditions involve the ratio between the minimum and maximum in- and out-degrees, the ratio of the minimum and maximum entry in the stationary distribution, and the smallest singular value of the transition matrix. Lastly, we give examples of applications of our results to known models of directed graphs.

Host: Jeff Remmel

### November 5, 2013

### 3:00 PM

### AP&M 7321

****************************