On waiting time distributions associated with compound patterns in a sequence of multi-state trials

In this article, waiting time distributions of compound patterns are considered in terms of the generating function of the numbers of occurrences of the compound patterns. Formulae for the evaluation of the generating functions of waiting time are given, which are very effective computational tools. We provide several viewpoints on waiting time problems associated with compound patterns and develop a general workable framework for the study of the corresponding distributions. The general theory is employed for the investigation of some examples in order to illustrate how the distributions of waiting time can be derived through our theoretical results. This research was partially supported by the ISM Cooperative Research Program (2006-ISM·CRP-2007).     

Sooner and Later Waiting Time Problems for Runs in Markov Dependent Bivariate Trials

In this paper we study exact distributions of sooner and later waiting times for runs in Markov dependent bivariate trials. We give systems of linear equations with respect to conditional probability generating functions of the waiting times. By considering bivariate trials, we can treat very general and practical waiting time problems for runs of two events which are not necessarily mutually exclusive. Numerical examples are also given in order to illustrate the feasibility of our results.     

Joint Distributions of Runs in a Sequence of Multi-State Trials

In this paper we introduce a Markov chain imbeddable vector of multinomial type and a Markov chain imbeddable variable of returnable type and discuss some of their properties. These concepts are extensions of the Markov chain imbeddable random variable of binomial type which was introduced and developed by Koutras and Alexandrou (1995, Ann. Inst. Statist. Math., 47, 743–766). By using the results, we obtain the distributions and the probability generating functions of numbers of occurrences of runs of a specified length based on four different ways of counting in a sequence of multi-state trials. Our results also yield the distribution of the waiting time problems.     

Random walks on colored graphs

We initiate a study of random walks on undirected graphs with colored edges. In our model, a sequence of colors is specified before the walk begins, and it dictates the color of edge to be followed at each step. We give tight upper and lower bounds on the expected cover time of a random walk on an undirected graph with colored edges. We show that, in general, graphs with two colors have exponential expected cover time, and graphs with three or more colors have doubly-exponential expected cover time. We also give polynomial bounds on the expected cover time in a number of interesting special cases. We described applications of our results to understanding the dominant eigenvectors of products and weighted averages of stochastic matrices, and to problems on time-inhomogeneous Markov chains. © 1994 John Wiley & Sons, Inc.     

Random walks and the effective resistance of networks

In this article we present an interpretation ofeffective resistance in electrical networks in terms of random walks on underlying graphs. Using this characterization we provide simple and elegant proofs for some known results in random walks and electrical networks. We also interpret the Reciprocity theorem of electrical networks in terms of traversals in random walks. The byproducts are (a) precise version of thetriangle inequality for effective resistances, and (b) an exact formula for the expectedone-way transit time between vertices.     

Coupled Continuous Time Random Maxima

Continuous Time Random Maxima (CTRM) are a generalization of classical extreme value theory: Instead of observing random events at regular intervals in time, the waiting times between the events are also random variables which have arbitrary distributions. In case that the waiting times between the events have infinite mean, the limit process that appears differs from the limit process that appears in the classical case. With a continuous mapping approach, we derive a limit theorem for the case that the waiting times and the subsequent events are dependent as well as for the case that the waiting times depend on the preceding events (in this case we speak of an Overshooting Continuous Time Random Maxima, abbr. OCTRM). We get the distribution functions of the limit processes and a formula for the Laplace transform in time of the CTRM and the OCTRM limit. With this formula we have another way to calculate the distribution functions of the limit processes, namely by inversion of the Laplace transform. Moreover, we present governing equations which in our case are time fractional differential equations whose solutions are the distribution functions of our limit processes.     

On the cover time of random walks on graphs

This article deals with random walks on arbitrary graphs. We consider the cover time of finite graphs. That is, we study the expected time needed for a random walk on a finite graph to visit every vertex at least once. We establish an upper bound ofO(n ²) for the expectation of the cover time for regular (or nearly regular) graphs. We prove a lower bound of (n logn) for the expected cover time for trees. We present examples showing all our bounds to be tight.Mike Saks was supported by NSF-DMS87-03541 and by AFOSR-0271. Jeff Kahn was supported by MCS-83-01867 and by AFOSR-0271.     

Gumbel fluctuations for cover times in the discrete torus

This work proves that the fluctuations of the cover time of simple random walk in the discrete torus of dimension at least three with large side-length are governed by the Gumbel extreme value distribution. This result was conjectured for example in Aldous and Fill (Reversible Markov chains and random walks on graphs, in preparation). We also derive some corollaries which qualitatively describe “how” covering happens. In addition, we develop a new and stronger coupling of the model of random interlacements, introduced by Sznitman (Ann Math (2) 171(3):2039–2087, 2010), and random walk in the torus. This coupling is used to prove the cover time result and is also of independent interest.     

Cover time and mixing time of random walks on dynamic graphs

The application of simple random walks on graphs is a powerful tool that is useful in many algorithmic settings such as network exploration, sampling, information spreading, and distributed computing. This is due to the reliance of a simple random walk on only local data, its negligible memory requirements, and its distributed nature. It is well known that for static graphs the cover time, that is, the expected time to visit every node of the graph, and the mixing time, that is, the time to sample a node according to the stationary distribution, are at most polynomial relative to the size of the graph. Motivated by real world networks, such as peer‐to‐peer and wireless networks, the conference version of this paper was the first to study random walks on arbitrary dynamic networks. We study the most general model in which an oblivious adversary is permitted to change the graph after every step of the random walk. In contrast to static graphs, and somewhat counter‐intuitively, we show that there are adversary strategies that force the expected cover time and the mixing time of the simple random walk on dynamic graphs to be exponentially long, even when at each time step the network is well connected and rapidly mixing. To resolve this, we propose a simple strategy, the lazy random walk, which guarantees, under minor conditions, polynomial cover time and polynomial mixing time regardless of the changes made by the adversary.     

Generalized binomial and negative binomial distributions of order<Emphasis Type="Italic">k</Emphasis> by the<Emphasis Type="Italic">l</Emphasis>-overlapping enumeration scheme

In this paper, we investigate the exact distribution of the waiting time for ther-th ℓ-overlapping occurrence of success-runs of a specified length in a sequence of two state Markov dependent trials. The probability generating functions are derived explicitly, and as asymptotic results, relationships of a negative binomial distribution of orderk and an extended Poisson distribution of orderk are discussed. We provide further insights into the run-related problems from the viewpoint of the ℓ-overlapping enumeration scheme. We also study the exact distribution of the number of ℓ-overlapping occurrences of success-runs in a fixed number of trials and derive the probability generating functions. The present work extends several properties of distributions of orderk and leads us a new type of geneses of the discrete distributions.     

A Communication Multiplexer Problem: Two Alternating Queues with Dependent Randomly-Timed Gated Regime

Two random traffic streams are competing for the service time of a single server (multiplexer). The streams form two queues, primary (queue 1) and secondary (queue 0). The primary queue is served exhaustively, after which the server switches over to queue 0. The duration of time the server resides in the secondary queue is determined by the dynamic evolution in queue 1. If there is an arrival to queue 1 while the server is still working in queue 0, the latter is immediately gated, and the server completes service there only to the gated jobs, upon which it switches back to the primary queue. We formulate this system as a two-queue polling model with a single alternating server and with randomly-timed gated (RTG) service discipline in queue 0, where the timer there depends on the arrival stream to the primary queue. We derive Laplace–Stieltjes transforms and generating functions for various key variables and calculate numerous performance measures such as mean queue sizes at polling instants and at an arbitrary moment, mean busy period duration and mean cycle time length, expected number of messages transmitted during a busy period and mean waiting times. Finally, we present graphs of numerical results comparing the mean waiting times in the two queues as functions of the relative loads, showing the effect of the RTG regime.     

A two-queue model with Bernoulli service schedule and switching times

In this paper, we present a detailed analysis of a cyclic-service queueing system consisting of two parallel queues, and a single server. The server serves the two queues with a Bernoulli service schedule described as follows. At the beginning of each visit to a queue, the server always serves a customer. At each epoch of service completion in the ith queue at which the queue is not empty, the server makes a random decision: with probability p_i, it serves the next customer; with probability 1-p_i, it switches to the other queue. The server takes switching times in its transition from one queue to the other. We derive the generating functions of the joint stationary queue-length distribution at service completion instants, by using the approach of the boundary value problem for complex variables. We also determine the Laplace-Stieltjes transforms of waiting time distributions for both queues, and obtain their mean waiting times. This revised version was published online in June 2006 with corrections to the Cover Date.     

The discrete-time single-server queue

In this paper we consider the discrete-time single server queueing model with exceptional first service. For this model we cannot define the steady-state waiting-time distribution simply as the limiting distribution of the waiting times, since this limit does not always exist. Instead, we use the Cesaro limit to define the limiting waiting-time distribution. We give an exact relation between the generating functions of the steady-state waiting-time distribution and of the idle-time distribution in the case of general interarrival-time and service-time distributions. Once we have this relation, we can give more explicit results when the generating function of either the interarrival-time distribution or the service-time distribution is rational. We also derive some results on the asymptotic behaviour of the waiting-time distribution.     

Length of clustering algorithms based on random walks with an application to neuroscience

In this paper we show how the notions of conductance and cutoff can be used to determine the length of the random walks in some clustering algorithms. We consider graphs which are globally sparse but locally dense. They present a community structure: there exists a partition of the set of vertices into subsets which display strong internal connections but few links between each other. Using a distance between nodes built on random walks we consider a hierarchical clustering algorithm which provides a most appropriate partition. The length of these random walks has to be chosen in advance and has to be appropriate. Finally, we introduce an extension of this clustering algorithm to dynamical sequences of graphs on the same set of vertices.     

Distributions of numbers of runs and scans on directed acyclic graphs with generation

In this paper, we introduce a class of a directed acyclic graph on the assumption that the collection of random variables indexed by the vertices has a Markov property. We present a flexible approach for the study of the exact distributions of runs and scans on the directed acyclic graph by extending the method of conditional probability generating functions. The results presented here provide a wide framework for developing the exact distribution theory of runs and scans on the graphical models. We also show that our theoretical results can easily be carried out through some computer algebra systems and give some numerical examples in order to demonstrate the feasibility of our theoretical results. As applications, two special reliability systems are considered, which are closely related to our general results. Finally, we address the parameter estimation in the distributions of runs and scans.     

Random Walks on Directed Covers of Graphs

Directed covers of finite graphs are also known as periodic trees or trees with finitely many cone types. We expand the existing theory of directed covers of finite graphs to those of infinite graphs. While the lower growth rate still equals the branching number, upper and lower growth rates no longer coincide in general. Furthermore, the behavior of random walks on directed covers of infinite graphs is more subtle. We provide a classification in terms of recurrence and transience and point out that the critical random walk may be recurrent or transient. Our proof is based on the observation that recurrence of the random walk is equivalent to the almost sure extinction of an appropriate branching process. Two examples in random environment are provided: homesick random walk on infinite percolation clusters and random walk in random environment on directed covers. Furthermore, we calculate, under reasonable assumptions, the rate of escape with respect to suitable length functions and prove the existence of the asymptotic entropy providing an explicit formula which is also a new result for directed covers of finite graphs. In particular, the asymptotic entropy of random walks on directed covers of finite graphs is positive if and only if the random walk is transient.     

Infinite measure preserving transformations with compact first regeneration

We study ergodic infinite measure preserving transformations T possessing reference sets of finite measure for which the set of densities of the conditional distributions given a first return (or entrance) at time n is precompact in a suitable function space. Assuming regular variation of wandering rates, we establish versions of the Darling-Kac theorem and the arcsine laws for waiting times and for occupation times which apply to transformations with indifferent orbits and to random walks driven by Gibbs-Markov maps. This research was supported by an APART [Austrian programme for advanced research and technology] fellowship of the Austrian Academy of Sciences. Much of this work was done at the Mathematics Department of Imperial College London. I also benefitted from a JRF at the ESI in Vienna.     

THE MATCHED QUEUEING SYSTEM GI。PH/PH/1

ＴＨＥＭＡＴＣＨＥＤＱＵＥＵＥＩＮＧＳＹＳＴＥＭＧＩ。ＰＨ／ＰＨ／１ＸＵＧＵＡＮＣＨＵＩ（ＧＵＡＮＧ－ＨＵＩＨＳＶ）（徐光煇）；ＨＥＱＩＭＩＮＧ（何启明）（ＩｎｓｔｉｔｕｔｅｏｆＡｐｐｌｉｅｄＭａｔｈｅｍａｔｉｃｓ，ｔｈｅＣｈｉｎｅｓｅＡｃａｄｅｍｙ...     

On Homogeneous Multivariate Distributions in Random Occupancy Models and Their Applications

Methodology and Computing in Applied Probability - In this article, we consider random occupancy models and the related problems based on the methods of generating functions. The waiting time...     

Joint distributions of numbers of success runs of specified lengths in linear and circular sequences

In this paper, we study two joint distributions of the numbers of success runs of several lengths in a sequence ofn Bernoulli trials arranged on a line (linear sequence) or on a circle (circular sequence) based on four different enumeration schemes. We present formulae for the evaluation of the joint probability functions, the joint probability generating functions and the higher order moments of these distributions. Besides, the present work throws light on the relation between the joint distributions of the numbers of success runs in the circular and linear binomial model. We give further insights into the run-related problems arisen from the circular sequence. Some examples are given in order to illustrate our theoretical results. Our results have potential applications to other problems such as statistical run tests for randomness and reliability theory. This research was partially supported by the ISM Cooperative Research Program (2003-ISM.CRP-2007).