# Probability of at least 2 adjacent events happening out of $n$ events

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?

-
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

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$.
$\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