mathematics – What is the probability that there will be at least one subseries of `M 'heads in a row in a series of` N' throws?

Question:

The problem conditions are as follows:

There is a coin that comes up heads with probability P (0 <P <1). What is the probability that there will be at least one subseries of M heads in a row in a series of N tosses?

The task is very non-trivial, I managed to google the version of the solution in English, but I was not quite able to understand what is written there and even how the result given there could be coded.

It is desirable that the solution could somehow be explained to a person with a rather shallow knowledge of the Terver, such as me (they taught us well, but it was too long ago and was practically not applied in life).

In general, a simplified version of the solution for p ~ 0.5 and N >> M (N is much greater than M) will suffice.

For example, numerical simulation of the situation (P = 0.5):

Series of 20000 trials was made 20000 times

Longest streak of 9 successes count 1 times
Longest streak of 10 successes count 148 times
Longest streak of 11 successes count 1569 times
Longest streak of 12 successes count 4090 times
Longest streak of 13 successes count 4870 times
Longest streak of 14 successes count 3995 times
Longest streak of 15 successes count 2531 times
Longest streak of 16 successes count 1358 times
Longest streak of 17 successes count 732 times
Longest streak of 18 successes count 367 times
Longest streak of 19 successes count 182 times
Longest streak of 20 successes count 81 times
Longest streak of 21 successes count 44 times
Longest streak of 22 successes count 15 times
Longest streak of 23 successes count 10 times
Longest streak of 24 successes count 4 times
Longest streak of 25 successes count 1 times
Longest streak of 26 successes count 1 times
Longest streak of 28 successes count 1 times

streaks of 18 successes coint 1359 times
streaks of 19 successes coint 638 times
streaks of 20 successes coint 296 times
streaks of 21 successes coint 139 times
streaks of 22 successes coint 63 times
streaks of 23 successes coint 31 times
streaks of 24 successes coint 14 times
streaks of 25 successes coint 7 times
streaks of 26 successes coint 4 times
streaks of 27 successes coint 2 times
streaks of 28 successes coint 1 times

Answer:

  • One is heads, zero is tails
  • p is the probability of getting units
  • ok(n, m) – the probability of having a subsequence
  • no(n, m) – probability of no subsequence

Further:

  • i+1 – the position from which the desired sequence of ones begins
  • i <= nm , otherwise the sequence of ones will not fit
  • If i = -1 , then there is no prefix.

Next, consider 0 <= i <= nm :

  • At position i is 0 , its probability is 1-p
  • The probability of getting a piece to position i is no(i-1, m)

  • The probability of getting the sequence itself p^m

Let's summarize:

2^p * (1 + .5 * sum { i=0 to n-m } of no(i-1, m))
2^p * (1 + .5 * sum { i=0 to n-m } of (1 - ok(i-1, m)))
Scroll to Top