On the Properties of a Tree-Structured Server Process
Komlos, J. ; Odlyzko, A. ; Ozarow, L. ; Shepp, L. A.
Ann. Appl. Probab., Tome 1 (1991) no. 4, p. 118-125 / Harvested from Project Euclid
Let $X_0$ be a nonnegative integer-valued random variable and let an independent copy of $X_0$ be assigned to each leaf of a binary tree of depth $k$. If $X_0$ and $X'_0$ are adjacent leaves, let $X_1 = (X_0 - 1)^+ + (X'_0 - 1)^+$ be assigned to the parent node. In general, if $X_j$ and $X'_j$ are assigned to adjacent nodes at level $j = 0, \cdots, k - 1$, then $X_j$ and $X'_j$ are, in turn, independent and the value assigned to their parent node is then $X_{j+1} = (X_j - 1)^+ + (X'_j - 1)^+$. We ask what is the behavior of $X_k$ as $k \rightarrow \infty$. We give sufficient conditions for $X_k \rightarrow \infty$ and for $X_k \rightarrow 0$ and ask whether these are the only nontrivial possibilities. The problem is of interest because it asks for the asymptotics of a nonlinear transform which has an expansive term (the + in the sense of addition) and a contractive term (the + in the sense of positive part).
Publié le : 1991-02-14
Classification:  Aloha,  Poisson tree,  nonlinear recurrence,  60K99
@article{1177005984,
     author = {Komlos, J. and Odlyzko, A. and Ozarow, L. and Shepp, L. A.},
     title = {On the Properties of a Tree-Structured Server Process},
     journal = {Ann. Appl. Probab.},
     volume = {1},
     number = {4},
     year = {1991},
     pages = { 118-125},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1177005984}
}
Komlos, J.; Odlyzko, A.; Ozarow, L.; Shepp, L. A. On the Properties of a Tree-Structured Server Process. Ann. Appl. Probab., Tome 1 (1991) no. 4, pp.  118-125. http://gdmltest.u-ga.fr/item/1177005984/