We find the large deviation rate I for convergence in probability of the product W k —W 1 W 0 of temporally dependent random stochastic matrices. As the model for temporal dependencies, we adopt the Markov chain whose set of states is the set of all possible graphs that support the matrices W k . Such model includes, for example, 1) token-based protocols, where a token is passed among nodes to determine the order of processing; and 2) temporally dependent link failures, where the temporal dependence is modeled by a Markov chain. We characterize the rate I as a function of the Markov chain transition probability matrix P. Examples further reveal how the temporal correlations (dependencies) affect the rate of convergence in probability I.
