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.

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.