Substring of a bit string probability

Question

Given a fixed bit string $A$ of length $k$ and a randomly generated bit string $B$ of length $n > k$, meaning each bit of $B$ has probability $1/2$ to be zero or one respectively, how can one determine the probability that $A$ is a substring of $B$, meaning that the sequence of bits of $A$ appears somewhere in $B$ (contiguously)? Unfortunately, I don't really have any approaches to this problem...

Answer 1

I believe this is not solvable in general without specifying $A$, as this depends on the string $A$ and the values of $n$ and $k$. Consider the case $k=3$, $n=4$ for example. If $A = 100$, then the event $E_1:=$"the first three digits of $B$ are equal to A" and the event $E_2:=$ "the last three digits of $B$ are equal to $A$" are disjoint. The respective probabilites of these events are $$\mathbb{P}(E_i) = 2^{-3}, \quad i = 1,2$$ so the total probability of the event $E:=$"$A$ appears in $B$" will be $$\mathbb{P}(E) = \mathbb{P}(E_1\cup E_2) =\mathbb{P}(E_1)+\mathbb{P}(E_2) = 1/4.$$ However, if $A = 000$, then $E_1 \cap E_2$ is the event that $B = 0000$, which happens with probability $2^{-4}$, such that by the inclusion-exclusion principle we have $$\mathbb{P}(E) = \mathbb{P}(E_1 \cup E_2) = \mathbb{P}(E_1)+\mathbb{P}(E_2) - \mathbb{P}(E_1\cap E_2) = 2\cdot 2^{-3} - 2^{-4} = 3/16. $$ Which shows that the question is not well-posed.