1
$\begingroup$

Imagine a memoryless source that outputs 0's and 1's with probabilities $P_X(0)$ and $P_X(1)$. For example, $P_{X^2}(00)=P_X(0)P_X(0)$.

How would you calculate the probability that the sequence $010$ is present in an $n$-length binary sequence?

What I have thought so far is that,

$$P[010 \text{ is in an } n\text{-length sequence}]=(n-3)P_X(0)^{\#0}P_X(1)^{\#1}$$

I am sure that I have to multiply the probabilities $P_X(0)$ and $P_X(1)$ by $n-3$, because I need to take into consideration all the possible combinations in which $010$ can appear (e.g. $\{010...x\}$,$\{x010...x\}$,etc.). But I am not sure about the number of zeros $\#0$ and the number of ones $\#1$.

$\endgroup$
15
  • $\begingroup$ This is not clear. Are you considering the universe of binary sequences generated by, say, the repeated tosses of a (possibly unfair) coin? Something else? $\endgroup$
    – lulu
    Jun 2, 2021 at 17:15
  • $\begingroup$ You seem to have a lot of double counting problems. If the sequence starts $01010$ aren't you counting it twice? $\endgroup$
    – saulspatz
    Jun 2, 2021 at 17:19
  • 1
    $\begingroup$ To your question: You'll need to work recursively to avoid double counting. I suggest starting from the fact that every sufficiently long "good" sequence must end in one of $1,00, 110$. $\endgroup$
    – lulu
    Jun 2, 2021 at 17:22
  • 1
    $\begingroup$ @BrianMoehring My comment was pretty vague. In the given problem, I'd divide the good sequences into $4$ types, according to whether they end in $11,01,00$ or $10$. I haven't written it out, but I think that's good enough...after all, the only banned action is to add a $0$ to the type ending in $01$. For longer 'forbidden' blocks, you'd need to consider more endings. $\endgroup$
    – lulu
    Jun 2, 2021 at 17:46
  • 1
    $\begingroup$ Should note that the posted solution, from @Onir, follows a more or less similar methodolgy to the one I am sketching. $\endgroup$
    – lulu
    Jun 2, 2021 at 17:52

1 Answer 1

Reset to default
4
$\begingroup$

Let $a(00,n), a(01,n), a(10,n), a(11,n)$ be the probability we get a sequence that doesn't contain $010$ and end in each of the finishes.

We get:

$a(00,n+1)=p(a(00,n) + a(10,0))$

$a(01,n+1) = (1-p)(a(00,n)+a(10,n))$

$a(10,n+1) = pa(11,n)$

$a(11,n+1) = (1-p)(a(01,n) + a(11,n))$

We can write this as:

$\begin{pmatrix} p & 0 & p & 0 \\ 1-p & 0 & 1-p & 0 \\ 0 & 0 & 0 & p \\ 0 & 1-p & 0 & 1-p \\ \end{pmatrix} \begin{pmatrix} a(00,n) \\ a(01,n) \\ a(10,n)\\ a(11,n) \end{pmatrix} = \begin{pmatrix} a(00,n+1) \\ a(01,n+1) \\ a(10,n+1)\\ a(11,n+1) \end{pmatrix} $

When $n=2$ the values are $(p^2,p(1-p),(1-p)p,(1-p)^2)$. Hence we have:

$\begin{pmatrix} p & 0 & p & 0 \\ 1-p & 0 & 1-p & 0 \\ 0 & 0 & 0 & p \\ 0 & 1-p & 0 & 1-p \\ \end{pmatrix}^{n-2} \begin{pmatrix} p^2 \\ p(1-p)\\ (1-p)p\\ (1-p)^2 \end{pmatrix} = \begin{pmatrix} a(00,n) \\ a(01,n) \\ a(10,n)\\ a(11,n) \end{pmatrix} $

If the matrix happens to be diagonalizable you can get explicit formulas, even if it isn't you can expect to put it in a good form. You can also use exponentiation by squaring for rapid computations.

$\endgroup$
5
  • $\begingroup$ Oh, there is $p$ and $1-p$ ? I need to change the transition matrix then. $\endgroup$
    – Asinomás
    Jun 2, 2021 at 17:50
  • $\begingroup$ "When $n=2$ all the values are $1$"? $\endgroup$
    – saulspatz
    Jun 2, 2021 at 19:27
  • $\begingroup$ Oh I forgot to remove that part. $\endgroup$
    – Asinomás
    Jun 2, 2021 at 19:28
  • 1
    $\begingroup$ When $n=2$, don't we have $a_2(0,0)=p^2,\ a_2(0,1)=p(1-p),$ etc? $\endgroup$
    – saulspatz
    Jun 2, 2021 at 19:32
  • $\begingroup$ Yes, thank you. $\endgroup$
    – Asinomás
    Jun 2, 2021 at 19:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.