Advances in Combinatorial Methods and Applications to Probability and Statistics

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.

I—Lattice Paths and Combinatorial Methods.- 1 Lattice Paths and Faber Polynomials.- 1.1 Introduction.- 1.2 Faber Polynomials.- 1.3 Counting Paths.- 1.4 A Positivity Result.- 1.5 Examples.- References.- 2 Lattice Path Enumeration and Umbral Calculus.- 2.1 Introduction.- 2.1.1 Notation.- 2.2 Initial Value Problems.- 2.2.1 The role of ex.- 2.2.2 Piecewise affine boundaries.- 2.2.3 Applications: Bounded paths.- 2.3 Systems of Operator Equations.- 2.3.1 Applications: Lattice paths with several step directions.- 2.4 Symmetric Sheffer Sequences.- 2.4.1 Applications: Weighted left turns.- 2.4.2 Paths inside a band.- 2.5 Geometric Sheffer Sequences.- 2.5.1 Applications: Crossings.- References.- 3 The Enumeration of Lattice Paths With Respect to Their Number of Turns.- 3.1 Introduction.- 3.2 Notation.- 3.3 Motivating Examples.- 3.4 Turn Enumeration of (Single) Lattice Paths.- 3.5 Applications.- 3.6 Nonintersecting Lattice Paths and Turns.- References.- 4 Lattice Path Counting Simple Random Walk Statistics, and Randomizations: An Analytic Approach.- 4.1 Introduction.- 4.2 Lattice Paths.- 4.3 Simple Random Walks.- 4.4 Randomized Random Walks.- References.- 5 Combinatorial Identities: A Generalization of Dougall’s Identity.- 5.1 Introduction.- 5.2 The Generalized Pfaff-Saalschütz Formula.- 5.3 A Modified Pfaff-Saalschiitz Sum of Type II(4,4,1)N.- 5.4 A Well-Balanced II(5,5,1)N Identity.- 5.5 A Generalization of Dougall’s Weil-Balanced II(7 7,1)N Identity.- References.- 6 A Comparison of Two Methods for Random Labelling of Balls by Vectors of Integers.- 6.1 First Way.- 6.2 Second Way.- 6.3 Variance and Standard Deviation.- 6.4 Analysis of the Second Way.- References.- II—Applications to Probability Problems.- 7 On the Ballot Theorems.- 7.1 Introduction.- 7.2 The Classical Ballot Theorem.- 7.3 The Original Proofs of Theorem 7.2.1.- 7.4 Historical Background.- 7.5 The General Ballot Theorem.- 7.6 Some Combinatorial Identities.- 7.7 Another Extension of The Classical Ballot Theorem.- References.- 8 Some Results for Two-Dimensional Random Walk.- 8.1 Introduction.- 8.2 Identities and Distributions.- 8.3 Pairs of LRW Paths.- References.- 9 Random Walks on SL(2, F2) and Jacobi Symbols of Quadratic Residues.- 9.1 Introduction.- 9.2 Preliminaries.- 9.3 A Calculation of the Character ?(?M,m)and Its Relation.- References.- 10 Rank Order Statistics Related to a Generalized Random Walk.- 10.1 Introduction.- 10.2 Some Auxiliary Results.- 10.3 The Technique.- 10.4 Definitions of Rank Order Statistics.- 10.5 Distributions of N?,n+* (a) and R?, n+*(a).- 10.6 Distributions of ??,n+ (a) and Rf?,n+(a).- 10.7 Distributions of N?,n* (a) and R?,n* (a).- References.- 11 On a Subset Sum Algorithm and Its Probabilistic and Other Applications.- 11.1 Introduction.- 11.2 A Derivation of the Algorithm.- 11.3 A Class of Discrete Probability Distributions.- 11.4 A Remark on a Summation Procedure When Constructing Partitions.- References.- 12 I and J Polynomials in a Potpourri of Probability Problems.- 12.1 Introduction.- 12.2 Guide to the Problems of this Paper.- 12.3 Triangular Network with Common Failure Probability q for Each Unit.- 12.4 Duality Levels in a Square with Diagonals That Do Not Intersect: Problem 12.5.- References.- 13 Stirling Numbers and Records.- 13.1 Stirling Numbers.- 13.2 Generalized Stirling Numbers.- 13.3 Stirling Numbers and Records.- 13.4 Generalized Stirling Numbers and Records in the F?-scheme.- 13.5 Record Values from Discrete Distributions and Generalized Stirling Numbers.- References.- III—Applications to Urn Models.- 14 Advances in Urn Models During The Past Two Decades.- 14.1 Introduction.- 14.2 Pólya-Eggenberger Urns and Their Generalizations and Modifications.- 14.3 Generalizations of the Classical Occupancy Model.- 14.4 Ehrenfest Urn Model.- 14.5 Pólya Urn Model with a Continuum of Colors.- 14.6 Stopping Problems in Urns.- 14.7 Limit Theorems for Urns with Random Drawings.- 14.8 Limit Theorems for Sequential Occupancy.- 14.9 Limit Theorems for Infinite Urn Models.- 14.10 Urn Models with Indistinguishable Balls (Bose-Einstein Statistics).- 14.11 Ewens Sampling Formula and Coalescent Urn Models.- 14.12 Reinforcement-Depletion (Compartmental) Urn Models.- 14.13 Urn Models for Interpretation of Mathematical and Probabilistic Concepts and Engineering and Statistical Applications.- References.- 15 A Unified Derivation of Occupancy and Sequential Occupancy Distributions.- 15.1 Introduction.- 15.2 Occupancy Distributions.- 15.3 Sequential Occupancy Distributions.- References.- 16 Moments Binomial Moments and Combinatorics.- 16.1 Basic Relations.- 16.2 Linear Inequalities in Sk, pr and qr.- 16.3 A Statistical Paradox and an Urn Model with Applications.- 16.4 Quadratic Inequalities.- References.- IV—Applications to Queueing Theory.- 17 Nonintersecting Paths and Applications to Queueing Theory.- 17.1 Introduction.- 17.2 Dissimilar Bernoulli Processes.- 17.3 The r-Node Series Jackson Network.- 17.4 The Dummy Path Lemma for Poisson Processes.- 17.5 A Special Variant of D/M/l Queues.- References.- 18 Transient Busy Period Analysis of Initially Non-Empty M/G/l Queues—Lattice Path Approach.- 18.1 Introduction.- 18.2 Lattice Path Approach.- 18.3 Discretized M/C2/l Model.- 18.3.1 Transition probabilities.- 18.3.2 Counting of lattice paths.- 18.3.3 Busy period probability.- 18.4 Continuous M/C2/l Model.- 18.5 Particular Cases.- References.- 19 Single Server Queueing System with Poisson Input: A Review of Some Recent Developments.- 19.1 Introduction.- 19.2 Exceptional Service for the First Unit in Each Busy Period.- 19.3 M/G/l With Random Setup Time 5.- 19.4 M/G/l System Under N-Policy.- 19.5 M/G/l Under N-Policy and With Setup Time.- 19.6 Queues With Vacation: M/G/l Queueing System With Vacation.- 19.7 M/G/l - Vm System.- 19.8 M/G/l - Vm With Exceptional First Vacation.- 19.9 M/G/l - Vs System.- 19.10 M/G/l System With Vacation and Under N-Policy (With Threshold N).- 19.11 Mx/G/1 System With Batch Arrival.- 19.12 Mx/G/1 Under N-Policy.- 19.13 Mx/G/1—Vm and Mx/G/1 — Vs.- 19.14 Mx/G/1 Vacation Queues Under N-Policy.- 19.15 Concluding Remarks.- References.- 20 Recent Advances in the Analysis of Polling Systems.- 20.1 Introduction.- 20.2 Notations and Preliminaries.- 20.3 Main Results.- 20.4 Some Related Models.- 20.4.1 Customer routing.- 20.4.2 Stopping only at a preferred station.- 20.4.3 Gated or mixed service policy.- 20.4.4 State-dependent setups.- 20.4.5 Periodic monitoring during idle period.- 20.5 Insights.- 20.6 Future Directions.- References.- V—Applications to Waiting Time Problems.- 21 Waiting Times and Number of Appearances of Events in a Sequence of Discrete Random Variables.- 21.1 Introduction.- 21.2 Definitions and Notations.- 21.3 General Results.- 21.4 Waiting Times and Number of Occurrences of Delayed Recurrent Events.- 21.5 Distribution of the Number of Success Runs in a Two-State Markov Chain.- 21.5.1 Non-overlapping success runs.- 21.5.2 Success runs of length at least k.- 21.5.3 Overlapping success runs.- 21.5.4 Number of non-overlapping windows of length at most k containing exactly 2 successes.- 21.6 Conclusions.- References.- 22 On Sooner and Later Problems Between Success and Failure Runs.- 22.1 Introduction.- 22.2 Number of Ocurrences of the Sooner Event Until the Later Waiting Time.- 22.3 Joint Distribution of Numbers of Runs.- References.- 23 Distributions of Numbers of Success-Runs Until the First Consecutive k Successes in Higher Order Markov Dependent Trials.- 23.1 Introduction.- 23.2 Numbers of Success-Runs in Higher Order Markov Chain.- 23.3 Case l < m.- References.- 24 On Multivariate Distributions of Various Orders Obtained by Waiting for the r-th Success Run of Length k in Trials With Multiple Outcomes.- 24.1 Introduction.- 24.2 Independent Trials.- 24.3 Generalized Sequence of Order k.- References.- 25 A Multivariate Negative Binomial Distribution of Order k Arising When Success Runs are Allowed to Overlap.- 25.1 Introduction.- 25.2 Multivari