François Delarue
Information Transmission under Random Emission Constraints
Abstract:
We model the transmission of a message on the complete graph with n
vertices and limited resources. The vertices of the graph represent
servers that may broadcast the message at random. Each server has a
random emission capital that decreases at each emission. Quantities of
interest are the number of servers that receive the information before
the capital of all the informed servers is exhausted and the
exhaustion time. We establish limit theorems (law of large numbers,
central limit theorem and large deviation principle), as n tends to
infinity, for the proportion of visited vertices before exhaustion and
for the total duration. The analysis relies on a construction of the
transmission procedure as a dynamical selection of successful nodes in
a Galton-Watson tree with respect to the success epochs of the coupon
collector problem.
Joint work with Francis Comets and Rene Schott.