Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe Number of Distinct Subsequences of a Random Binary String
113
0
0.0
(
0
)
Authors
Michael J. Collins
Ask ChatGPT about the research
No Arabic abstract
We determine the average number of distinct subsequences in a random binary string, and derive an estimate for the average number of distinct subsequences of a particular length.
rate research
Read More
When considering binary strings, its 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.
Let $pi_n$ be a uniformly chosen random permutation on $[n]$. Using an analysis of the probability that two overlapping consecutive $k$-permutations are order isomorphic, we show that the expected number of distinct consecutive patterns in $pi_n$ is $frac{n^2}{2}(1-o(1))$. This exhibits the fact that random permutations pack consecutive patterns near-perfectly.
We revisit staircases for words and prove several exact as well as asymptotic results for longest left-most staircase subsequences and subwords and staircase separation number, the latter being defined as the number of consecutive maximal staircase subwords packed in a word. We study asymptotic properties of the sequence $h_{r,k}(n),$ the number of $n$-array words with $r$ separations over alphabet $[k]$ and show that for any $rgeq 0,$ the growth sequence $big(h_{r,k}(n)big)^{1/n}$ converges to a characterized limit, independent of $r.$ In addition, we study the asymptotic behavior of the random variable $mathcal{S}_k(n),$ the number of staircase separations in a random word in $[k]^n$ and obtain several limit theorems for the distribution of $mathcal{S}_k(n),$ including a law of large numbers, a central limit theorem, and the exact growth rate of the entropy of $mathcal{S}_k(n).$ Finally, we obtain similar results, including growth limits, for longest $L$-staircase subwords and subsequences.
For $n > 2k geq 4$ we consider intersecting families $mathcal F$ consisting of $k$-subsets of ${1, 2, ldots, n}$. Let $mathcal I(mathcal F)$ denote the family of all distinct intersections $F cap F$, $F eq F$ and $F, Fin mathcal F$. Let $mathcal A$ consist of the $k$-sets $A$ satisfying $|A cap {1, 2, 3}| geq 2$. We prove that for $n geq 50 k^2$ $|mathcal I(mathcal F)|$ is maximized by $mathcal A$.
A fringe subtree of a rooted tree is a subtree induced by one of the vertices and all its descendants. We consider the problem of estimating the number of distinct fringe subtrees in two types of random trees: simply generated trees and families of increasing trees (recursive trees, $d$-ary increasing trees and generalized plane-oriented recursive trees). We prove that the order of magnitude of the number of distinct fringe subtrees (under rather mild assumptions on what `distinct means) in random trees with $n$ vertices is $n/sqrt{log n}$ for simply generated trees and $n/log n$ for increasing trees.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
