Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I have some length $L$ binary string consisting of an ordered array of bits: $(b_1, b_2, ..., b_{L})$, where all bit values $b_i$ are originally set to zero. I'd like a particular set of $n$ bits to hold the value $1$. For example, if $L = 5$, starting from $00000$ we might want to reach the state $01101$ where a specific set of $n = 3$ bits have the value $1$. However, I can only do two things:

[1] Choose a bit in the string at position $i$ where $b_i = 0$, with uniform random probability over all bits in the string with this value, and set $b_i = 1$. To be clear, here, if there are nine bits with the value $0$ and one bit with the value $1$, a particular bit with the value $0$ would be selected for a $0 \to 1$ transition with probability $\frac{1}{9}$.

[2] Choose a bit in the string at position $i$ where $b_i = 1$, with uniform random probability over all bits in the string with this value, and set $b_i = 0$.

What distribution do we have for the length of time until we reach the state where at least $k \leq L$ of the ordered array of bits have the desired $0$ and $1$ value ($k = L$ implying that only the aforementioned $n$ positions have the value $1$)?

What if we make it increasingly likely for us to select the previously flipped bit in [2], for example, if the immediately preceding $0 \to 1$ transition had a probability $r$ times greater of being reversed in [2] than any other bit with the value $1$ being flipped to the value $0$ (implying that the immediately previously flipped bit has a $1 \to 0$ transition probability during [2] of $Prob(1 \to 0) = \frac{r}{(q+r)}$ if there are $q$ OTHER $1$ bits that can be flipped to $0$ with probability $\frac{1}{(q+r)})$? As $r \to \infty$, one would imagine that it would be possible to quickly drift any binary string from some initial state to another desired state.


Alternative Question Formulation:

There's another fun way to ask this question. Given that the set of single bit flip transitions for a length $L$ binary string can be represented with a graph $G$ having the topology of an $L$-dimensional hypercube, draw this hypercube and replace each edge with a pair of directed RED and BLUE edges (that can only be traversed in a single direction). RED directed edges imply a $0 \to 1$ bit flip, and BLUE directed edges imply a $1 \to 0$ bit flip.

Starting one vertex $v_i$, our task is to reach another vertex $v_j$ in the fewest number of hops. However, we can only decide to select a RED or BLUE edge (pointing in the correct direction to allow traversal) at any given point in time, and then we need to pick one of the edges of the desired color randomly with uniform probability.

In terms of the "bias" in the original posting, we can say that we're $r$ times more likely to move back to the previously occupied vertex than any other vertex if we previously traversed a RED directed edge and now decide to traverse a BLUE directed EDGE.


Update - I wrote "...What distribution do we have for the length of time until we reach the state where at least $k \leq L$ of the ordered array of bits have the desired $0$ and $1$ value..." in the original posting. However, this could unnecessarily complicate things. So please feel free to set $k = L$. Also feel free to assume that the optimal "strategy" here is to immediately switch to process [2] when the wrong bit has its value flipped from $0$ to $1$.


Update 2 - Intuitively, letting $m_0$ be the number of $0$ bits and $m_1$ be the number of $1$ bits, we can probably guess that the length of time to reach the target string will probably have some dependency on $\delta = || m_1 - m_0 ||$, where smaller values of $\delta$ (i.e. where $m_0 \approx m_1$) imply longer average times to reach the desired string target structure. This "seems" like it might be true because ${L}\choose{m_0}$ and ${L}\choose{m_1}$ are simultaneously maximized at this limit.

Simulations (!!! where we immediately try to flip back "incorrect" $1$ bits by applying procedure [2] for as long as necessary to do so) appear to back up this intuition. For a length $L = 10$ binary string where the target string 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)$

However, we also see see that the length of the string $L$ and $\delta = || m_1 - m_0 ||$ do not provide enough information to predict waiting times, specifically that for the same value of $\delta$, $m_1 > m_0$ implies a larger number of necessary bit flips to reach the target string. I suppose this makes sense given that the initial string is populated with only $0$-valued bits.

I see no reason why these relationships wouldn't hold with the "previous flipped bit" selection bias discussed at the end of the original question posting, though I could obviously be wrong about this.

Let's add some $L = 20$ values for the unbiased case (we're only doing $10^3$ trials here because these trials take a lot longer):

$L=20$ and $k=9$ yields a {mean, median} $= (\mu, \mu_{1/2}) = (118,487.382, 82,308)$

$L=20$ and $k=10$ yields a {mean, median} $= (\mu, \mu_{1/2}) = (127,382.07, 90,858)$

As Will Sawin nicely points out, for $k = 11$, we could quickly drift our string to the state where we have all-$1$ bit values, and then achieve roughly the same number of expected bit flips (in the unbiased case!) as if we had $k = 9$.

share|improve this question
    
Upper bound: $2 \left(\begin{array}{c} L \\ m_0 \end{array}\right) + m_1$. Strategy: add $1$s until you have $m_1$ $1$s, then alternate adding a $1$ and adding a $0$. You are equally likely to get each of the strings with $m_1$ ones at each step, so this computes the expected value. It seems likely that this is asymptotically quite close to optimal. –  Will Sawin Jan 19 at 21:12
    
However, this is not perfectly optimal - if your first bit flip is bad, I believe you should immediately flip it back. Taking this to its logical conclusion, you could add a $0$ any time you have a bad $1$ and add a $1$ otherwise. I'm not sure how to analyze this Markov chain. –  Will Sawin Jan 19 at 21:14
    
@WillSawin So you're saying we need to "wander around" the Markov chain states where $m_0$ and $m_1$ are within one of the values for the target string, as it doesn't make sense to search through other states. I'm curious though if there's a way to get a more precise estimate. Where is your factor of $2$ coming from? –  Barium Jan 19 at 21:17
    
It takes two moves to get back to a state with the same number of $1$ bits. –  Will Sawin Jan 19 at 21:18
    
@WillSawin Ah, I see, sorry. Hmm, it's not really clear to me if this strategy makes more sense than immediately trying to flip back $1$ bits that are incorrect. On average, you're going to have large swings in intermediate $m_0$ and $m_1$ values if you do this... –  Barium Jan 19 at 21:20

1 Answer 1

Ignoring the specific binary string structure of the problem for a moment, let's generalize it to an arbitrary digraph $G$ with vertices $V$ and edges $E$ divided into two disjoint subsets $E = E_\mathrm R \sqcup E_\mathrm B$ (for "red" and "blue" respectively).

Equivalently, let us denote the "red" and "blue" neighbors of each vertex $v \in V$ as $N_\mathrm R(v)$ and $N_\mathrm B(v)$, where $v' \in N_c(v) \iff (v,v') \in E_c$ for $c \in \{\mathrm R, \mathrm B\}$. (Note that a single vertex $v$ can be a red neighbor of $v'$ and a blue neighbor of $v''$ at the same time — the color is really a property of the edges, not of the nodes.)

We wish to minimize the expected number of steps needed to reach an arbitrary goal set $A \subset V$ from an arbitrary initial vertex $v_0 \in V$, given that, at each step $k$, we have the choice of picking $v_{k+1}$ uniformly at random from either $N_\mathrm R(v_k)$ or $N_\mathrm B(v_k)$.

Let us denote the expected number of steps to reach $A$ from an initial vertex $v$ using strategy $\mathcal S$ by $T_\mathcal S(v)$. (For consistency, I'm assuming that $A$ is in fact reachable from any vertex $v \in V$.) For $v \in A$, we naturally have $T_\mathcal S(v) = 0$, while for $v \notin A$ we have $$ T_\mathcal S(v) = 1 + \frac{P_\mathrm R(\mathcal S,v)}{|N_\mathrm R(v)|} \sum_{v'\in N_\mathrm R(v)} T_\mathcal S(v') + \frac{P_\mathrm B(\mathcal S,v)}{|N_\mathrm B(v)|} \sum_{v'\in N_\mathrm B(v)} T_\mathcal S(v') \tag{1} \label{answer-155160-1} $$ where $P_\mathrm R(\mathcal S,v)$ and $P_\mathrm B(\mathcal S,v) = 1 - P_\mathrm R(\mathcal S,v)$ are the respective probabilities of jumping to a red or a blue neighbor of $v$ under the strategy $\mathcal S$.

(Of course, if $N_c(v) = \emptyset$ for either $c \in \{\mathrm R, \mathrm B\}$, we must have $P_c(\mathcal S,v) = 0$ and simply $T_\mathcal S(v)$ $=$ $1$ $+$ $\frac{1}{|N(v)|} \sum_{v'\in N(v)} T_\mathcal S(v')$, where $N(v) = N_\mathrm R(v) \cup N_\mathrm B(v)$.)

(Note that I'm only considering "Markovian" strategies, where $P_\mathrm R(\mathcal S,v)$ and $P_\mathrm B(\mathcal S,v)$ are constant for each $\mathcal S,v$ and, in particular, independent of the way we may have ended up at $v$. It's not hard to show that the optimal strategy must indeed be Markovian, but I'll skip that bit for brevity.)

The nice thing about equation $\eqref{answer-155160-1}$ is that it's linear! Therefore, we can find the optimal solution to it, subject to the constraints that $P_\mathrm R(\mathcal S,v) \ge 0$ and $P_\mathrm B(\mathcal S,v) \ge 0$ for all $v$, using linear programming.

(In fact, from the form of the constraints, we can immediately tell that the optimal solution $\mathcal S^*$ will have $P_\mathrm R(\mathcal S^*,v) \in \{0,1\}$ for all $v$, except possibly for degenerate cases where any value of $P_\mathrm R(\mathcal S^*,v)$ will yield the same $T_{\mathcal S^*}(v)$.)

I have not actually tested this method in practice yet, but I see no reason why it shouldn't work. Note that, for large $L$ (where optimizing a system of $2^L$ linear equations may not be practical), we may want to exploit the structure of the problem by collapsing equivalent states: in particular, it should be sufficient to represent each state by two numbers $(n_0, n_1)$ giving respectively the number of mismatched $0$ and $1$ bits in the string. This will reduce the number of distinct states from $2^L$ to $(n+1)(L-n+1)$ $\le$ $(L/2+1)^2$.

share|improve this answer
    
It would be fascinating to see how well the optimal strategy performs... For the case where we have bias, I'm assuming there are problems to implement the same strategy: "Note that I'm only considering "Markovian" strategies, where PR(S,v) and PB(S,v) are constant for each S,v and, in particular, independent of the way we may have ended up at v"? –  Barium Jan 20 at 15:19
    
@Barium: Ah, yes, I missed the "What if we make it increasingly likely for us to select the previously flipped bit" part in your question. I think we could deal with that by defining the process over the set of edges $E$ instead of the vertices $V$; in particular, in the specific case in your question, it should be enough to store $(n_0, n_1, \Delta n_0, \Delta n_1)$, where $(\Delta n_0, \Delta n_1) \in \{(0,1),(0,-1),(1,0),(-1,0)\}$ denotes the change in $(n_0, n_1)$ during the previous iteration. –  Ilmari Karonen Jan 20 at 21:43

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.