Skip to main content
main-content

Über dieses Buch

Sri Gopal Mohanty has made pioneering contributions to lattice path counting and its applications to probability and statistics. This is clearly evident from his lifetime publications list and the numerous citations his publications have received over the past three decades. My association with him began in 1982 when I came to McMaster Univer­ sity. Since then, I have been associated with him on many different issues at professional as well as cultural levels; I have benefited greatly from him on both these grounds. I have enjoyed very much being his colleague in the statistics group here at McMaster University and also as his friend. While I admire him for his honesty, sincerity and dedication, I appreciate very much his kindness, modesty and broad-mindedness. Aside from our common interest in mathematics and statistics, we both have great love for Indian classical music and dance. We have spent numerous many different subjects associated with the Indian music and hours discussing dance. I still remember fondly the long drive (to Amherst, Massachusetts) I had a few years ago with him and his wife, Shantimayee, and all the hearty discussions we had during that journey. Combinatorics and applications of combinatorial methods in probability and statistics has become a very active and fertile area of research in the recent past.

Inhaltsverzeichnis

Frontmatter

Lattice Paths and Combinatorial Methods

Frontmatter

1. Lattice Paths and Faber Polynomials

The r-th Faber polynomial of the Laurent series f(t) = t + f0 + f1/t + f2/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.

Ira M. Gessel, Sangwook Ree

2. Lattice Path Enumeration and Umbral Calculus

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.

Heinrich Niederhausen

3. The Enumeration of Lattice Paths With Respect to Their Number of Turns

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.

C. Krattenthaler

4. Lattice Path Counting, Simple Random Walk Statistics, and Randomization: An Analytic Approach

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.

Wolfgang Panny, Walter Katzenbeisser

5. Combinatorial Identities: A Generalization of Dougall’s Identity

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.

Erik Sparre Andersen, Mogens Esrom Larsen

6. A Comparison Of Two Methods For Random Labelling of Balls by Vectors of Integers

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 (a1,…, 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.

Doron Zeilberger

Applications to Probability Problems

Frontmatter

7. On The Ballot Theorems

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.

Lajos Takàcs

8. Some Results for Two-Dimensional Random Walk

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.

Endre Csáki

9. Random Walks on SL(2, F2) and Jacobi Symbols of Quadratic Residues

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

Toshihiro Watanabe

10. Rank Order Statistics Related to a Generalized Random Walk

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).

Jagdish Saran, Sarita Rani

11. On a Subset Sum Algorithm and Its Probabilistic and Other Applications

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.

V. G. Voinov, M. S. Nikulin

12. I and J Polynomials in a Potpourri of Probability 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.

Milton Sobel

13. Stirling Numbers and Records

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.

N. Balakrishnan, V. B. Nevzorov

Applications to Urn Models

Frontmatter

14. Advances in Urn Models during the Past Two Decades

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.

Samuel Kotz, N. Balakrishnan

15. A Unified Derivation of Occupancy and Sequential Occupancy Distributions

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 Sn+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 − K0 of occupied urns (by at least one ball), among n specified urns, given that Sn+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[Wk+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.

A. Charalambides

16. Moments, Binomial Moments and Combinatorics

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.

Janos Galambos

Applications to Queueing Theory

Frontmatter

17. Nonintersecting Paths and Applications in Queueing Theory

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.

Walter Böhm

18. Transient Busy Period Analysis of Initially Non-Empty M/G/l Queues—Lattice Path Approach

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, C2. 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 C2, that has Markovian property, amenable to the application of lattice paths combinatorial analysis, the use of C2 therefore has led us to achieve transient results applicable to almost any real life queueing system M/G/l.

Kanwar Sen, Manju Agarwal

19. Single Server Queueing System with Poisson Input: A Review of Some Recent Developments

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.

J. Medhi

20. Recent Advances in the Analysis of Polling Systems

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.

Diwakar Gupta, Yavuz Günalay

Applications to Waiting Time Problems

Frontmatter

21. Waiting Times and Number of Appearances of Events in a Sequence of Discrete Random Variables

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.

Markos V. Koutras

22. On Sooner and Later Problems Between Success and Failure Runs

Let X0, X1, X2,… be a sequence of {0, 1}-valued Markov chain. Let E1 denote a run of “1” of length k and E0 denote a run of “0” of length r. We observe which run comes sooner or later in the sequence X0, X1, X2, …. 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 F1 be a success run of length k or more and let F0 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 F1 and F0 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.

Sigeo Aki

23. Distributions of Numbers of Success-Runs Until the First Consecutive k Successes in Higher Order Markov Dependent 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.

Katuomi Hirano, Sigeo Aki, Masayuki Uchida

24. On Multivariate Distributions of Various Orders Obtained by Waiting for the r-th Success Run of Length k in Trials With Multiple Outcomes

A sequence of independent trials with m + 1 mutually exclusive outcomes S, F 1 , F2,…, 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).

Demetrios L. Antzoulakos, Andreas N. Philippou

25. A Multivariate Negative Binomial Distribution of Order k Arising When Success Runs are Allowed to Overlap

Ling (1989) introduced and studied a negative binomial distribution of order k, type III, which he denoted by NBk 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 ),$$.

Gregory A. Tripsiannis, Andreas N. Philippou

Applications to Distribution Theory

Frontmatter

26. The Joint Energy Distributions of the Bose-Einstein and of the Fermi-Dirac Particles

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)].

I. Vincze, R. Tőrös

27. On Modified q-Bessel Functions and Some Statistical Applications

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.

A. W. Kemp

28. A q-Logarithmic Distribution

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.

C. David Kemp

29. Bernoulli Learning Models: Uppuluri Numbers

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.

K. G. Janardan

Applications to Nonparametric Statistics

Frontmatter

30. Linear Nonparametric Tests Against Restricted Alternatives: The Simple-Tree Order and The Simple Order

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.

S. Chakraborti, W. Schaafsma

31. Nonparametric Estimation of the Ratio of Variance Components

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.

M. Mahibbur Rahman, Z. Govindarajulu

32. Limit Theorems for M-Processes Via Rank Statistics Processes

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.

M. Hušková

Backmatter

Weitere Informationen