Random Motion on Simple Graphs
E. Papageorgiou, V.G. Papanicolaou, and D. Lepipas
Department of Mathematics
NationalTechnicalUniversity of Athens
CaliforniaStateUniversity, Stanislaus
Abstract. Consider a (star-like) graph with n edges meeting at one node and a Brownian Motion on this graph with a Kirchhoff condition at the node. We compute exit probabilities and certain other probabilistic quantities regarding exit and occupation times. This mathematical model can be applied to random propagation of information in networks.
1 Introduction
Letbe the set consisting ofsemiaxes, , with a common originandthe Brownian motion process on, namely the diffusion process on whose infinitesimal generatoris
(1)
where
,
together with the continuity conditions
(2)
and the so-called ‘Kirchhoff condition’
(3)
It is well-known thatdefines a (unique) self-adjoint operator on the space
The processdoes a standard Brownian motion on each of the semiaxes and, when it hits, it continues its motion on the -th semiaxis, withprobability(see, e.g., [3]). For notational clarity it is helpful to use the coordinate, , for the semiaxis, . Notice that, ifis a function onthen its-th component,, is a function on, hence.
In this article we study certain issues regarding exit (or hitting) times and occupational times of. Our results extend certain classsical results for thestandard Brownian motion on (e.g. the continuous gambler’s ruin problem—see, e.g., [1]) which actually corresponds to the case (, where ). Possible applications may include random flow of information in simple networks.
2 Exit Times and Exit Probabilities (Explicit Calculations)
On each semiaxis, , consider the point. These points define the (bounded) subset of
(thusconsists ofline segments of lengths, with a common initial point, namely). We assume thatand we denote bythe exit time of, i.e. the smallest time such that, for some.We also introduce the events
(4)
If, we denote the associated probability measure byand the expectation by. Let us now consider the following boundary value problem for
, (5)
whereis a complex parameter and (2),(3) namely
, (6)
, (7)
together with the boundary conditions
(8)
and
, (9)
The solutionof the above problem has the Feynman-Kac representation (see, e.g., [2] or [4])
(10)
as long as
where is the smallest eigenvalue of acting onwith Dirichlet (i.e.) boundary conditions at , . In particular (10) is valid for all . It is straightforward to check that is the smallest positive zero of
.
Set. Sinceand, it follows that
Let us calculate the solutionof the problem (5)–(9). First assume . To satisfy (5), (8), and (9) we must take
(11)
and
, (12)
To determine the constantswe have to use (6) and (7). From (6) we get
,
hence
, (13)
By (7) we have
. (14)
Using (13) in (14) yields
or
Therefore
(15)
and hence (13) becomes
, (16)
for .
Let us also analyze the somehow exceptional case . In this case the equation (5) becomes
, ,
and the boundary conditions are again (6), (7), (8), and (9). By formula (10) we can see
immediately that the solution has the probabilistic interpretation
(18)
To satisfy (17), (8), and (9) we must take
,
and
, .
To determine the constantswe have to use (6) and (7). From (6) we get
,
hence
, . (19)
On the other hand, from (7) we get
. (20)
Using (19) in (20) yields
or
.
Therefore
(21)
and hence (19) becomes
, (22)
For .
We summarize the above results in the following theorem:
Theorem 1.For (or more generally for, ,where is the smallest eigenvalue of acting onwith Dirichlet boundary conditions at , ) we have
,
if . Also
If , the above formulas become
,
if . Finally
.
Remark.If we set (or ) in the above formulas, we obtain
. (23)
In particular ()
(24)