Margaret Archibald ; Aubrey Blecher ; Charlotte Brennan ; Arnold Knopfmacher ; Stephan Wagner et al. - The number of distinct adjacent pairs in geometrically distributed words

dmtcs:5686 - Discrete Mathematics & Theoretical Computer Science, January 28, 2021, vol. 22 no. 4 - https://doi.org/10.23638/DMTCS-22-4-10
The number of distinct adjacent pairs in geometrically distributed words

Authors: Margaret Archibald ; Aubrey Blecher ; Charlotte Brennan ; Arnold Knopfmacher ; Stephan Wagner ; Mark Ward

    A sequence of geometric random variables of length $n$ is a sequence of $n$ independent and identically distributed geometric random variables ($\Gamma_1, \Gamma_2, \dots, \Gamma_n$) where $\mathbb{P}(\Gamma_j=i)=pq^{i-1}$ for $1~\leq~j~\leq~n$ with $p+q=1.$ We study the number of distinct adjacent two letter patterns in such sequences. Initially we directly count the number of distinct pairs in words of short length. Because of the rapid growth of the number of word patterns we change our approach to this problem by obtaining an expression for the expected number of distinct pairs in words of length $n$. We also obtain the asymptotics for the expected number as $n \to \infty$.


    Volume: vol. 22 no. 4
    Section: Analysis of Algorithms
    Published on: January 28, 2021
    Accepted on: November 10, 2020
    Submitted on: August 12, 2019
    Keywords: Mathematics - Combinatorics,05A15, 05A05

    Share

    Consultation statistics

    This page has been seen 306 times.
    This article's PDF has been downloaded 76 times.