Robin Pemantle (U.W.-Madison); work is joint with
Yuval Peres (U.C. Berkeley and Hebrew Univ.)

<h2>
Title: Recursions coming in from infinity on a tree, applied to
models of information propagation.
</h2>
<br>
Abstract: Let T be a finite tree of height n and suppose that
each vertex is assigned either a 1 or a -1.  Neighboring bits
like to agree, but an error is introduced with some fixed probability.
We consider three problems: (1) the root is given a fixed sign
the remaining vertices are chosen according to the above
probability scheme; can we guess the sign at the root from looking
at the leaves when n is large?  (2) all the leaves are assigned +1;
does this affect the likelihood of a 1 at the root as n goes to infinity?
(3) Suppose now the signs are assigned at random (independent coin flips)
at the leaves; now is the likelihood of a 1 given the leaves always
1/2 for large n?  In order to solve these problems, we solve a class
of recursions that "come in from infinity".  The solution shows that
the answers to the three questions depend on how large T is in a
capacity-theoretic sense.  For two of the questions, one obtains a
standard L^2 capacity, known to be equivalent to electrical network
properties of T and to recurrence of a certain random walk on T.  In
the third case, one gets a non-standard L^3 capacity.
<hr>