Given two binary strings of length $n$ and $m$, determine in polynomial time the probability of the first appearance of one string being earlier than the first appearance of the other one in an evenly distributed infinitely long binary sequence.

Edit: I didn't consider my attempts at solving this to be relevant, they are as follows:

I've considered to use a Markov chain and the fact that $P(A_j)$, the probability of absorbtion of the chain in the $j$-th absorbing state, $=(b^{(0)}NR)_j$, where $b^{(0)}$ is the vector of probabilites of the starting state, $N$ is the fundamental matrix of the chain and $R$ is the matrix that describes the probability of transitioning from some transient state to some absorbing state.

I've indexed the chain states by $(i, j)$, where $i$ is the length of the longest prefix of the first string ($s_1$) that matches in the current state, and $j$ is the same for $s_2$.

Absorbing states are $(n, *)$ and $(*, m)$, where $*$ denotes any number, therefore splitting $P$, the transition matrix of the chain, into $Q$ and $R$ is trivial.

The only thing left is to compute $P$ in polynomial time, which is where I'm stuck. I have written this algorithm, but it's not correct:

for i = 0...n
    for j = 0...m
        if i == n || j == m // absorbing state
            P[(i,j)][(i,j)] = 1
        else if s[i+1] == r[i+1] // bits are the same => either in both strings the next bit will match or it will in neither
            P[(i,j)][(i+1, j+1)] = 0.5
            P[(i,j)][(0,0)] = 0.5
        else // bits are not the same => in both cases only one of the bits will match
            P[(i,j)][(i+1,0)] = 0.5
            P[(i,j)][(0,j+1)] = 0.5

The problem with this algorithm is that in case a bit does not match, the matching prefix length may not be zero, for example on sequence $010...$ for the string $011$ the matching prefix length will be $1\rightarrow 2\rightarrow 1\rightarrow\ldots$, instead of $0$, as my algorithm implies.

  • 1
    $\begingroup$ I see a problem statement, but not question here. $\endgroup$ – Yuval Filmus Mar 24 '20 at 19:33
  • $\begingroup$ What have you tried? Where did you get stuck? $\endgroup$ – Yuval Filmus Mar 24 '20 at 19:33
  • $\begingroup$ We're a question-and-answer site, so we require you to articulate a specific question about your situation. You're more likely to get help if you think hard about your problem before asking, share with us what progress you've made, tell us what approaches you've considered, and give some indication of where or why you are stuck. $\endgroup$ – D.W. Mar 24 '20 at 19:35
  • $\begingroup$ Do you mean "appearing in front of" or "appearing before"? Any occurence of the string, or the first occurence? How long is the binary sequence? $\endgroup$ – gnasher729 Mar 24 '20 at 20:57
  • $\begingroup$ @gnasher729 what is the difference in these statements? They seem the exact same to me. I meant the first occurence, and the sequence is infinite. $\endgroup$ – lsparki Mar 24 '20 at 21:32

Here is the rough idea, for determining the probability that $x$ appears before $y$:

  • Construct a DFA that accepts the language of all binary strings in which $x$ appears before $y$.
  • Take the adjacency matrix of the DFA, replace the edges by $1/2$ entries.
  • Relate the probability that you're after to this matrix, and using this, calculate the probability.

I'll let you sort out the remaining details.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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