Probability that 2 sequences of k trials (success/failure) are identical.

A single trial has probability p of success and (1-p) of failure. For simplicity, we assume p = 1/2 = (1-p). An experiment is defined as a sequences of trials until 4 consecutive success or failures.

Suppose two such experiments were conducted. What is the probability that they will be identical?

Attempt

Given an outcome of experiment 1 that is made up of k trials. Then the probability of experiment 2 being exactly the same is, $$P(k)(1/2^k)$$

where P(k) is the probability of an experiment being k trials in length. Since experiment 1 can be of length 4 to infinity, the final probability is, $$\sum_{k=4}^{\infty} P(k)^2(1/2^k)$$

Question

1. How do I find P(k)?
2. Is this the right approach? Or is there a simpler way?
-
By identical do you mean (1) that they last the same length k and that the two sequences of success and failure are identical or (2) that they stop at the same k for the same reason (i.e. both ended with four consecutive successes or both ended with four consecutive failures or (3) they both stop at k regardless of the reason? These three possibilities should give three different results. –  Michael Chernick Jul 6 '12 at 17:23
I meant (1). Same length k, and two sequences of success and failure are identical. –  Legendre Jul 7 '12 at 16:04
Got something from the answer below? –  Did Jul 14 '12 at 14:28
I am sorry this is taking some time. I wanted to accept your answer at first, but I calculated the probabilities for the first few cases (k = 1,2,3,4..) and got a result that might suggests your answer is wrong. :p I am still very interested in this problem and will sort it out in a few days. :D –  Legendre Jul 17 '12 at 9:58
Wrong? No less? Wow... Veeeerry curious to see those results I am! :-) (But please next time, use the @ to signal a comment, I saw yours only by chance although you clearly meant to talk to me.) –  Did Jul 20 '12 at 18:35

Call $T$ the number of trials needed to complete a full experiment. For $1\leqslant k\leqslant3$, call $T_k$ the number of supplementary trials needed to complete an experiment, starting from $k$ identical trials. Thus, $T\stackrel{\text{dist}}{=}1+T_1$, $T_1\stackrel{\text{dist}}{=}1+T_2$ or $1+T_1$ with equal probabilities, $T_2\stackrel{\text{dist}}{=}1+T_3$ or $1+T_1$ with equal probabilities, and $T_3\stackrel{\text{dist}}{=}1$ or $1+T_1$ with equal probabilities.
Fix $|s|\leqslant1$ and call $u_k=\mathrm E(s^{T_k})$. The identities between distributions stated above are translated into the relations $\mathrm E(s^T)=su_1$, $u_1=\frac12s(u_1+u_2)$, $u_2=\frac12s(u_3+u_1)$ and $u_3=\frac12s(1+u_1)$. Solving for $\mathrm E(s^T)$ this system yields $$\mathrm E(s^T)=\frac{s^4}{8-4s-2s^2-s^3}.$$ The probability that the first experiment has length $k$ is $\mathrm P(T=k)$. Conditionally on $[T=k]$, the second experiment is identical to the first one with probability $\frac1{2^k}$. Hence, the probability $Q$ that the two experiments are identical is $$Q=\sum\limits_k\mathrm P(T=k)\frac1{2^k}=\left.\mathrm E(s^T)\right|_{s=\frac12}=\frac1{86}.$$