probabilities of increasing events under different product measures.

Question

Let $(B_i)$ be a collection of i.i.d. random variables taking values 0 or 1.

Suppose $0 < x^- < x^+ < 1$. Consider two different "success probabilities" for the i.i.d. collection $B_i$: under measure $P^-$, each $B_i$ takes value 1 with probability $x^-$, while under measure $P^+$, each $B_i$ takes value 1 with probability $x^+$.

Consider increasing events which are functions of the collection $(B_i)$.

I'm looking for a result of the following form: given $u^-\in(0,1)$, there exists $u^+>u^-$ such that if $A$ is an increasing event with $P^-(A)\geq u^-$, then $P^+(A)\geq u^+$.

Perhaps I'm missing something simple.... There are easy arguments, for example, when $x^+\geq (x^-)^{1/2}$. (Then one can consider two independent samples of $(B_i)$ from $P^+$, and take the min of the two samples; this dominates a sample from $P^-$. From this the result follows with $u^+=(u^-)^{1/2}$.)

Answer 1

Say the $B_i$'s have success probability $x$, and let $P_x(A)$ denote the resulting probability of the increasing event $A$. Then the derivative of $P_x(A)$ at $x$ is equal to the "sum of the $x$-biased influences of $A$", which is a measure of the "edge-boundary" of $A$. Specifically, it equals $(1/x) \sum_{i} P_x(A_i)$, where $A_i$ is the event that $(B_1, \dots, B_n) \in A$ but $(B_1, \dots, -B_i, \dots, B_n) \notin A$. This is the "Russo-Margulis Lemma".

For particular events $A$, one can sometimes argue that the sum of the $x$-biased influences of $A$ is large based on symmetries of $A$. In that case, $P_x(A)$ increases quickly as a function of $x$. It's hard to describe more in a short space; you could take a look at Ehud Friedgut's survey on his work on "sharp thresholds": "Hunting for Sharp Thresholds", Random Structures Algorithms 26 (2005), no. 1-2, 37--51; also at http://www.ma.huji.ac.il/~ehudf/docs/survey.ps

Answer 2

I managed to hack out an answer to this question, and get the following result:

For any $k$ and $\epsilon$, if

$ x^+\geq 1-(1-x^-)^{1+1/k} $

and

$ P_{x^-}(A)\in (k\epsilon^{1/2}, 1-k\epsilon^{1/2}) $

then

$ P_{x^+}(A)-P_{x^-}(A)\geq \epsilon. $

Given $u^-$, $x^-$ and $x^+$, it's easy to use this to get a $u^+$ of the form I was asking for, by choosing appropriate $k$ and $\epsilon$.

As it happens, this result is not enough to get a lower bound on the influences that I was asking for under Ryan's post (such a bound would follow for example if one could replace the interval $(k\epsilon^{1/2}, 1-k\epsilon^{1/2})$ by $(k\epsilon, 1-k\epsilon)$ above).

The argument I've got is not deep but too long to post here. It involves considering $k+1$ copies of the collection of Bernoulli random variables, then comparing the probability of the event A occurring based on the max of all $k+1$ of the copies or based on the max of just $k$ of the copies. Looking at an appropriate sequence of conditional probabilities as more information about the Bernoulli collections is revealed, one shows that if there is enough randomness in the sequence for the probability of the event occurring to be significantly away from 0 and from 1, then also there must be a significant chance that the event occurs based on the max of $k+1$ copies but not on $k$ copies. For completeness and just in case anyone happens to care, I've put some messy notes about it at http://www.stats.ox.ac.uk/~martin/papers/increasing.pdf

Of course I'd still be very interested to hear of any references where this or something similar has been done. I wouldn't be surprised if a more general approach involving isoperimetry or concentration is possible.....

Answer 3

if the $C_i$ are Bernoulli rvs independent from everything, with $P(C_i=1)=\alpha$ and $\alpha(1-x^-)=x^+$ then $B_i \wedge C_i$ are also Bernoulli rvs with success rate $x^+$. Hence $P^+(A) \geq P^-(A) + (1-P^-(A))P^{\alpha}(A)$, isn't it ?