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.
