An Erdős-Révész Type Law for the Length of the Longest Match of Two Coin-Tossing Sequences

An Erdős-Révész Type Law for the Length of the Longest Match of Two Coin-Tossing Sequences

Consider a coin-tossing sequence, i.e., a sequence of independent variables, taking values 0 and 1 with probability <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mn>1</mn><mo>/</mo&...

Full description

Saved in:
Bibliographic Details
Main Author: Karl Grill
Format: Article
Language:English
Published: MDPI AG 2025-01-01
Series:Entropy
Subjects:
coin tossing
runs
matching subsequences
strong asymptotics
Online Access:https://www.mdpi.com/1099-4300/27/1/34
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Consider a coin-tossing sequence, i.e., a sequence of independent variables, taking values 0 and 1 with probability <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mn>1</mn><mo>/</mo><mn>2</mn></mrow></semantics></math></inline-formula>. The famous Erdős-Rényi law of large numbers implies that the longest run of ones in the first <i>n</i> observations has a length <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>R</mi><mi>n</mi></msub></semantics></math></inline-formula> that behaves like <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>log</mi><mo>(</mo><mi>n</mi><mo>)</mo></mrow></semantics></math></inline-formula>, as <i>n</i> tends to infinity (throughout this article, log denotes logarithm with base 2). Erdős and Révész refined this result by providing a description of the Lévy upper and lower classes of the process <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>R</mi><mi>n</mi></msub></semantics></math></inline-formula>. In another direction, Arratia and Waterman extended the Erdős-Rényi result to the longest matching subsequence (with shifts) of two coin-tossing sequences, finding that it behaves asymptotically like <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mn>2</mn><mi>log</mi><mo>(</mo><mi>n</mi><mo>)</mo></mrow></semantics></math></inline-formula>. The present paper provides some Erdős-Révész type results in this situation, obtaining a complete description of the upper classes and a partial result on the lower ones.
ISSN:1099-4300

Similar Items