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

Правка en3, от quinoa, 2020-12-22 01:32:04

Say you have a binary string of length N where 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?

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский quinoa 2020-12-22 01:32:04 39
en2 Английский quinoa 2020-12-22 01:31:19 20
en1 Английский quinoa 2020-12-22 01:30:15 454 Initial revision (published)