The time is now - Spring classes are filling up!

MIT PRIMES/Art of Problem Solving

CROWDMATH 2021: Extremal combinatorics

G
Topic
First Poster
Last Poster
The $u$-free process on sequences
JGeneson   27
N Dec 20, 2021 by PiGuy3141592
Consider the following process:

Fix a sequence $u$ with $r$ distinct letters. Let $S_0 = [ ]$ (the empty sequence).

1. For $i > 0$, we uniformly at random select a letter $\ell$ from $a_1, \dots, a_n$ (each with probability $1/n$).

2. Let $T$ be the sequence obtained from $S_{i-1}$ by addending the letter $\ell$.

3. If $T$ does not contain $u$ and the last $r$ letters of $T$ are all distinct, let $S_{i} = T$ and increment $i$ and go back to 1. Otherwise, let $S_i = S_{i-1}$ and increment $i$ and go back to 1. (Note: the definition of containment here is the same as on the problem/resource pages.)

Eventually, this process produces a sequence for which it is impossible to add any more letters to the end without forcing containment of $u$ or a repeated letter among the last $r$, so $S_i$ is constant after a certain point.

Define $Fr(u, n)$ to be the expected length of the sequence that we obtain using the above process.

The problem is to find $Fr(u,n)$ for all sequences $u$.

Some (possibly?) easier $u$ to start with:
$u = aa$, $u = aaa$, $u = aaaa$, $\dots$

$u = a b$, $u = a b c$, $u = a b c d$, $\dots$

$u = a b a$, $u = a b a b$, $u = a b a b a$, $\dots$

and any other nice sequences $u$ that you can think of.

Is there an algorithm to calculate $Fr(u,n)$ in general?

This problem is an analogue of the $H$-free process on graphs: see e.g. https://arxiv.org/abs/0908.0429
27 replies
JGeneson
Mar 5, 2021
PiGuy3141592
Dec 20, 2021
Symmetric versions of $u$-free process on sequence
parityhome   0
Jun 8, 2021
I don't mean to add more versions of $Fr$ just for fun. The motivation is to make $Fr$ more symmetric. For example, we know that $Fr(aab, n)$ and $Fr(abb, n)$ are quite different.

One version is $Fb$, where b stands for Bidirectional, and in the process we are allowed to insert a symbol to the beginning of the sequence as long as $u$ is avoided and the required sparsity is still preserved.

Another version is $Fi$, where i stands for Insertion: we can insert any symbol anywhere with the same constraints.

Both these versions can have variant that only respects sparsity, and the process terminates whenever $u$ is present.
0 replies
parityhome
Jun 8, 2021
0 replies
No more topics!
a