On the Properties of a Tree-Structured Server Process

Abstract

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).

Locations

• The Annals of Applied Probability - View - PDF