MAKE A BETTER PREDICTION ABOUT FUTURE EVENTS
What is Expected Value
There is a concept in Probability Theory called Expected Value(EV). So what the
Internet says about EV.
Definition: “Expected value(EV) is the average value of a random variable over a large
number of experiments”.
OK, but it looks like “Mean” to me? Then what is the difference between EV and Mean?
Let’s play a simple game. I come up to you and offer you to play coins, if it’s heads, I get a dollar, if it’s
tails, you get three dollars.Easy bet right? The mean is 3+(−1)/2 = +1. The mean outcome is +1 for
you. But, what I don’t tell you is that the coin flips heads with probability of .8 and tails with probability
of .2. The expected value is not +1 for you, but instead (0.8∗−1)+(0.2∗3)=−0.2. The expected value is
the weighted mean for a random event like described above. The mean is the expected value but for
samples,instead of random variables.
Hmmmm, But still I am not getting what the heck this EV is? Link-2
We can divide most the experiments in two categories i.e; is Deterministic and Probabilistic.
Keeping deterministic experiments aside for a while let us focus more on probabilistic
situations. In case of probabilistic events, they are the events whose possible outcomes are
known but what’s not known is how many of each of those outcomes will actually turn up?
Basically EV is a way to think about all possible future events as a single number. We can do
this by considering every single reasonable outcome, how likely those outcomes are and how
much value each outcome provides and then sum it all up.Mathematically, If X is an event the
its expected value is -:
EV(X) = P(X)* X ---- Eq-1
An important theorem for EV is called Linearity of EV.
E(X+Y) = E(X) + E(Y) ---- Eq-2
Eq-2 states that if we have to find the EV of multiple events then simply add all the EV’s of individual
events.
Example: Let's say we bought a lottery ticket for 2$. We will win 10$ with probability 10%, and 20$
with probability 2%. On average, it gives us 0.1·10 + 0.02·20 = 1.4. The computed average is called the
expected value.
Mathematically, if P(% to win 10$) = 10/100 = 0.1
P(% to win 20$) = 2/100 = 0.02
Then EV = P(% to win 10$) * 10$ + P(% to win 20$) * 20$
= 0.1*10 + 0.02*20
= 1.4 which is off after buying the ticket.
Practical application of Expected Value(EV)
What EV is?
How to use EV
Why it’s Vital...
+EV -EV
+EV : A play is Expected to be profitable in the long run.
-EV : A play is Expected to lose money in the long run.
Now, from Eq-1 we can get, the following equation can be used in the game of poker.
EV = [%W * $W] - [%L * $L]
Where %W = How often we’ll win
$W = How much $ we’ll win
%L = How often we’ll lose
$L = How much $ we’ll lose
Let’s play a game ....
If we flip a coin we get +$3 on heads and -$1 on getting tails. Now we want to calculate whether
we are in loss or in profit in the long run.
Using the above formula of EV %W and %L are 0.5 that is the probability of winning and losing.
Value of $W and $L are +$3 and $1 respectively.
Putting the values in we get
EV = 0.5*3 - 0.5*1
= 1
So we are in profit of +$1 in the long run.
Programming problem based on Expected Value(EV)
Problem : 453 A : Little Pony and Expected Maximum(codeforces)
Goal: We compute the number of times i appears as the maximum number among the n rolls.
To achieve this goal we can make certain observations these are .
Observation 1:
m = No.of faces on the dice
n = No. of time dice is tossed
If m = 3 and n =1
1
2
3
If m = 3 n = 2
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3
If m = 3 and n = 3
1 1 1
1 1 2
1 2 1
2 1 1
1 1 3
1 3 1
3 1 1
2 2 2
2 2 1
2 1 2
1 2 2
2 2 3
2 3 2
3 2 2
3 3 3
3 3 1
3 1 3
1 3 3
3 3 2
3 2 3
2 3 3
1 2 3
2 1 3
2 3 1
1 3 2
3 1 2
3 2 1
Now from above three experiments we get following observations:
Total number of cases are as follows: m^n.
Since all the events are independents so the P(Toss) is the probability of each tossing of dice.
P(Toss) = 1/m^n
If we consider case III then P(Getting 1) = (Total No. of 1)/ m^n
P(Getting 2) = (Total no of 2) / m^n
So, P( getting ith face on dice) = (total number of i’s)/m^n
Now we know EV(i) = (Value of i)*P(Getting i)
Or we can say EV can be stated as
Our major task is to find the total count for each ith value.
Observation 2:
For i to be maximum, we may not have any number greater than i appearing. In other words,
there are in ways to do this; each roll has i possibilities, and there are n rolls.
For example: For i = 1 there is only 1 possibility
For i = 2 there are two possibilities that are 1 and 2.
For i = 3 there are three possibilities that are 1,2 and 3.
For i = 4 there are four possibilities that are 1,2,3 and 4.
For i = 5 there are five possibilities that are 1,2,3,4 and 5.
.
.
.So on...
Now suppose we have to find the possibility for 2 then we take 1 and 2 in consideration.
For example if we roll two dice and finding the max for 2 then following cases are possible.
1 1 MAX = 1
1 2 MAX = 2
2 1 MAX = 2
2 2 MAX = 2
Now in case of i = 2 MAX =1 is not considerable so we subtract all the possibilities for (i-1).
Hence, 
Code for 453A
#include<bits/stdc++.h>
#define fast_in ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
int main()
{
fast_in;
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
double m,n,answer = 0;
scanf("%lf%lf",&m,&n);
for(int i=1;i<=m;i++){
answer += i*(pow(i/m,n)-pow((i-1)/m,n));
}
printf("%0.12lf",answer);
return 0;
}
Note(For more reference)
We compute the number of times i appears as the maximum number among the n rolls.
However, in case none of the rolls gives i, we cannot have i appearing as maximum; it doesn't even appear.
Thus we must subtract with the number of cases this happens, which is (i - 1)n for the same reason as above.
Thus i appears as maximum in in - (i - 1)n cases.
Now we just use the expected value formula: sum of values over all cases divided by the number of cases.
The sum of values can be rephrased as sum of (each value times number of cases); in other words,
. For each i = 1, 2, ..., m, the value is the maximum, namely i, and the number
of cases has been computed above. The total number of cases is clearly mn.
Thus we get the formula: .
Now, it's obvious that we will get various overflows; just take i = 100000, n = 100000, and in = 100000100000 =
10500000. Thus we should merge in the denominator to the numerator, producing an easier-to-compute
. We get losses of precision, but they don't matter.
Bibliography
Programming Problems
Comments
Post a Comment