Learning Temporal Structures of Random Patterns by Generating Functions

Abstract

We present a method of generating functions to compute the distributions of the first-arrival and inter-arrival times of random patterns in independent Bernoulli trials and first-order Markov trials. We use segmentation of pattern events and diagrams of Markov chains to illustrate the recursive structures represented by generating functions. We then relate the results of pattern time to the probability of first occurrence and the probability of occurrence at least once within a finite sample size. Through symbolic manipulation of formal power series and multiple levels of compression, generating functions provide a powerful way to discover the rich statistical structures embedded in random sequences.

KEYWORDS:

• Cognitive bias
• Event segmentation
• Generating function
• Waiting time

Acknowledgments

We would like to offer special thanks to the late Professor Emeritus Ryan D. Tweney, who carefully read and commented on an early version of this article, and continues to inspire by his example and dedication to the students he served over the course of his career.

Additional information

Funding

This work was partially supported by the Office of Naval Research (ONR) grant N00014-16-1-2111.