Expected Number of Distinct Subsequences in Randomly Generated Binary Strings
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 t...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2018-06-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/3287/pdf |
| _version_ | 1797270095993503744 |
|---|---|
| author | Yonah Biers-Ariel Anant Godbole Elizabeth Kelley |
| author_facet | Yonah Biers-Ariel Anant Godbole Elizabeth Kelley |
| author_sort | Yonah Biers-Ariel |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-25T01:58:50Z |
| format | Article |
| id | doaj.art-b89ccac7bb244e5c916d4286bf814e6d |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T01:58:50Z |
| publishDate | 2018-06-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-b89ccac7bb244e5c916d4286bf814e6d2024-03-07T15:33:33ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502018-06-01Vol. 19 no. 2, Permutation...Permutation Patterns10.23638/DMTCS-19-2-103287Expected Number of Distinct Subsequences in Randomly Generated Binary StringsYonah Biers-ArielAnant GodboleElizabeth KelleyWhen 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.https://dmtcs.episciences.org/3287/pdfmathematics - combinatorics05d40, 60c05 |
| spellingShingle | Yonah Biers-Ariel Anant Godbole Elizabeth Kelley Expected Number of Distinct Subsequences in Randomly Generated Binary Strings Discrete Mathematics & Theoretical Computer Science mathematics - combinatorics 05d40, 60c05 |
| title | Expected Number of Distinct Subsequences in Randomly Generated Binary Strings |
| title_full | Expected Number of Distinct Subsequences in Randomly Generated Binary Strings |
| title_fullStr | Expected Number of Distinct Subsequences in Randomly Generated Binary Strings |
| title_full_unstemmed | Expected Number of Distinct Subsequences in Randomly Generated Binary Strings |
| title_short | Expected Number of Distinct Subsequences in Randomly Generated Binary Strings |
| title_sort | expected number of distinct subsequences in randomly generated binary strings |
| topic | mathematics - combinatorics 05d40, 60c05 |
| url | https://dmtcs.episciences.org/3287/pdf |
| work_keys_str_mv | AT yonahbiersariel expectednumberofdistinctsubsequencesinrandomlygeneratedbinarystrings AT anantgodbole expectednumberofdistinctsubsequencesinrandomlygeneratedbinarystrings AT elizabethkelley expectednumberofdistinctsubsequencesinrandomlygeneratedbinarystrings |