Title: Randomized Load Balancing on Networks with Stochastic Inputs,
Abstract: Iterative load balancing algorithms for indivisible tokens have been studied
intensively in the past. Complementing previous worst-case analyses, we study
an average-case scenario where the load inputs are drawn from a fixed
probability distribution. For cycles, tori, hypercubes and expanders, we obtain
almost matching upper and lower bounds on the discrepancy, the difference
between the maximum and the minimum load. Our bounds hold for a variety of
probability distributions including the uniform and binomial distribution but
also distributions with unbounded range such as the Poisson and geometric
distribution. For graphs with slow convergence like cycles and tori, our
results demonstrate a substantial difference between the convergence in the
worst- and average-case. An important ingredient in our analysis is new upper
bound on the t-step transition probability of a general Markov chain, which is
derived by invoking the evolving set process.