Making change probability question
 

so I originally posted this in the Math forum, then I realized there actually is a Probability forum. Like probability isn't math, but ok.


~~~~

So I was working the cash register today for my job, and this problem came to mind. (Yup, I'm a nerd, I like to think about math when I'm bored)

Lets say you had an infinite jar of coins. The probabilities of drawing out a quarter is 1/4, a dime is 1/4, a nickel is 1/4 and a penny is 1/4.

(and if anyone has issues with an infinite jar of coins, just take a jar of 4 coins, one of each, each time you draw one out you replace it. Problem is the same)

What is the expected number of coins you draw before you have exact change for a dollar?

What if the jar is finite with 100 of each?

What if the jar is finite with 4 quarters, 10 dimes, 20 nickels, and 100 pennies?

I can't seem to think of any way to solve this without brute forcing it, listing off all the possibilities of making change for a dollar and then calculating the expected draws from that. But i thought it was an interesting problem

Re: Making change probability question
 

You don't need brute force. If you have exactly a dollar, then of course you have change for a dollar. If you have more than a dollar then you have change for a dollar except for one case, three quarters and three dimes.

Therefore, figure out the expected number of coins you draw before getting $1.00 or more; and subtract off the correction for three quarters/three dimes.

This works for the other variants as well.

Re: Making change probability question
 

[ QUOTE ]
You don't need brute force. If you have exactly a dollar, then of course you have change for a dollar. If you have more than a dollar then you have change for a dollar except for one case, three quarters and three dimes.

Therefore, figure out the expected number of coins you draw before getting $1.00 or more; and subtract off the correction for three quarters/three dimes.

This works for the other variants as well.

[/ QUOTE ]

Actually, there are other situations where you have more than a dollar, but don't have exact change
1 quarter + (8-9) dimes + (0-4) pennies
3 quarters + (3-4) dimes + (0-4) pennies

Although they're not that likely to occur.
I would expect that the expected number necessay to draw 1.20 and the expected number to draw 1.00 are reasonable upper and lower bounds on that, but that really only puts you between 5 and 6 coins, which is not a particularly satsifactory answer.