Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I've been having some trouble with what I thought at first should be quite a simple problem.

I have n events in total and they can only be 0 or 1 (so it's a binomial). Lets say the probability of a single event being equal to 1 is X [and therefore $P(1)=X$ and $P(0)=1-X$].

I'm only interested in situations where 2 adjacent events are equal to 1. i.e. $P(11), P(110), P(011), P(111)$ but not $P(101)$ because the events equal to 1 are not adjacent.

I'm trying to find how the probability of having at least 2 adjacent events out of n total.

So far I've managed to get to $n=5$, but i'm struggling to find a solution to the general problem

$n=2, P=X^2$

$n=3, P=X^3 + 2(X^2)(1-X)$

$n=4, P=X^3 + 4(X^3)(1-X) + 3(X^2)((1-X)^2)$

$n=5, P=X^4 + 5(X^4)(1-X) + 9(X^3)((1-X)^2) + 4(X^2)((1-X)^3)$

Any Ideas?

share|improve this question
    
Try computing the probability of not having two adjacent successes. This boils down to understanding the number of ways in which you can distribute $k$ successes, $k\leq n/2$, on $n$ events, such that no two successes are adjacent. –  Eckhard Jan 10 '13 at 16:36
add comment

1 Answer 1

Call $T$ the time when 11 first appears and $S$ the number of events before 11 first appears starting from 1. Then $T=1+T'$ where $T'$ is distributed like $S$ with probability $x$ and like $T$ with probability $1-x$. Likewise, $S=1+S'$ where $S'$ is $0$ with probability $x$ and distributed like $T$ with probability $1-x$. Thus, for every $|z|\leqslant1$, $$ \mathbb E(z^T)=s(x\mathbb E(z^S)+(1-x)\mathbb E(z^T)),\qquad \mathbb E(z^S)=s(x+(1-x)\mathbb E(z^T)), $$ that is, $$ \mathbb E(z^T)=\frac{x^2z^2}{1-(1-x)z-x(1-x)z^2}. $$ Let $u$ and $v$ denote the two positive real numbers such that $u-v=1-x$ and $uv=x(1-x)$, then $1-(1-x)z-x(1-x)z^2=(1-uz)(1+vz)$ hence $$ \mathbb E(z^T)=\frac{x^2z^2}{u+v}\left(\frac{u}{1-uz}+\frac{v}{1+vz}\right)=\sum_{n\geqslant2}t_nz^n, $$ where $$ t_n=\frac{x^2}{u+v}\left(u^{n-1}+(-1)^{n}v^{n-1}\right). $$ Thus $t_n=\mathbb P(T=n)$ for every $n\geqslant2$ and you are asking for $$ \mathbb P(T\leqslant n)=1-\sum_{k\geqslant n+1}t_k=1-\frac{x^2}{u+v}\left(\frac{u^n}{1-u}+(-1)^{n+1}\frac{v^n}{1+v}\right), $$ where $0\lt v\lt u\lt1$ since $$ u=\frac{\sqrt{(1-x)(1+3x)}+1-x}2,\qquad v=\frac{\sqrt{(1-x)(1+3x)}-(1-x)}2. $$ Sanity checks: $\mathbb P(T\leqslant1)=0$, $\mathbb P(T\leqslant2)=x^2$, $\lim\limits_{n\to\infty}\mathbb P(T\leqslant n)=1$.

share|improve this answer
    
What do E and z represent? –  user1696811 Jan 10 '13 at 17:42
    
$\mathbb E$ = expectation, $z$ = a variable in the complex unit disk, used as the argument of the generating function of the distributions of $T$ and $S$. –  Did Jan 10 '13 at 20:30
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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