Advances in Combinatorial Methods and Applications to Probability and Statistics

The r-th Faber polynomial of the Laurent series f(t) = t + f₀ + f₁/t + f₂/t2 + … is the unique polynomial F _r (u) of degree r in u such that F _r (f) = tr + negative powers of t. We apply Faber polynomials, which were originally used to study univalent functions, to lattice path enumeration.

The Umbral Calculus is an excellent tool for solving systems of difference equations with given initial values. Many lattice path enumeration problems can be formulated as such systems. Examples are paths underneath a boundary of straight lines, path inside a diagonal band, weighted paths, paths with several step directions, and paths crossing some line a given number of times.

We survey old and new results on the enumeration of lattice paths in the plane with a given number of turns, including the recent developments on the enumeration of nonintersecting lattice paths with a given number of turns. Motivations to consider such enumeration problems come from various fields, e.g. probability, statistics, combinatorics, and commutative algebra. We show that the appropriate tool for treating turn enumeration of lattice paths is the encoding of lattice paths in terms of two-rowed arrays.

In this paper an approach to lattice paths, simple random walks and randomized random walks is presented, which emphasizes the common features and permits to treat various aspects in a unified framework.

In this paper, I will discuss combinatorial identities as a tool for individuals working with combinatorial problems. I will also present a generalization of Dougall’s (1907) identity. In the notations of this paper, the general combinatorial identity established is the following: If p = b + c + d + e − n + 1 is a non-negative integer then we have: $$\begin{gathered} \sum\limits_{{k = 0}}^{n} {\left( {\begin{array}{*{20}{c}} n \\ k \\ \end{array} } \right){{{\left[ {n + 2a} \right]}}_{k}}{{{\left[ {b + a} \right]}}_{k}}} {{\left[ {c + a} \right]}_{k}}{{\left[ {d + a} \right]}_{k}} \hfill \\ \times {{\left[ {n - 2a} \right]}_{{n - k}}}{{\left[ {b - a} \right]}_{{n - k}}}{{\left[ {c - a} \right]}_{{n - k}}}{{\left[ {d - a} \right]}_{{n - k}}}{{\left[ {e - a} \right]}_{{n - k}}}\left( {n + 2a - 2k} \right) \hfill \\ = {{\left( { - 1} \right)}^{n}}{{\left[ {n + 2a} \right]}_{{2n - 1}}}{{\left[ {b + d - p} \right]}_{{n - p}}}{{\left[ {b + e - p} \right]}_{{n - p}}}{{\left[ {d + e - p} \right]}_{{n - p}}} \hfill \\ \times \sum\limits_{{j = 0}}^{p} {\left( {\begin{array}{*{20}{c}} p \\ j \\ \end{array} } \right){{{\left[ n \right]}}_{j}}{{{\left[ {c + a} \right]}}_{j}}{{{\left[ {c - a} \right]}}_{j}}{{{\left[ {b + e - n} \right]}}_{{p - j}}}{{{\left[ {d + e - n} \right]}}_{{p - j}}}{{{\left[ {d + e - n} \right]}}_{{p - j}}}} \hfill \\ \end{gathered} $$ where [x] _k denotes the descending factorial. Dougall’s identity, which is usually written in terms of a hypergeometric series, corresponds to the case p = 0.

Kirk (1993) raised the question of comparing the following two ways for labelling balls. Given r pre-determined positive integers n _i (1 ≤ i ≤ r), and given N balls (N large), consider two ways to randomly assign r–component vectors of integers (a₁,…, a _r ) to them, such that 1 ≤ a _i ≤ n _i . We will call these vectors labels. Of course, altogether there are $$\prod {_{i = 1}^r \,n_i }$$ possible labels.

The discovery of various ballot theorems has had great impact on several areas of combinatorics and probability theory. This paper deals with the historical background and the development of these theorems, analyzes various proofs and gives some applications.

We present some results for simple symmetric two-dimensional random walk. Our treatment is based on results concerning independent simple symmetric one-dimensional random walks.

The Euclidean algorithm with respect to the modulus 4 is given as random walks on the group SL(2, F₂). The quadratic reciprocity law and a simple part of Zolotareff’s Theorem are proved in terms of values on each step in the walks.

This paper deals with the derivation of the joint and marginal distributions of certain rank order statistics related to the generalized random walk with steps +1 and −µ by using the extended Dwass technique evolved by Mohanty and Handa (1970). These generalize and extend the results of Saran and Rani (1991a, b).

An algorithm for constructing partitions of an integer by arbitrary positive integers has been considered. The algorithm helps in introducing a class of discrete probability distributions which are useful in a sampling survey of populations, in constructing probability models describing texture images, etc. It can also be used in integer programming, cryptography, and some other problems.

Some new methodology is developed for Network Reliability problems and for random paths on finite lattices. In terms of stopping sets which define different (random) ways of reaching a goal in a geometrical setting, certain I and J polynomials are developed which give rise to the probability distribution (and its moments) of the waiting time (WT) needed to reach the preassigned goal. These new techniques have many different applications from Network Reliability to Recreational problems of tic-tac-toe and attacking all the squares on a chess board with randomly placed rooks or knights or queens, etc. Failure probabilities need not be equal and random sampling can be carried out with replacement, without replacement or by Pólya sampling schemes.

Stirling numbers and generalized Stirling numbers and their properties are briefly described first. Then some relationships between Stirling numbers and record times are presented. Finally, we show that generalized Stirling numbers of the first kind describe distributions of some record statistics in the so-called Fα-scheme.

This paper surveys some key developments that have occurred pertaining to urn models in probabilistic, statistical and biological literatures during the past two decades. It should be regarded as a compact sequel to the book Urn Models and Their Applications by Johnson and Kotz (1977) and as a natural companion to the two chapters in the book Discrete Multivariate Distributions by Johnson, Kotz and Balakrishnan (1997) dealing with multivariate Pólya-Eggenberger distributions and multivariate Ewens distributions, respectively.

Consider a supply of balls randomly distributed in n + r distinguishable urns and assume that the number X of balls distributed in any specific urn is a random variable with probability function Pr[X = j] = q _j , j = 0,1,2…. The probability function and factorial moments of the number K _i of urns occupied by i balls each, among n specified urns, given that a total of S_n+r = m balls are distributed in the n + r urns, are expressed in terms of finite differences of the u-fold convolution of q _j , j = 0,1,2,…. As a particular case, the probability function and factorial moments of the number K = n − K₀ of occupied urns (by at least one ball), among n specified urns, given that S_n+r = m, are deduced. Further, when balls are sequentially distributed, the probability function and ascending factorial moments of the number W _k of balls required until a predetermined number k of urns, among n specified urns, are occupied, are also expressed in terms of finite differences of the u-fold convolution of q _j , jj = 0,1, 2,…. Finally, the conditional probability function Pr[W_k+1 − W _k = j|W _k = m], j = 1,2,…, is derived. Illustrating these results, the cases with q _j , j = 0,1,2,…, the Poisson, geometric, binomial and negative binomial distributions are presented.

The relation of Bonferroni-type inequalities to combinatorial problems is demonstrated. An urn model in this setting leads to a statistical paradox as well as to an open problem concerning a statistical test of goodness of fit. An extension of Bonferroni-type inequalities to quadratic inequalities is discussed, which are then applied to the analysis of the structure of pairwisely independent events and of exchangeable events.

In this paper, some applications of nonintersecting lattice paths to queueing problems are presented. In particular, we derive a determinant formula for non-coincidence probabilities of non-identically distributed Poisson processes from which, in an almost elementary way, zero-avoiding transition probabilities in a Markovian tandem queue can be found. Finally, we present a result about D/M/l queues, where the arrival instances are not equally spaced.

This paper aims at transient busy period analysis of M/G/l queueing systems starting initially with i customers through lattice path approach. The service time distribution is approximated by a 2-phase Cox distribution, C₂. Distributions having rational Laplace-Stieltjes transforms and square coefficient of variation lying in $$\left. {\frac{1}{2},\infty } \right)$$ form a very wide class of distributions. As any distribution of this class can be approximated by a C₂, that has Markovian property, amenable to the application of lattice paths combinatorial analysis, the use of C₂ therefore has led us to achieve transient results applicable to almost any real life queueing system M/G/l.

The classical single-server queue with Poisson input has been extended to include several types of generalizations, to which attention has been paid by several researchers. It would be worthwhile to look into some sort of unified approach of the results of several models. It is also of interest to investigate a few important performance measures through heuristic ‘mean value analysis’ only without looking through the ‘Laplacian Curtain’. The purpose of this paper is to make a comprehensive survey of many interesting results that have appeared recently with a view to unify the results and to derive some new ones. The review is based on recent contributions as listed in the References.

This article summarizes some recent advances in the analysis of polling models in which the server uses system-state information to affect its behavior. Literature dealing with a special class of such models in which the server lies dormant upon finding the system empty, and reactivates only when the system is populated by a critical number of customers, is closely examined. Rather than provide a broad review of literature, the focus of this article is on providing insights, on building bridges with earlier literature, and on identifying common underlying principles.

In this article, the probability and moment generating functions of the number of appearances of a pattern ε in a sequence of discrete random variables (repeated trials) are expressed in terms of the generating function of the waiting time for the r-th occurrence of ε, The special case of delayed recurrent events is also examined in some detail. Finally, the general theory is employed for a systematic investigation of success runs enumeration problems in a sequence of binary outcomes arising from a first-order Markov chain.

Let X₀, X₁, X₂,… be a sequence of {0, 1}-valued Markov chain. Let E₁ denote a run of “1” of length k and E₀ denote a run of “0” of length r. We observe which run comes sooner or later in the sequence X₀, X₁, X₂, …. The exact distributions of the numbers of overlapping sooner runs and nonoverlapping sooner runs until the later run occurs (for the first time) are derived. Let F₁ be a success run of length k or more and let F₀ be a failure run of length r or more. The exact distribution of the number of occurrences of the sooner event until the first occurrence of the later event between F₁ and F₀ is also studied. Further, when X’s have more than two values, more general problems are discussed and the exact joint distribution of the numbers of occurrences of the first, the second,…, and the j-th runs until the j-th run occurs (for the first time) is obtained in the case of independent trials.

The distributions of numbers of overlapping and non-overlapping occurrences of success-runs of length l, and the distributions of numbers of occurrences of success-runs of exact length l and of length l or more until the first occurrence of success-run of length k in the m-th order Markov dependent trials are studied. When m ≤ l < k the derived distributions do not depend on the initial distribution of the m-th order Markov chain and they are shown to be equal to the corresponding distributions considered in independent trials with a success probability whose value is given by the transition probability that a success occurs after a success-run of length m in the m-th order Markov chain. When l < m the distributions depend on the initial distribution of the m-th order Markov chain and are not necessarily so simple as the above case. A method for deriving the probability generating function of the conditional distribution of the number of overlapping occurrences of success-runs of length l until the first occurrence of success-run of length k under each initial condition is given.

A sequence of independent trials with m + 1 mutually exclusive outcomes S, F ₁ , F₂,…, F _m is considered until the occurrence of the r-th nonoverlapping success run of length k, and the distributions of related random and the distributions of related random vectors are derived. First a new genesis scheme is established for the multivariate negative binomial distribution of order k type I, of Philippou, Antzoulakos and Tripsiannis (1988). It is shown that it is the distribution of the sum of two random vectors: the i-th component of the first one is the number of occurrences of F _i and the i-th component of the second one is the total number of S’s which precede directly the occurrences of F _i but do not belong to any success run of length k (1 ≤ i ≤ m). Furthermore, we obtain exact distributions of random vectors whose components are numbers of failures, non-overlapping runs of failures, successes, overlapping success runs of length l and success runs of length at least l. The majority of the above problems are also treated in the case of the generalized sequence of order k and corresponding results are established regarding the k and corresponding results are established regarding the multivariate extended negative binomial distribution of order k of Philippou and Antzoulakos (1990). The present paper generalizes several results of Aki and Hirano (1994, 1995).

Ling (1989) introduced and studied a negative binomial distribution of order k, type III, which he denoted by NB_{k III}(r, p), as the probability distribution of the number of Bernoulli trials M _r (k) until the occurrence of r possibly overlapping success runs of length k [see also Hirano et al. (1991)]. In the present paper, independent trials are considered with m + 1 possible outcomes and the multivariate negative binomial distribution of order k, type III, say $$\overline {MNB} _{k,III} (r;q_1 \ldots ,q_m ),$$ is introduced as the distribution of a random vector Y which is a multivariate analogue of Y _r (k) − (k + r − 1). The probability generating function, mean and variance-covariance, and several distributional properties of Y are established. The present paper generalizes to the multivariate case shifted versions of results of Ling (1989) and Hirano et al. (1991) on NB _k,III (r, p). Three new results on NB _k,III (r, p) or/and its shifted version are derived first; another one arises as a corollary of a proposition on $$\overline {MNB} _{k,III} (r;q_1 \ldots ,q_m ),$$.

Vincze (1959, 1961) derived the Planck-Bose-Einstein (PBE) probability density function for the energy distribution of black body radiation. This derivation was based on an expression for the information measure (negentropy) belonging to a continuous random variable and on the Bose-Einstein statistics; the quantum hypothesis of Planck was not needed. The present note considers the joint distribution of several variables. In earlier works, the method for solving the extreme value problem happened with a method due to Kullback and Leibler (1951) and the result did not agree with the formula given by Planck (1900), unless certain element was neglected. In this paper, the authors consider again the extreme value problem but through Lagrange method of the theory of variation which yields the PBE formula exactly. For the Fermi-Dirac case, the procedure goes on the same line. As a consequence, one has the property “indistinguishability of the particles” as a tool for arriving at the results, but the dependence of the random, variables is essential. This suggests that our procedure is appropriate even for gases which are neither bosons nor fermions, but the particles influence each other and their distributions are not independent [see Wilczek (1991)].

The paper defines two modified q-Bessel functions and uses their properties in the study of the distribution of the differences of (i) two Euler variables, (ii) two Heine variables (these are q-analogues of Poisson variables); three-term recurrence relations for the probabilities are obtained and the logcon-cavity of the distributions is established. A particular case of (ii) is the bilateral discrete normal distribution—this involves Jacobi’s triple product. The Euler and the Heine distributions are both special cases of the generalized Euler distribution. The difference of two generalized Euler variables is discussed briefly; other special cases lead to Ramanujan’s _1ψ1 sum and to its finite form.

The distribution considered here is obtained by replacing the ordinary Gaussian hypergeometric function by an appropriate q-hypergeometric (basic hypergeometric) function in the Kemp (1968) formulation of the probability generating function for the logarithmic distribution. Properties of the resulting q-logarithmic distribution are examined; a birth-and-death process model for group sizes is proposed whose equilibrium distribution is the q-logarithmic.

When an operator works on a machine, it is reasonable to assume that in a learning situation the probability of making an error changes from trial to trial, thus leading to a general Bernoulli process. In this paper, some results concerning two random variables—S _n , the number of errors made in a fixed number n of trials and T _r , the waiting time for the r-th success in this general Bernoulli process are studied. The probability distributions of S _n and T _r satisfy certain recursive relations and lead to interesting connections with the results found in combinatorial theory. The details of some interesting results which lead to what we call Uppuluri numbers, and in some special cases, relate to signless Stirling numbers of the first kind and to Pascal’s triangle are alsopresented.

The problem of testing homogeneity of distributions against some ordered alternatives is considered without making specific parametric model assumptions. The alternatives of interest include the simple-tree order and the simple order. The approach is based on a reformulation of the testing problems, regarding them as being composed of a finite number of two-sample sub-testing problems. The Mann-Whitney-Wilcoxon test is used, as an example, for the component problems, the main issue being how to combine dependent test statistics into a single efficient overall test. Keeping the practitioner’s needs in mind, a linear function of the individual test statistics is considered and the Abelson-Tukey-Schaafsma-Smid principle (of minimizing “the maximum shortcoming”) is applied to derive the optimal (minimax) coefficients in the linear combination. The advantages of using optimal weights are illustrated by making ARE comparisons with the Jonckheere-Terpstra-Tryon-Hettmansperger test. The restriction to the class of linear combinations is attractive from the practitioner’s viewpoint but the theoretical statistician will argue that such linear combinations leading to “somewhere” most powerful tests makes them questionable from an overall point of view. Hence, alternative approaches are discussed, at least to some extent. The main purpose of the paper, however, is to assist the practitioner who has decided to use a linear combination but worries about the weights to be chosen. It is argued that the restriction by linearity is less questionable for the simple order than for the simple-tree order.

Consider the one-way random effects model Z _ij = µ + α _i + ε _ij , i = 1,2,…, m, j = 1,2,…, n, where α _i and ε _ij are mutually independent and distributed with mean zero and variance σ_α2 and σ_ε2, respectively. An estimation procedure is developed for estimating $$\rho ^2 = \sigma _\alpha ^2 /\sigma _\varepsilon ^2$$, the ratio of variance components, using a method similar to that proposed by Shorack (1969) for estimating the ratio of two scale parameters. An extensive Monte Carlo study is carried out in order to investigate the performance of the proposed method when compared with the other two methods provided by Groggel, Wackerly and Rao (1987) and Bhattacharyya (1977). The study suggests that the proposed method is superior to those two alternative methods for certain ranges of the model parameters. Finally, we propose a small-sample adjustment which improves the performance of the estimation method.

The purpose of this paper is to study limit behavior of processes related to M-estimators using certain properties of related rank statistics processes proved in Hušková (1996b). The results are then employed to obtain the limit distribution of M-statistics for change point problem, particularly, to get the limit behavior of the test statistics for detection of a change and limit behavior of estimators of the change.