MHB Probability of binary consecutive occurence with unequal probability

[cygi1989]

I have been with this to some forums but it didn't help and I was advised to come to this one, so here is the question.

My task is to compute given N - length binary series and P = p(0) and 1-P = p(1) expected number of consecutive occurence of 0 or 1 of k - length. For example 10011100 has one serie of 1 with length 1 and one serie with length 3,
and also have two series of 0 of length 2.
I know that when the probability of 0 and 1 is equal than
Expected number of series of 0 or 1 of k-lenth in n-length binary numbers is = (n-k+3)/2^(k+2).
But what the case when probability of 0 is for example (0.4) or any another?

Sebastian

 

[chisigma]

Re: Probability of binary consecutive occurence with uneqaul probability

In order to clarify the question let's consider an example: if $p(0)=p(1)=\frac{1}{2}$ what is the probability to have a sequence of three ones in a string of four binary symbols?... in this case the possible strings are 1110 and 0111 on a total of 16 strings so that the requested probability is $\displaystyle P=\frac{2}{16}=\frac{1}{8}$...

Is that correct?...

Kind regards

$\chi$ $\sigma$

 

[cygi1989]

Re: Probability of binary consecutive occurence with uneqaul probability

Yes, it's correct.
Regards to my formula it gives
(4 - 3 + 3 ) / (2^ 5) = 4 / 32 = 1 / 8.
My exact task is to find expected number of series of k - lenth for k = 1 .. 6, with P(1) = 800 / 2007 and N = 2007

 

[CaptainBlack]

Re: Probability of binary consecutive occurence with uneqaul probability

Yes, it's correct.
Regards to my formula it gives
(4 - 3 + 3 ) / (2^ 5) = 4 / 32 = 1 / 8.
My exact task is to find expected number of series of k - lenth for k = 1 .. 6, with P(1) = 800 / 2007 and N = 2007

Does this need to be an exact closed form solution or will an Monte-Carlo estimate be OK?

CB

 

[cygi1989]

Re: Probability of binary consecutive occurence with uneqaul probability

Exact result will be better I guess because I have calculated estimation by myself (I run this test for 1000 esembles) and I need to compare my result with expected ones. Anyway, what result will come from Monte Carlo method and how to calculate it?

 

[CaptainBlack]

Re: Probability of binary consecutive occurence with uneqaul probability

Exact result will be better I guess because I have calculated estimation by myself (I run this test for 1000 esembles) and I need to compare my result with expected ones. Anyway, what result will come from Monte Carlo method and how to calculate it?

It sounds like you already have a Monte-Carlo estimate (which would be produced by generating random strings of length 2007 and counting run lengths for lengths 1..6 and dividing the totals by 2007).

CB

 

[chisigma]

Re: Probability of binary consecutive occurence with uneqaul probability

I have been with this to some forums but it didn't help and I was advised to come to this one, so here is the question.

My task is to compute given N - length binary series and P = p(0) and 1-P = p(1) expected number of consecutive occurence of 0 or 1 of k - length. For example 10011100 has one serie of 1 with length 1 and one serie with length 3,
and also have two series of 0 of length 2.
I know that when the probability of 0 and 1 is equal than
Expected number of series of 0 or 1 of k-lenth in n-length binary numbers is = (n-k+3)/2^(k+2).
But what the case when probability of 0 is for example (0.4) or any another?

Sebastian

Let p the probability of the symbol 1 [and 1-p the probability of the symbol 0...]. A sequence of k consecutive ones is detected if in a string of k+2 symbols the first and the last are 0 and all others are 1. The probability of such a recurrence is...

$\displaystyle P_{k}= p^{k}\ (1-p)^{2}$ (1)

... and because in a sequence of n symbols there are n-k+3 possible subsequence on k+2 symbols, the expected number of k consecutive 1 is...

$\displaystyle E_{n,k}= (n-k+3)\ P_{k}=(n-k+3)\ p^{k}\ (1-p)^{2}$ (2)

For $p=\frac{1}{2}$ we find Your formula...

Kind regards

$\chi$ $\sigma$

 

[CaptainBlack]

Re: Probability of binary consecutive occurence with uneqaul probability

Let p the probability of the symbol 1 [and 1-p the probability of the symbol 0...]. A sequence of k consecutive ones is detected if in a string of k+2 symbols the first and the last are 0 and all others are 1. The probability of such a recurrence is...

$\displaystyle P_{k}= p^{k}\ (1-p)^{2}$ (1)

... and because in a sequence of n symbols there are n-k+3 possible subsequence on k+2 symbols, the expected number of k consecutive 1 is...

And are they independent/uncorrelated?

CB

 

[chisigma]

Re: Probability of binary consecutive occurence with uneqaul probability

And are they independent/uncorrelated?

CB

Is the 'they' related to the symbols, to the strings of k+2 symbols or to something else... please?...

Kind regards

$\chi$ $\sigma$

 

[CaptainBlack]

Re: Probability of binary consecutive occurence with uneqaul probability

Is the 'they' related to the symbols, to the strings of k+2 symbols or to something else... please?...

Kind regards

$\chi$ $\sigma$

The strings of k+2 symbols.

CB

 

[chisigma]

Re: Probability of binary consecutive occurence with uneqaul probability

The strings of k+2 symbols.

CB

Very well!... let's suppose to have a sequence of random binary symbols $a_{i}$ and, independently from i, is $P\{a_{i}=1\} = p \implies P\{a_{i}=0\}=1-p$. Now we consider a subsequence of k+2 consecutive symbols $\overrightarrow {a}_{i}= [a_{i},a_{i+1}, ... , a_{i+k+1}]$. Independently from i is...

$\displaystyle P_{i,k}=P\{\overrightarrow {a}_{i}= [0,1, ... . 1, 0]\}= p^{k}\ (1-p)^2$ (1)

... so that, if You observe m subsequences of k+2 consecutive symbols, the expected value of times on which is $\overrightarrow {a}_{i}= [0,1, ... , 1, 0]$ is $m\ P_{i,k}$...

Kind regards

$\chi$ $\sigma$

 

[cygi1989]

Re: Probability of binary consecutive occurence with uneqaul probability

Let p the probability of the symbol 1 [and 1-p the probability of the symbol 0...]. A sequence of k consecutive ones is detected if in a string of k+2 symbols the first and the last are 0 and all others are 1. The probability of such a recurrence is...

$\displaystyle P_{k}= p^{k}\ (1-p)^{2}$ (1)

... and because in a sequence of n symbols there are n-k+3 possible subsequence on k+2 symbols, the expected number of k consecutive 1 is...

$\displaystyle E_{n,k}= (n-k+3)\ P_{k}=(n-k+3)\ p^{k}\ (1-p)^{2}$ (2)

For $p=\frac{1}{2}$ we find Your formula...

Kind regards

$\chi$ $\sigma$

Absolutely brilliant. Many thanks!