# Probability of a Sequence in a Permutation

I wanted to know how to compute for the probability of a certain string to appear in a permutation.

What is the probability that two heads or two tails show in a row when I flip a coin $$10$$ times?

I know the answer is $$\frac{511}{512}$$ because $$\text{THTHTHTHTH}$$ and $$\text{HTHTHTHTHT}$$ are the only permutations that doesn't have two faces in a row. And the solution is $$\sum_{n=1}^{k} (\frac{1}{2})^k$$, with $$k$$ being the number of coin tosses minus one which would be $$9$$.

But I don't know how to compute for other problems like the probability of three same faces in a row when I roll a dice five times. Can we make a general formula for this?

I figured that to know the answer to this:

the probability of three same faces in a row when I roll a dice five times.

it's by checking the first $$n$$ rolls then the second, third, etc. (the $$n$$ in our case is $$3$$ because we're figuring out three same faces in a row). The first three rolls have a chance of $$\frac{1}{36}$$ of being a row of the same face/value. But there's a chance of it not happening in which case the row with the same face could be the second, third, and fourth rolls. At this point, I don't how to continue using my method. I'm guessing you compute for the probability that the second and third roll have the same face then compute the probability that the fourth roll is the same as the first two, but I'm stuck on it.

• you might want to take a look at Markov chains to solve this kind of problem Commented Oct 21, 2020 at 6:58
• for instance: math.stackexchange.com/questions/2281487/… Commented Oct 21, 2020 at 7:04

May be you can do like that, let $$A_i=\text{first three same faces in row starts in i}$$ And $$B_{i}=\text{There is no three same faces in row in first i roll of dice}$$

Then $$\mathrm{P}(A_i)=\mathrm{P}(B_{i-1}\,)\cdot\frac{5}{6}\cdot\frac{1}{6}\cdot\frac{1}{6}$$

(first we choose face which isn't same with last in first $$i-1$$ rows, and then choose two faces same with first chosen one)

Then $$A_i$$ are disjoint (because $$i$$ uniquely determined by first occurrence of three same faces in row) and $$\mathrm{P}(\text{there is three same faces in row in n rolls}) = \sum_{i=1}^{n-2}\mathrm{P}(A_i) = \sum_{i=1}^{n-2}\mathrm{P}(B_{i-1}\,)\cdot\frac{5}{6}\cdot\frac{1}{6}\cdot\frac{1}{6}$$

But $$\mathrm{P}(\text{there is three same faces in row in n rolls})=1 - \mathrm{P}(B_n)$$

Therefore $$\mathrm{P}(B_n)=1 - \sum_{i=1}^{n-2}\mathrm{P}(B_{i-1}\,)\cdot\frac{5}{6}\cdot\frac{1}{6}\cdot\frac{1}{6}$$

And you have recursive rule for $$\mathrm{P}(B_n)$$. Knowing that $$\mathrm{P}(B_0)=\mathrm{P}(B_1)=\mathrm{P}(B_2) = 1$$ You can compute $$\mathrm{P}(B_n)$$ for any $$n\ge3$$

And $$\mathrm{P}(\text{there is three same faces in row in n rolls})=1 - \mathrm{P}(B_n)$$