# Keeping time by randomly drifting a $q$-ary string

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.

• With two symbols the probability of “no change at all” in a single time interval is 0.5. Do I understand the procedure correctly? Jun 14 '13 at 12:28
• @Waldemar Yes, I believe you do. We uniformly select a site on the string at some time interval, and then mutate it randomly. As such, the probability that the character is changed is $\frac{q-1}{q}$, or $\frac{1}{2}$ for $q=2$. Jun 15 '13 at 2:27
• I think that this is essentially what biologists do when estimating the time when different species split away from each other during evolution (see en.wikipedia.org/wiki/Molecular_clock). Thus, there may be useful papers in the biology literature. Jun 17 '13 at 11:13

$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.

• I would think the conditional Kolmogorov complexity of $s_f$ given $s_0$ has a better chance of being relevant than the difference that you call $k$. Consider, for example, two scenarios, both with $q=2$. In one, we start with an initial string that's all 0's; in the other we start with a random string $r$ as our $s_0$. Differences of Kolmogorov complexities will look very different in these two scenarios, yet what's "really" going on is the same. You can convert either scenario to the other by just considering the bitwise XOR of all your strings with $r$. Jun 18 '13 at 15:27

I suggest a Bayesian approach to your problem. First, you assume a prior distribution over N. Then, you get to know the state of the string after N time increments but you don’t know the true value of N. However, now you can calculate a posterior probability over N as you know the observed state of the string. It’s a direct consequence of the fact that knowing N and the initial string you can calculate a distribution over states of the string. Finally, if you wish, you can use Kullback–Leibler divergence as a measure of the information gain in moving from a prior distribution to a posterior distribution.

• I agree with the Bayesian idea, at least to the extent that there is not enough information in the randomly drifting string to determine a probability distribution for $N$ unless one assumes some prior distribution for $N$. One can determine the probability of any particular string after $N$ steps, given $N$ and the initial string, but one cannot determine the probability of any $N$ given only the string after $N$ steps and the initial string. Jun 18 '13 at 15:31