Probability of substring of K 1 characters in binary string of length N?

Revision en2, by quinoa, 2020-12-22 01:31:19

Say you have a binary (0 or 1 characters) string of N characters. Each character is equally likely to appear. What is the probability that there will be a substring of K 1 characters?

For instance if K = 2, N = 3 the answer is 3/8 = 37.5%.

000: NO
001: NO
010: NO
011: YES
100: NO
101: NO
110: YES
111: YES

How to solve this problem. Can it be done in polynomial time?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English quinoa 2020-12-22 01:32:04 39
en2 English quinoa 2020-12-22 01:31:19 20
en1 English quinoa 2020-12-22 01:30:15 454 Initial revision (published)