Fix a sequence with distinct letters. Let (the empty sequence).
1. For , we uniformly at random select a letter from (each with probability ).
2. Let be the sequence obtained from by addending the letter .
3. If does not contain and the last letters of are all distinct, let and increment and go back to 1. Otherwise, let and increment 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 or a repeated letter among the last , so is constant after a certain point.
Define to be the expected length of the sequence that we obtain using the above process.
The problem is to find for all sequences .
Some (possibly?) easier to start with: ,,,
,,,
,,,
and any other nice sequences that you can think of.
Is there an algorithm to calculate in general?
This problem is an analogue of the -free process on graphs: see e.g. https://arxiv.org/abs/0908.0429
Symmetric versions of $u$-free process on sequence
parityhome0
Jun 8, 2021
I don't mean to add more versions of just for fun. The motivation is to make more symmetric. For example, we know that and are quite different.
One version is , 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 is avoided and the required sparsity is still preserved.
Another version is , 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 is present.