11 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 $(\omega_n)$ be a $p$-Bernoulli sequence of $2$ or $3$, meaning that the $\omega_n$ are independent and satisfy $P(\omega_n=2)=p=1-P(\omega_n=3)$ for fixed $0<p<1$. Consider th…

Consider the generalized Ulam–Kac adder … where $\gamma$ is the parameter in the source's generalized recurrence. Let $c_m$ denote the corresponding moment-growth constants, and le…

Let $(X_n)_{n\geq 0}$ be the Ulam–Kac adder sequence, and write $f(n)\sim g(n)$ when $\lim_{n\to\infty}f(n)/g(n)=1$. For each positive integer $m$, let $c_m$ denote the constant go…

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…

Square-root growth conjecture. For random sequences $\mathcal{S}$ over $\mathbb{F}_q$, the expansion complexity $E_N(\mathcal{S})$ has exact order of magnitude $N^{1/2}$ as…

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…

Consider the max-$2$ process and the min-$2$ process on the unit circle, each starting from finitely many distinct points in an arbitrary configuration. At each step, sample two po…

Let $\mathcal{G}$ be an infinite graph with uniformly bounded degree, and let $p_c^{\mathcal{G}}$ denote its critical threshold for site percolation. Let $p\in(0,1)$ and let $\mu$…

Let $(X_t)_{t\in\mathbb Z}$ be independent identically distributed random variables with a continuous distribution function. Declare $n$ to be a maximum point when…