On Estimation of Maxima of Sums of Random Variables Indexed by Edges of Graphs

This paper considers a family of independent identically distributed random variables that are indexed by the edges of a graph. The maximum of sums of such variables along the paths of the graph is studied. We show that if one graph covers another one, then the maximum of sums for the first graph is stochastically greater than that for the second graph.