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

Improve this question
$\endgroup$
4
  • 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, 2012 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, 2012 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, 2012 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, 2012 at 5:34

2 Answers 2

Reset to default
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$.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Not exactly what I expected but that's it. Thank you $\endgroup$
    – Rodolphe
    Dec 12, 2012 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, 2012 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, 2012 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, 2012 at 9:33
0
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\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, 2013 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.