Waiting Time Distribution for the Emergence of Superpatterns

Consider a sequence \(\{X_{n}\}_{n=1}^{\infty }\) of i.i.d. uniform random variables taking values in the alphabet set {1, 2,…, d}. A k-superpattern is a realization of \(\{X_{n}\}_{n=1}^{t}\) that contains, as an embedded subsequence, each of the non-order-isomorphic subpatterns of length k. We focus on the (non-trivial) case of d = k = 3 and study the waiting time distribution of \(\tau =\inf \{t\ge 1:\{X_{n}\}_{n=1}^{t}\ \text {is\ a\ superpattern}\}\). Our restricted set-up leads to proofs that are very combinatorial in nature, since we are essentially conducting a string analysis.     

On the Waiting Time for the First Success Run

Let k and m are positive integers with k ≥ m. The probability generating function of the waiting time for the first occurrence of consecutive k successes in a sequence of m-th order Markov dependent trials is given as a function of the conditional probability generating functions of the waiting time for the first occurrence of consecutive m successes. This provides an efficient algorithm for obtaining the probability generating function when k is large. In particular, in the case of independent trials a simple relationship between the geometric distribution of order k and the geometric distribution of order k−1 is obtained. This research was partially supported by the ISM Cooperative Research Program(2004-ISM-CRP-2006) and by a Grant-in-Aid for Scientific Research (C) of the JSPI (Grant Number 16500183)     

Queueing Models for Hospital Waiting Lists

Results of some recent research into queueing models are applied to the hospital waiting-list problem to give some important insights into the likely implications of attempts to reduce waiting lists.     

Asymptotic Recurrence and Waiting Times for Stationary Processes

Let be a discrete-valued stationary ergodic process distributed according to P and let x=(..., x _–1, x ₀, x ₁,...) denote a realization from X. We investigate the asymptotic behavior of the recurrence time R _n defined as the first time that the initial n-block reappears in the past of x. We identify an associated random walk, on the same probability space as X, and we prove a strong approximation theorem between log R _n and . From this we deduce an almost sure invariance principle for log R _n. As a byproduct of our analysis we get unified proofs for several recent results that were previously established using methods from ergodic theory, the theory of Poisson approximation and the analysis of random trees. Similar results are proved for the waiting time W _n defined as the first time until the initial n-block from one realization first appears in an independent realization generated by the same (or by a different) process.     

Waiting time problems for a two-dimensional pattern

We consider waiting time problems for a two-dimensional pattern in a sequence of i.i.d. random vectors each of whose entries is 0 or 1. We deal with a two-dimensional pattern with a general shape in the two-dimensional lattice which is generated by the above sequence of random vectors. A general method for obtaining the exact distribution of the waiting time for the first occurrence of the pattern in the sequence is presented. The method is an extension of the method of conditional probability generating functions and it is very suitable for computations with computer algebra systems as well as usual numerical computations. Computational results applied to computation of exact system reliability are also given. Department of Statistical Science, School of Mathematical and Physical Science, The Graduate University for Advanced Studies This research was partially supported by the ISM Cooperative Research Program (2002-ISM-CRP-2007).     

The Virtual Waiting Time for the Batch Arrival Queueing Systems

Abstract

In the article the G ^η I/G/1-type batch arrival system with infinite waiting-room is considered. The explicit formulae for the distribution of the virtual waiting time at any fixed moment t and as t → ∞ are obtained. The study is based on generalization of Korolyuk's method for semi-markov random walks.     

Groundwater management: Waiting for a drought*

In this article we present a stylized model for optimal management of an unconfined groundwater resource when the threat of drought exists. The drought is modeled as a stochastic event that hits at an uncertain date and two benchmark management policies are investigated: (a) A policy of optimal dynamic management ignoring the threat of drought; and (b) an economically optimal policy that accounts for the threat of a drought. We show that the optimal predrought steady‐state equilibrium stock size of groundwater under policy b is larger than that under policy (a) Furthermore, we show that an increase in the probability of a drought gives rise to two counteracting effects: One in the direction of a larger predrought steady‐state equilibrium stock size (a recovery effect) and one in the direction of a lower predrought steady‐state equilibrium stock (an extinction effect). We find that the recovery effect dominates the extinction effect. Recommendations for Resource Managers: We analyze two groundwater extraction policies that can be used when a threat of drought exists: (a) Dynamic optimal management ignoring the threat of drought; and (b) dynamic optimal management taking the threat of drought into account. We show that the predrought steady‐state equilibrium stock size of water should be larger under the policy (b) than under policy (a). This conclusion has three implications for resource managers:

• Current groundwater management should take future extraction possibilities into account.

• A resource manager ought to take the threat of drought into account in groundwater management.

• A buffer stock of water should be built‐up before the drought to be drawn upon during the event.

     

一类随机徘徊的等待时间

以一种随机徘徊为例,说明由独立增量点过程的等待时间生成的两类随机量——点间间距、给定时刻前后两次事件出现的时间差——之间的关系.     

Waiting times and stopping probabilities for patterns in Markov chains

Suppose that C is a finite collection of patterns. Observe a Markov chain until one of the patterns in C occurs as a run. This time is denoted by τ. In this paper, we aim to give an easy way to calculate the mean waiting time E(τ) and the stopping probabilities P(τ = τA)with A ∈ C, where τA is the waiting time until the pattern A appears as a run.     

Waiting time for consecutive repetitions of a pattern and related distributions

Annals of the Institute of Statistical Mathematics - Let k be a positive integer. Some exact distributions of the waiting time random variables for k consecutive repetitions of a pattern are...     

A list heuristic for vertex cover

We analyze a list heuristic for the vertex cover problem that handles the vertices in a given static order based on the degree sequence. We prove an approximation ratio of at most for a nonincreasing degree sequence, and show that no ordering can achieve an approximation ratio of less than .     

Waiting time effect for motion by positive second derivatives and applications

We discuss the waiting time effect for the evolution of a planar graph governed by its positive part of second derivative. For any smooth periodic function which contains finitely many convex pieces in one period, we show that the waiting time is continuous by using comparison arguments. Moreover, we show that the convex parts keep expanding in size in a strict manner, which answers an open question posed by Kohn and Serfaty (Commun Pure Appl Math 59:344–407, 2006) in this special case. The results on waiting time effect are also applied to the stationary problem of mean curvature type on an unbounded nonconvex domain for our study of its game-theoretic interpretation.     

Waiting times for clumps of patterns and for structured motifs in random sequences

This paper provides exact probability results for waiting times associated with occurrences of two types of motifs in a random sequence. First, we provide an explicit expression for the probability generating function of the interarrival time between two clumps of a pattern. It allows, in particular, to measure the quality of the Poisson approximation which is currently used for evaluation of the distribution of the number of clumps of a pattern. Second, we provide explicit expressions for the probability generating functions of both the waiting time until the first occurrence, and the interarrival time between consecutive occurrences, of a structured motif. Distributional results for structured motifs are of interest in genome analysis because such motifs are promoter candidates. As an application, we determine significant structured motifs in a data set of DNA regulatory sequences.     

On Waiting Time for Reversed Patterns in Random Sequences

By using a combinatorial method it is shown that for every finite pattern, the distribution of the waiting time for the reversed pattern coincides with that of the waiting time for the original pattern in a multi-state dependent sequence with a certain type of exchangeability. The number of the typical sequences until the occurrence of a given pattern and that of the typical sequences until the occurrence of the reversed pattern are shown to be equal. Further, the corresponding results for the waiting time for the r-th occurrence of the pattern, and for the number of occurrences of a specified pattern in n trials are also studied. Illustrative examples based on urn models are also given.     

Balancing the NHS balanced scorecard!

In the UK, the split between opposition and supporters views of the National Health Service (NHS) performance ratings system is growing. Objective argument and consensus would be facilitated if a methodology was developed which showed the cause and effect relationships between the components of the performance rating system. The NHS hospital trust performance ratings data used in 2002 and 2003 were downloaded from the Department of Health performance rating website. Structural equation modelling was used to construct a causal-loop diagram showing the cause and effect relationships between the 16 common performance indicators in the two years. Scenario testing suggests that indicators of delayed transfer of care and of data quality are compromised if emergency readmissions performance is improved.     

On the complexity of suboptimal decoding for list and decision feedback schemes

We consider bounded distance list decoding, such that the decoder calculates the list of all codewords within a sphere around the received vector. We analyze the performance and the complexity of this suboptimum list decoding scheme for the binary symmetric channel. The reliability function of the list decoding scheme is equivalent to the sphere-packing bound, where the decoding complexity is asymptotically bounded by 2^nR(1-R). Furthermore, we investigate a decision feedback strategy that is based on bounded distance list decoding. Here, any output with zero or many codewords will call for a repeated transmission. In this case the decoding complexity will be of the order 2^nR(1-C), where C denotes the channel capacity. The reliability function is close to Forney's feedback exponent.