Extended Renovation Theory and Limit Theorems for Stochastic Ordered Graphs,

S.G. Foss, T. Konstantopoulos

2003, v.9, Issue 3, 413-468

ABSTRACT

We extend Borovkov's renovation theory to obtain criteria for coupling-convergence of stochastic processes that do not necessarily obey stochastic recursions. The results are applied to an ``infinite bin model'', a particular system that is an abstraction of a stochastic ordered graph, i.e., a graph on the integers that has $(i,j)$, $i < j$, as an edge, with probability $p$, independently from edge to edge. A question of interest is an estimate of the length $L_n$ of a longest path between two vertices at distance $n$. We give sharp bounds on $C=\lim_{n\to\infty} (L_n/n)$. This is done by first constructing the unique stationary version of the infinite bin model, using extended renovation theory. We also prove a functional law of large numbers and a functional central limit theorem for the infinite bin model. Finally, we discuss perfect simulation, in connection to extended renovation theory, and as a means for simulating the particular stochastic models considered in this paper.

Keywords: stationary and ergodic processes,renovation theory,functional limit theorems,weak convergence,coupling,perfect simulation

COMMENTS

Please log in or register to leave a comment