1
$\begingroup$

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

| cite | improve this question | |
$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Thierry Zell Dec 10 '12 at 13:37
  • 1
    $\begingroup$ @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? $\endgroup$ – Pietro Majer Dec 10 '12 at 16:14
  • $\begingroup$ 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 ?$$ $\endgroup$ – Kevin P. Costello Dec 11 '12 at 0:54
  • $\begingroup$ 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... $\endgroup$ – fedja Dec 13 '12 at 5:34
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Not exactly what I expected but that's it. Thank you $\endgroup$ – Rodolphe Dec 12 '12 at 5:06
  • 2
    $\begingroup$ 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... $\endgroup$ – fedja Dec 12 '12 at 5:44
  • $\begingroup$ 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. $\endgroup$ – Pietro Majer Dec 12 '12 at 9:32
  • $\begingroup$ @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. $\endgroup$ – Pietro Majer Dec 12 '12 at 9:33
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Would you make your comment to be a more complete answer? For example, how do you get the lower bound? $\endgroup$ – András Bátkai Sep 4 '13 at 19:53

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.