6
$\begingroup$

If I'm attempting to mutate one arbitrarily chosen binary string $s_a$, to another arbitrarily chosen binary string $s_b$, in the smallest number of steps (i.e. with the smallest number of mutations) via a procedure where I decide to either:

(1) Randomly and with uniform probability choose a "0" bit and flip it to a "1" bit. E.g. if there are three "0" bits in our string $s_a$ at some decision / mutation step, and $10^2$ "1" bits, here a particular "0" bit would be selected for mutation to a "1" bit with probability $\frac{1}{3}$.

(2) Randomly and with uniform probability choose a "1" bit and flip it to a "0" bit.

Is there a good intuitive reason why I might not want to always choose (1) or (2) based on which option maximizes the probability that the Hamming distance to the target string will be smaller in the next step?

Let me write a specific statement about where my thinking is failing: I thought it would be the case that any string within a fixed Hamming distance of the target string would have a (topologically) indistinguishable representation on the $n$-dimensional hypercube where vertices represent all possible states of a length $n$ binary string (i.e. a length $n$ Hamming code - http://en.wikipedia.org/wiki/Hamming_distance). Given that the $n$-dimensional hypercube is a distance transitive graph, all vertices within a fixed distance $k$ of another vertex should be identical up to isomorphism of the $n$-cube (http://en.wikipedia.org/wiki/Distance-transitive_graph). Now, since "passing through" each set of topologically indistinguishable vertices within a Hamming distance $(1,2,...)$ of the target string must be done to reach the target string, what advantage could we have in not maximizing our chance to move one step closer to the target string at each step of the aforementioned decision process?

The above is NOT intended to be anything other than an illustration of where my intuition is likely failing.

Note: This question is related to The time to drift a binary string from one state to another via deterministic selection of two possible random bit mutation procedures. I also asked this question in a long-winded manner in a (now deleted) question that received no answers, but where Douglas Zare in the comments claimed that a "Hamming distance" strategy for the above decision process failed in simple counterexamples. I haven't been able to see this, it's on me and I thank him for his time. But I'd really like to understand better what's going on, so I'd like to ask the above with the "soft-question" tag.

Let me provide some support that my intuition is failing here. Here are simulations for the time to mutate some length $n = 10$ string $s_a = 0000000000$ to another string $s_b$ with $k$ $1$ bits under a strategy where we immediately try to flip back "incorrect" $1$ bits by applying procedure [2] for as long as necessary to do so. Where the target string $s_b$ has $k$ bits with value $1$ (where exactly these bits are in the string should be irrelevant), and performing $10^4$ trials:

$k=0$ trivially implies a {mean, median} $= (\mu, \mu_{1/2}) = (0, 0)$

$k=1$ yields a {mean, median} $= (\mu, \mu_{1/2}) = (19.3202, 13)$

$k=2$ yields a {mean, median} $= (\mu, \mu_{1/2}) = (66.2872, 46)$

$k=3$ yields a {mean, median} $= (\mu, \mu_{1/2}) = (152.303, 107)$

$k=4$ yields a {mean, median} $= (\mu, \mu_{1/2}) = (258.273, 180)$

$k=5$ yields a {mean, median} $= (\mu, \mu_{1/2}) = (333.897, 237)$

$k=6$ yields a {mean, median} $= (\mu, \mu_{1/2}) = (321.758, 226)$

$k=7$ yields a {mean, median} $= (\mu, \mu_{1/2}) = (238.742, 167)$

$k=8$ yields a {mean, median} $= (\mu, \mu_{1/2}) = (130.412, 94)$

$k=9$ yields a {mean, median} $= (\mu, \mu_{1/2}) = (50.1086, 37)$

$k=10$ trivially implies a {mean, median} $= (\mu, \mu_{1/2}) = (L, L) = (10, 10)$

Now, under the strategy where we try to pick procedure [1] vs. procedure [2] based on which one maximizes the chance of moving closer to $s_b$ (in terms of Hamming distance) at any given time step, we have:

$k=5$ yields a {mean, median} $= (\mu, \mu_{1/2}) = (436.988, 303)$

Which is a lot worse than what we found for the strategy where we immediately try to eradicate incorrect bit flips by mutating using procedure [2] until they are removed.

Improve this question
$\endgroup$
9
  • $\begingroup$ It is not clear what exactly you are trying to achieve. Are you trying to minimize the expected time to hit a target? what options other than 1 and 2 do you have? $\endgroup$
    – Omer
    Commented Jan 21, 2014 at 17:54
  • $\begingroup$ @Omer That's precisely right, I'm trying to minimize the time (or number of mutations) necessary to hit an arbitrary string $s_b$ starting from an arbitrary string $s_a$. There are no options other than the two listed above (a "do nothing" step wouldn't make sense). However, one is forced to perform procedure (2) if there are no "0" bits, and procedure (1) if there are no "1" bits. $\endgroup$
    – Barium
    Commented Jan 21, 2014 at 18:15
  • $\begingroup$ @Omer I've hopefully clarified the decision process a bit in the posting. $\endgroup$
    – Barium
    Commented Jan 21, 2014 at 18:21
  • $\begingroup$ @PeterDukes It seems like something like that could make sense. Where I'm confused is that, if we think about lenght $n$ Hamming codes on the $n$-cube, topologically speaking, the strings "110" and "000" (both a Hamming distance $k = 1$ from "100") should be identical with respect to their relationship to the string "100" (up to isomorphisms of the cube). So why would it be advantageous to be at one vertex / string or the other? $\endgroup$
    – Barium
    Commented Jan 21, 2014 at 20:59
  • $\begingroup$ I retracted my earlier comment... sorry. I did the calculation and was wrong. I think it turns out to be best approaching a weight one word from the all-zero word. This defied my intuition a little. The sense in which "110" is better than "000" is that the required bit switch draws from a smaller pool of identical bits. Isomorphism of the cube doesn't really respect the calculation of probabilities here. $\endgroup$
    – Peter Dukes
    Commented Jan 21, 2014 at 21:16

1 Answer 1

Reset to default
5
$\begingroup$

I'll appeal to the linked question's answers for computational details.

Intuition only: (as requested here)

It is "easier" using your procedure to move from $00110^{n-4}$ to $11000^{n-4}$ than it is to go from $0000^{n-3}$ to $1110^{n-3}$, despite the Hamming distance being smaller in the latter case. You have to "win the lottery" three times in the latter case.

Therefore, a priori it is unclear that reducing Hamming distance at each step is optimal.

Improve this answer
$\endgroup$
4
  • $\begingroup$ In terms of actually finding an optimal strategy, I suppose we can color the edges of a hypercube graph to represent the probability of each transition, and then choose procedure [1] or [2] based on some metric where we compute each neighboring vertices shortest path to the target string state (using some modified version of Dijkstra's algorithm to account for edge weights). It seems fairly hopeless to rule out falling into local minima or traps. $\endgroup$
    – Barium
    Commented Jan 21, 2014 at 22:47
  • $\begingroup$ In retrospect, it seems that this question was trivial, so thanks also for your patience and answer. $\endgroup$
    – Barium
    Commented Jan 21, 2014 at 22:49
  • $\begingroup$ It may be prudent to choose a bit flip direction based on likelihood of reducing some quantity, perhaps something like $\max(d_{01}(\mathbf{u},\mathbf{v}),d_{10}(\mathbf{u},\mathbf{v}))$, where $d_{ij}$ counts positions with an $i$ in the first argument and a $j$ in the second. $\endgroup$
    – Peter Dukes
    Commented Jan 21, 2014 at 22:50
  • $\begingroup$ Hmm, it seems like that could be the case. Let me know if you happen to think of an optimal strategy. I'll continue to see what I can do. $\endgroup$
    – Barium
    Commented Jan 21, 2014 at 22:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .