Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
we may think on second measure $P^{+}$ as a coupling of $P^{-}$ and another Bernoulli scheme (that is, $B^{+}=\max(B^{-},C)$, where $C$ takes values 0,1 with suitable probabilities). In this case, any element of $cn$-neighborhood of $A=\{(B_1,\dots,B_n)\}$ w.r.t Hamming distance would hold with probabilty almost 1, provided $c$ is small enough. So, your question essentially reduces to isoperimetric inequalities on Bernoulli cube. Sorry that it is not answer, and is not very clear –  Fedor Petrov May 31 '10 at 20:59
add comment

3 Answers 3

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

share|improve this answer
    
Thanks Ryan, and thanks Fedor and Alekk too. I guess Fedor's suggestion of isoperimetric bounds is rather in the same direction as the question of influences. –  James Martin Jun 2 '10 at 11:18
    
Ryan, the question now becomes: can one find a bound on $\sum_i P_x(A_i)$ in terms of $P_x(A)$? In particular, if $P_x(A)$ is not too close to 0 or 1, does it follow that $\sum_i P_x(A_i)$ is reasonably large? –  James Martin Jun 2 '10 at 11:19
    
My impression is that the power of Friedgut's results is when the number of variables becomes large. Perhaps here, in looking for a bound that is uniform in $A$, it will be events that depend (or nearly depend) on a small number of variables that are the most important. –  James Martin Jun 2 '10 at 11:21
    
The rough philosophy of Friedgut's results is that events A which do not "essentially depend on a small number of coordinates" have the property that the derivative of $P_x(A)$ is large at the "critical probability" (i.e., the $x_c$ such that $P_{x_c}(A)$ is $1/2$). Thus the event has probability nearly $0$ or $1$ for almost all $x$. –  Ryan O'Donnell Jun 2 '10 at 22:27
add comment
up vote 1 down vote accepted

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

share|improve this answer
add comment

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 ?

share|improve this answer
    
Yes, but what then? How to estimate fom below $P^{\alpha}$. I guess, no uniform bound exists by trivial examples. –  Fedor Petrov May 31 '10 at 21:46
    
I do not think that there is a uniform bound from below: what would make you think that such a bound exists ? –  Alekk May 31 '10 at 22:25
    
As I understand, $u^{+}$ should depend only on $x^{-}$, $x^{+}$ and $u^{-}$. It is likely that it really is so, but I do not remember appropriate isoperimetric inequalities (see my comment to the initial post). –  Fedor Petrov May 31 '10 at 22:34
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.