Bit flipping models

Speaker : Sergei Zuyev
Chalmers university, Sweden
Date: 21/02/2012
Time: 2:00 pm - 2:30 pm
Location: LINCS Meeting Room 40

Abstract

In many areas of engineering and science one faces with an array of devices which possess a few states. In the simplest case these could be on-off or idle-activated states, in other situations broken or `dead’ states are added. If the activation-deactivation (flipping) or breakage cycles produce in a random fashion, a natural question to ask is when, if at all, the system of devices, which we call bits, recovers to some initial or ground state. By this we usually mean the state when all the bits are not active, allowing only for idling and/or broken bits to be seen. When the number of bits is infinite, the time to recover may assume finite or infinite values when the system actually does not recover. In the latter case we speak of transient behaviour of the system. In the former case, depending of whether the mean of the recover time exists or not, we speak of positive or null-recurrence of the system. The terminology is borrowed from Markov chains setting and the above classification is tightly related to the exact random mechanism governing the change of bits’ states. The main result for models involving infinite number of bits is the existence of the critical decay of flipping intensities, at which the model changes from transient to the recurrent behaviour. We show that the recurrence is always null recurrence and estimate which moments of the recover time exist. Besides, a central limit theorem can be established for the exact way the system behaves in the transient regime.