Even prize distribution

Question

I'm currently facing interesting algorithm problem and I am looking for ideas or possible solutions. Topic seems to be common so maybe it's known and solved but I'm unable to find it.

So lets assume that I'm running shop and I'm making lottery for buying customers. Each time they buy something they can win prize.

• Prizes are given to customers instantly after buying.
• I have X prizes and
• I will be running lottery for Y days
• Paying customer (act of buying, transaction) should have equal chance to win prize
• Prizes should be distributed till last day (at last day there should be left some prizes to distribute)
• There can not be left prizes at the end
• I do not have historical data of transactions per day (no data from before lottery) to estimate average number of transactions (yet lottery could change number of transactions)
• I can gather data while lottery is running

It this is not-solvable, what is closest solution? Instant prize distribution have to stay.

Answer 1

Possible Solution #1

Based on @m69 comment

Lets says there are 6 prizes (total prizes) and 2 days of lottery. Lets define Prizes By Day as PBD (to satisfy requirement have prizes till last day). PBD = total prizes / days We randomly choose as many as PBD events every day. Every transaction after this event is winning transaction. Can be optimized to no to use last hour of last day of lottery to guarantee giving away all of prizes.

Pluses

Random. Simple, elegant solution.

Minuses

Seems that users have no equal chance to win.

Possible Solution #2

Based on @Sorin answer

We start to analyze first time frame (example 1 hour). And we calculate chance to win as: where: Δprizes = left prizes, Δframes = left frames

Answer 2

What you're trying to do is impossible. Once you've gave away the last prize you can't prove any guarantee for the number of customers left, so not all customers will have equal chance to win a prize.

You can do something that approximates it fairly well. You can try to estimate the number of customers you will have, assume that they are evenly distributed and then spread the prizes over the period while the contest is running. This will give you a ratio that you can use to say if a given customer is a winner. Then as the contest progresses, change the estimates to match what you see, and what prizes are left. Run this update every x (hours/ minutes or even customer transaction) to make sure the rate isn't too low and every q prizes to make sure the rate isn't too high. Don't run the update too often if the prizes are given away or the algorithm might react too strongly if there's a period with low traffic (say overnight).

Let me give you an example. Say you figure out that you're going to see 100 customers per hour and you should give prizes every 200 customers. So roughly 1 every 2 hours. After 3 hours you come back and you see you saw 300 customers per hour and you've given out 4 prizes already. So you can now adjust the expectation to 300 customers per hour and adjust the distribution rate to match what is left.

This will work even if your initial is too low or too high. This will break badly if your estimate is too far AND you updates are far in between (say you only check after a day but you've already given away all the prizes).

This can leave prizes on the table. If you don't want that you can reduce the amount of time the program considers the contest as running so that it should finish the prizes before the end of the contest. You can limit the number of prizes awarded in a given day to make the distribution more uniform (don't set it to X/Y, but something like X/Y * .25 so that there's some variation), and update the limit at the end of the day to account for variation in awards given.