# Apparently simple probability

Hello,

Let $x\in[0;1]$ and $(B_i)_i$ be events defined by $P(B_i)\leq x, \forall i$. Furthermore, this inequality is independent of the other events $B_i$ but the events are not necessarily independent.

I want to upperbound the probability of $A_k = (B_1\cup B_2)\cap (B_2\cup B_3)\cap\cdots\cap (B_k\cup B_{k+1})$. The first terms give (I simplified each $A_i$):

$$P(A_1)\leq 2x$$

$$P(A_2)=P((B_1\cap B_3) \cup B_2)\leq x^2 + x$$

$$P(A_3)=P((B_2\cap B_3)\cup(B_2\cap B_4)\cup(B_1\cap B_3))\leq 3x^2$$

What's the upperbound for any $k$ ?

Thank you very much

-
If your events are not independent, there is no way this works, is there? For $x$ small enough, take $B_1=B_3$ totally disjoint from $B_2$. Then, $P(A_2)=2x$ which is larger than the bound of $x^2+x$ that you have. – Thierry Zell Dec 10 '12 at 13:37
@Rodolphe: you should state more precisely the bound you want. I understand that you want $$\alpha(x,k):=\sup \mathbb{P}(A_k)$$ where the supremum is taken over all probability spaces $(\Omega,\mathbb{P}, \mathcal{S})$ and all sequences $(B _i) _ i\subset\mathcal{S}$ of events with $\mathcal{P}(B _ i)\le x$. Is it so? – Pietro Majer Dec 10 '12 at 16:14
By "this inequality is independent of the other events $B_i$", do you mean that for any disjoint $S$ and $T$ and any $i \notin S \cup T$ that $$P(B_i \vert B_j \textrm { holds for all } j \in S \textrm{ but does not hold for any } j \in T) \leq x ?$$ – Kevin P. Costello Dec 11 '12 at 0:54
As far as I understand it, the meaning is that for every event $A$ generated by all events $B_j$ other than $B_i$, we have $P(B_i|A)\le x$ but I'd prefer the OP to confirm it before I start thinking of the problem... – fedja Dec 13 '12 at 5:34

Let $m:=\big\lfloor\frac{k+1}{2} \big \rfloor$. Then, assuming $\mathbb{P}(B _ i)\le x$, $$\mathbb{P}\big((B _ 1\cap B _ 2) \cup(B _ 2\cap B _ 3) \dots \cup(B_k\cap B_{k+1})\big)\le mx\wedge 1\, ,$$ which follows immediately by the inclusion $$(B _ 1\cap B _ 2) \cup(B _ 2\cap B _ 3)\cup \dots \cup(B_k\cap B_{k+1}) \subset B _ 2 \cup B _ 4\cup \dots \cup B_ {2m} \, .$$ The equality is realized in any atomless measure space, taking a sequence of measurable sets $(B _ i) _ {i\ge1}$ such that $B_{2i-1}=B_{2i}$ and $\mathbb{P}(B _ {2i})=x\wedge \frac{1}{m}$, for all $1\le i\le m$, $B_{2i}\cap B_{2j}=\emptyset$ for $i\neq j$,
and $B _ i=\emptyset$ for all $i > m$.

-
Not exactly what I expected but that's it. Thank you – Rodolphe Dec 12 '12 at 5:06
Pietro, how can you have $B_{2i-1}=B_{2i}$ if Rodolphe told us that $P(B_i\cap B_j)\le xP(B_j)$ for all $j\ne i$? One of us is confused here... – fedja Dec 12 '12 at 5:44
Well, I wrote the inequality that follows from $(B _i)$ being any sequence of measurable sets of measure not greater than $x$, just to make it clear what happens if no other assumption are made. – Pietro Majer Dec 12 '12 at 9:32
@Rodolphe: thank you, but you don't need to accept an answer if it is not what you are looking for. Actually, if you un-accept it maybe we can discuss it with other people. I'm quite sure it is an interesting optimization problem, if you make it more clear. – Pietro Majer Dec 12 '12 at 9:33

Looks like an application of Asymmetric Local Lemma http://en.wikipedia.org/wiki/Lov%C3%A1sz_local_lemma

-
Would you make your comment to be a more complete answer? For example, how do you get the lower bound? – András Bátkai Sep 4 '13 at 19:53