Given a binary vector, what is the probability that no 2 adjacent bits are 1?
Let's say the probability for value 1 is p.
I thought to calculate it by dynamic programming. So I thought to define recursive function P(n) that represnts the probability that no 2 adjacent bits are 1 in binary vecotr in size n.
so P(1) = 1, and P(2) = 1 - p^2.
And now we need to split to two options for n>2:
- the first bit is 0, so we need to enforce it for the rest bits, namely:
P(n-1) - the first bit is 1, so the second bit must be 0, and we need to enforce it for the rest bits, namely:
(1-p)*P(n-2).
My question is: should I multiple any option in probability bit?
namely:
P(n-1)+(1-p)*P(n-2)
or:
(1-p)*P(n-1)+p*(1-p)*P(n-2)
By "the probability for value 1 is p", I assume you mean to say that each element of the binary vector is selected independently such that the probability of that element being a $1$ is $p$.
If that's the case, then your second recurrence is correct. That is, we have $$ P(n) = (1-p)P(n-1) + p(1-p)P(n-2) $$
I think that the best way to convince you that the first approach is wrong is to see what happens for $n=3$. To make our calculations simpler, take $p = 1/2$ so that all strings are equally likely.
The first approach predicts $$ P(3) = P(3-1) + (1-p)P(3-2) = \left(1 - \left(\frac 12\right)^2 \right) + \frac 12 \cdot 1\\ P(3) = \frac 34 + \frac 12 = \frac 54 > 1, $$ which is clearly impossible. On the other hand, the second approach yields $$ P(3) = \frac 12 P(2) + \frac 14 P(1) = \frac 12 \cdot \frac 34 + \frac 14 = \frac 58, $$ which is correct. The three prohibited strings are $011$, $110$, $111$, leaving $5$ possibilities where no two adjacent bits are $1$.
Notably, this is a linear recurrence with constant coefficients, so we can find $P(n)$ explicitly as a function of $n$. We find the characteristic equation of this linear recurrence to be $$ \begin{align} &r^2 - (1-p)r - p(1-p) = 0 \implies\\ r &= \frac{1-p \pm \sqrt{(1-p)^2 + 4p(1-p)}}{2} \\ & = \frac{1-p \pm \sqrt{(1-p)(1 + 3p)}}{2} \end{align}. $$ Let $r_+, r_-$ denote the solutions to this equation, namely $$ r_+ = \frac{1-p + \sqrt{(1-p)(1 + 3p)}}{2}, \quad r_- = \frac{1-p - \sqrt{(1-p)(1 + 3p)}}{2}. $$ Notably, assuming that $0<p<1$, these solutions are real with $r_- < 0 < r_+$. We find that $P(n)$ must be of the form $$ P(n) = C_-r_-^n + C_+r_+^n $$ for some constants $C_-,C_+$. We can find the specific constants using the fact that $P(0) = P(1) = 1$. In particular, we have $$ C_- r_-^0 + C_+r_+^0 = 1 \implies C_- + C_+ = 1\\ C_- r_-^1 + C_+ r_+^1 = 1 \implies r_-C_-+ r_+C_+ = 1. $$ We can solve this linear system as follows. $$ A = \pmatrix{1 & 1\\r_- & r_+} \implies A^{-1} = \frac 1{r_+ - r_-} \pmatrix{r_+ & -1\\-r_-&1} \\ = \frac 1{\sqrt{(1-p)(1+3p)}} \pmatrix{r_+ & -1\\-r_-&1}\\ A \pmatrix{C_-\\C_+}= \pmatrix{1\\1} \implies \\ \pmatrix{C_-\\C_+} = A^{-1}\pmatrix{1\\1} = \frac 1{\sqrt{(1-p)(1 + 3p)}}\pmatrix{r_+ - 1\\r_- + 1}. $$