Decoupling Combinatorial Complexity: a Two-Step Approach to Distributions of Runs

Runs statistics have found many applications in various fields and have attracted attentions of many researchers. Traditional methods used to investigate run-related distributions are ad hoc and not easy to generalize. The problems often become tedious because of the combinatorial complexity involved. Several unified methods have been devised to overcome the combinatorial difficulties. One of them is the finite Markov chain imbedding approach. Recently we used a different systematic approach that is inspired by methods in statistical physics. In this approach the study of runs distributions is decoupled into two easy independent steps. In the first step, elements of each of the same object are considered in isolation without regards of elements of the other objects. By considering only one kind of object each time the complexity involved is reduced considerably. In the second step, general formulas in matrix or explicit forms combine the results from the first step into a whole multi-object system with potential nearest neighbor interactions. The method reduces the complicated combinatorics to simple mechanical manipulations of binomial and multinomial coefficients, which can be carried out automatically by the Gosper-Zeilberger method. Many commonly studied run and pattern distributions, such as exact length runs, runs of Type I, II, III, the longest runs, rises and falls, among others, can be handled by the method. Novel run-related distributions have been derived using the method. We’ll discuss the general framework of the method and use some examples to illustrate its application to distributions of runs, including the derivation of the m th longest runs distributions of multivariate random sequences.