Distributions of periods and frequencies of runs in random binary sequences

DOI10.1016/0196-8858(89)90015-8MaRDI QIDQ915253zbMATH OpenOpenAlexFDO

Authors S. W. Golomb

Publication date 1989

Published in Advances in Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0196-8858(89)90015-8

zbMATH Keywords

generating functionperiods and frequencies of runsrandom binary sequences

Mathematics Subject Classification ID

Combinatorial probability (60C05) Characteristic functions; other transforms (60E10) Limit theorems in probability theory (60F99)

Review text

The paper concerns random binary sequences in which 1's and 0's occur independently, with respective probabilities p and \(q=1-p\). As the main result it is shown that the probabilities p(k) that the length of the interval from the beginning of one run of 1's to the next is exactly k units, is equal to \((p^ kq-q^ kp)/(p-q)\) for \(p\neq q\) and \((k- 1)2^{-k}\) if \(p=q=1/2\). This result seems to be well-known for a long time. It could be a good exercise for students in a first course of probability.

Recommendations

• Generalizations of runs and patterns distributions for sequences of binary trials
• On the distribution of runs of ones in binary strings
• Autocorrelations of Binary Sequences and Run Structure
• Approximating the distributions of runs and patterns
• Central limit theorem approximations for the number of runs in Markov-dependent binary sequences
• Almost periodic random sequences in probability
• Almost periodic random sequences in probability
• On a problem of the statistical analysis of binary random sequences
• scientific article; zbMATH DE number 431871
• On random binary sequences

Cites work

• scientific article; zbMATH DE number 3165668 (Why is no real title available?)
• scientific article; zbMATH DE number 3059214 (Why is no real title available?)
• Sources which maximize the choice of a Huffman coding tree

Cited in

(11)

• ``Periods of de Bruijn sequences
• Run distribution in nonlinear binary generators.
• Joint distribution of some statistics of random bit sequences
• Weak runs in sequences of binary trials
• Checking the randomness of bits disposition in local segments of the \((0, 1)\)-sequence
• Generalizations of runs and patterns distributions for sequences of binary trials
• How long until a random sequence decreases?
• scientific article; zbMATH DE number 4007323 (Why is no real title available?)
• Generating Functions Associated with Random Binary Sequences Consisting of Runs of Lengths 1 and 2
• Limiting distributions of two random sequences
• On the distribution of runs of ones in binary strings

This page was built for publication: Distributions of periods and frequencies of runs in random binary sequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q915253)