.ds xX .aU
.de aU
.sp .3
..
.ds yY .bU
.de bU
.sp -1.7v
..
.ds zZ .cU
.de cU
Murray Hill, New Jersey 07974
..
.de HX
.if \\$1=3 .ds }0
..
.EQ
delim $$
define 2k % 2 sp k %
define 3e % == back 65 {down 5 {size +2 /}} %
define aR % ~->~ %
define mi % ~-~ %
define ee % ~=~ %
define 3d % ,^ "...",^ %
define pl % ~+~ %
define sb % sub %
define sp % sup %
define la % lambda %
define gw % > back 80 up 45 wig % 
define lw % < back 80 up 45 wig % 
define mem % ~member~ %
define al % alpha %
define rth % sup {roman th} %
define gt % ~>~ %
define lt % ~<~ %
define ge % ~>=~ %
define le % ~<=~ %
define lf % lim from %
define sf % sum from %
define de % delta %
define ssp % sup prime %
define rR % roman %
define dar % ~{= back 30 = back 70 >} ~ %
define lar % "\v'-.040i'\l'.3i'\h'-.1i'\v'.040i'>" %
.EN
.am DE
.sp
.ls 2
..
.nr Pt 1
.nr Ht 1
.HM I
.ds HP 10 10 10
.ds HF 3 3 3
.ND "December 14, 1989"
.TL "311404-2199, 311404-2399, 311404-2699" 20878
On the Properties of a Tree-Structured Server Process
.sp
.AF "Rutgers University" 1
.AU "J. Komlos" JK xX
.AF "" 1
.AU "A. Odlyzko" AO yY
.AF "" 1
.AU "L. Ozarow" LO yY
.AF "AT&T Bell Laboratories" 1
.AU "L. A. Shepp" LAS zZ
.TM "11211-891214-20TM" "11217-891214-19TM"
.AS 1
.ls 2
.P
Let $X sb 0$ be a nonnegative integer-valued random variable and let
an independent copy of $X sb 0$ be assigned to each leaf of a binary
tree of depth $k$.
If $X sb 0$ and $X sb 0 ssp$ are adjacent leaves let $X sb 1 ee (X sb 0 mi 1 ) sp + pl ( X sb 0 ssp mi 1 ) sp +$
be assigned to the parent node.
In general, if $X sb j$ and $X sb j ssp$, are assigned to adjacent nodes at
level $j~=~ 0 3d k-1$,
then $X sb j$ and $X sb j ssp$
are, in turn, independent and the value assigned to their parent
node is then $X sb j+1 ee ( X sb j mi 1 ) sp + pl (X sb j ssp mi 1 ) sp +$.
We ask what is the behavior of $X sb k$ as $k aR inf$.
We give sufficient conditions for $X sb k aR inf$ and for $X sb k aR 0$ and
ask whether these are the only nontrivial possibilities.
The problem is of interest because it asks for the asymptotics of a non-linear
transform which has an expansive term (the $+$ in the sense of addition)
and a contractive term (the $+$'s in the sense of positive part).
.ls 1
.AE
.OK ""
.MT 4 1
.ls 2
.H 1 "INTRODUCTION"
In this paper we give some partial results
about the following process:
Let $"{" X sb 0 (i) ,~ ~ i ee 0,^ 1,^ "..." "}"$ be
independent, identically distributed,
non-negative integer variables.
For $j ee 1,^ 2,^ "..."$ we
define recursively,
.DS 3
.EQ
X sb j (i) ee ( X sb j-1 (2i) mi 1 ) sp + pl ( X sb j-1 (2i +1) mi 1 ) sp +^,
~~~i ee 0,^ 1 ,^ "..."
.EN
.DE
.P
We may think of the $"{" X sb 0 ( cdot )"}"$ as being the number of customers
associated with the leaves of a complete binary tree.
At each epoch, the number of customers at each leaf is diminished by one,
if it is positive.
The customers remaining at each pair of leaves are handed down and
collected at the parent node, which now becomes a leaf.
We want to study the behavior of $X sb k ee X sb k (0)$ as
$k aR inf$.
This model originally arose as a crude model of the Aloha
network as well as of a resource allocation model slightly related to that of [2] and became interesting in its own right.
.P
One obvious question
is to determine those
probability
laws governing $X sb 0$ for which $X sb k$ tends to zero
as $k^->^inf$.
In general we might ask what types of limiting behavior can occur.
.P
In particular consider the case where $X sb 0$ is
Poisson with mean $la$.
While this arrangement bears a superficial resemblance to the tree-structured
contention resolution algorithms introduced by Capetenakis [1], there
appears to be no real connection.
In any event, for Poisson variables we are interested in that value of
$la$ below which $X sb k aR 0$.
We find, using the results to follow and extensive numerical calculations, that for $la le .999$,
$X sb k aR 0$, and for $la ge 1.001$, $X sb k aR inf$, but
have been unable to prove or disprove the tempting conjecture that the critical
value of $la$ is 1.
.P
In the sequel we prove three results concerning the limiting
behavior of $X sb k$.
.H 3 "Theorem\ 1:"
If the probability distribution of $X sb k$ approaches a limit $X sb inf$,
then either
.DS
.TS
center;
r2 l l.
i)	$rR Pr ^ [ X sb inf ee 0 ] ee 1$,	i.e. $X sb inf ~==~ 0$
.sp
ii)	$rR Pr ^ [X sb inf ee 2 ] ee 1$,	i.e. $X sb inf ~==~ 2$
.sp
iii)	$rR Pr ^ [ X sb inf lt t ] ee 0$ for all $t$,	i.e. $X sb inf ~==~ inf$.
.TE
.DE
Furthermore, case ii) only occurs if for all $k ee 0,^ 1,^ "..."$,
$rR Pr ^[X sb k ~==~ 2 ] ~==~ 1$.
Now for any $j$, define
.DS 3
.EQ
g sb j ( al ) ee E^ [ al sp {X sb j} ] ^,
.EN
.DE
where $X sb j$ is a generic $j rth$ generation variable.
We shall prove
.H 3 "Theorem\ 2:"
If for some $al gt 2$ and some $j$, $g sb j ( al )$ satisfies
.DS 3
.EQ
g sb j ( al ) lt ( al mi 1 ) sp 2 ^,
.EN
.DE
then
.DS 3
.EQ
X sb k ~{lar} to {roman {size +2 a.s.}} ~ 0 ^.
.EN
.DE
On the other hand,
.H 3 "Theorem\ 3:"
If for some $j$, the mean of $X sb j$ satisfies
.DS 3
.EQ
E ^ [ X sb j ] gt 2 ^,
.EN
.DE
then $X sb k$ blows up, i.e.
.DS 3
.EQ
X sb k ~{lar} to {roman {size +2 a.s.}} ~ inf ^.
.EN
.DE
Corollary to Theorem\ 3 is a form parallel to that of Theorem\ 2:
.H 3 "Corollary 3a:"
If for some $al lt 1$ and some $j$, $g sb j ( al )$
satisfies
.DS 3
.EQ
g sb j ( al ) lt al sp 2 ^,
.EN
.DE
then $X sb k$ blows up.
.P
We show also that there is a gap between the hypotheses of Theorems\ 2 and 3,
i.e. there are $X sb 0$ satisfying neither hypothesis.
We nevertheless think it may be true that one of
$X sb k aR 0$, $X sb k aR inf$, or $X sb k ~==~ 2$,
always holds.
.H 3 "Proofs of the results."
We first prove
Theorem\ 1.
Note that if
$X sub k$
approaches a limit, then
for all $0 le al le 1$, $g sb k ( al )$ approaches a limit $g sb inf ( al )$.
Now, since
.DS 3
.EQ
X sb j+1 (i) ee ( X sb j ( 2i) mi 1 ) sp + pl
(X sb j ( 2i+1) mi 1 ) sp + ^,
.EN
.DE
then for
.DS 3
.EQ
g sb j ( al ) ee sf 0 to inf ~ rR Pr ^ [ X sb j ee i ] ^al sp i ^,
.EN
.DE
we get the recurrence
.DS 3
.EQ (1)
g sb j+1 ( al ) ee left [ {g sb j ( al ) pl ( al -1) p sb j} over al
right ] sp 2 ^,
.EN
.DE
where
.DS 3
.EQ
p sb j ~=del~ rR Pr ^ [ X sb j ee 0 ] ^.
.EN
.DE
Now if $g sb j ( al ) aR g sb inf ( al )$ for $0 le al le 1$, then
$p sb j aR p sb inf$ and
.DS 3
.EQ
g sb inf ( al ) ee left [ {g sb inf ( al ) pl ( al -1) p sb inf } over
al right ] sp 2 ^.
.EN
.DE
This quadratic equation can be solved to yield
.DS 3
.EQ (2)
g sb inf ( al ) ee ( 1 - al ) p sb inf pl {al sp 2} over 2 ~+-~
1 over 2 ^al ^ sqrt { al sp 2 mi 4 p sb inf ^al pl 4 p sb inf} ^.
.EN
.DE
If $p sb inf ee 0$, this has the solutions
.DS 3
.EQ
g sb inf ( al ) ee 0 ,^ al sp 2 ^,
.EN
.DE
corresponding to cases ii) and iii) above.
If $p sb inf ee 1$, then (2) has solutions
.DS 3
.EQ
g sb inf ( al ) ee 1 ,~~~ (1 mi al ) sp 2 ^.
.EN
.DE
The former corresponds to case i), and the latter is
spurious (i.e. not increasing and so clearly not a probability generating function).
We can further see that case ii) cannot be approached, but
can only arise if
$rR Pr ^ [ X sb 0 ( cdot ) ee 2 ] ee 1$.
To see this, let
$p sb ji ee P^(X sb j ee i)$ and thinking of $j$ as fixed, set
.DS 3
.EQ
al sb i ee rR Pr ^ [ X sb j ee i ] ^,
.EN
.DE
and
.DS 3
.EQ
beta sb i ee rR Pr ^ [ X sb j+1 ee i ] ^.
.EN
.DE
Since rule (1) gives
.DS 3
.EQ
beta sb 2 ee 2( al sb 0 pl al sb 1 ) ^ al sb 3 pl al sb 2 sp 2
.EN
.DE
and since $( al sb 0 pl al sb 1 ) pl al sb 3 le 1 mi al sb 2$
we have
.DS 3
.EQ
beta sb 2 le 2 ^ left ( {1 mi al sb 2} over 2 right ) sp 2 pl
al sb 2 sp 2 lt al sb 2 ~~ rR if ~~ 1 over 3 lt al sb 2 lt 1 ^.
.EN
.DE
Thus if $p sb  j2$ satisfies
$1 over 3 lt p sb j2 lt 1$,
then $p sb j+1,2 lt p sb j2$,
so that $p sb j2$ cannot approach 1 from below.
.P
Note also that a solution to equation\ (2) for which $0 lt p sb inf lt 1$
cannot be a generating function.
The reason for this is that a generating function, viewed as a function
on the complex plane, must have its innermost singularity on the real line
(see [3; Section\ 7.2]).
However, since the solution of equation (2) has singularities at
.DS 3
.EQ
alpha ~=~ 2 ^ p sb inf ~+-~ 2 ^sqrt {p sb inf ^ ( p sb inf ^-^ 1)} ^,
.EN
.DE
these singularities are complex unless $p sb inf ~=~0$ or $p sb inf ~=~ 1$.
.P
Theorem\ 1 is proven.
.P
Now, to prove Theorem\ 2, assume that for some
$j$ and $al gt 2$,
.DS 3
.EQ
g sb j ( al ) ee theta ( al - 1 ) sp 2 ^,
.EN
.DE
where,
by the hypothesis of Theorem\ 2 and the fact that $g sb j ^( al ) gt 1$ for
$al gt 1$,
.DS 3
.EQ (3)
1 over {( al -1 ) sp 2} lt theta lt 1 ^.
.EN
.DE
Using (1), we get
.DS 3
.EQ (4)
g sb j+1 ( al ) mark ee left [ {g sb j ( al ) pl p sb j ( al -1)} over
al right ] sp 2
.EN
.sp
.EQ
lineup ee left [ { theta ( al -1) sp 2 pl p sb j ( al -1) } over
al right ] sp 2
.EN
.sp
.EQ
lineup ee ( al -1) sp 2 ~ left [ {theta ( al -1) pl p sb j} over al
right ] sp 2 ^,
.EN
.DE
or since $p sb j lt 1$
.DS 3
.EQ
{g sb j+1 ( al )} over {g sb j ( al )} lt 1 over theta ~
left [ {theta ( al -1) pl 1} over al right ] sp 2 ^.
.EN
.DE
The right-hand side is strictly less than 1 for all $theta$ satisfying
(3), so that $g sb j ( al ) ~\(da~ 1$.
Now if $g sb j ( al ) ee 1 pl de$, then
from (4) since $p sb j le 1$,
.DS 3
.EQ
g sb j+1 ( al ) mark ~<=~ left [ {1 pl de pl al -1} over al right ] sp 2
.EN
.sp
.EQ
lineup ee left ( 1 pl de over al right ) sp 2
.EN
.sp
.EQ
lineup ee 1 pl 2 over al ^de pl {de sp 2} over {al sp 2}
.EN
.sp
.EQ
lineup ee 1 pl de ^ left [ 2 over al pl de over {al sp 2} right ] ^.
.EN
.DE
Now since $al gt 2$, if $de$ is sufficiently small,
.DS 3
.EQ
g sb j+1 ( al ) lt 1 pl rho de ,~~~ rR {f or}
.EN
.DE
some
.DS 3
.EQ
rho lt 1 ,
.EN
.DE
hence for all $j gt j ssp$
.DS 3
.EQ
g sb j ( al ) lt 1 pl rho sp {j ^-^ j ssp} de ^.
.EN
.DE
Now
.DS 3
.EQ
g sb j ( al ) mark ge roman Pr ^ [ X sb j ee 0 ] pl al ~ rR Pr ^ [ X sb j gt 0 ]
.EN
.sp
.EQ
lineup ee p sb j pl al (1 mi p sb j ) ^.
.EN
.sp
.EQ
1 pl rho sp {j-j ssp} ^de mark ge p sb j pl al (1 mi p sb j )^,~~~
roman {f or~all}~~
j gt j ssp
.EN
.DE
or
.DS 3
.EQ
( al - 1 ) (1 - p sb j ) mark le rho sp {j-j ssp} de
.EN
.sp
.EQ
( al -1) ^sf {j ssp} to inf ~ (1 mi p sb j ) le de ^
sf {j ssp} to inf ~ rho sp {j-j ssp} ee de over {1 mi rho} lt inf ^,
.EN
.DE
so by the Borel-Cantelli lemma $rR Pr^ [ X sb j gt 0 ] aR 0$ a.s.
.P
To prove Theorem\ 3, suppose that
.DS 3
.EQ
E^[X sb j ] ee 2 pl de ^.
.EN
.DE
Since
.DS 3
.EQ
X sb j+1 ( i) mark ee (X sb j ( 2i ) mi 1 ) sp + pl (X sb j ( 2i+1) mi 1 ) sp +
.EN
.sp
.EQ
lineup ge X sb j ( 2i ) pl X sb j ( 2i+1) mi 2
.EN
.sp
.EQ
E^[X sb j+1 ] lineup ge 2E^[X sb j ] mi 2
.EN
.sp
.EQ
lineup ee 2 pl 2 de ^.
.EN
.DE
Thus
.DS 3
.EQ
E^[ X sb {j ssp} ] ge 2 pl 2 sp {(j ssp - j)} ^de ^, ~~~
roman {f or ~all}~~ j ssp ge j ^.
.EN
.DE
Now
.DS 3
.EQ
rR Var ^ ( X sb j+1 ) ee 2 ^rR Var ^ [( X sb j mi 1 ) sp + ] ^.
.EN
.DE
But
.DS 3
.EQ
rR Var ^ [ (X sb j mi 1 ) sp + ] ee rR Var ^ (X sb j ) pl p sb j
( 1 mi p sb j mi 2 E ^X sb j ) ^.
.EN
.DE
Since
.DS 3
.EQ
E^X sb j gt 2
.EN
.DE
the last term is $lt 0$, so
.DS 3
.EQ
rR Var ^ ( X sb j+1 ) lt 2 ^rR Var ^( X sb j ) ^.
.EN
.DE
Hence
.DS 3
.EQ
rR Var ^( X sb {j ssp} ) lt 2 sp {j ssp - j} ^rR Var ^ ( X sb j ) ^.
.EN
.DE
Since the mean of $X sb j$ grows, we can apply the Chebyshev
inequality to show that for any finite $t$, for sufficiently
large $j ssp$,
.DS 3
.EQ
rR Pr ^ [ X sb {j ssp} lt t ] le k left ( 1 over 2 right ) sp {j ssp} ^,
.EN
.DE
hence goes to zero.
A Borel-Cantelli argument shows $X sb j aR inf$ strongly.
.P
To show the equivalence of Theorem\ 3 and Corollary\ 3a,
note that $g sb j ( al )$ is continuous, at least on the unit disc.
Then since
.DS 3
.EQ
E^ X sb j ee d over {d al } ~ g sb j ( al ) | sb {al ee 1} ^,
.EN
.DE
the function $g sb j ( al ) mi al sp 2$ is continuous on $[0,^ 1]$, is
zero at $al ee 1$ and increasing at that point.
Hence it must be negative for some interval including the point
$al ee 1$.
Therefore
.DS 3
.EQ
E^ [ X sb j ] gt 2 dar g sb j ( al ) lt al sp 2
.EN
.DE
for some $al$ sufficiently near 1.
.P
As for the reverse implication, consider the function
.DS 3
.EQ
h sb j ( al ) ee {g sb j ( al )} over al ^.
.EN
.DE
Clearly $h sb j (1) ee 1$.
Now
.DS 3
.EQ
h sb j ssp ( al ) ee {g sb j ssp ( al )} over al mi
{g sb j ( al )} over {al sp 2} ^.
.EN
.DE
Also
.DS 3
.EQ (5)
h sb j sp {prime prime} ( al ) mark ee {d sp 2} over
{d al sp 2} ~sf 0 to inf ~ p sb j al sp j-1
.EN
.sp
.EQ
lineup ee d over {d al} ~sf 0 to inf ~ ( j-1) ^ p sb j al sp j-2
.EN
.sp
.EQ
lineup ee sf 0 to inf ~ ( j-1) (j-2) ^p sb j al sp j-3 ^.
.EN
.DE
Since all the terms in (5) are non-negative, $h sb j ( al )$ is
convex.
If
.DS 3
.EQ
E^X sb j lt 2 ^,
.EN
.DE
then
.DS 3
.EQ
h sb j ssp ( 1) ee {g sb j ssp (1)} over 1 mi
{g sb j (1)} over 1 lt 1 ^.
.EN
.DE
Thus $h sb j ( al )$, since it is convex must lie above the line $al$,
and we have shown
.DS 3
.EQ
E^[X sb j ] le 2 dar g sb j ( al ) ge al sp 2 ^,
.EN
.DE
for all $al lt 1$.
Therefore Theorem\ 3 is equivalent to Corollary\ 3a.
.H 1 "CONCLUSION"
We have proved the theorems described in the introduction.
In particular, Theorems\ 2 and 3 applied to a Poisson starting
distribution yield that
.DS 3
.EQ
la lt 0.999 dar X sb k aR 0 ^,
.EN
.DE
and
.DS 3
.EQ
la gt 1.001 dar X sb k aR inf ^.
.EN
.DE
The lower number follows from the fact that
$g sb 55 ^ ( 2.03) ee 1.059 lt ( 2.03 mi 1 ) sp 2 ee 1.0609$.
The upper value is implied by the fact that $E^[X sb 170 ] ee 2.311$.
The region of uncertainty can be narrowed with more numerical work, but the computations
become onerous because of difficulty of dealing with roundoff errors.
Our computations were carried out using the multiprecision facilities
of the Maple symbolic computation language.
.P
It remains to be seen whether any behavior other than that described
in Theorem\ 1 is possible.
.P
We finally prove there is a gap between the hypotheses of
Theorems\ 2 and 3, that is there is an $X sb 0$ which satisfies neither
hypothesis.
Nevertheless, it seems likely that the conclusion of Theorem\ 1 always holds,
i.e. either $X sb k aR 0$, $X sb k aR inf$, or the trivial case
$X sb k ~==~ 2$ holds.
We have been unable to prove this.
.P
To show an example it seems worthwhile to slightly change notation by
replacing for each $k ge 0$,
.DS 3
.EQ
Y sb k ee ( X sb k mi 1 ) sp +
.EN
.DE
so that the recurrence becomes
.DS 3
.EQ
Y sb k+1 ee ( Y sb k pl Y sb k ssp mi 1 ) sp + ^,~~ k ge 0 ^.
.EN
.DE
Although $X sb k$ represents the original notation, calculations become
simpler in the $Y sb k$ notation.
Theorems\ 2 and a slightly stronger version of Theorem\ 3, become in the $Y$ notation,
.H 3 "Theorem\ $bold {2 ssp}$."
If $E ^ al sp {Y sb k} le al ^-^ 1$ for some $al gt 2$ and $k ge 0$, then
.DS 3
.EQ
Y sb k ~{lar} to {roman {size +2 a.s.}} ~ 0 ^.
.EN
.DE
.H 3 "Theorem\ $bold {3 ssp}$."
If $E ^Y sb k ge 1$ for some $k$ and if $Y sb 0 ~3e~ 1$, then
.DS 3
.EQ
Y sb k ~{lar} to {roman {size +2 a.s.}} ~ inf ^.
.EN
.DE
.P
We will give an example of $Y sb 0$ where $E ^ al sp {Y sb k} gt al -1$ for
all $k$ and $al gt 0$ but $E^ Y sb k lt 1$ for all $k$.
To do this fix $0 lt eta lt 1$ and let $ Y sb 0 ( eta )$ take values 0 and
2 only with probabilities
.DS 3
.EQ
P( Y sb 0 ( eta ) ee 2 ) ee eta
.EN
.sp
.EQ
P( Y sb 0 ( eta ) ee 0 ) ee 1 - eta ^.
.EN
.DE
We will show that for some $eta ,^ Y sb 0 ( eta )$ lies in the gap.
.P
Let $eta sb n$ be that value of $eta$ for which $E ^ al sp {Y sb n ( eta )}$
is tangent to the line $al -1$, i.e. there is a value $al ee al sb n$
for which
.DS 3
.EQ
E^ al sb n sp {Y sb n ( eta sb n )} mark ee al sb n mi 1
.EN
.sp
.EQ
d over {d al} ~ E^ al sp {Y sb n ( eta sb n )} lineup ee 1 ~~~~ rR at ~ al ee al sb n ^.
.EN
.DE
It is easy to verify since $E^ al sp {Y sb n ( eta )}$ increases in $eta$
for $al gt 1$ that $al sb n ~ \(da$ in $n$ and $eta sb n ~\(ua$
in $n$.
Denote $eta sb inf ee lim ^ eta sb n$.
.P
For each fixed $n$, $Y sb k ^ ( eta sb n ) aR 0$ as $k aR inf$ because of
Theorem\ $2 ssp$ so that by Theorem\ $3 ssp$,
.DS 3
.EQ (6)
E ^Y sb k ^ ( eta sb n ) lt 1 ~~~ roman {f or ~all}~k ge 0 ,~~
n ge 0 ^.
.EN
.DE
Since $Y sb k ^ ( eta sb n ) ~\(ua~ Y sb k ^ ( eta sb inf )$ we must
have from (6),
.DS 3
.EQ
E^Y sb k ^ ( eta sb inf ) le 1 ~~~ roman { f or ~ all}~~ k ge 0
.EN
.DE
It follows that $Y sb 0 ^ ( eta sb inf )$ satisfies neither the hypothesis of
Theorem\ $2 ssp$ nor $3 ssp$ and $X sb 0 ee Y sb 0 ^ ( eta sb inf ) pl 1$
satisfies neither the hypothesis of Theorem\ 2 nor of Theorem\ 3.
.P
Nevertheless it seems possible that there is no $Y sb 0$ for which $Y sb k$ oscillates,
i.e. neither $Y sb k aR 0$ nor $Y sb k aR inf$ (except for $Y sb 0 ~==~ 1$).
On the other hand, if there is such an example it probably has the following
property:
.DS 3
.EQ (7)
E^ Y sb k lt 1 ~~~ roman {f or ~ all}~~ k
.EN
.DE
but if $Y sb 0 ssp gt Y sb 0$ in the stochastic sense then
.DS 3
.EQ
Y sb k ssp aR inf ^.
.EN
.DE
To see that there are $Y sb 0$'s with this property, suppose $Y sb 0 sp {up 25 (0)}$ has $P ( Y sb 0 sp {up 25 (0)} gt 1 ) gt 0$
and (7) holds for $Y sb 0 ee Y sb 0 sp {up 25 (0)}$.
Let $P( Y sb 0 sp {up 25 (1)} ee j ) ee P( Y sb 0 sp {up 25 (0)} ee j )$ for
$j gt 1$ and let $P( Y sb 0 sp {up 25 (1)} ee 1 )$
be as large as possible subject to (7) holding for
$Y sb 0 ee Y sb 0 sp {up 25 (1)}$.
If $Y sb 0 sp {up 25 (n)}$ has been defined, let $P( Y sb 0 sp {up 25 (n+1)} ee j ) ee P (Y sb 0 sp {up 25 (n)} ee j )$ for
$j gt n+1$ and for $j lt n$ and let $P( Y sb 0 sp {up 25 (n+1)} ee n pl 1 )$
be as large as possible subject to (7) holding for
$Y sb 0 ee Y sb 0 sp {up 25 (n+1)}$.
Then we have $Y sb 0 sp {up 25 (n)}$ stochastically increases in $n$ say to
$Y sb 0 sp {up 25 {( inf )}}$.
Since
.DS 3
.EQ
E^Y sb k sp {up 25 (n)} lt 1
.EN
.DE
for all $k$ and $n$ we must have
.DS 3
.EQ
E^ Y sb k sp {up 25 {( inf )}} le 1 
.EN
.DE
but since $P( Y sb 0 sp {up 25 (0)} gt 1 ) gt 0$, we must have
.DS 3
.EQ
E^Y sb k sp {up 25 {( inf )}} lt 1 ~~~ roman {f or~ all}~~ k ^.
.EN
.DE
It follows that if $Y sb 0 ssp gt Y sb 0 sp {up 25 {( inf )}}$ then
$Y sb 0 ssp gt Y sb 0 sp {up 25 (k)}$ for some $k$ and $Y sb k ssp aR inf$.
.PH ""
.ls 2
.bp
.ce
\f3REFERENCE\f1
.sp
.RL
.LI
J. Capetenakis,
``Tree Algorithms for packet broadcast channels,''
IEEE Trans. on Inf. Th., IT-25, Sept. 79 (505-515).
.LI
M. Fisher, N. Griffeth, L. Guibas, and N. Lynch,
Optimal placement of identical resources in a tree,
\f2Inform. Comp.\f1, to appear.
.LI
E. C. Titchmarsh, \f2The Theory of Functions\f1,
Oxford University Press, (London, 1939).
.LE
.ls 1
.CS