probability of selecting an n-bit string in which there is a substring of length at least k in which each bit is a 1

Question

An n-bit binary string is selected uniformly at random.For a k $\geq$ 1,what is the probability of selecting an n-bit string in which there is a substring of length at least k in which each bit is a 1?

Comments

@Sambit

I have only problem with the word consecutive

Say I took an example

0011110000111111

Here if k=3

strings will be 111,1111,11111,111111

but how can we get such a logic in probability?

---

 srestha  question says different thing.read the question carefully

---

where is difference @Sambit?

string means it must have consecutive 1's

Answer 1

For an n bit binary string there are 2 options for each of the bit i.e each bit can be either 1 or 0. So for an n bit binary no. total no of combinations is :2^n. Now we have to find the probability that out of these there is a substring of length at least k which contains all 1's So that implies for atleast k values we dont have any choice they all are ones where as for the rest n-k bits we have a choice. So the no of substrings for them in this case is : 2^(n-k)

Probability:2^(n-k)/2^n=1/2^k.

I guess this is the ans for this ques.

Comments

your calculation is based on a particular index i to i+k-1 index.So wrong approach.

---

it can be any substring in that string...

Answer 2

I think it can be solved like this :-

Comments

same strings are being intersected by each cases