On Random Combinatorial Structures
and the Local Time of some Brownian Functionals

Bernhard Gittenberger

Technische Universität Wien, Austria

Algorithms Seminar

May 17, 1999

[summary by Philippe Flajolet]

A properly typeset version of this document is available in postscript and in pdf.

If some fonts do not look right on your screen, this might be fixed by configuring your browser (see the documentation here).

Two methods are presented in order to derive an integral representation of the multi-dimensional densities of the local times of Brownian excursion and reflected Brownian bridge. One is a direct method based on Kac's formula for Brownian functionals, the other is indirect and it uses the fact that functionals for Galton-Watson trees and random mappings yield corresponding Brownian functionals (on excursions and bridges respectively) as a limit. The latter approach relies on generating functions and singularity analysis. The presentation is based on joint works with Guy Louchard (Brussels).

1   Introduction

Brownian motion (BM) models discrete random walks on the integers upon a time normalization by the walk length n and a space normalization proportional to (n)1/2. Brownian excursion (BE) models walks constrained to start and end at level 0 and not allowed to become negative. Brownian Bridge (BB) corresponds to the constraint that the initial and final altitudes are the same (0, say). The problem tackled here is that of characterizing the amount of time an excursion or a bridge spends at various altitudes. Technically, the local time of the process x(t) at a is
T+(t,a)=
 
lim
e®0
1
e
ó
õ
t


0
I
 
[a,a+e]
(x(s))   ds,
where IP(·) is the indicator function of the predicate P.

Two methods are employed here in a complementary manner: (i) Kac's formula for Brownian functionals; (ii) singularity analysis applied to generating functions of simple random walks.

2   Kac's Formula

The starting point here is Kac's formula that relates the expectation of a functional of Brownian motion and the solution of an associated second order differential equation. Consider the functional
u
 
a
(a)=E a ó
õ
¥


0
e
-a t
 
exp æ
ç
ç
ç
ç
è		 - ó
õ
t


0
h[x(s)]  ds ö
÷
÷
÷
÷
ø		 f(x(t))  dt,
that is determined by h and f. (There, Ea means expectation when the process is conditioned by the initial value x(0)=a.) Then, the value ua(a) is a solution to the second order differential equation
(a- G)u=f,     G[u](a)=
1
2
u''(a)-h(a)u(a).     (1)
For instance setting h(x)=x establishes the connection between area problems and Airy functions.

The main result is established in part by means of Kac's formula and Green functions. It constitutes a powerful generalization to d-dimensional motion of the situation for 1-dimensional Brownian excursion, where
fx(y)=
1
i(2p)1/2
ó
õ
1+i¥


1-i¥
wew
sinh2(x(w)1/2)
exp æ
ç
ç
è		 -
y
(2)1/2
(w)1/2e
x(2w)1/2
 
sinh(x(w)1/2)
ö
÷
÷
ø		   dw
is the density function of T+(1,x). (See [1] and [2] for statements.) What is interesting is the companion use of discrete models in the proof, as discussed below.

3   Random Trees and Discrete Walks

One can also approach properties of Brownian excursion from the discrete version provided by simple random walks, where the steps are only of type ±1. In that case, useful combinatorial decompositions are available. The problem of the time spent at various altitudes for BE is rephrased as the problem of determining the number of times a fixed set S of levels are traversed by a discrete walk. (If one prefers, the corresponding distribution is also the distribution of the total number of nodes at altitude in S in a ``general'' random tree, given the usual combinatorial correspondence between trees and simple walks.) First, the discrete model is exactly solvable since one knows the generating function where uj marks traversal of level j,
G(u0,u1,...;z)=
zu0
1-
zu1
1-
zu2
·  
 · 
  ·
.
Second, upon rescaling, when the levels in S are of the form xj(n)1/2, the function G renormalizes nicely for z near the relevant singularity 1/4. In that case, contour integration in the style of Flajolet and Odlyzko's singularity analysis techniques yields the result. The end product is the formula already alluded to for the d-dimensional density for the local time of Brownian excursion.

4   Applications

The results obtained provide information of any algorithm or computer system that is modelled in the limit by Brownian excursions. Naturally, this applies to the M/M/1 model of queueing theory fame. It also applies to detailed aspects of tree traversals, to shellsort (in fact, the phase of sorting a 2-ordered permutation), and to the analysis of dynamic data structures under random evolutions (Françon's model of ``histories''), especially of the stack variety.

References

[1]
Gittenberger (Bernhard) and Louchard (Guy). -- The Brownian excursion multi-dimensional local time density. -- Preprint, 1999.

[2]
Gittenberger (Bernhard) and Louchard (Guy). -- On the local time density of the reflecting Brownian bridge. -- Preprint, 1999.
This document was translated from LATEX by HEVEA.