Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userPeriodic words, common subsequences and frogs
355
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Let $W^{(n)}$ be the $n$-letter word obtained by repeating a fixed word $W$, and let $R_n$ be a random $n$-letter word over the same alphabet. We show several results about the length of the longest common subsequence (LCS) between $W^{(n)}$ and $R_n$; in particular, we show that its expectation is $gamma_W n-O(sqrt{n})$ for an efficiently-computable constant $gamma_W$. This is done by relating the problem to a new interacting particle system, which we dub frog dynamics. In this system, the particles (`frogs) hop over one another in the order given by their labels. Stripped of the labeling, the frog dynamics reduces to a variant of the PushTASEP. In the special case when all symbols of $W$ are distinct, we obtain an explicit formula for the constant $gamma_W$ and a closed-form expression for the stationary distribution of the associated frog dynamics. In addition, we propose new conjectures about the asymptotic of the LCS of a pair of random words. These conjectures are informed by computer experiments using a new heuristic algorithm to compute the LCS. Through our computations, we found periodic words that are more random-like than a random word, as measured by the LCS.
rate research
Read More
We consider the expected length of the longest common subsequence between two random words of lengths $n$ and $(1-varepsilon)kn$ over $k$-symbol alphabet. It is well-known that this quantity is asymptotic to $gamma_{k,varepsilon} n$ for some constant $gamma_{k,varepsilon}$. We show that $gamma_{k,varepsilon}$ is of the order $1-cvarepsilon^2$ uniformly in $k$ and $varepsilon$. In addition, for large $k$, we give evidence that $gamma_{k,varepsilon}$ approaches $1-tfrac{1}{4}varepsilon^2$, and prove a matching lower bound.
Let $X=(X_i)_{ige 1}$ and $Y=(Y_i)_{ige 1}$ be two sequences of independent and identically distributed (iid) random variables taking their values, uniformly, in a common totally ordered finite alphabet. Let LCI$_n$ be the length of the longest common and (weakly) increasing subsequence of $X_1cdots X_n$ and $Y_1cdots Y_n$. As $n$ grows without bound, and when properly centered and normalized, LCI$_n$ is shown to converge, in distribution, towards a Brownian functional that we identify.
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.
We consider a Markov chain that iteratively generates a sequence of random finite words in such a way that the $n^{mathrm{th}}$ word is uniformly distributed over the set of words of length $2n$ in which $n$ letters are $a$ and $n$ letters are $b$: at each step an $a$ and a $b$ are shuffled in uniformly at random among the letters of the current word. We obtain a concrete characterization of the Doob-Martin boundary of this Markov chain. Writing $N(u)$ for the number of letters $a$ (equivalently, $b$) in the finite word $u$, we show that a sequence $(u_n)_{n in mathbb{N}}$ of finite words converges to a point in the boundary if, for an arbitrary word $v$, there is convergence as $n$ tends to infinity of the probability that the selection of $N(v)$ letters $a$ and $N(v)$ letters $b$ uniformly at random from $u_n$ and maintaining their relative order results in $v$. We exhibit a bijective correspondence between the points in the boundary and ergodic random total orders on the set ${a_1, b_1, a_2, b_2, ldots }$ that have distributions which are separately invariant under finite permutations of the indices of the $a$s and those of the $b$s. We establish a further bijective correspondence between the set of such random total orders and the set of pairs $(mu, u)$ of diffuse probability measures on $[0,1]$ such that $frac{1}{2}(mu+ u)$ is Lebesgue measure: the restriction of the random total order to ${a_1, b_1, ldots, a_n, b_n}$ is obtained by taking $X_1, ldots, X_n$ (resp. $Y_1, ldots, Y_n$) i.i.d. with common distribution $mu$ (resp. $ u$), letting $(Z_1, ldots, Z_{2n})$ be ${X_1, Y_1, ldots, X_n, Y_n}$ in increasing order, and declaring that the $k^{mathrm{th}}$ smallest element in the restricted total order is $a_i$ (resp. $b_j$) if $Z_k = X_i$ (resp. $Z_k = Y_j$).
A two-type version of the frog model on $mathbb{Z}^d$ is formulated, where active type $i$ particles move according to lazy random walks with probability $p_i$ of jumping in each time step ($i=1,2$). Each site is independently assigned a random number of particles. At time 0, the particles at the origin are activated and assigned type 1 and the particles at one other site are activated and assigned type 2, while all other particles are sleeping. When an active type $i$ particle moves to a new site, any sleeping particles there are activated and assigned type $i$, with an arbitrary tie-breaker deciding the type if the site is hit by particles of both types in the same time step. We show that the event $G_i$ that type $i$ activates infinitely many particles has positive probability for all $p_1,p_2in(0,1]$ ($i=1,2$). Furthermore, if $p_1=p_2$, then the types can coexist in the sense that $mathbb{P}(G_1cap G_2)>0$. We also formulate several open problems. For instance, we conjecture that, when the initial number of particles per site has a heavy tail, the types can coexist also when $p_1 eq p_2$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
