Trivedi/Wojtczak: Timed Branching Processes.

Timed Branching Processes.

Ashutosh Trivedi and Dominik Wojtczak.

We study Timed Branching Processes (TBPs), a natural extension of (multitype) Branching Processes (BPs) where each entity is equipped with a finite set of private continuous variables, called clocks. Clocks grow uniformly with the same rate and using them various timing constraints can be imposed on the branching rules of the system, e.g. the way an entity reproduces (branches) can depend on its age. In comparison with discrete-time BPs, where all the entities live for a constant amount of time before they branch (and die), and more general continuous-time BPs, where for each entity the amount of time before the branching takes place is governed by an exponential distribution, our model can be seen as an abstraction of continuous-time BPs where we do not know the exact distribution on the time before an entity branches, but rather some time interval when it happens. Allowing an external controller to decide at what point in time the branching takes place permits us to study the best/worst behaviour of the system. For each given instance of TBP, we show how to answer the following questions: What is the supremum probability of extinction for a given initial population? What is the supremum probability that a given population becomes extinct in less than t time units? What is the supremum expected number of entities of a given type that will be created before the population becomes extinct?

Proceedings of the Seventh International Conference on the Quantitative Evaluation of Systems (QEST 10), Pages 219 - 228, IEEE, 2010.