Expected Number of Distinct Subsequences in Randomly Generated Binary Strings

MaRDI QIDQ4560193zbMATH OpenFDO

Authors Yonah Biers-Ariel, Anant P. Godbole, Elizabeth Kelley

Publication date 10 December 2018

Full work available at URL https://arxiv.org/abs/1704.08661, https://dmtcs.episciences.org/4590/pdf

zbMATH Keywords

subadditivityrandom stringsdistinct subsequences

Mathematics Subject Classification ID

Combinatorial probability (60C05) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Abstract: 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 $alphain[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.

Recommendations

• On the probability of existence of substrings with the same structure in a random sequence
• On a Conjecture about Binary Strings Distribution
• scientific article; zbMATH DE number 2185636
• Upper bounds for the expected length of a longest common subsequence of two binary sequences
• Joint distributions of counts of strings in finite Bernoulli sequences
• On random binary sequences
• LATIN 2004: Theoretical Informatics
• Expected length of the longest common subsequence for large alphabets
• Common Subsequences and Supersequences and their Expected Length

Cited in

(6)

• Universal arrays
• Some generalizations on counting binary strings
• Finding binary words with a given number of subsequences
• Probabilities of Clumps in a Binary Sequence (and How to Evaluate Them Without Knowing a Lot)
• On a Conjecture about Binary Strings Distribution
• Minimizing positive integer sequences without duplicate substrings

This page was built for publication: Expected Number of Distinct Subsequences in Randomly Generated Binary Strings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4560193)