Binomial coefficient fun, mathematicians welcome

Factual Questions
1

This is not for homework. This is not for work work either. This is related to some stuff at work that I’ve already solved numerically, but I’m wondering if there’s an elegant algebraic solution, and hoping that a more mathematically astute Doper can lend a hand.

Let me introduce Gary the Gambler. Gary gambles, but he’s not addicted to gambling. To prove to himself that he’s not addicted, whenever he goes out for a night of gambling, he sets a limit on the number of games he’ll let himself lose. Once he’s lost that many games, regardless of how many he’s won, he’ll quit for the night and head home to play Farmville. But some nights he won’t hit his limit. Maybe he gets on a winning streak until it gets to be closing time at the gambling den, or maybe the DVR is busted and Fringe is on, or he gets kicked out for excessive punning or whatever.

What we’d like to know is, assuming we know the maximum number of games he’d be able to play on a given night, and assuming he has a constant probability of winning a given game, how many games do we expect him to lose?

Let’s call the probability that he’d win a given game a. For convenience, we’ll call the probability that he’ll lose a game b even though by definition it’s merely 1 - a. The maximum number of games he can play that night we’ll call m and his self-imposed loss limit we’ll call L.

A while back, Omphaloskeptic (if I recall correctly) mentioned in this forum that if you consider the generating polynomial (bx + a)[sup]m[/sup], the probability that there will be n successes (in our case, losses) in m trials will be equal to the coefficient for x[sup]n[/sup] when you multiply out the terms. For example, if Gary will only have a chance to play 5 games that night, then the probability that he’ll lose exactly 3 games is (5 choose 3) * b[sup]3[/sup] * a[sup]2[/sup]. If a = 75%, then there’s a 10 * 0.25[sup]3[/sup] * 0.75[sup]2[/sup] =~ 8.8% chance that he’ll lose 3 games.

To calculate the expected number of losses, then, we need merely multiply each coefficient by the number of losses associated with that term and sum up those values. For a given term where n <= L, this is multiplying the coefficient by the power of x that it’s associated with. When m <= L, this turns out to be calculating the derivative of our generating polynomial with respect to x and solving for x = 1.

This breaks down, however, then m > L. I’ve been trying to think of some kind of manipulation of Omphaloskeptic’s generating polynomial that will somehow remove the terms that have n > L and put back in the coefficients for those terms but multiplied by x[sup]L[/sup]. But I’ve had no luck, having neither a strong enough mathematical background nor powerful enough Google-fu.

Any ideas?

2

First let’s assume M > L otherwise he just plays M games every night and the expected number of losses is aM

Then he can lose L straight games with probability a[sup]L[/sup]

or he can lose L-1 games out of the first L then lose the last with probability [sub]L-1[/sub]C[sub]L[/sub]a[sup]L[/sup]b

or he can lose L-1 games out of the first L+1 then lose the last with probability [sub]L-1[/sub]C[sub]L+1[/sub]a[sup]L[/sup]b[sup]2[/sup]

…

or he can lose L-1 games out of the first M-1 then lose the last with probability [sub]L-1[/sub]C[sub]M-1[/sub]a[sup]L[/sup]b[sup]M-L[/sup]

or he can lose L-1 out of M with probability [sub]L-1[/sub]C[sub]M[/sub]a[sup]L-1[/sup]b[sup]M-L+1[/sup]

…

or he can lose 0 out of M with probability b[sup]M[/sup]

Multiply each of those by the number of losses and add.

ETA [sub]i[/sub]C[sub]j[/sub] is the binomial coefficient.

3

I don’t see how to do it with generating functions, but there’s a random walk approach that shouldn’t be too bad. Gary starts at (0, 0), and when he’s at (i, j), he moves to (i + 1, j) with probability p, and (i + 1, j + 1) with probability 1 - p. The game is over when the first coordinate hits m or the second coordinate hits L. There’s a pretty straightforward recurrence relation based on the next step from any given position, but I’m not up to working it out tonight.

4

Yes, I’ve already solved it numerically. It’s not that much work to compute it that way, but I was hoping to be able to put a nice function in a slide to describe what I’m calculating, even if solving it algebraically is more work in practice.

5

Oh, and the numeric solution:

Create array A of size L+1
A[0] = 1
A[1 … L] = 0
for(i = 0 to m-1) doCreate array B of size L
for(j = 0 to L-1) do[INDENT]B[j] = A[j] * bdone
A[0] = A[0] - B[0]
for(j = 1 to L-1) doA[j] = A[j] - B[j] + B[j-1]done
A[L] = A[L] + B[L-1]
[/INDENT]done
result = 0
for(i = 1 to L) doresult = result + A* * idone

So for the case where a = 75%, b = 25%, m = 5, L = 3
Initially A = [1 0 0 0]
Iteration 1
B = [0.25 0 0]
A = [0.75 0.25 0 0]
Iteration 2
B = [0.19 0.06 0]
A = [0.56 0.38 0.06 0]
Iteration 3
B = [0.14 0.09 0.2]
A = [0.42 0.42 0.14 0.02]
Iteration 4
B = [0.11 0.11 0.04]
A = [0.32 0.42 0.21 0.05]
Iteration 5
B = [0.08 0.11 0.05]
A = [0.24 0.40 0.26 0.10]
Result = 0.40 * 1 + 0.26 * 2 + 0.10 * 3 = 1.23

6

The solution for the unbounded problem is, in your example:
1 * (5a^4b) + 2 * (10a^3b^2) + 3 * (10a^2b^3) + 4 * (5ab^4) + 5 * (b^5)
with the front multipliers (1, 2, 3, 4, 5) being the number of losses associated with that term. With a limit (e.g. 3) on losses, simply replace each multiplier larger than 3 with 3:
1 * (5a^4b) + 2 * (10a^3b^2) + 3 * (10a^2b^3) + 3 * (5ab^4) + 3 * (b^5)

7

Lets let K be the number of wins.

The two cases is either K<=M-L and he stops at L losses or K>M-L and he stops with M games.

In the first case the probability of getting K wins is defined by thenegative binomial.

In the second it is defined by the binomial you mentioned in your OP.
Alternatively you could solely use the binomial distribution but when computing the expectation set the values for for all cases in which the number of losses was more than L, set it equal to L.

From the expected losses you can calculate the expected number of games and wins by

E(games) = Expected (losses)/b
E(wins) = a*Expected (losses)/b