# Long twins in random words

Andrzej Dudek  Department of Mathematics, Western Michigan University,
Kalamazoo, MI, USA<EMAIL_ADDRESS>,  Jarosław Grytczuk  Faculty of
Mathematics and Information Science, Warsaw University of Technology, Warsaw,
Poland<EMAIL_ADDRESS>and  Andrzej Ruciński  Department of
Discrete Mathematics, Adam Mickiewicz University, Poznań, Poland
<EMAIL_ADDRESS>
###### Abstract.

_Twins_ in a finite word are formed by a pair of identical subwords placed at
disjoint sets of positions. We investigate the maximum length of twins in _a
random_ word over a $k$-letter alphabet. The obtained lower bounds for small
values of $k$ significantly improve the best estimates known in the
deterministic case.

Bukh and Zhou in 2016 showed that every ternary word of length $n$ contains
twins of length at least $0.34n$. Our main result, with a computer-assisted
proof, states that in a random ternary word of length $n$, with high
probability, one can find twins of length at least $0.41n$. In the general
case of alphabets of size $k\geq 3$ we obtain analogous lower bounds of the
form $\frac{1.64}{k+1}n$ which are better than the known deterministic bounds
for $k\leq 354$. In addition, we present similar results for _multiple_ twins
in random words.

The first author was supported in part by Simons Foundation Grant #522400.

The second author was supported in part by Narodowe Centrum Nauki, grant
2020/37/B/ST1/03298.

The third author was supported in part by Narodowe Centrum Nauki, grant
2018/29/B/ST1/00426

##  1\. Introduction

Looking for twin objects in mathematical structures is a natural trend
originating in some ancient geometric dissection puzzles. Amusing as they are,
problems of this nature can lead to pretty surprising observations like, for
instance, the Bolyai-Gerwien theorem, stating that any two polygons with the
same area can be dissected into a finite number of pieces that can be matched
into congruent pairs, or the Banach-Tarski paradox, asserting that a similar
property holds for any pair of solids in the $3$-dimensional space (regardless
of their size) (see, e.g., [30]).

Analogous properties can be considered for discrete structures as well. For
instance, Ulam (see, e.g., [8]) proposed to measure the degree of similarity
of two graphs in terms of their edge decompositions into pairwise isomorphic
subgraphs. If the number of subgraphs in a decomposition is small, then there
must be a large pair among them, which leads to the following general
question: given a combinatorial structure (or a pair of structures), how large
disjoint isomorphic substructures does it (do they) contain?

In this paper we study this question for random words. To put our work in a
broader perspective, we briefly discuss a couple of similar problems and
results for graphs and permutations (see [3] for further examples).

###  1.1. Twins in graphs and permutations

The first problem we would like to mention is to find two large isomorphic
subgraphs in a given graph. Let $f(m)$ denote the largest integer $k$ such
that every graph with $m$ edges contains a pair of twins, that is, two edge-
disjoint isomorphic subgraphs with $k$ edges each. The problem was stated
independently by Jacobson and Schönheim (see [12]). Currently, the best
general result, due to Lee, Loh, and Sudakov [23], states that
$f(m)=\Theta((m\log m)^{2/3})$. In [1], Alon, Caro, and Krasikov proved that
every tree with $m$ edges contains a pair of twins of (asymptotically optimal)
size $m/2-o(m)$.

Similar questions were studied for permutations, with the notion of twins
based on the relative order of the elements, that is, twins are formed by two
subsequences which are order-isomorphic. The length of the longest twins
guaranteed in every permutation of order $n$ has been proved to be
$\Omega(n^{3/5})$ [6] and $O(n^{2/3})$ [15]. Moreover, for random
permutations, with high probability the length of the longest twins is
$\Theta(n^{2/3})$ [6, 10].

There is also a weaker notion of twins in permutations where similarity is
claimed whenever only _neighboring_ elements preserve the order. In this case
one may expect longer twins and, indeed, it was proved in [11] that the length
of the longest _weak_ twins guaranteed in every permutation falls between
$n/12$ and $n-O(n^{1/3})$. It is conjectured in [11] that, in fact, it is
$n/2-o(n)$.

###  1.2. Twins in words: history and background

Axenovich, Person, and Puzynina [4] were the first to study twins in words. We
say that a word $w=w_{1}w_{2}\cdots w_{n}\in A^{n}$, $|A|<\infty$, contains
_twins_ of _length $t$_ if there exist _disjoint_ subsets
$\\{i_{1}<i_{2}<\cdots<i_{t}\\}$ and $\\{j_{1}<j_{2}<\cdots<j_{t}\\}$ of
indices such that $w_{i_{1}}w_{i_{2}}\cdots w_{i_{t}}=w_{j_{1}}w_{j_{2}}\cdots
w_{j_{t}}$. Let $t(w)$ denote the maximum length of twins in $w$ and let
$t(n,k)$ denote the minimum of $t(w)$ over all words $w$ of length $n$ over a
$k$-element alphabet $A$. They proved in [4] that $t(n,2)=n/2-o(n)$. In other
words, every finite binary word can be split into a pair of identical
subwords, up to an asymptotically negligible remainder. To get this striking
result they developed a regularity lemma for words – an interesting tool with
a great potential for further applications (see, e.g., [18]).

At present, it is not known whether the same is true for larger alphabets. By
considering the sub-word formed by two most frequent letters, the above
mentioned estimate $t(n,2)=n/2-o(n)$ from [4] implies that $t(n,k)\geq
n/k-o(n)$. For $k\geq 3$, this was slightly improved by Bukh and Zhou [7] to

$t(n,k)\geq 1.02\cdot\frac{n}{k}-o(n)$ (1.1)

and to

$t(n,k)\geq\left(\frac{k}{81}\right)^{1/3}\cdot\frac{n}{k}-(k/3)^{1/3},$ (1.2)

the latter being a (much) better estimate for larger $k$. In [4] and [7] there
are also some upper bounds on $t(n,k)$ valid for $k\geq 4$. In particular,
$t(n,4)\leq 0.4932n$.

Twins in _random_ words were not much studied before, although the proofs of
the upper bounds in [4] and [7] were obtained via the probabilistic method.
The only work addressing this issue directly is a recent paper by He, Huang,
Nam, and Thaper [19], where it is proved that, with high probability, binary
words of length contain twins of size $n/2-\omega\sqrt{n}$, for any function
$\omega=\omega(n)$ tending to infinity with $n$. Moreover, the authors of [19]
formulate a striking conjecture that almost every binary word with even
numbers of ones and zeros is a shuffle square. If true, this would imply that,
with high probability, a random binary word of an _even_ length $n$ contains
twins of size at least $n/2-1$ (when the number of ones is odd, this is the
best one can get).

Another interesting problem, whose connection to twins in random words was
noticed and utilized in [7], was raised by Chvátal and Sankoff in 1975 [9]:
what is the expected length of the _longest common subsequence_ in a pair of
random words of length $n$ over an alphabet with $k$ letters? Denoting this
quantity by $f_{k}(n)$, they observed that, for every fixed $k\geq 2$, the
sequence $f_{k}(n)/n$ is convergent and asked for determination of the limit
$\gamma_{k}:=\lim_{n\to\infty}\frac{f_{k}(n)}{n}$. The problem appeared to be
quite challenging and, despite quite an effort (see, e.g., [5]), none of the
constants $\gamma_{k}$ is known exactly at present. One spectacular result was
obtained by Kiwi, Loebl, and Matoušek [22], who proved that
$\lim_{k\to\infty}\gamma_{k}\sqrt{k}=2$, confirming thereby a conjecture of
Sankoff and Mainville (see [28]) and some earlier speculations on a mysterious
relation with another celebrated problem concerning the _longest increasing
subsequence_ in a random permutation (see [22]).

###  1.3. Our results

In this paper we study twins in a _random word_ $W_{k}(n)$ obtained by drawing
one with probability $k^{-n}$ out of all $k$-ary words of length $n$.
Equivalently, one could toss a $k$-sided fair die, independently, $n$ times.
Either way, this is an equiprobable space.

Our main result improves the lower bound (1.1) for all but very few ternary
($k=3)$ words of length $n$.

######  Theorem 1.1.

With probability $1-e^{-\Omega(n/(\log n))}$,

$t(W_{3}(n))\geq 0.411n.$

The proof involves computer-assisted calculations. It seems plausible that
substantially stronger computational devices could bring further improvements
of the bound. For computer-skeptical readers we have a ‘cheap substitute’, a
bound of only $0.375n$ proved by classical methods (cf. Example 3.8 in
Subsection 3.4).

For larger alphabets we have the following result. We present it in a form
which emphasizes the improvement over the deterministic bound (1.1). We say
that an event $\mathcal{E}_{n}$ holds _asymptotically almost surely (a.a.s.)_
if $\Pr(\mathcal{E}_{n})\to 1$ as $n\to\infty$.

######  Theorem 1.2.

For each $k\geq 3$ and large $n$, a.a.s.

$t(W_{k}(n))\geq\frac{1.64k}{k+1}\cdot\frac{n}{k},$

This gives an improvement upon the (deterministic) estimates (1.1) and, for
all $k\leq 354$, upon (1.2) (see Table 1).

$k$ | 3 | 4 | 5 | 10 | 50 | 100 | 200 | 400
---|---|---|---|---|---|---|---|---
$\left(\frac{k}{81}\right)^{1/3}$ | 0.333 | 0.367 | 0.395 | 0.498 | 0.851 | 1.073 | 1.352 | 1.703
$\frac{1.64k}{k+1}$ | 1.230 | 1.312 | 1.367 | 1.491 | 1.608 | 1.624 | 1.632 | 1.636
Table 1. Comparing bound (1.2) of Bukh and Zhou [7] with Theorem 1.2.

The proof uses a tool called the Boosting Lemma (Lemma 3.4). It is stated in
terms of a special model of random words which allows for iterative
enhancement of the twin length, while adding a new letter to the alphabet.
This new model assumes that the numbers of occurrences of letters are fixed in
such a way that the model is asymptotically equivalent to $W_{k}(n)$.

###  1.4. Multiple twins

We also consider a more general notion of _multiple_ twins. By _$r$ -twins_ in
a word $w$ we mean $r$ disjoint identical subwords of $w$. Let $t^{(r)}(w)$ be
the maximum length of $r$-twins in $w$ and let $t^{(r)}(n,k)$ be the minimum
of $t^{(r)}(w)$ over all words $w$ of length $n$ from a $k$-letter alphabet.
By the results of [4] and [7] we know, respectively, that $t^{(r)}(n,k)\sim
n/r$ when $r\geq k$, and

$t^{(r)}(n,k)\geq C_{r}\cdot k^{1/\binom{2r-1}{r}}\cdot\frac{n}{k}-O(1),$
(1.3)

for $k>r\geq 3$, where
$C_{r}=\left(\frac{1}{2r-1}\right)^{1+1/\binom{2r-1}{r}}$ and the $O(1)$ term
depends on $r$ and $k$ only. Estimate (1.3) was only mentioned in the
concluding remarks in [7] and the explicit form of $C_{r}$ was not given.
However, based on the proof of inequality (1.2) therein, it is quite obvious
how it should be computed.

For a random word $W_{k}(n)$ we get the following estimates which, again, for
small $r$ and $k$ yield better lower bounds than (1.3) (see Table 2). For
$r,k\geq 2$, let $\Pi_{r,k}=\prod_{j=r+1}^{k}\frac{j^{r}}{j^{r}-1}$.

######  Theorem 1.3.

For every $k>r\geq 3$, a.a.s.

$t^{(r)}(W_{k}(n))\geq\Pi_{r,k}\cdot\frac{n}{k}-o(n).$

$(r,k)$ | $(3,4)$ | $(3,10)$ | $(3,100)$ | $(3,1000)$ | $(3,10^{10})$ | $(4,10^{10})$ | $(4,10^{40})$
---|---|---|---|---|---|---|---
$C_{r}\cdot k^{1/\binom{2r-1}{r}}$ | 0.196 | 0.214 | 1.036 | 0.340 | 1.703 | 0.261 | 1.878
$\Pi_{r,k}$ | 1.016 | 1.036 | 1.041 | 1.041 | 1.041 | 1.003 | 1.003
Table 2. Comparing bound (1.3) of Bukh and Zhou [7] with Theorem 1.3.

###  1.5. Organization

In the next section we prove Theorem 1.1. Section 3 begins with a short proof
of the known bound $t^{(r)}(n,k)\sim n/r$, $r\geq k$, for random words. We do
so for self-containment, as the proof in [4] (for _all_ words) is quite
involved. The next subsection contains a standard proof of an asymptotic
equivalence between $W_{k}(n)$ and another model of random words. Then comes
the crucial Boosting Lemma, while the last subsection of Section 3 brings
applications of the Boosting Lemma, among them short proofs of Theorems 1.2
and 1.3, the former utilizing also Theorem 1.1. The last section contains some
remarks and open problems, while the Appendix presents a Maple code used for
derivation of the data collected in Table 3, as well as a proof of a technical
estimate needed in Section 3.3.

##  2\. Computer assisted bound

In this section we prove Theorem 1.1.

###### Proof of Theorem 1.1.

Fix a positive integer $s$ and split the set of positions of a ternary random
word $W_{3}(n)$ into $m:=n/s$ segments of length $s$ (we assume $s|n$). For
$1\leq j\leq m$ and $1\leq t\leq\lfloor\frac{s}{2}\rfloor$, let $X^{j}_{t}$ be
the indicator random variable such that $X^{j}_{t}=1$ if the $j$-th segment of
a random word $W_{3}(n)$ contains twins of length $t$ but not $t+1$; otherwise
$X^{j}_{t}=0$. Furthermore, define $X_{t}:=\sum_{j=1}^{m}X^{j}_{t}$.

First we calculate the expected value of $X_{t}$. Let $\lambda_{t}$ count the
number of ternary words of length $s$ with twins of length $t$ but not $t+1$.
Clearly, $\sum_{t=1}^{\lfloor s/2\rfloor}\lambda_{t}=3^{s}$. In general,
finding (or even tightly approximating) $\lambda_{t}$ does not seem to be an
easy problem. However, for small $s$ one can use a computer program to
determine $\lambda_{s}$. In Table 3 we present all values of $\lambda_{t}$ for
all $6\leq s\leq 14$ and $1\leq t\leq\lfloor s/2\rfloor$ (see Appendix A for
more details). Since $X_{t}$ has the binomial distribution
$\mathrm{Bin}(m,\lambda_{t}/3^{s})$, its expectation is

${\mathds{E}}(X_{t})=\frac{\lambda_{t}}{3^{s}}m=\frac{\lambda_{t}}{s3^{s}}n.$

Moreover, a standard application of the Chernoff inequality (see, e.g., ineq.
(2.9) in [21]) together with the union bound yields that for all $1\leq j\leq
m$ and $1\leq t\leq\lfloor\frac{s}{2}\rfloor$, $X_{t}$ is highly concentrated
around its mean, i.e.,

$X_{t}=\frac{\lambda_{t}}{s3^{s}}(1+o(1))n$

with probability $1-e^{-\Omega(n/(\log n))}$.

To finish the proof of Theorem 1.1 we construct twins in $W_{3}(n)$ as
follows. Let, for each $1\leq j\leq m$, $A_{j}$ and $B_{j}$ be a pair of the
longest twins in the $j$-th segment. Observe that concatenating $A_{j}$ and
$B_{j}$ over all $m$ segments yields, a.a.s., twins $A_{1}A_{2}\dots A_{m}$
and $B_{1}B_{2}\dots B_{m}$ of length

$\sum_{t=1}^{\lfloor s/2\rfloor}tX_{t}=\sum_{t=1}^{\lfloor
s/2\rfloor}\frac{t\lambda_{t}}{s3^{s}}(1+o(1))n=\varrho_{s}(1+o(1))n,$

where

$\varrho_{s}:=\sum_{t=1}^{\lfloor s/2\rfloor}\frac{t\lambda_{t}}{s3^{s}}.$

From the last column of Table 3 we compute that

$\varrho_{14}=\frac{4\cdot 24\>\\!894+5\cdot 1\>\\!312\>\\!530+6\cdot
3\>\\!196\>\\!644+7\cdot 248\>\\!901}{14\cdot
3^{14}}=\frac{27\>\\!584\>\\!397}{66\>\\!961\>\\!566}>0.4119.$

This completes the proof. ∎

$s$ | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14
---|---|---|---|---|---|---|---|---|---
$\lambda_{1}$ | 42 | 6 |  | Zero
$\lambda_{2}$ | 594 | 1 086 | 822 | 288 | 42
$\lambda_{3}$ | 93 | 1 095 | 5 118 | 11 010 | 10 806 | 5 292 | 1 350 | 162 |
$\lambda_{4}$ |  | 621 | 8 385 | 43 776 | 106 032 | 123 750 | 75 810 | 24 894
$\lambda_{5}$ |  | 4 425 | 65 823 | 373 638 | 992 244 | 1 312 530
$\lambda_{6}$ | Zero | 32 703 | 526 107 | 3 196 644
$\lambda_{7}$ |  | 248 901
Table 3. The exact values fo $\lambda_{t}$ for all $6\leq s\leq 14$ and $1\leq
t\leq\lfloor s/2\rfloor$.

##  3\. General bounds

###  3.1. More twins than letters

It was shown in [4] that for all $r\geq k$

$t^{(r)}(n,k)\geq\frac{n}{r}-O\left(\left(\frac{\log\log n}{\log
n}\right)^{1/4}\right).$

For self-containment (and self-contentment) we insignificantly improve this
lower bound for _almost_ all words. The new bound holds with probability so
close to 1 that a passage to the alternative model employed in Subsection 3.4
is still possible.

To this end, let us recall the main observation in [4]: if there is a
partition of a $k$-word $w$ of length $n$ into $m$ segments $w_{1}w_{2}\cdots
w_{m}$ of sizes $N:=n/m$ (we assume $m|n$) and in each segment each letter
occurs at least $\mu$ times, then one can construct $r$-twins in $w$ via a
natural interlacing. Namely, Twin 1 consists of $\mu$ elements $a_{1}$ of
$w_{1}$, $\mu$ elements $a_{2}$ of $w_{a}$,…, $\mu$ elements $a_{k}$ of
$w_{k}$, followed by $\mu$ elements $a_{1}$ of $w_{r+1}$, $\mu$ elements
$a_{2}$ of $w_{r+2}$, and so on, for as long as there are still at least $r-1$
segments ahead. Twin 2 follows the same pattern except that it begins with
$\mu$ elements $a_{1}$ of $w_{2}$, that is, it is shifted by one segment with
respect to Twin 1. Then Twin 3 begins with $\mu$ elements $a_{1}$ of $w_{3}$,
etc.

This way all $r$ twins are disjoint and they use together $k\mu$ elements from
each segment except the first $k-1$ ones where the consumption gradually grows
from $\mu$ to $(k-1)\mu$, and, in the worst case, when $m=r-1\
(\\!\\!\\!\mod{r})$, the last $r-1$ ones, where the consumption declines from
$(k-1)\mu$ to $\mu$, leaving the last $r-k$ segments completely untouched. The
exact worst case count yields that together twins $T_{1},\dots,T_{r}$ cover at
least

$\left[m-(k-1)-(r-1)\right]k\mu+2\binom{k}{2}\mu=(m-r+1)k\mu$ (3.1)

elements of $w$.

The R-H-S of (3.1) is, given $m\to\infty$ as $n\to\infty$, very close to
$mk\mu$, which, in turn, will be close to $n$, provided $\mu\sim N/k$. To get
these relations, the authors of [4] developed a regularity lemma for words.
Here we are in a more comfortable situation as we are dealing with random
words. Therefore, a simple application of Chernoff’s bound yields the
following result.

######  Lemma 3.1.

For $r\geq k\geq 2$, with probability at least $1-O(n^{-k+1/3})$,

$t^{(r)}(W_{k}(n))=n/r-O\left(n^{2/3}\sqrt{\log n}\right).$

###### Proof.

Split the set of positions of $W_{k}(n)$ into $m:=n^{1/3}$ consecutive
segments of length $N:=n^{2/3}$. For $j=1,\dots,m$ and $i=1,\dots,k$, let
$X:=X_{i}^{j}$ be the number of elements $a_{i}$ in the $j$-th segment. Then
${\mathds{E}}X=N/k$ and, by Chernoff’s bound from [21], ineq. (2.6), we have

${\mathds{P}}(X\leq(1-\varepsilon){\mathds{E}}X)\leq n^{-k},$

where $\varepsilon=kn^{-1/3}\sqrt{2\log n}$. As we only have $km=O(n^{1/3})$
random variables $X_{i}^{j}$, with probability at least $1-O(n^{-k+1/3})$,
they all satisfy the opposite bound, that is, for all $j=1,\dots,m$ and
$i=1,\dots,k$,

$X_{i}^{j}\geq\mu:=(1-\varepsilon)n^{2/3}/k=n^{2/3}/k-O(n^{1/3}\sqrt{\log
n}).$

Upon applying (3.1) with this $\mu$, we conclude that the number of elements
uncovered by the $r$-twins is, indeed, at most
$n-(m-r+1)k\mu=O(n^{2/3}\sqrt{\log n})$. ∎

Notice that for $r=k=2$, the estimate for $t(W_{2}(n))$ in the lemma is
slightly weaker than the one from [19] mentioned in the introduction. However,
this fact does not affect our results, as all we really need in the proofs
(see Example 3.8 and the proof of Theorem 1.3) is an estimate
$t^{(r)}(W_{k}(n))=n/r-o(1)$. Besides, it is not clear how to generalize the
result from [19] to other values of $k$ and $r$.

###  3.2. Equivalence of models of random words

Guided by analogy to random graphs, we consider two basic models of random
words: the binomial and the fixed-letter-count model. Given positive integers
$k$ and $n$, an alphabet $A=\\{a_{1},\dots,a_{k}\\}$, and constants $0\leq
p_{1},\dots,p_{k}\leq 1$, where $p_{1}+\cdots+p_{k}=1$, the _binomial random
word_ $W(n;p_{1},\dots,p_{k})$ is a sequence of independent random variables
$(X_{1},\dots,X_{n})$, where for each $j=1,\dots,n$ and $i=1,\dots,k$ we have
${\mathds{P}}(X_{j}=a_{i})=p_{i}$. Here we are exclusively interested in the
special, equiprobable instance $W_{k}(n):=W(n;1/k,\dots,1/k)$.

As a technical tool rather than an object of genuine interest we also define
another model of a random word. Given integers $0\leq M_{1},\dots,M_{k}\leq
n$, where $M_{1}+\dots+M_{k}=n$, _the fixed-letter-count random word_
$W(n;M_{1},\dots,M_{k})$ is obtained by taking uniformly at random a
permutation (with repetitions) of $n$ elements, among which, $i=1,\dots,k$,
there are $M_{i}$ elements $a_{i}$. Thus, in the latter model, we restrict
ourselves to words with prescribed numbers of each letter and every such word
has the same probability $\binom{n}{M_{1},\dots,M_{k}}^{-1}$ to be chosen.

The asymptotic equivalence between the two models goes smoothly one way (from
fixed-letter-count to binomial), but to proceed the other way the models lack
monotonicity, so we are forced to recourse to an analog of Pittel’s inequality
(see, e.g., ineq. (1.6) in [21]) which bring, however, some limitations.

Let $Q$ be a property (subset) of words of length $n$ over alphabet $A$.
Although more general statements can be easily proved, we restrict ourselves
to the special case of the model $W_{k}(n)$ and also to limiting probabilities
equal to 1 only. The proofs follow those for random graphs (cf. Section 1.4 in
[21], in particular, proofs of Prop. 1.12 and of Pittel’s inequality (1.6)
therein) and rely on the law of total probability and the fact that the space
of $W_{k}(n)$ conditioned on $M_{i}$’s being the numbers of occurrences of the
elements $a_{i}\in A$, $i=1,\dots,k$, coincides with that of
$W(n;M_{1},\dots,M_{k})$.

######  Proposition 3.2.

If for all $M_{1},\dots,M_{k}$ such that $M_{1}+\cdots+M_{k}=n$ and
$M_{i}=n/k+O(\sqrt{n})$, $i=1,\dots,k$,
${\mathds{P}}(W(n;M_{1},\dots,M_{k})\in Q)\to 1$ as $n\to\infty$, then
${\mathds{P}}(W_{k}(n)\in Q)\to 1$ as $n\to\infty$.

###### Proof.

Let $C$ be a large constant and define (for each $n$)

${\mathcal{M}}_{C}=\\{(M_{1},\dots,M_{k}):M_{1}+\cdots+M_{k}=n\quad\mbox{and}\quad|M_{i}-n/k|\leq
C\sqrt{n}\\}.$

Let $(M^{*}_{1},\dots,M^{*}_{k})$ minimize
${\mathds{P}}(W(n;M_{1},\dots,M_{k})\in Q)$ over ${\mathcal{M}}_{C}$. Finally,
let $X_{i}$ be the number of occurrences of letter $a_{i}$ in $W_{k}(n)$. Note
that each $X_{i}$ has binomial distribution with expectation $n/k$ and
variance less than $n/k$. Then, by the law of total probability

${\mathds{P}}(W_{k}(n)\in Q)\geq{\mathds{P}}(W(n;M^{*}_{1},\dots,M^{*}_{k})\in
Q){\mathds{P}}((X_{1},\dots,X_{k})\in{\mathcal{M}}_{C}).$

By assumption, ${\mathds{P}}(W(n;M^{*}_{1},\dots,M^{*}_{k})\in Q)\to 1$ as
$n\to\infty$. By Chebyshev’s inequality applied together with the union bound,

${\mathds{P}}((X_{1},\dots,X_{k})\not\in{\mathcal{M}}_{C})\leq
k\frac{n/k}{C^{2}n}=C^{-2}.$

Thus, $\liminf_{n\to\infty}{\mathds{P}}(W_{k}(n)\in Q)\geq 1-C^{-2}$. As this
is true for every $C$, letting $C\to\infty$ yields
$\lim_{n\to\infty}{\mathds{P}}(W_{k}(n)\in Q)=1$. ∎

######  Proposition 3.3.

If ${\mathds{P}}(W_{k}(n)\in Q)=1-o(n^{-k/2})$ as $n\to\infty$, then for all
$M_{i}=n/k+\omega_{i}$, where $|\omega_{i}|\leq\sqrt{(n\log n)/(3k^{2})}$ and
$\sum_{i}\omega_{i}=0$, ${\mathds{P}}(W(n;M_{1},\dots,M_{k})\in Q)\to 1$ as
$n\to\infty$.

###### Proof.

Fix $M_{1},\dots,M_{k}$ as in the statement of the proposition. By the law of
total probability, we obtain

$\displaystyle{\mathds{P}}(W_{k}(n)\not\in Q)$
$\displaystyle=\sum_{M^{\prime}_{1},\dots,M^{\prime}_{k}}{\mathds{P}}(W(n;M^{\prime}_{1},\dots,M^{\prime}_{k})\not\in
Q)\binom{n}{M_{1}^{\prime},\dots,M^{\prime}_{k}}\frac{1}{k^{n}}$
$\displaystyle\geq{\mathds{P}}(W(n;M_{1},\dots,M_{k})\not\in
Q)\binom{n}{M_{1},\dots,M_{k}}\frac{1}{k^{n}},$

from which we get

${\mathds{P}}(W(n;M_{1},\dots,M_{k})\not\in
Q)\leq\frac{k^{n}}{\binom{n}{M_{1},\dots,M_{k}}}{\mathds{P}}(W_{k}(n)\not\in
Q).$

It remains to estimate the ratio $\frac{k^{n}}{\binom{n}{M_{1},\dots,M_{k}}}$.
Using Stirling’s formula several times, we get

$\frac{k^{n}}{\binom{n}{M_{1},\dots,M_{k}}}=O(n^{(k-1)/2})\prod_{i=1}^{k}(1+k\omega_{i}/n)^{M_{i}}\\\
\leq O(n^{(k-1)/2})\exp\left\\{\sum_{i=1}^{k}k\omega_{i}M_{i}/n\right\\}.$

Now since $M_{i}=n/k+\omega_{i}$ and $\sum_{i}\omega_{i}=0$, we get

$\sum_{i=1}^{k}k\omega_{i}M_{i}/n=\sum_{i=1}^{k}k\omega_{i}\left(\frac{1}{k}+\frac{\omega_{i}}{n}\right)=\sum_{i=1}^{k}\frac{k\omega_{i}^{2}}{n}\leq\frac{\log
n}{3}$

and so ${k^{n}}/{\binom{n}{M_{1},\dots,M_{k}}}=O(n^{k/2-1/6})$, which yields
that ${\mathds{P}}(W_{k}(n)\not\in Q)=o(1)$. ∎

###  3.3. Boosting Lemma

Fix $2\leq r\leq k$ and observe that if for all $n\geq n_{0}$ and some
$\lambda>0$, we have $t^{(r)}(n,k)\geq\lambda n$, then also, by dropping the
least frequent letter, $t^{(r)}(N,k+1)\geq\frac{\lambda k}{k+1}N$, provided
$N\geq\tfrac{k+1}{k}n_{0}$. In this section we show that for random words this
trivial bound can be improved if one considers the fixed-letter-count model.

To get a similar result for the binomial model $W_{k}(n)$ one has to switch
first to the fixed-letter-count model $W(n;M_{1},\dots,M_{k})$ and then back
to $W_{k+1}(N)$, the switches facilitated, respectively, by Propositions 3.3
and 3.2. The reason for switching is that the fixed-letter-count model can be
broken into two phases allowing the enlargement of the twins.

Indeed, let $M_{1},\dots,M_{k+1}$ be given such that
$\sum_{i=1}^{k+1}M_{i}=N$. We generate the random word
$W(N;M_{1},\dots,M_{k+1})$ by first permuting all $n:=M_{1}+\cdots+M_{k}$
letters from $A\smallsetminus\\{a_{k+1}\\}$ (Phase 1). This can be done in
precisely $\binom{n}{M_{1},\dots,M_{k}}$. Then we throw in the $M_{k+1}$
letters $a_{k+1}$ which can go anywhere between the previously distributed
letters (Phase 2). This can be done, by the formula for the number of ways to
allocate $M_{k+1}$ balls into $n+1$ bins, in $\binom{N}{M_{k+1}}$ ways. Note
that the product of these two numbers is, indeed,
$\binom{N}{M_{1},\dots,M_{k+1}}$ and that the outcome of Phase 1 is precisely
the random word $W(n;M_{1},\dots,M_{k})$.

######  Lemma 3.4 (Boosting Lemma).

For $2\leq r\leq k$ and $n$ sufficiently large, let a partition
$n=M_{1}+\cdots+M_{k}$ into nonnegative integers be given. If
$M_{k+1}=n/k+O(\sqrt{n})$ and, for some $\lambda=\lambda(n)>0$, a.a.s.
$t^{(r)}(W(n;M_{1},\dots,M_{k}))\geq\lambda n$, then a.a.s.

$t^{(r)}(W(N;M_{1},\dots,M_{k},M_{k+1}))\geq\left(1+\frac{1}{(k+1)^{r}-1}\right)\frac{\lambda
k}{k+1}N(1-o(1)),$

where $N=n+M_{k+1}$.

Note that the factor of $\frac{\lambda k}{k+1}N$ comes for free already after
Phase 1, so that the actual improvement sits in the parentheses. Also, notice
that

$\frac{n}{N}=\frac{k}{k+1}\left(1+O\left(\frac{1}{\sqrt{n}}\right)\right).$

In the proof of Lemma 3.4 we will need a technical estimate on a ratio of
binomial coefficients, the proof of which is deferred to Appendix B.

######  Fact 3.5.

Let $M=\Theta(N)$ and $\ell^{2}=o(N)$. Then,

$\frac{\binom{N-\ell}{M-\ell}}{\binom{N}{M}}=\left(\frac{M}{N}\right)^{\ell}\left(1+O\left(\frac{\ell^{2}}{N}\right)\right).$

###### Proof of Lemma 3.4.

We generate $W(N;M_{1},\dots,M_{k+1})$ in two rounds as described prior to the
statement of the lemma. Let $W^{\prime}$ be the outcome of round one, that is,
an instance of $W(n;M_{1},\dots,M_{k})$. Further, let $Q^{\prime}$ be the
event that $t^{(r)}(W(n;M_{1},\dots,M_{k}))\geq\lambda n$ and $Q$ – the
ultimate event that

$t^{(r)}(W(N;M_{1},\dots,M_{k},M_{k+1}))\geq\left(1+\frac{1}{(k+1)^{r}-1}\right)\frac{\lambda
k}{k+1}N(1-o(1)).$

By the law of total probability,

${\mathds{P}}(Q)=\sum_{W^{\prime}}{\mathds{P}}(Q|W^{\prime}){\mathds{P}}(W^{\prime})=\sum_{W^{\prime}\in
Q^{\prime}}{\mathds{P}}(Q|W^{\prime}){\mathds{P}}(W^{\prime})+o(1).$ (3.2)

We now focus on ${\mathds{P}}(Q|W^{\prime})$ with $W^{\prime}\in Q^{\prime}$,
that is, fixing an instance $W^{\prime}$ of round one with
$t^{(r)}(W)\geq\lambda n$, we are going to thoroughly investigate the outcome
of the second round. Fix $W^{\prime}=w_{1}\cdots w_{n}$ and $r$-twins
$T_{1},\dots,T_{r}$ therein of length $|T_{1}|=\cdots=|T_{r}|=\lambda n$ (we
may assume that $\lambda n$ is an integer). We treat the $n+1$ spaces before,
between, and after the letters of $W^{\prime}$ as bins and the $M_{k+1}$
letters $a_{k+1}$ as balls. Precisely, bin $b_{0}$ is in front of $w_{1}$, for
$i=1,\dots,n-1$, bin $b_{i}$ lies between $w_{i}$ and $w_{i+1}$, and bin
$b_{n}$ is to the right of $w_{n}$.

We group the bins lying immediately to the right of the elements of the
$r$-wins $T_{1},\dots,T_{r}$ into _$r$ -tuples of bins_ denoted by
$R_{1},\dots,R_{\lambda n}$. Formally, if $T_{j}=w_{i_{1}}^{(j)}\cdots
w_{i_{\lambda n}}^{(j)}$, $j=1,\dots,r$, then the $r$-tuple of bins $R_{\ell}$
consists of the bins $b_{i_{\ell}}^{(1)},\dots,b_{i_{\ell}}^{(r)}$, for
$\ell=1,\dots,\lambda n$.

######  Example 3.6.

Let $k=r=3$, $n=27$, and

$W^{\prime}=w_{1}\cdots
w_{27}=b\;\hbox{\pagecolor{cyan}$a$}\;\hbox{\pagecolor{cyan}$a$}\;c\;\hbox{\pagecolor{Lavender}$a$}\;c\;b\;\hbox{\pagecolor{cyan}$b$}\;\hbox{\pagecolor{Lavender}$a$}\;\hbox{\pagecolor{Lavender}$b$}\;\hbox{\pagecolor{cyan}$c$}\;\hbox{\pagecolor{green}$a$}\;\hbox{\pagecolor{Lavender}$c$}\;a\;c\;\hbox{\pagecolor{green}$a$}\;b\;b\;\hbox{\pagecolor{cyan}$c$}\;\hbox{\pagecolor{green}$b$}\;a\;\hbox{\pagecolor{green}$c$}\;\hbox{\pagecolor{Lavender}$c$}\;\hbox{\pagecolor{green}$c$}\;b\;a\;b.$

There are 3-twins of length 5 here, each forming the word $aabcc$, namely,
$T_{1}=w_{2}w_{3}w_{8}w_{11}w_{19}$, $T_{2}=w_{5}w_{9}w_{10}w_{13}w_{23}$, and
$T_{3}=w_{12}w_{16}w_{20}w_{22}w_{24}$. For instance, consider the first
triple of bins, $R_{1}=\\{b_{2},b_{5},b_{12}\\}$. If the letter $d$ is
inserted into each of these three bins, a longer word

$b\;\hbox{\pagecolor{cyan}$a$}\;\underline{d}\;\hbox{\pagecolor{cyan}$a$}\;c\;\hbox{\pagecolor{Lavender}$a$}\;\underline{d}\;c\;b\;\hbox{\pagecolor{cyan}$b$}\;\hbox{\pagecolor{Lavender}$a$}\;\hbox{\pagecolor{Lavender}$b$}\;\hbox{\pagecolor{cyan}$c$}\;\hbox{\pagecolor{green}$a$}\;\underline{d}\;\hbox{\pagecolor{Lavender}$c$}\;a\;c\;\hbox{\pagecolor{green}$a$}\;b\;b\;\hbox{\pagecolor{cyan}$c$}\;\hbox{\pagecolor{green}$b$}\;a\;\hbox{\pagecolor{green}$c$}\;\hbox{\pagecolor{Lavender}$c$}\;\hbox{\pagecolor{green}$c$}\;b\;a\;b,$

is obtained, and the length of the twins, each forming now the word $adabcc$,
increases by one.

Clearly, if each bin from an $r$-tuple receives $s$ balls (read: $s$ letters
$a_{k+1}$), then the length of the twins can be extended by $s$. Since we
would like to utilize several $r$-tuples of bins simultaneously, we categorize
them with respect to the minimum number of balls.

For $1\leq s\leq\log n$, let $X_{s}$ be the number of $r$-tuples of bins with
at least $s$ balls in each bin and exactly $s$ balls in some bin (i.e. there
is a bin with exactly $s$ balls). We call each such $r$-tuple of bins an _$s$
-provider_. For each $\ell=1,\dots,\lambda n$, let $I_{\ell}$ be the indicator
random variable such that $I_{\ell}=1$ if $R_{\ell}$ is an $s$-provider and 0
otherwise. Hence, $X_{s}=\sum_{\ell=1}^{\lambda n}I_{\ell}$.

The event $\\{I_{\ell}=1\\}$ is the set difference of two events: that each
bin in ℓ has at least $s$ balls and that each bin in $R_{\ell}$ has at least
$s+1$ balls. Thus, setting $M:=M_{k+1}$,

${\mathds{P}}(I_{i}=1)=\frac{\binom{N-rs}{M-rs}}{\binom{N}{M}}-\frac{\binom{N-rs-r}{M-rs-r}}{\binom{N}{M}}$

and Fact 3.5 yields

$\displaystyle{\mathds{P}}(I_{i}=1)$
$\displaystyle=\left(\frac{M}{N}\right)^{rs}\left(1-\left(\frac{M}{N}\right)^{r}\right)\left(1+O\left(\frac{s^{2}}{N}\right)\right)$
$\displaystyle=\left(\frac{1}{k+1}\right)^{rs}\left(1-\left(\frac{1}{k+1}\right)^{r}\right)\left(1+O\left(\frac{1}{\sqrt{n}}\right)\right).$

Thus, setting $\kappa=(k+1)^{-r}$, we have ${\mathds{E}}X_{s}=\lambda
n(1-\kappa)\kappa^{s}\left(1+O\left(1/{\sqrt{n}}\right)\right)$.

Our goal is to show a.a.s. simultaneous concentration of each $X_{s}$,
$s\leq\log n$, near its expectation. We are going to use Chebyshev’s
inequality (followed by the union bound over all $s$)

${\mathds{P}}(|X_{s}-{\mathds{E}}X_{s}|\geq\gamma{\mathds{E}}X_{s})\leq\frac{VarX_{s}}{(\gamma{\mathds{E}}X_{s})^{2}}$

with $\gamma=1/\log n$. To facilitate the future use of the union bound, we
need to show that $VarX_{s}=o(({\mathds{E}}X_{s})^{2}/\log^{3}n)$, which will
imply that $\frac{VarX_{s}}{(\gamma{\mathds{E}}X_{s})^{2}}=o(1/\log n)$. To
this end we write

$VarX_{s}={\mathds{E}}(X_{s}(X_{s}-1))+{\mathds{E}}X_{s}-({\mathds{E}}X_{s})^{2}.$

Note that $\\{I_{\ell_{1}}=I_{\ell_{2}}=1\\}=A\smallsetminus(B_{1}\cup
B_{2})$, where $A$ is the event that all $2r$ bins in $R_{\ell_{1}}$ and
$R_{\ell_{2}}$ contain each at least $s$ balls, while $B_{i}$, $i=1,2$, is the
event that all bins in $R_{\ell_{i}}$ contain each at least $s$ ball and those
in $R_{\ell_{3-i}}$ – each at least $s+1$ balls. Thus

$\displaystyle{\mathds{P}}(I_{\ell_{1}}=I_{\ell_{2}}=1)$
$\displaystyle={\mathds{P}}(A)-{\mathds{P}}(B_{1})-{\mathds{P}}(B_{2})+{\mathds{P}}(B_{1}\cap
B_{2})$
$\displaystyle=\frac{\binom{N-2rs}{M-2rs}}{\binom{N}{M}}-2\frac{\binom{N-2rs-r}{M-2rs-r}}{\binom{N}{M}}+\frac{\binom{N-2rs-2r}{M-2rs-2r}}{\binom{N}{M}}$

which by Fact 3.5 is equal to

$\left(\kappa^{2s}-2\kappa^{2s+1}+\kappa^{2s+2}\right)\left(1+O\left(\frac{1}{\sqrt{n}}\right)\right)=\left((1-\kappa)\kappa^{s}\right)^{2}\left(1+O\left(\frac{1}{\sqrt{n}}\right)\right).$

Thus,

$\displaystyle VarX_{s}$ $\displaystyle=\lambda n(\lambda
n-1)\left((1-\kappa)\kappa^{s}\right)^{2}\left(1+O\left(\frac{1}{\sqrt{n}}\right)\right)$
$\displaystyle\qquad+\lambda
n(1-\kappa)\kappa^{s}\left(1+O\left(\frac{1}{\sqrt{n}}\right)\right)-\left(\lambda
n(1-\kappa)\kappa^{s}\left(1+O\left(\frac{1}{\sqrt{n}}\right)\right)\right)^{2}$
$\displaystyle=O(n^{3/2})=o(({\mathds{E}}X_{s})^{2}/\log^{3}n),$

with a big margin.

Hence,

$\sum_{s=1}^{\lfloor\log
n\rfloor}{\mathds{P}}(|X_{s}-{\mathds{E}}X_{s}|\geq\gamma{\mathds{E}}X_{s})=o(1),$

and, in particular, a.a.s., for all $1\leq s\leq\log n$,

$\displaystyle X_{s}$ $\displaystyle\geq{\mathds{E}}X_{s}\left(1-\frac{1}{\log
n}\right)$ $\displaystyle=\lambda
n(1-\kappa)\kappa^{s}\left(1+O\left(\frac{1}{\sqrt{n}}\right)\right)\left(1-\frac{1}{\log
n}\right)=\lambda n(1-\kappa)\kappa^{s}\left(1-O\left(\frac{1}{\log
n}\right)\right).$

As each $X_{s}$ contributes $s$ towards an enlargement of the twins
$T_{1},\dots,T_{r}$, we need to calculate $\sum_{s=1}^{\lfloor\log
n\rfloor}sX_{s}$. Since for every positive integer $p$

$\sum_{s=1}^{p}s\kappa^{s}=\sum_{s=1}^{\infty}s\kappa^{s}-\sum_{s=p+1}^{\infty}s\kappa^{s}=\frac{\kappa}{(1-\kappa)^{2}}-\frac{(1+(1-k)p)\kappa^{p+1}}{(1-\kappa)^{2}},$

we get

$\displaystyle\sum_{s=1}^{\lfloor\log n\rfloor}sX_{s}$
$\displaystyle\geq\lambda n(1-\kappa)\left(1-O\left(\frac{1}{\log
n}\right)\right)\sum_{s=1}^{\lfloor\log n\rfloor}s\kappa^{s}$
$\displaystyle=\lambda n(1-\kappa)\left(1-O\left(\frac{1}{\log
n}\right)\right)\left(\frac{\kappa}{(1-\kappa)^{2}}-\Theta(\kappa^{\log
n})\right)$
$\displaystyle=\frac{\lambda\kappa}{1-\kappa}n(1-o(1))=\frac{\lambda}{(1+k)^{r}-1}n(1-o(1)).$

Hence, still conditioning on $W^{\prime}$, a.a.s., there are in
$W(N;M_{1},\dots,M_{k},M_{k+1})$ twins of length at least

$\lambda
n+\frac{\lambda}{(1+k)^{r}-1}n(1-o(1))=\left(1+\frac{1}{(1+k)^{r}-1}\right)\lambda
n(1-o(1)).$

As $n=\frac{k}{k+1}N(1+o(1))$, this means that
${\mathds{P}}(Q|W^{\prime})=1-o(1)$ for every $W^{\prime}\in Q^{\prime}$, and,
by (3.2), the lemma follows. ∎

######  Remark 3.7.

By considering only one random variable $X$ counting $r$-tuples of bins with
no bin empty, the proof becomes a bit simpler, but the result is slightly
weaker: a.a.s.

$t^{(r)}(W(N;M_{1},\dots,M_{k},M_{k+1}))\geq\left(1+\frac{1}{(k+1)^{r}}\right)\frac{\lambda
k}{k+1}N.$

We get rid of $o(1)$, but lose $-1$ in the denominator, so overall the bound
is lower, though for large $k$ the difference is insignificant.

###  3.4. Applications

In this subsection we present applications of the Boosting Lemma (Lemma 3.4),
most importantly, in the proofs of Theorems 1.2 and 1.3. Each time the
scenario is the same: we pick an existing lower bound on the length of twins
in $W_{k^{\prime}}(n)$ (e.g., the bound in Theorem 1.1 above or any
deterministic result from [4] or [7]), translate it via Proposition 3.3 to the
fixed-letter-count model and then apply (iteratively) the Boosting Lemma to
get a bound, still in the fixed-letter-count model, for the targeted value of
$k>k^{\prime}$. At the end we go back to the binomial model $W_{k}(n)$ via
Proposition 3.2. For this we need to have our estimate valid for all $M_{i}$,
$i=1,\dots,k$, satisfying the assumptions of Proposition 3.2. This means,
however, that also the input bound has to be valid for a corresponding range
of $M_{i}$, $i=1,\dots,k^{\prime}$.

Let us now analyze what it really means. Fix $k$ and let $M_{i}=n/k+w_{i}$,
$i=1,\dots,k$, where $|w_{i}|=O(\sqrt{n})$ and $\sum_{i=1}^{k}w_{i}=0$. How
these assumptions alter when we drop $M_{k}$? Let
$n_{k-1}=M_{1}+\cdots+M_{k-1}$. Then, for each $i=1,\dots,k-1$,

$n_{k-1}=\frac{k-1}{k}n+\sum_{i=1}^{k-1}w_{i}=(k-1)M_{i}-(k-1)w_{i}-w_{k},$

thus

$M_{i}=\frac{n_{k-1}}{k-1}+w_{i}+\frac{w_{k}}{k-1}=\frac{n_{k-1}}{k-1}+w_{i}^{(k-1)},$

where $w_{i}^{(k-1)}=w_{i}+\frac{w_{k}}{k-1}$. Note that
$\sum_{i=1}^{k-1}w_{i}^{(k-1)}=0$ as it should. We may iterate this relation
all the way down to $k^{\prime}$ (where we want to begin the process of
applying Lemma 3.4), obtaining for $j=k-1,\dots,k^{\prime}$ and
$i=1,\dots,k^{\prime}$, with $n_{j}=M_{1}+\cdots+M_{j}$,

$M_{i}=\frac{n_{j}}{k}+w_{i}^{(j)},$ (3.3)

where

$w_{i}^{(j)}=w_{i}+\frac{1}{j}\sum_{q=j+1}^{k}w_{q}.$ (3.4)

Observe that $w_{i}^{(k^{\prime})}=O(\sqrt{n})$, so we stay within the range
required in Proposition 3.3. Below we illustrate how to apply the Boosting
Lemma.

######  Example 3.8.

Let $r=2$ and $k=3$. We know, either by our Lemma 3.1 or by the result in [4],
that a.a.s. a random binary word $W_{2}(n)$ contains twins of length
$\left(\tfrac{1}{2}-o(1)\right)n$. We would like to deduce from this, via
Lemma 3.4, a lower bound on the length of twins in the random ternary word
$W_{3}(n)$ (so, we take $k^{\prime}=2$ here).

Fix $M_{i}=n/3+w_{i}$, $i=1,2,3$, where $|w_{i}|=O(\sqrt{n})$ and
$w_{1}+w_{2}+w_{3}=0$. Suppressing $M_{3}$, we get, with $n^{\prime}=n-M_{3}$,
an instance of $W(n^{\prime};M_{1},M_{2})$ which satisfies the assumptions of
Proposition 3.3, that is, for $i=1,2$, we have
$M_{i}=n^{\prime}/2+w_{i}^{(2)}$, where
$w_{i}^{(2)}=w_{i}+\frac{w_{3}}{2}=O(\sqrt{n})$. Thus, we may conclude that
a.a.s. $t^{(2)}(W(n^{\prime};M_{1},M_{2}))\geq\lambda n^{\prime}$ with
$\lambda=\tfrac{1}{2}-o(1)$. In turn, by Lemma 3.4, a.a.s.

$t^{(2)}(W(n;M_{1},M_{2},M_{3}))\geq\left(1+\frac{1}{8}\right)\frac{2\lambda}{3}n(1-o(1))\geq
0.375n(1-o(1)).$

Since this is true for all choices of $M_{i}$ as above, by Proposition 3.2, we
finally get that a.a.s. $t^{(2)}(W_{3}(n))\geq 0.375n(1-o(1))$. This is much
less than the bound in Theorem 1.1, so the result has some value only for
computer-skeptical readers. On the other hand, it is still better than the
bound $t^{(2)}(W_{3}(n))\geq 0.34n(1-o(1))$ in (1.1), though the latter holds
for _all_ ternary words.

Continuing with this example, let us iterate applications of Lemma 3.4 till,
say, $k=10$. Skipping details, we see that the obtained bound is a.a.s.

$\displaystyle t^{(2)}(W_{10}(n))$
$\displaystyle\geq\frac{9}{8}\cdot\frac{16}{15}\cdot\frac{25}{24}\cdot\frac{36}{35}\cdot\frac{49}{48}\cdot\frac{64}{63}\cdot\frac{81}{80}\cdot\frac{100}{99}\cdot\frac{n}{10}(1+o(1))$
$\displaystyle=\frac{15}{11}\cdot\frac{n}{10}(1-o(1))=1.\overline{36}\cdot\frac{n}{10}(1-o(1)).$

It is perhaps interesting to compare the above bound with $1.337(n/10)$ – one
obtained by the simpler and weaker version of Lemma 3.4 mentioned in Remark
3.7.

###### Proof of Theorem 1.2.

As a starting point we take our computer-assisted Theorem 1.1, so we set
$k^{\prime}=3$. Preparing for the final transition to the binomial model, fix
any $M_{i}=n/k+w_{i}$, $i=1,\dots,k$, where $|w_{i}|=O(\sqrt{n})$ and
$\sum_{i=1}^{k}w_{i}=0$. By (3.3) with $j=3$, we then have
$M_{i}=n_{3}/3+w_{i}^{(3)}$, where $n_{3}=M_{1}+M_{2}+M_{3}$ and
$w_{i}^{(3)}=O(\sqrt{n})$, $i=1,2,3$, by (3.4).

By Theorem 1.1, $t(W_{3}(n))\geq 0.411n$ with probability at least
$1-e^{-\Omega(n/(\log n))}=1-o(n^{-k/2})$. Thus, by Proposition 3.3, a.a.s.
$t(W(n_{3};M_{1},M_{2},M_{3}))\geq 0.411n$, and, in turn, by Boosting Lemma
(Lemma 3.4) with $\lambda=0.411$, a.a.s.
$t(W(n_{4};M_{1},M_{2},M_{3},M_{4}))\geq\frac{16}{15}\cdot
1.233\cdot\frac{n_{4}}{4}$. We iterate this transition (or use induction)
until reaching the random word $W(n;M_{1},\dots,M_{k})$. Observe that

$\prod_{j=4}^{k}\frac{j^{2}}{j^{2}-1}=\prod_{j=4}^{k}\frac{j^{2}}{(j-1)(j+1)}=\frac{4^{2}}{3\cdot
5}\cdot\frac{5^{2}}{4\cdot 6}\cdot\frac{6^{2}}{5\cdot
7}\cdots\frac{k^{2}}{(k-1)(k+1)}=\frac{4k}{3(k+1)}.$

Hence, we get, a.a.s.,

$t^{(2)}(W(n;M_{1},\dots,M_{k}))\geq\prod_{j=4}^{k}\frac{j^{2}}{j^{2}-1}\cdot(3\varrho_{14})\cdot\frac{n}{k}(1-o(1))\geq\frac{1.64k}{k+1}\cdot\frac{n}{k}.$

(We drop $0.004$ to “kill” the error term $1-o(1)$.)

As this is true for all choices of $M_{i}=n/k+w_{i}$, we are in position to
apply Proposition 3.2 and conclude that a.a.s.
$t^{(2)}(W_{k}(n))\geq\frac{1.64k}{k+1}\cdot\frac{n}{k}.$ ∎

###### Proof of Theorem 1.3.

This proof is very similar except that we now take $k^{\prime}=r$ and launch
off with the bound $t^{(r)}(W_{k^{\prime}}(n))=n/r-o(n)$ from Lemma 3.1 (or
its deterministic counterpart from [4]). Other minor differences are that for
$r\geq 3$ there is no nice formula for the product
$\Pi_{r,k}=\prod_{j=r+1}^{k}\frac{j^{r}}{j^{r}-1}$ and, unlike before, we
cannot get rid of the error term $1-o(1)$. We omit the details. ∎

##  4\. Concluding remarks

Let us conclude the paper with some open questions and suggestions for future
studies. The first problem naturally concerns twins in ternary words.

######  Problem 4.1.

Does $t(n,3)=n/2-o(n)$?

Even if the answer is negative it can still be true that _almost all_ ternary
words contain twins of such length, that is, a.a.s. $t(W_{3}(n))=n/2-o(n)$. It
is known, as demonstrated in [7], that a.a.s. $t(W_{4}(n))\leq 0.4932n$ which
makes a similar statement for random _quaternary_ words false. In general, it
is not clear how close $t(W_{k}(n))$ and $t(n,k)$ are from each other.

######  Problem 4.2.

Does $t(W_{k}(n))=t(n,k)+o(n)$ hold a.a.s. for all $k\geq 2$?

By the result of Axenovich, Person, and Puzynina [4] we know that this is the
case for $k=2$.

One may also consider more restricted notions of twins in words reflecting
their placement in the word. For instance, it may happen that twins occupy
together a connected segment forming a _shuffle square_ , as in the example
below:

$a\;b\;\hbox{\pagecolor{cyan}c}\;\hbox{\pagecolor{cyan}a}\;\hbox{\pagecolor{Lavender}c}\;\hbox{\pagecolor{cyan}b}\;\hbox{\pagecolor{Lavender}a}\;\hbox{\pagecolor{Lavender}b}\;c\;b\;a\;c.$

As proved by Guégan and Ochem [17] (see also [16], [26]), there exist
arbitrarily long words over a $7$-letter alphabet containing no shuffle
squares. It is not known, however, if the size of the alphabet in this result
is optimal and, more generally, what is the maximum length of a shuffle square
guaranteed to be present in _every_ (long) $k$-letter word, $k=2,\dots,6$.

For random words, we formulate a question which is close in the spirit to the
Chvatal and Sankoff problem discussed in Section 1.2.

######  Problem 4.3.

What is the expected maximum length of a shuffle square in a random word
$W_{k}(n)$?

This question sounds particularly intriguing in the light of a recent
conjecture by He, Huang, Nam, and Thaper [19] (mentioned already in Section
1.2), that almost every binary word (with even numbers of ones and zeros) is a
shuffle square. For more on counting shuffle squares and their variants see,
e.g., [20]. Similar problems can also be considered for _shuffle cubes_ , or
more generally, for arbitrary _shuffle $r$-powers_, in analogy to general
$r$-twins.

Even more restricted version of twins is obtained when each twin in a shuffle
square occupies itself a connected segment, like in the example below:

$a\;b\;\hbox{\pagecolor{cyan}c}\;\hbox{\pagecolor{cyan}a}\;\hbox{\pagecolor{cyan}b}\;\hbox{\pagecolor{Lavender}c}\;\hbox{\pagecolor{Lavender}a}\;\hbox{\pagecolor{Lavender}b}\;c\;b\;a\;c.$

This basic structure is well-known and widely studied in combinatorics on
words under the name of a _square_ or a _repetition_ (see [24], [27]). By the
famous result of Thue [29] we know that there exist ternary words of any
length with no squares altogether. In the binary case, it is known that there
exist arbitrarily long words avoiding squares of length greater than $2$, as
proved by Fraenkel and Simpson [14]. However, not much is known about squares
in random words.

######  Problem 4.4.

What is the expected maximum length of a square in a random word $W_{k}(n)$?

Let us finely remark that many similar ideas are intensively studied in
molecular biology in connection to DNA sequence analysis (see [25], [31]). For
instance, in [2] Arratia and Waterman considered the maximum length $M_{n}$ of
common blocks (subsequences consisting of consecutive terms) in two random
binary words of length $n$. They proved that a.a.s. $M_{n}\sim 2\log_{1/p}n$,
where $p\in(0,1)$ is the probability of picking one of the two letters in the
alphabet. It is worth noticing that, accordingly to the classic Erdős-Rényi
law [13], this value is twice as big as the longest run of heads during $n$
tosses of a coin.

## References

  * [1] N. Alon, Y. Caro, I. Krasikov, Bisection of trees and sequences, in Combinatorics and Algorithms (Jerusalem, 1988). Discrete Mathematics, vol. 114, no. 1–3 (Amsterdam, North-Holland, 1993), pp. 3–7.
  * [2] R. Arratia, M. S. Waterman, An Erdős-Rényi Law with Shifts, Advances in Mathematics 55, (1985), 13–23.
  * [3] M. Axenovich, Repetitions in graphs and sequences, in Recent Trends in Combinatorics, Springer 2016.
  * [4] M. Axenovich, Y. Person, and S. Puzynina, A regularity lemma and twins in words, Journal of Combinatorial Theory. Series A 120 (2013), 733–743.
  * [5] R. Baeza-Yates, G. Navarro, R. Gavaldâ, and R. Schehing, Bounding the expected length of the longest common subsequences and forests, Theory Comput. Systems 32 (4) (1999) 435–452.
  * [6] B. Bukh and O. Rudenko, Order-isomorphic twins in permutations, SIAM J. Discrete Math. 34 (2020) 1620–1622.
  * [7] B. Bukh and L. Zhou, Twins in words and long common subsequences in permutations, Israel Journal of Mathematics 213 (2016), 183–209.
  * [8] F. R. K. Chung, P. Erdős, R. L. Graham, S. M. Ulam, and F. F. Yao, Minimal decompositions of two graphs into pairwise isomorphic subgraphs. Congr. Numer. 23 (1979) 3–18.
  * [9] V. Chvátal and D. Sankoff, Longest common subsequences of two random sequences, J. Appl. Probab. 12 (1975) 306–315.
  * [10] A. Dudek, J. Grytczuk, and A. Ruciński, Variations on twins in permutations, Electronic Journal of Combinatorics 28 (2021), no. 3, P3.19.
  * [11] A. Dudek, J. Grytczuk, and A. Ruciński, On weak twins and up-and-down subpermutations, Integers 21A (2021), Ron Graham Memorial Volume, Paper No. A10, 17 pp.
  * [12] P. Erdős, J. Pach, and L. Pyber, Isomorphic subgraphs in a graph, in Combinatorics (Eger, 1987). Colloquia Mathematica Societatis János Bolyai, vol. 52 (North-Holland, Amsterdam, 1988), pp. 553–556.
  * [13] P. Erdős and A. Rényi, On a new law of large numbers, J. Anal. Math. 22 (1970) 103–111.
  * [14] A. S. Fraenkel and R. J. Simpson, How Many Squares Must a Binary Sequence Contain?, Electronic Journal of Combinatorics 2 (1995) R2.
  * [15] M. Gawron, Izomorficzne podstruktury w słowach i permutacjach, Master Thesis, 2014.
  * [16] J. Grytczuk, J. Kozik and B. Zaleski, Avoiding tight twins in sequences via entropy compression, Institute Mittag-Leffler, REPORT No. 50, 2013/2014, spring.
  * [17] G. Guégan and P. Ochem, A short proof that shuffle squares are 7-avoidable. RAIRO Theor. Inform. Appl. 50(1) (2016) 101–103.
  * [18] H. Hàn, M. Kiwi, and M. Pavez-Signé, Quasi-random words and limits of word sequences, arXiv:2003.03664 [math.CO].
  * [19] X. He, E. Huang, I. Nam, and R. Thaper, Shuffle squares and reverse shuffle squares, arXiv:2109.12455 [math.CO].
  * [20] D. Henshall, N. Rampersad, and J. Shallit, Shuffling and Unshuffling, Bull. EATCS 107 (2012) 131–142.
  * [21] S. Janson, T. Łuczak, and A. Ruciński, _Random Graphs_ , John Wiley and Sons, 2000.
  * [22] M. Kiwi, M. Loebl, and J. Matoušek, Expected length of the longest common subsequence for large alphabets, Advances in Mathematics 197 (2005), 480–498.
  * [23] C. Lee, P. Loh, and B. Sudakov, Self-similarity of graphs. SIAM J. Discret. Math. 27(2) (2013) 959–972.
  * [24] M. Lothaire, Combinatorics on Words, Addison-Wesley, Reading, MA, 1983.
  * [25] M. Lothaire, Applied Combinatorics on Words, Encyclopedia of Mathematics and its Applications 105, Cambridge Univ. Press, 2005.
  * [26] ] P. Ochem, M. Rao, and M. Rosenfeld, Avoiding or limiting regularities in words, in: Sequences, Groups and Number Theory, Sept. 2018, pp. 177–212.
  * [27] N. Rampersad and J. Shallit, Repetitions in words, in V. Berthé and M. Rigo, eds., Combinatorics, Words and Symbolic Dynamics, Encyclopedia of Mathematics and Its Applications, vol. 159, Cambridge University Press, 2016, pp. 101–150.
  * [28] D. Sankoff and J. Kruskal (Eds.), Common Subsequences and Monotone Subsequences, Addison-Wesley, Reading, MA, 1983, pp. 363–365. (Chapter 17).
  * [29] A. Thue, Über unendliche Zeichenreichen, Norske vid. Selsk. Skr. Mat. Nat. Kl. 7 (1906), 1–22. Reprinted in Selected Mathematical Papers of Axel Thue, T. Nagell, editor, Universitetsforlaget, Oslo, 1977, pp. 139–158.
  * [30] G. Tomkowicz and S. Wagon, The Banach-Tarski Paradox, Encyclopedia of Mathematics and its Applications, Cambridge, 2016.
  * [31] M. S. Waterman, Introduction to Computational Biology, CRC Press, 1995.

##  Appendix A Maple code

Here we present a simple program written in _Maple_ that counts the number of
ternary words of length $s$ that contain twins of length at least $t$. This
easily allows to calculate the number of ternary words of length $s$ with
twins of length $t$ but not $t+1$ (defined as $\lambda_{t}$ in the proof of
Theorem 1.1). Indeed, $\lambda_{t}$ is equal to the difference between the
number of words having twins of length at least $t$ minus the one with twins
of length at least $t+1$.

For the sake of clarity, we did not attempt to optimize our program.

⬇

with(combinat): # Load combinatorial functions

##########################################################

# This procedure returns the number of ternary words

# of length s that contain twins of length at least t

##########################################################

count_twins := proc(s, t)

local P_list, P, sizeP, K, sizeK, L, sizeL, L1, L2, counter, p, k, l, i:

# Generate all ternary words of length s

P_list := [seq(1, i = 1 .. s), seq(2, i = 1 .. s), seq(3, i = 1 .. s)]:

P := permute(P_list, s):

sizeP := nops(P):

# Generate all 2t-subsets of {1,...,s}

K := choose([seq(i, i = 1 .. seq_length)], 2*t):

sizeK := nops(K):

# Partition {1,...,2t} into two sets, each of size t

L := setpartition([seq(i, i = 1 .. 2*t)], t):

sizeL := nops(L):

counter := 0: # Number of words with twins of length at least t

for p to sizeP # Over all ternary words

do

for k to sizeK # Over all 2t subsets of {1,...,s}

do

for l to sizeL # Over all partitions of {1,...,2t}

do

L1 := L[l][1]: # Indices for the first possible twin

L2 := L[l][2]: # Indices for the second possible twin

if evalb(P[p][K[k][L1]] = P[p][K[k][L2]]) # Twins?

then

# Twins found

counter := counter + 1:

# Move to the next word in P

l := sizeL: # Break the loop over l

k := sizeK: # Break the loop over k

end if:

end do: # Over l

end do: # Over k

end do: # Over p

counter: # Return the value of the variable counter

end proc:

Listing 1: The main procedure.

In Listing 2 we show how the procedure from Listing 1 can be used yielding
results summarized in Table 3.

⬇

seq_length := 6: # Length of the ternary words

min_twin_length := 1: # Min length of possible twins

max_twin_length := floor(seq_length/2): # Max length of possible twins

for i from max_twin_length by -1 to min_twin_length do

c[i] := count_twins(seq_length, i): # Number of twins of length >= i

if i = max_twin_length

then

d[i] := c[i]: # Since there are no twins of length max_twin_length+1,
c[max_twin_length] stores the number of words with the longest twins of length
max_twin_length

else

d[i] := c[i] - c[i + 1]:

end if:

printf("Number of words with the longest twins of length %d = %d\n", i, d[i]):

end do:

Listing 2: Calling the main procedure.

##  Appendix B Proof of Fact 3.5

###### Proof of Fact 3.5.

We are going to use the following form of Stirling’s formula:

$N!=\sqrt{2\pi
N}\left(\frac{N}{e}\right)^{N}\left(1+O\left(\frac{1}{N}\right)\right).$

Hence,

$\frac{N!}{(N-\ell)!}=\sqrt{\frac{N}{N-\ell}}\cdot\frac{N^{N}}{(N-\ell)^{N-\ell}}\cdot
e^{-\ell}\left(1+O\left(\frac{1}{N}\right)\right).$

Since

$\sqrt{\frac{N}{N-\ell}}=\left(1+\frac{\ell}{N-\ell}\right)^{1/2}=1+O\left(\frac{\ell}{N}\right),$

we get

$\frac{N!}{(N-\ell)!}=\frac{N^{N}}{(N-\ell)^{N-\ell}}\cdot
e^{-\ell}\left(1+O\left(\frac{\ell}{N}\right)\right).$

Consequently, as

$\frac{\binom{N-\ell}{M-\ell}}{\binom{N}{M}}=\frac{{M!}/{(M-\ell)!}}{{N!}/{(N-\ell)!}},$

we obtain

$\frac{\binom{N-\ell}{M-\ell}}{\binom{N}{M}}=\frac{{M^{M}}/{(M-\ell)^{M-\ell}}}{{N^{N}}/{(N-\ell)^{N-\ell}}}\left(1+O\left(\frac{\ell}{N}\right)\right).$

Further, since $1+x=e^{x+O(x^{2})}$ whenever $x\to 0$,

$\frac{{M^{M}}/{(M-\ell)^{M-\ell}}}{{N^{N}}/{(N-\ell)^{N-\ell}}}=\left(\frac{M}{N}\right)^{\ell}\frac{\left(1-\frac{\ell}{N}\right)^{N-\ell}}{\left(1-\frac{\ell}{M}\right)^{M-\ell}}=\left(\frac{M}{N}\right)^{\ell}\frac{e^{-\ell(N-\ell)/N+O(\ell^{2}/N)}}{e^{-\ell(M-\ell)/M+O(\ell^{2}/M)}}=\left(\frac{M}{N}\right)^{\ell}e^{O(\ell^{2}/N)},$

where the last equality follows, because
$-\ell(N-\ell)/N+\ell(M-\ell)/M=\ell^{2}(M-N)/(MN)$ and $M=\Theta(N)$.
Finally, as by assumption $\ell^{2}=o(N)$, we have
$e^{O(\ell^{2}/N)}=1+O(\ell^{2}/N)$ and so

$\frac{\binom{N-\ell}{M-\ell}}{\binom{N}{M}}=\left(\frac{M}{N}\right)^{\ell}\left(1+O\left(\frac{\ell^{2}}{N}\right)\right)\left(1+O\left(\frac{\ell}{N}\right)\right)=\left(\frac{M}{N}\right)^{\ell}\left(1+O\left(\frac{\ell^{2}}{N}\right)\right),$

as required. ∎