Y by Mango247
Consider the following process:
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
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
This post has been edited 2 times. Last edited by JGeneson, Mar 31, 2021, 2:12 AM