Return to Question

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.

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.

If I'm attempting to mutate one binary string to another, in the smallest number of steps, via a procedure where I decide to either:

(1) Randomly choose a "0" bit and flip it to a "1" bit.

(2) Randomly 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.

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.