Creating order and ballot sequences

Abstract

Rudolf Ahlswede introduced the theory of creating order roughly at the same time as his theory of identification. He was always surprised that it did not achieve the same popularity as identification. We shall here present a multi-user model in which, contrasting to Ahlswede's original model, the size of the memory may vary in time. The influence of the maximum size of the memory device on the expected occurrence of the first 0 in the sequence produced by the organizer is studied. In the case that there is one outgoing bit in each time unit two steps of a simple random walk on the lattice can be combined to one step in a random walk for the exhaustion of the memory. © Springer-Verlag Berlin Heidelberg 2013.