Some aspects of time-dependent one-dimensional random walks

This dissertation contains a study of related topics connected with the one-dimensional random walk which proceeds by steps of ±1 occurring at random time intervals. In general it is assumed that these intervals are identically and independently distributed. This model may be specialized to the queuing process by inserting a reflecting barrier at the origin so that the displacement S(t) of the random walk at any time t is non-negative.

Throughout most of the dissertation it is assumed that the time intervals between steps of the same kind are independently and negative exponentially distributed with non-time- dependent parameter λ for positive steps, and μ for negative steps. Under this assumption we designate the single-server queuing process by the usual notation M/M/l. Using an obvious extension to the queuing notation, we denote by –2/M/M the unrestricted walk in which S(t) may range over the entire set of positive and negative integers including zero.

Topics of classical interest are discussed such as first-passage times, first maxima, the time of occurrence of the rth return to zero, and the number of returns to zero during an arbitrary time interval (0,t). In addition to the discussion of these topics for ∞²/M/M and M/M/1, probability density functions are obtained for the first-passage times and the epoch of the maximum on the assumption that time intervals between steps of +1 have a general distribution and steps of -1 occur in a Poisson stream and vice-versa. These more general expressions are new.

Special emphasis is placed on the two-state sojourn problem in which it is assumed that at any time t, S(t) belongs to one of two possible states, A and B. The distribution of the sojourn time σ_B(t) in a given state B during the arbitrary time interval (0,t) is given. The general result for the distribution of σ_B(t) is applied to the M/M/I queuing process to obtain the distribution of the busy time. A similar application is made to the walk ∞²/M/M to obtain the distribution of σ_B(t) for the two cases:

(i) B is the set of all non-zero integers; and (ii) B is the set of all positive integers.

New expressions are given the distribution function of σ_B(t) in all three cases. New asymptotic formulae for these cases are derived and compared numerically with those obtained by Takacs using different methods.

For the more difficult sojourn time problem assuming three possible states, A, B₁, and B₂, the joint probability density function of σ_A(t) and σ_B₁(t) is derived. This result, not published before, is applied to –2/M/M assuming that A contains zero only and that B₁ and B₂ consist of the sets of positive and negative integers, respectively.

The dissertation also includes a discussion of several results by E. Sparre Andersen concerning fluctuations of sums of random variables and their time-dependent analogues.