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

Yong Kong ()
Additional contact information
Yong Kong: Yale University

Methodology and Computing in Applied Probability, 2019, vol. 21, issue 3, 789-803

Abstract: Abstract 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.

Keywords: Combinatorial complexity; Generating function; Distribution-free statistical test; Combinatorial identities; Gosper-Zeilberger method; Randomness test; Runs length test; Distributions of runs; Multivariate ligand binding; 05A15; 60C05; 68R05; 68R15; 92C05 (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s11009-018-9689-1 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:metcap:v:21:y:2019:i:3:d:10.1007_s11009-018-9689-1

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/11009

DOI: 10.1007/s11009-018-9689-1

Access Statistics for this article

Methodology and Computing in Applied Probability is currently edited by Joseph Glaz

More articles in Methodology and Computing in Applied Probability from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().