Functional Equations as an Important Analytic Method in Stochastic Modelling and in Combinatorics

G. Fayolle

2018, v.24, Issue 5, 811-846

ABSTRACT

Functional equations (FE) arise quite naturally in the analysis of stochastic systems of different kinds\,: queueing and telecommunication networks, random walks, enumeration of planar lattice walks, etc. Frequently, the object is to determine the probability generating function of some positive random vector in $\Zb_+^n$. Although the situation $n=1$ is more classical, we quote an interesting non local functional equation which appeared in modelling a divide and conquer protocol for a multi-access broadcast channel. As for $n=2$, we outline the theory reducing these linear FEs to boundary value problems of Riemann\tire Hilbert\tire Carleman type, with closed form integral solutions. Typical queueing examples analyzed over the last $45$ years are sketched. Furthermore, it is also sometimes possible to determine the \emph{nature of the functions} (e.g., rational, algebraic, holonomic), as illustrated in a combinatorial context, where asymptotics are briefly tackled. For general situations (e.g., big jumps, or $n\ge3$), only prospective comments are made, because then no concrete theory exists.

Keywords: algebraic curve, automorphism, boundary value problem, functional equation, Galois group, genus, Markov process, quarter-plane, queueing system, random walk, uniformization

COMMENTS

Please log in or register to leave a comment