Help with Expected Value.

Arithmetic, algebra, number theory, sequence and series, analysis, ...
Post Reply
Posts: 41
Joined: Tue Sep 06, 2011 3:56 am

Help with Expected Value.

Post by drwhat » Fri Jun 26, 2015 6:54 am

EV problems have always been the hardest for me to figure how to get a formula for them, esp open ended ones where the results are not guaranteed to happen. (e.g how many times do you have to pick a random number between 1-1000 before you choose a 1).

So I have problem I'm trying to write an app for based on Marvel Heroes 2015 game. There are 30+ heroes you can purchase. Each of them cost 200,400,600 credits. However, you can purchase a random hero for 175 credits. But if you get a duplicate too bad your out 175.

Assuming the following:
There are 30 heroes: 10 of each cost (200,400,600).
Let a,b,c be the number of 200,400,600 heroes you own.
You are going to buy 175 cost boxes until you receive a hero you don't own.
F(a,b,c) = Expected number of boxes you need to buy to get a hero you don't own.
G(a,b,c) = Expected profit (Positive/negative) from doing so.

if a=b=c = 0 (you don't own any yet) it pretty trivial
F(0,0,0) = 1
G(0,0,0) = 225

I've done a lot of searching to figure how to setup an EV problem of this nature, and I can easily see how to calculate G(a,b,c) given only 1 attempt. (regardless of the values of a,b,c). But I can't seem to figure out how to setup a formula for F(a,b,c) iterating over multiple tries given that you don't know when (if ever ) you will succeed? Any help or links to a site would be helpful. All my google searches seem to end up on sites that explain EV in terms of a finite set of items with fixed probability and only 1 try at choosing them.

Just after posting I stumbled across a site I think helped: I believe this is the formula I need .. F(a,b,c) = x
x = (x+1)(a/30)+(x+1)(b/30)+(x+1)(c/30)+(30-a-b-c)/30

and given uneven number of 200,400,600 heroes where A,B,C are the total of each (instead of 10 each)
x=(A+B+C)/(A+B+C-a-b-c) ?

User avatar
Posts: 528
Joined: Tue Mar 25, 2008 3:57 pm

Re: Help with Expected Value.

Post by jaap » Fri Jun 26, 2015 8:51 am

Let's take a simpler example. When using a pair of ordinary six-sided dice, what is the expected number of times you need to roll them to get a double six?

Let E be that expected number of rolls.

The probability of rolling sixes immediately on the first throw is 1/36. If you don't get sixes, then you have 'wasted' a roll, but are otherwise in exactly the same situation as you were before the first throw - still the same probabilities and the expected number of further rolls needed to get sixes is still the same value E.

So you either use 1 roll (1/36 probability) or need 1+E rolls (with 35/36 probability), which gives:
E = 1/36 * 1 + 35/36 * (1+E)
From which we get:
E = 1 + 35/36 * E
1/36 * E = 1
E = 36

More generally, if you have probability p of winning at each roll, the expected number of rolls is 1/p.

In your problem you don't have 1/36 probability of 'winning', but there are 30-a-b-c heroes you don't have out of 30, so you have (30-a-b-c)/30 probability of winning at each purchase. This means you expect to need 30/(30-a-b-c) purchases to gain a new hero.

Calculating G(a,b,c) can be done in a similar way, but it is easier to reuse the above result. It is now merely a question of finding the relative probabilities of getting an a, b, or c hero in that last purchase where you finally gain a hero. In other words, you need the conditional probabilities P(getting an a/b/c hero in a purchase, given that the purchase does gain you a hero and you have a,b,c of each). These are (10-a)/(30-a-b-c), (10-b)/(30-a-b-c), and (10-c)/(30-a-b-c).

So now you can put together the formula for G(a,b,c):

G(a,b,c) = -175*30/(30-a-b-c) + 200*(10-a)/(30-a-b-c) + 400*(10-b)/(30-a-b-c) + 600*(10-c)/(30-a-b-c)
G(a,b,c) = [ -175*30 + 200*(10-a) + 400*(10-b) + 600*(10-c) ]/(30-a-b-c)

Or more generally:

G(a,b,c) = [ -175*(A+B+C) + 200*(A-a) + 400*(B-b) + 600*(C-c) ]/(A+B+C-a-b-c)

Post Reply