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&...
Saved in:
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2025-01-01
|
| Series: | Entropy |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1099-4300/27/1/34 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832588559162277888 |
|---|---|
| author | Karl Grill |
| author_facet | Karl Grill |
| author_sort | Karl Grill |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-7832e24009844c82a6617e83dfca76c3 |
| institution | Kabale University |
| issn | 1099-4300 |
| language | English |
| publishDate | 2025-01-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Entropy |
| spelling | doaj-art-7832e24009844c82a6617e83dfca76c32025-01-24T13:31:45ZengMDPI AGEntropy1099-43002025-01-012713410.3390/e27010034An Erdős-Révész Type Law for the Length of the Longest Match of Two Coin-Tossing SequencesKarl Grill0Institute of Statistics and Mathematical Methods in Economy, TU Wien, Wiedner Hauptstraße 8-10, 1040 Vienna, AustriaConsider 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.https://www.mdpi.com/1099-4300/27/1/34coin tossingrunsmatching subsequencesstrong asymptotics |
| spellingShingle | Karl Grill An Erdős-Révész Type Law for the Length of the Longest Match of Two Coin-Tossing Sequences Entropy coin tossing runs matching subsequences strong asymptotics |
| title | An Erdős-Révész Type Law for the Length of the Longest Match of Two Coin-Tossing Sequences |
| title_full | An Erdős-Révész Type Law for the Length of the Longest Match of Two Coin-Tossing Sequences |
| title_fullStr | An Erdős-Révész Type Law for the Length of the Longest Match of Two Coin-Tossing Sequences |
| title_full_unstemmed | An Erdős-Révész Type Law for the Length of the Longest Match of Two Coin-Tossing Sequences |
| title_short | An Erdős-Révész Type Law for the Length of the Longest Match of Two Coin-Tossing Sequences |
| title_sort | erdos revesz type law for the length of the longest match of two coin tossing sequences |
| topic | coin tossing runs matching subsequences strong asymptotics |
| url | https://www.mdpi.com/1099-4300/27/1/34 |
| work_keys_str_mv | AT karlgrill anerdosrevesztypelawforthelengthofthelongestmatchoftwocointossingsequences AT karlgrill erdosrevesztypelawforthelengthofthelongestmatchoftwocointossingsequences |