Geodesic
Expected Number of Distinct Subsequences in Randomly Generated Binary Strings
Discrete mathematics & theoretical computer science, Permutation Patterns 2016, Tome 19 (2017-2018) no. 2

Voir la notice de l'article provenant de la source Episciences

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. 
@article{DMTCS_2018_19_2_a9,
     author = {Biers-Ariel, Yonah and Godbole, Anant and Kelley, Elizabeth},
     title = {Expected {Number} of {Distinct} {Subsequences} in {Randomly} {Generated} {Binary} {Strings}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {19},
     number = {2},
     year = {2017-2018},
     doi = {10.23638/DMTCS-19-2-10},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-19-2-10/}
}
TY  - JOUR
AU  - Biers-Ariel, Yonah
AU  - Godbole, Anant
AU  - Kelley, Elizabeth
TI  - Expected Number of Distinct Subsequences in Randomly Generated Binary Strings
JO  - Discrete mathematics & theoretical computer science
PY  - 2017-2018
VL  - 19
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-19-2-10/
DO  - 10.23638/DMTCS-19-2-10
LA  - en
ID  - DMTCS_2018_19_2_a9
ER  - 
%0 Journal Article
%A Biers-Ariel, Yonah
%A Godbole, Anant
%A Kelley, Elizabeth
%T Expected Number of Distinct Subsequences in Randomly Generated Binary Strings
%J Discrete mathematics & theoretical computer science
%D 2017-2018
%V 19
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-19-2-10/
%R 10.23638/DMTCS-19-2-10
%G en
%F DMTCS_2018_19_2_a9
Biers-Ariel, Yonah; Godbole, Anant; Kelley, Elizabeth. Expected Number of Distinct Subsequences in Randomly Generated Binary Strings. Discrete mathematics & theoretical computer science, Permutation Patterns 2016, Tome 19 (2017-2018) no. 2. doi: 10.23638/DMTCS-19-2-10

Cité par Sources :