An algorithm to determine probability of one string appearing earlier than another string in an evenly distributed binary sequence
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.