Mixing
upper bound on probability random variable is at most a constant times the mean
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
I would like to upper bound the probability
$$Pr[X leq C cdot E[X]]$$ where the upper bound involves only the expectation and the constant $C$. The best I could find is in the case $X leq B$, ($B$ may be another r.v. or a constant) for all $X$, where we have
$$ Pr[ X leq C cdot E[X] ] leq fracE[B-X]B-Ccdot E[X] $$
(Cor 2 in http://www.cs.ubc.ca/~nickhar/W12/Lecture2Notes.pdf )
The random variable X is discrete and takes a finite number of values (I want to avoid an upper bound that depends on the size of the domain).
probability probability-theory discrete-mathematics inequality
asked Jul 31 at 9:00
Kyriakos Kats
1
add a comment |Â
up vote
0
down vote
favorite
I would like to upper bound the probability
$$Pr[X leq C cdot E[X]]$$ where the upper bound involves only the expectation and the constant $C$. The best I could find is in the case $X leq B$, ($B$ may be another r.v. or a constant) for all $X$, where we have
$$ Pr[ X leq C cdot E[X] ] leq fracE[B-X]B-Ccdot E[X] $$
(Cor 2 in http://www.cs.ubc.ca/~nickhar/W12/Lecture2Notes.pdf )
The random variable X is discrete and takes a finite number of values (I want to avoid an upper bound that depends on the size of the domain).
probability probability-theory discrete-mathematics inequality
asked Jul 31 at 9:00
Kyriakos Kats
1
add a comment |Â
up vote
0
down vote
favorite
up vote
0
down vote
favorite
I would like to upper bound the probability
$$Pr[X leq C cdot E[X]]$$ where the upper bound involves only the expectation and the constant $C$. The best I could find is in the case $X leq B$, ($B$ may be another r.v. or a constant) for all $X$, where we have
$$ Pr[ X leq C cdot E[X] ] leq fracE[B-X]B-Ccdot E[X] $$
(Cor 2 in http://www.cs.ubc.ca/~nickhar/W12/Lecture2Notes.pdf )
The random variable X is discrete and takes a finite number of values (I want to avoid an upper bound that depends on the size of the domain).
probability probability-theory discrete-mathematics inequality
asked Jul 31 at 9:00
Kyriakos Kats
1
I would like to upper bound the probability
$$Pr[X leq C cdot E[X]]$$ where the upper bound involves only the expectation and the constant $C$. The best I could find is in the case $X leq B$, ($B$ may be another r.v. or a constant) for all $X$, where we have
$$ Pr[ X leq C cdot E[X] ] leq fracE[B-X]B-Ccdot E[X] $$
(Cor 2 in http://www.cs.ubc.ca/~nickhar/W12/Lecture2Notes.pdf )
The random variable X is discrete and takes a finite number of values (I want to avoid an upper bound that depends on the size of the domain).
probability probability-theory discrete-mathematics inequality
asked Jul 31 at 9:00
Kyriakos Kats
1
asked Jul 31 at 9:00
Kyriakos Kats
1
asked Jul 31 at 9:00
Kyriakos Kats
1
asked Jul 31 at 9:00
Kyriakos Kats
1
1
add a comment |Â
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
2
down vote
There may be no upper bound for $Pr(X leq C cdot E[X])$ apart from $1$.
Consider $Pr(X=0)=1-frac1n$ and $Pr(X=n)=fracmun$ and then let $n$ increase
As for a lower bound when $X$ is non-negative, try Markov's inequality to get $Pr(X leq C cdot E[X]) ge 1 - frac1C$
answered Jul 31 at 9:07
Henry
92.8k469147
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
There may be no upper bound for $Pr(X leq C cdot E[X])$ apart from $1$.
Consider $Pr(X=0)=1-frac1n$ and $Pr(X=n)=fracmun$ and then let $n$ increase
As for a lower bound when $X$ is non-negative, try Markov's inequality to get $Pr(X leq C cdot E[X]) ge 1 - frac1C$
answered Jul 31 at 9:07
Henry
92.8k469147
add a comment |Â
up vote
2
down vote
There may be no upper bound for $Pr(X leq C cdot E[X])$ apart from $1$.
Consider $Pr(X=0)=1-frac1n$ and $Pr(X=n)=fracmun$ and then let $n$ increase
As for a lower bound when $X$ is non-negative, try Markov's inequality to get $Pr(X leq C cdot E[X]) ge 1 - frac1C$
answered Jul 31 at 9:07
Henry
92.8k469147
add a comment |Â
up vote
2
down vote
up vote
2
down vote
There may be no upper bound for $Pr(X leq C cdot E[X])$ apart from $1$.
Consider $Pr(X=0)=1-frac1n$ and $Pr(X=n)=fracmun$ and then let $n$ increase
As for a lower bound when $X$ is non-negative, try Markov's inequality to get $Pr(X leq C cdot E[X]) ge 1 - frac1C$
answered Jul 31 at 9:07
Henry
92.8k469147
There may be no upper bound for $Pr(X leq C cdot E[X])$ apart from $1$.
Consider $Pr(X=0)=1-frac1n$ and $Pr(X=n)=fracmun$ and then let $n$ increase
As for a lower bound when $X$ is non-negative, try Markov's inequality to get $Pr(X leq C cdot E[X]) ge 1 - frac1C$
answered Jul 31 at 9:07
Henry
92.8k469147
answered Jul 31 at 9:07
Henry
92.8k469147
answered Jul 31 at 9:07
Henry
92.8k469147
answered Jul 31 at 9:07
Henry
92.8k469147
92.8k469147
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2867821%2fupper-bound-on-probability-random-variable-is-at-most-a-constant-times-the-mean%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password