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
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 21, 2014 at 22:52 | comment | added | Barium | 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. | |
| Jan 21, 2014 at 22:50 | comment | added | Peter Dukes | 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. | |
| Jan 21, 2014 at 22:49 | comment | added | Barium | In retrospect, it seems that this question was trivial, so thanks also for your patience and answer. | |
| Jan 21, 2014 at 22:47 | comment | added | Barium | 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. | |
| Jan 21, 2014 at 22:40 | vote | accept | Barium | ||
| Jan 21, 2014 at 22:26 | history | answered | Peter Dukes | CC BY-SA 3.0 |