Timeline for An intutive reason why a "distance" metric may be a poor one for a procedure where we attempt to modify a string (mutating 0 OR 1 bits)
Current License: CC BY-SA 3.0
17 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:58 | history | edited | CommunityBot |
replaced http://mathoverflow.net/ with https://mathoverflow.net/
|
|
| Jan 21, 2014 at 22:40 | vote | accept | Barium | ||
| Jan 21, 2014 at 22:26 | answer | added | Peter Dukes | timeline score: 5 | |
| Jan 21, 2014 at 22:17 | comment | added | Barium | @PeterDukes Completely obvious now, thank you. :) | |
| Jan 21, 2014 at 22:12 | history | edited | Barium | CC BY-SA 3.0 |
added 1765 characters in body
|
| Jan 21, 2014 at 22:09 | comment | added | Peter Dukes | Maybe I am missing something, but in the case of "110" to "100", you are choosing a $1 \rightarrow 0$ move from only two positions. In the case of "000" to "100", you are choosing a $0 \rightarrow 1$ move from three positions. I think you already realize this, though. In short, the symmetries of the cube which permute positions respect your procedure; the symmetries flipping bits definitely do not. | |
| Jan 21, 2014 at 21:26 | comment | added | Barium | @PeterDukes If you could detail out your calculation, that would be terrific, because I can't seem to reason properly about this. Really, this comes down to making decisions to move along one edge or the other on the cube... so how could we be in a better position if the we're at two identical vertices (up to isomorphism)? | |
| Jan 21, 2014 at 21:20 | comment | added | Barium | @PeterDukes Ok, so it's easier to "hit" "100" from "110" than "000"? Why would this be the case, and wouldn't this violate distance transitivity of the $n$-cube graph where vertices represent Hamming codes? It seems like if we randomly select a bit to mutate in "110" or "000", we're just as likely to move further away from "100" as we are to moving closer to it. | |
| Jan 21, 2014 at 21:16 | comment | added | Peter Dukes | 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. | |
| Jan 21, 2014 at 20:59 | comment | added | Barium | @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? | |
| Jan 21, 2014 at 18:21 | comment | added | Barium | @Omer I've hopefully clarified the decision process a bit in the posting. | |
| Jan 21, 2014 at 18:18 | history | edited | Barium | CC BY-SA 3.0 |
added 166 characters in body
|
| Jan 21, 2014 at 18:15 | comment | added | Barium | @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. | |
| Jan 21, 2014 at 17:54 | comment | added | Omer | 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? | |
| Jan 21, 2014 at 17:27 | history | edited | Barium | CC BY-SA 3.0 |
added 52 characters in body
|
| Jan 21, 2014 at 17:21 | history | edited | Barium | CC BY-SA 3.0 |
added 1115 characters in body
|
| Jan 21, 2014 at 17:06 | history | asked | Barium | CC BY-SA 3.0 |