Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userExpected Number of Distinct Subsequences in Randomly Generated Binary Strings
54
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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.
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.
There exists a significant body of work on determining the acquisition number $a_t(G)$ of various graphs when the vertices of those graphs are each initially assigned a unit weight. We determine properties of the acquisition number of the path, star, complete, complete bipartite, cycle, and wheel graphs for variations on this initial weighting scheme, with the majority of our work focusing on the expected acquisition number of randomly weighted graphs. In particular, we bound the expected acquisition number $E(a_t(P_n))$ of the $n$-path when $n$ distinguishable units of integral weight, or chips, are randomly distributed across its vertices between $0.242n$ and $0.375n$. With computer support, we improve it by showing that $E(a_t(P_n))$ lies between $0.29523n$ and $0.29576n$. We then use subadditivity to show that the limiting ratio $lim E(a_t(P_n))/n$ exists, and simulations reveal more exactly what the limiting value equals. The Hoeffding-Azuma inequality is used to prove that the acquisition number is tightly concentrated around its expected value. Additionally, in a different context, we offer a non-optimal acquisition protocol algorithm for the randomly weighted path and exactly compute the expected size of the resultant residual set.
A well-known conjecture by Lovasz and Plummer from the 1970s asserted that a bridgeless cubic graph has exponentially many perfect matchings. It was solved in the affirmative by Esperet et al. (Adv. Math. 2011). On the other hand, Chudnovsky and Seymour (Combinatorica 2012) proved the conjecture in the special case of cubic planar graphs. In our work we consider random bridgeless cubic planar graphs with the uniform distribution on graphs with $n$ vertices. Under this model we show that the expected number of perfect matchings in labeled bridgeless cubic planar graphs is asymptotically $cgamma^n$, where $c>0$ and $gamma sim 1.14196$ is an explicit algebraic number. We also compute the expected number of perfect matchings in (non necessarily bridgeless) cubic planar graphs and provide lower bounds for unlabeled graphs. Our starting point is a correspondence between counting perfect matchings in rooted cubic planar maps and the partition function of the Ising model in rooted triangulations.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
