13 problems

Let $X$ and $Y$ be independent identically distributed symmetric Bernoulli sequences, and let $\ell_n$ denote the length of their longest common subsequence among the first $n$ sym…

Let $L_n$ be the length of the longest common subsequence of two random sequences. Waterman's conjecture. The variance grows linearly: … This conjecture addresses the order of fluc…

Let $k\geq 2$ be fixed, and suppose that as $\varepsilon\to 0$ the constant $\gamma_{k,\varepsilon}$ has an expansion involving a coefficient $\gamma_k'$ of $\varepsilon^2$, namely…

Let $V$ and $W$ be independent random words of length $2n$, written as concatenations $V=V_1V_2$ and $W=W_1W_2$, where each component has length $n$. Define … and write…

Let $\Sigma$ be a finite alphabet, and let $V,W\sim\Sigma^n$ be independent random words of equal length $n$. Suppose $\operatorname{LCS}(V,W)=\ell$, and let … be a common subseque…

Let $\mathfrak{S}_n$ be the symmetric group on $\{1,\dots,n\}$. For each $n\geq 1$, let $\sigma_{1,n}$ and $\sigma_{2,n}$ be independent identically distributed random permutations…

Let $c_k$ denote the Chvátal–Sankoff constant, defined as the limiting normalized length of the longest common subsequence of two independent random words of length $n$ over a $k$-…

Let $LC_n$ denote the length of the longest common subsequence of two random sequences of length $n$ in the experiments described, with the symbol distributions varying as specifie…

Let $[n]=\{1,2,\ldots,n\}$. Consider two independent identically distributed random permutations of $[n]$, and let their longest common subsequence have length whose expectation is…

For the longest common subsequences of two random words, let $g$ be the shape function and let $\kappa$ be its curvature power at $(1,1)$. Curvature power conjecture. The curvature…

Let $E_n$ be the conditional expected score change produced by the random transformation $\mathcal{R}$ used in the proof of A3, namely … Here $Z$ is a Markov chain, and the source…

Let $L_n$ be the optimal alignment score of two random sequences, and let $\operatorname{Var}(L_n)$ denote its variance. Write $\mathcal{N}(0,1)$ for the standard centered normal d…

Upper-bound conjecture. The function $\psi^{\ast}$ is an upper bound for $\psi$.