1-Dependent Stationary Sequences for Some Given Joint Distributions of Two Consecutive Random Variables

We provide a method to construct a 1-dependent stationary sequence provided some mixing condition on the joint distribution of two consecutive random variables. Two illustrations of computational benefits of the method are given. We obtain analytical formulas to compute the expectation and variance of the number of occurrences of a word in a sequence of letters from a finite alphabet generated by the 1-dependent model.We also obtain an approximation formula for the distribution of the longest success run in a Bernoulli sequence generated by our model.     

Numbers of Success-Runs of Specified Length Until Certain Stopping Time Rules and Generalized Binomial Distributions of Order k

A new distribution called a generalized binomial distribution of order k is defined and some properties are investigated. A class of enumeration schemes for success-runs of a specified length including non-overlapping and overlapping enumeration schemes is rigorously studied. For each nonnegative integer less than the specified length of the runs, an enumeration scheme called -overlapping way of counting is defined. Let k and be positive integers satisfying < k. Based on independent Bernoulli trials, it is shown that the number of (– 1)-overlapping occurrences of success-run of length k until the n-th overlapping occurrence of success-run of length follows the generalized binomial distribution of order (k–). In particular, the number of non-overlapping occurrences of success-run of length k until the n-th success follows the generalized binomial distribution of order (k– 1). The distribution remains unchanged essentially even if the underlying sequence is changed from the sequence of independent Bernoulli trials to a dependent sequence such as higher order Markov dependent trials. A practical example of the generalized binomial distribution of order k is also given.     

On the Number of Appearances of a Word in a Sequence of I.I.D. Trials

Let X ₁,...,X _n be a sequence of i.i.d. random variables taking values in an alphabet =₁,...,_q,q 2, with probabilities P(X _a=_i)=p _i,a=1,...,n,i=1,...,q. We consider a fixed h-letter word W=w₁...w_h which is produced under the above scheme. We define by R(W) the number of appearances of W as Renewal (which is equal with the maximum number of non-overlapping appearances) and by N(W) the number of total appearances of W (overlapping ones) in the sequence X _{a 1} a1n under the i.i.d. hypothesis. We derive a bound on the total variation distance between the distribution (R(W)) of the r.v. R(W) and that of a Poisson with parameter E(R(W)). We use the Stein-Chen method and related results from Barbour et al. (1992), as well as, combinatorial results from Schbath (1995b) concerning the periodic structure of the word W. Analogous results are obtained for the total variation distance between the distribution of the r.v. N(W) and that of an appropriate Compound Poisson r.v. Related limit theorems are obtained and via numerical computations our bounds are presented in tables.     

A combined forecast—inventory control procedure for spare parts

This paper examines the performance of two different (s, Q) inventory models, namely a simple and an advanced model, for spare parts in a production plant of a confectionery producer in the Netherlands. The simple approach is more or less standard: the undershoot of the reorder level is not taken into account and the normal distribution is used as the distribution of demand during lead-time. The advanced model takes undershoots into account, differentiates between zero and nonzero demands during lead-time, and utilises the gamma distribution for the demand distribution. Both models are fed with parameters estimated by a procedure that forecasts demand sizes and time between demand occurrences separately (intermittent demand). The results show that the advanced approach yields a service level close to the desired one under many circumstances, while the simple approach is not consistent, in that it leads to much larger inventories in meeting the desired service level for all spare parts.     

Distribution of the shape of Markovian random words

The distribution of the shape of the semi-standard tableau of a random word in k letters is asymptotically given by the distribution of the spectrum of a random traceless k×k Gaussian Unitary Ensemble (GUE) matrix provided that these letters are independent with uniform distribution. Kuperberg (2002) conjectured that this result by Johansson (2001) remains valid if the letters of the word are generated by an irreducible Markov chain on the alphabet with cyclic transition matrix. In this paper we give a proof of this conjecture for an alphabet with k=2 letters.Research supported by DFG GO-420/3-3 in Bielefeld.Research supported by INTAS 99-00317, RFBR–DFG 99-01-04027.Mathematics Subject Classification (2000): 82B41, 60C05, 60F05, 60F10     

And/or trees: A local limit point of view

We present here a new and universal approach for the study of random and/or trees, unifying in one framework many different models, including some novel ones not yet understood in the literature. An and/or tree is a Boolean expression represented in (one of) its tree shapes. Fix an integer k, take a sequence of random (rooted) trees of increasing size, say , and label each of these random trees uniformly at random in order to get a random Boolean expression on k variables. We prove that, under rather weak local conditions on the sequence of random trees , the distribution induced on Boolean functions by this procedure converges as n tends to infinity. In particular, we characterize two different behaviors of this limit distribution depending on the shape of the local limit of : a degenerate case when the local limit has no leaves; and a non‐degenerate case, which we are able to describe in more details under stronger conditions. In this latter case, we provide a relationship between the probability of a given Boolean function and its complexity. The examples covered by this unified framework include trees that interpolate between models with logarithmic typical distances (such as random binary search trees) and other ones with square root typical distances (such as conditioned Galton–Watson trees).     

Asymptotic behaviour of time evolutions of infinite particle systems

Summary Motions of one-dimensional infinite particle systems are considered where the dynamics is given by systems of ordinary differential equations of first order. The aim of the paper is to show that under certain assumptions about the system of differential equations the distribution law P _tof the particle system at time t becomes more and more regular under the influence of such an interaction. Moreover, P _tis tending weakly toward a distribution describing a random particle system with equal successive spacings.     

A Gap in GRM Code Weight Distributions

The weight distribution of GRM (generalized Reed-Muller) codes is unknown in general. This article describes and applies some new techniques to the codes over F3. Specifically, we decompose GRM codewords into words from smaller codes and use this decomposition, along with a projective geometry technique, to relate weights occurring in one code with weights occurring in simpler codes. In doing so, we discover a new gap in the weight distribution of many codes. In particular, we show there is no word of weight 3^m–2 in GRM₃(4,m) for m>6, and for even-order codes over the ternary field, we show that under certain conditions, there is no word of weight d+, where d is the minimum distance and is the largest integer dividing all weights occurring in the code.     

The statistics of words on rings

We analyze sequences of letters on a ring. Our objective is to determine the statistics of the occurrences of a set of r‐letter words when the sequence is chosen as a periodic Markov chain of order ≤ r ? 1. We first obtain a generating function for the associated probability distribution and then display its Poisson limit. For an i.i.d. letter sequence, correction terms to the Poisson limit are given. Finally, we indicate how a hidden Markov chain fits into this scheme. © 2005 Wiley Periodicals, Inc.     

The maximum surplus in a finite‐time interval for a discrete‐time risk model with exchangeable,dependent claim occurrences

This paper investigates a discrete‐time risk model that involves exchangeable dependent loss generating claim occurrences and compound binomially distributed aggregate loss amounts. First, a general framework is presented to derive the distribution of a surplus sequence using the model. This framework is then applied to obtain the distribution of any function of a surplus sequence in a finite‐time interval. Specifically, the distribution of the maximum surplus is obtained under nonruin conditions. Based on this distribution, the computation of the minimum surplus distribution is given. Asset and risk management–oriented implications are discussed for the obtained distributions based on numerical evaluations. In addition, comparisons are made involving the corresponding results of the classical discrete‐time compound binomial risk model, for which claim occurrences are independent and identically distributed.     

On the longitudinal librations of Hyperion

We study a nonlinear, second order ordinary differential equation that models the longitudinal librations of the longest axis L of a satellite with respect to the planet-satellite center line C. Combining theoretical arguments and numerical evidence we prove that, in the case of Hyperion, a satellite of Saturn, the angle A between L and C can change in a chaotic manner at the moments when the distance from Hyperion to Saturn reaches its minimum value. More precisely, given an arbitrary sequence of zeros and ones, we show that there is at least one initial velocity of A such that its successive positions reproduce the given sequence.      

The sequence of open and closed prefixes of a Sturmian word

A finite word is closed if it contains a factor that occurs both as a prefix and as a suffix but does not have internal occurrences, otherwise it is open. We are interested in the oc-sequence of a word, which is the binary sequence whose n-th element is 0 if the prefix of length n of the word is open, or 1 if it is closed. We exhibit results showing that this sequence is deeply related to the combinatorial and periodic structure of a word. In the case of Sturmian words, we show that these are uniquely determined (up to renaming letters) by their oc-sequence. Moreover, we prove that the class of finite Sturmian words is a maximal element with this property in the class of binary factorial languages. We then discuss several aspects of Sturmian words that can be expressed through this sequence. Finally, we provide a linear-time algorithm that computes the oc-sequence of a finite word, and a linear-time algorithm that reconstructs a finite Sturmian word from its oc-sequence.     

The probability of avoiding consecutive patterns in the Mallows distribution

We use combinatorial and probabilistic techniques to study growth rates for the probability that a random permutation from the Mallows distribution avoids consecutive patterns. The Mallows distribution is a q‐analogue of the uniform distribution weighting each permutation π by , where is the number of inversions in π and q is a positive, real‐valued parameter. We prove that the growth rate exists for all patterns and all q > 0, and we generalize Goulden and Jackson's cluster method to keep track of the number of inversions in permutations avoiding a given consecutive pattern. Using singularity analysis, we approximate the growth rates for length‐3 patterns, monotone patterns, and non‐overlapping patterns starting with 1, and we compare growth rates between different patterns. We also use Stein's method to show that, under certain assumptions on q and σ, the number of occurrences of a given pattern σ is well approximated by the normal distribution.     

Quantitative Approximation to the Ordered Dirichlet Distribution under Varying Basic Probability Spaces

An approximate expansion of a sequence of ordered Dirichlet densities is given under the set-up with varying dimensions of the relating basic probability spaces. The problem is handled as the approximation to the joint distribution of an increasing number of selected order statistics based on the random sample drawn from the uniform distribution U(0, 1). Some inverse factorial series to the expansion of logarithmic function enable us to give quantitative error evaluations to our problem. With the help of them the relating modified K-L information number, which is defined on an approximate main domain and different from the usual ones, is accurately evaluated. Further, the proof of the approximate joint normality of the selected order statistics is more systematically presented than those given in existing works. Concerning the approximate normality the modified affinity and the half variation distance are also evaluated.     

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.     

An Iterative Approach to Determining the Length of the Longest Common Subsequence of Two Strings

This paper concerns the longest common subsequence (LCS) shared by two sequences (or strings) of length N, whose elements are chosen at random from a finite alphabet. The exact distribution and the expected value of the length of the LCS, k say, between two random sequences is still an open problem in applied probability. While the expected value E(N) of the length of the LCS of two random strings is known to lie within certain limits, the exact value of E(N) and the exact distribution are unknown. In this paper, we calculate the length of the LCS for all possible pairs of binary sequences from N=1 to 14. The length of the LCS and the Hamming distance are represented in color on two all-against-all arrays. An iterative approach is then introduced in which we determine the pairs of sequences whose LCS lengths increased by one upon the addition of one letter to each sequence. The pairs whose score did increase are shown in black and white on an array, which has an interesting fractal-like structure. As the sequence length increases, R(N) (the proportion of sequences whose score increased) approaches the Chvátal–Sankoff constant a _c (the proportionality constant for the linear growth of the expected length of the LCS with sequence length). We show that R(N) is converging more rapidly to a _c than E(N)/N.     

Monoidal composition of distributions

Summary A useful property of a Poisson process is that if occurrences are independently selected with probability a, then the resulting process is Poisson with mean a, where is the original process mean. This property is examined from an abstract viewpoint under a natural restriction on the selection mechanism, namely that if a, b, characterize two selection mechanisms of interest, then the composite selection, when acting on a given distribution, is characterized by a o b, where o is an associative operation. In the terminology of Bourbaki, the quantities, a,b,..., together with o, form a monoid. The monoid will, for simplicity, be assumed to possess a two-sided unit e. The class of processes is generalized under a related closure restriction, which is that the distributions are members of a parametric family which is invariant under a monoidal selection mechanism. Various consequences of these assumptions are deduced, relating to the form of the selection mechanism and of the parametric families. The methods of Aczél are used here.Under the special assumption that the monoid involved is the multiplicative monoid of reals in the unit interval, that the selection is positively compatible with the parametric family, and that the generating functions are univariate and of Mandelbrojt type, it follows from the Bernstein-Widder Theorem that the distributions are mixtures of stuttering (also called compound) Poisson distributions. Moreover, it is shown that every parametric family is positively compatible with linear selection, and that negative binomial distributions are positively compatible with exponential selection.     

Configurations in 4-Cycle Systems

A 4-cycle system of order n, denoted by 4CS(n), exists if and only if n1 (mod 8). There are four configurations which can be formed by two 4-cycles in a 4CS(n). Formulas connecting the number of occurrences of each such configuration in a 4CS(n) are given. The number of occurrences of each configuration is determined completely by the number d of occurrences of the configuration D consisting of two 4-cycles sharing a common diagonal. It is shown that for every n1 (mod 8) there exists a 4CS(n) which avoids the configuration D, i.e. for which d=0. The exact upper bound for d in a 4CS(n) is also determined.Acknowledgments A substantial part of the work forming this paper was done while the first author was visiting the Department of Pure Mathematics of The Open University at Milton Keynes; he thanks the Department for hospitality and the UK EPSRC for financial support (grant number GR/R78282/01). The first author also gratefully acknowledges the support of the Australian Research Council. The fourth author is supported by the VEGA grant 1/0261/03. All the authors thank the referees for their helpful comments.Final version received: November 11, 2003     

Joint distributions of numbers of occurrences of a discrete pattern and weak convergence of an empirical process for the pattern

For a {0, 1}-pattern of finite length, an empirical process is introduced in order to describe the number of overlapping occurrences of the pattern at each level t[0,1] in a sequence of the corresponding indicators of i.i.d. [0, 1]-valued observations of length n. A method for obtaining the exact finite-dimensional distributions of the empirical process is given. The weak convergence of the process to a Gaussian process in D[0,1] as n tends to infinity is also established. The limiting process depends on the given pattern. The exact covariance function is compared with the asymptotic covariance function in a numerical example.     

Der Richtungsabstand

In the study of chemical structural phenomena, the idea of mixedness appears to provide most valuable information if this notion is understood as a quantity that counts for a natural distinction between more or less mixed situations. The search for such a concept was initiated by the need of a corresponding valuation of chemical molecules that differ in the type-composition of a system of varying molecular parts at given molecular skeleton sites. In other words, an order relation for the partitions of a finite set was sought that explains the extent of mixing in a canonical way. This and related questions led to the concepts of themixing character andmixing distance. Success in applying these concepts to further chemical and physical problems, to graph theory, to representation theory of the symmetric group, and to probability theory confirmed the hope that there is a common background in some basic mathematics that allows a systematic treatment.The expected concept summarizing the above-mentioned experience is called thedirection distance and the mathematics concerned is linear geometry with a normspecific metric or structural analysis of normed vector spaces, respectively. Direction distance is defined as a map that represents the total metric information on any pair of directions (= pair of half-lines with a common vertex or a corresponding figure in normed vector spaces). Generally, that metrical figure changes when the half-lines are interchanged. As a consequence thereof, Hilbert's congruence axioms do not permit a metric criterion for the congruence of angles except in particular cases. The metric figures of direction pairs, however, may be classified according to metric congruence, and the normspecific metric induces an order in the set of congruence classes. This order, as a rule, is partial; it proves to be total if and only if the vector spaces are (pre-) Hilbert spaces (Lemma 8). A thorough comparison of the direction distance with the conventional distance deepens the understanding of the novel concept and justifies the terminology. The results are summarized in a number of lemmata. Furthermore, so-calledd-complete systems of order-homomorphic functional (so-calledd-functionals) establish an alternative formulation of the direction distance order. If and only if the order is total,d-complete systems can be represented by singled-functionals. Consequently, the case that normed vector spaces are (pre-) Hilbert spaces is pinpointed by the fact that the negative scalar product is already ad-complete system. These particular circumstances allow a metric congruence relation for angles.Another family of normed vector spaces is traced out by the conditions under which the direction distance takes the part of the mixing distance. Roughly speaking, a subset of vectors may be viewed as representing mixtures if it has two properties. First, with any two vectors of this subset all positive linear combinations are vectors of it as well. Second, the length of these vectors is an additive property. Correspondingly, the definition of the mentioned family, the family of so-calledmc-spaces, is based on the concepts of ameasure cone (Def. 5 and Def. 5) and an associated class ofmc- (= measure cone)norms being responsible for length additivity ofpositive vectors (= vectors of the measure cone) (Def. 6). Such norms provide congruence classes for positive vectors and positive direction pairs marked by the propertieslength andmixing distance, respectively. These congruence classes do not depend on the choice of the particularmc-norm within the class associated with a given measure cone, however, the mixing distance does. The consistency of the stipulated mathematical instrumentarium becomes apparent with Theorem 1 stating: The mixing distanceorder doesnot depend on the choice of a particular norm within the measure cone specific class; this order, together with the stipulated length of positive vectors, are properties necessary and sufficient for fixing the measure cone specific class ofmc-norms.Decreasing (or constant) mixing distance was found to describe a characteristic change in the relation between two probability distributions on a given set of classical events, a change in fact necessary and sufficient for the existence of alinear stochastic operator that maps a given pair of distributions into another given pair. This physically notable statement was originally proved for the space ofL ¹-functions on a compact -interval, it was expected to keep its validity for probability distributions in the range of classical physics and, as a consequence of that, for measures of any type. Theorem 2 presents the said statement in terms ofmc-endomorphisms ofmc-spaces; after an extension of the original proof to a more general family ofL ¹-spaces another method presented in a separate paper confirms Theorem 2 for bounded additive set functions and, accordingly, secures the expected range of validity. The discussion below is without reference to the validity range and primarily devoted to geometrical consequences without detailed speculations about physical applications.A few remarks on applications, however, illustrate the physical relevance of the mixing distance and its specialization, theq-character, in the particular context of Theorem 2. With reference to measure cones with such physical interpretations as statistical systems,mc-endomorphisms effect changes that can be described by linear stochastic operators and result physically either from an approach to some equilibrium state or from an adoption to a time-dependent influence on the system from outside. Theorem 2 provides a necessary and sufficient criterion for such changes. The discussion may concern phenomena of irreversible thermodynamics as well as evolving systems under the influence of a surrounding world summarized asorganization phenomena. Entropies and relative entropies of the Renyi-type ared-functionais which do not establishd-complete systems. The validity of Theorem 2 does not encompass the nonclassical case; the reason for it is of high physical interest. The full range of validity and its connection with symmetry arguments seems a promising mathematical problem in the sense of Klein'sErlanger Programm. From the point of mathematical history, the Hardy-Littlewood-Polya theorem should be quoted as a very special case of Theorem 2.