View Question
Q: Need formula for the expected value of a specific situation ( No Answer,   3 Comments )
 Question
 Subject: Need formula for the expected value of a specific situation Category: Science > Math Asked by: jbejaran-ga List Price: \$20.00 Posted: 20 Oct 2006 08:34 PDT Expires: 19 Nov 2006 07:34 PST Question ID: 775366
 ```Assume I have a random-number picking contest. I can pick random numbers between 1 and n. The winner of the contest is the first number that gets picked m times. The minimum number of picks I'll have to make is m which is the case where I pick the same number every time. The maximum number of picks I'll have to make is ((m-1)*n)+1 which is the case where I've picked each number m-1 times, and the next number picked will definitely be a winner. My question is, what is the expected (or average) number of picks I'll need to make for a winner to be crowned?``` Clarification of Question by jbejaran-ga on 20 Oct 2006 10:06 PDT ```The reason I'm asking this is that I'm building a simulated horse-racing spreadsheet/application for my company's casino night, and the answer to this question will become part of the formula that determines how much advantage or disadvantage one horse has over the other. This is not a homework assignment or anything like that. Also, any insights into understanding the formula above and beyond just the actual formula would be very welcome. Thanks very much.```
 There is no answer at this time.

 ```This is essentially a problem in combinatorics. Consider the variables X1,X2,...,Xn where n is the ticket numbers.Suppose we pick tickets k times, we want to know in how many of them one particular number got picked more than m times. This is equivalent to the following: how many non-negative integral solutions does the following equation can have: X1 + X2 + ... + Xn = k ................. (1) satisfying the condition that at least one of the variables is greater than or equal to m. Which is equivalent to: Total number of non-negative solutions of (1) - Solutions in which all of the variable values are less than m. These values can be calculated using IEP(inclusion-exclusion principle).Look at the following link for details: http://mathforum.org/library/drmath/view/52269.html For a particular k, we therefore, get the probability, call this P(k). Now your expected value is simply: summation(from m to (n-1)*m+1) of summand P(k)*k computer implementation will require some care as you may not be able to directly evaluate a combinatorial sum (as you might need to calculate large factorials and do arithmetic with them).```
 ```I don't know if this will help you at all but here is an alternate method for determining the winner. In most programming languages getting a random number returns a number greater than or equal to zero and less than 1. (0 <= x < 1) Here is the idea: Suppose that you have 5 horses all with equal odds of winning. The distribution for the random number would look like: 0.0 <= H1 < 0.2 0.2 <= H2 < 0.4 0.4 <= H3 < 0.6 0.6 <= H4 < 0.8 0.6 <= H5 < 1.0 Here is is easy to see that each horse has an equal chance of being picked. (20%) (i.e if the random number is 0.3434, Horse 2 would win) Now to play with the odds a little bit...simply start changing the ranges. i.e. suppose you wanted the following percentages of winning: H1 30% H2 15% H3 10% H4 20% H5 25% Then the distribution would look like: 0.00 <= H1 < 0.30 0.30 <= H2 < 0.45 0.45 <= H3 < 0.55 0.55 <= H4 < 0.75 0.75 <= H5 < 1.00 One note is that this method only works for the final outcome of the race not for the distance along the way. (I gather the "m" represents the total distance of the course.) Don't know if this helps at all, I just thought that I would mention an alternate solution.```
 ```I too don't quite have the answer, but think of it like rolling a die or playing roulette. There's nothing special about this other than to think of the problem in aggregate, as though you are looking for X rolls of a roulette wheel to get 5 (m) occurences of 00 (here n=38). I thought this could be expressed as X choose m [ C(X m) ] = X! / m! (X-m)! time (1/n)^m, which is the probability of each race. I figured that finding X that would cause the expression to be greater than .5 would be the answer you're looking for. This is not correct unfortunatley, but along with looking up the Birthday Paradox and this: http://discuss.fogcreek.com/techInterview/default.asp?cmd=show&ixPost=1642, it might lead you to an answer.```