Yonah Biers-Ariel ; Anant Godbole ; Elizabeth Kelley - Expected Number of Distinct Subsequences in Randomly Generated Binary Strings

dmtcs:3287 - Discrete Mathematics & Theoretical Computer Science, June 26, 2018, Vol. 19 no. 2, Permutation Patterns 2016 - https://doi.org/10.23638/DMTCS-19-2-10
Expected Number of Distinct Subsequences in Randomly Generated Binary StringsArticle

Authors: Yonah Biers-Ariel ; Anant Godbole ; Elizabeth Kelley

    When considering binary strings, it's natural to wonder how many distinct subsequences might exist in a given string. Given that there is an existing algorithm which provides a straightforward way to compute the number of distinct subsequences in a fixed string, we might next be interested in the expected number of distinct subsequences in random strings. This expected value is already known for random binary strings where each letter in the string is, independently, equally likely to be a 1 or a 0. We generalize this result to random strings where the letter 1 appears independently with probability $\alpha \in [0,1]$. Also, we make some progress in the case of random strings from an arbitrary alphabet as well as when the string is generated by a two-state Markov chain.


    Volume: Vol. 19 no. 2, Permutation Patterns 2016
    Section: Permutation Patterns
    Published on: June 26, 2018
    Accepted on: June 1, 2018
    Submitted on: April 28, 2017
    Keywords: Mathematics - Combinatorics,05D40, 60C05
    Funding:
      Source : OpenAIRE Graph
    • REU Site: Combinatorics and Probability; Funder: National Science Foundation; Code: 1263009

    Consultation statistics

    This page has been seen 485 times.
    This article's PDF has been downloaded 310 times.