Imagine I have a string $s$ of length $L$ encoded over an alphabet of size $q$, e.g. $s = 000101$, where $L = 6$ & $q = 2$. For each of $T$ time intervals, $(t\_1, ..., t\_N) \in T$, I select a bit in the string with uniform probability, then randomly mutate or "flip" the bit to another of the $q$ characters in the alphabet (again selected with uniform probability). For example, at time $t\_i$ we might have $s\_{i} = 000000$ and at time $t\_{i+1}$ we might have $s\_{(i+1)} = 000100$ (or perhaps no change at all). 


My question is the following:


Provided some initial string state $s\_0$ for a string of length $L$, and the state of this string after $N$ time increments, $s\_N$, what probability distribution can we come up with for $N$? In other words, how well can one "tell time" by comparing the normal and mutated string, and can say anything quantitative?




---


In response to a comment by ARi asking for motivation - 


What I'm actually interested in here is a better understanding of how some entropy increasing process (here, the random bit flips) will slowly erase the initial state of a discrete physical system encoded along the length of some string $s$. How does one understand a "mixing time" for some Markov process in terms of the amount of information left about the system's original state? When are all initial states equal in terms of mixing time?


If my hand is forced, I suppose I could say that this system could be relevant to understanding the tradeoff between data storage and compression in a noisy environment. 



Keeping time by randomly drifting a $q$-ary string
$P(T = n) = \binom{L-1}{k-1} \sum\_{j=0}^{k-1} (-1)^j \binom{k - 1}{j} \left(\frac{k - j - 1}{L}\right)^{n-1}, \quad n \in \{k, k + 1, \ldots\}
$


k = $K(s\_f) - K(s\_0)$


Where K(s) is the Kolmogorov complexity of string s based on a particular description language;(the effect of changing languages is bounded ); Note: a program can not find K(s); the function being incomputable.


$s\_0$ is the initial string


$s\_1$ is the final string



> 
> Expalnation
> 
> 
> 


The amount of randomness added in the string can be measured through a difference in the kolmogrov complexity of two strings. I would love to consider the initial one as less complex.


Based on this variation in complexity we assume as to how many bits have been flipped ie k. Based on this we find the probability distribution function for n


for this one can find an analogy in the "coupon collectors problem" and find the likely hood of the sample size being n given k different coupons have been picked out of L different ones



> 
> Analysis
> 
> 
> 


The lower bound for n is deterministically set to k. There apparently is no upper bound although much higher sample sizes are expected as k increases.


