0

I'm trying to figure out a win/lose algorithm where we have to have (around) X winners per day spread across the day without knowing the number of participations.

A user sends a request to an application that immediately decides at random whether the user has won or not. We don't know the number of requests when we start. Is there a way to make this work more or less? We want to spread the winners over the number of requests, not over time, because the requests are not divided equally over the day.

I was thinking about starting with an estimated number of requests per day, dividing the winning participations across that number, and altering the estimated number with the average of the actual requests. Any other suggestions?

Improve this question
2
  • 3
    That is exactly where I would start - and where I would probably end as well. Unless you have any additional information you haven't mentioned, this is the optimal probabilistically correct solution.
    – Kilian Foth
    Dec 18, 2017 at 9:42
  • 1
    This would make an interesting math problem. How to calculate a probability that fluctuates according to number of average daily requests, number of requests thus far, number of total daily winners, and number of winners thus far. If done right, the probability would mostly stay the same throughout the day and statistically the number of daily winners will be constant.
    – Neil
    Dec 18, 2017 at 10:37

8 Answers 8

Reset to default
4

Predicting the number of people to your site and basing the probability off of the is probablly not going to be reliable.

Why not randomly pick timestamps, and the first request that gets processed after each timestamp wins for each timestamp respectively. This makes it easy to spread the winners out across the day. Doing it this way, you dont care how many people visit your site.

You should also be able to report the esitmated probablity of winning bsed on your prediction of the traffic to the site.

Improve this answer
8
  • 1
    This application is only for users within the same timezone. There are significantly less users between 11pm and 9am. We've noticed in our analytics that we have around 200 times as much active users at noon then at midnight. Having fixed timestamps would also make it predictable.
    – dumazy
    Dec 19, 2017 at 12:26
  • 2
    You randomly choose the timestamps. If you want a winner between 11 pm and 9 am you pick a random time the day before to give the payout.
    – Robert Baron
    Dec 19, 2017 at 12:36
  • But then you never have a winner in that timeframe. It should be possible too, but will be less probable
    – dumazy
    Dec 19, 2017 at 12:59
  • That day before you randomly choose two times between 1:00 am and 9:00am - say 6:05:12 and 7:15:50, in addtion to radomly selecting the other times the outher payouts. This way you controll the number of winners, i.e. the race to be the first to be processed after a randomly selected timestamp, as opposed to just randomly selecting the individual ar the time they show up.
    – Robert Baron
    Dec 19, 2017 at 13:11
  • 3
    Define a Probability Density Function across the day. If you want to have the same number of winners every hour, make it flat. If you want fewer winners between 11pm and 9am, decrease the probability there. If you want it to match your viewership, take yesterday's site visits (or last week's site visits, if you have weekly cycles), and use that to seed your distribution. The sky is the limit with this approach.
    – Cort Ammon
    Dec 19, 2017 at 19:10
3

You are not clear whether there has to be X winners per day, or that over an extended length of time there will be on average X winners per day. But given that you can't know how many people will visit your site on a particular day in the future I can't see how you can achieve the former.

But for the latter I would suggest taking the past history of visits and feeding that data into a Linear Predictive Filter (EG Kalman Filter) and basing the awarding of prizes at the predicted rate divided by X. This will result in an over/under awarding of prizes per specific day, but in the long term will even out to X per day.

(Which after reading your question is basically what you were initially proposing)

Improve this answer
1

Another approach you can try is to distribute the remaining prizes among the expected remaining participants for that day.

The number of expected remaining participants R is simply the difference between the expected total number of participants N and the number of participants up till now n(t). R = N - n(t)

You can estimate N by looking at your historical average number of participants.

If X is your total number of prizes and W is the number of prizes that have been won already, then a participant's probability of winning will be p = (X - W) / R.

The advantage of this approach is that a participant's probability of winning will increase or decrease as the day progresses depending on the number of prizes that have been won. If many prizes are left at the end of the day, the probability will increase; if few (or no) prizes are left, probability will drop to zero.

Improve this answer
0

If you're willing to risk under awarding prizes to your winners (X) a simple solution is to estimate the number of participants (N). If you predicted correctly the odds of winning will be R = X/N. Just count through the number of losers (L) you expect each time then award the prize. L=N/X-1.

This also risks giving prizes away early if you're suddenly awash in participants. In any case keep count of awarded prizes and never give out more than you have. The best mitigation against giving them out early is to recalculate your estimate of the number of participants using your latest numbers. That should keep a sudden wave of participants from forcing you to give them out early. It will also mitigate under awarding if this turns out to be a slow day.

Improve this answer
0

You can start each day with an estimate per hour (or smaller time period).

You can just assume the number left for the day is the estimate of future time periods.

The other dynamic is if the completed time periods are is high or low do you factor in the rest of the day will be off the same?

Improve this answer
0

I think by saying: "application that immediately decides at random whether the user has won or not." You are saying the user is immediatly informed if they have won. If that is correct then I have nothing to add.

If the user isnt informed at time of entry if they have won, then: Unless there is some other regulation at play, those user who lost, could be considered as future winners. This doesn't change the solution to the problem and I think the first answer is still the best one, but it could help make your application seem smoother and more consistent in how it appears to select winners.

Even without knowing anything about application density during timeframes, you can set up time based regulations such as: If X winners have not won by time T, select winner from applicants. You'd still have to rely on a preset statistical model, but until the time you had a larger data set to build your model, this would help consistency.

Improve this answer
0

Another technique that might be useful is weighted reservoir sampling to obtain your X winners over a stream of n requests.The problem it solves looks much like your problem.The main idea is that you choose k samples from n items with a weighted probability when n is unknown.

Since you are restricted to immediately announce to someone if he wins or not, it means that you 'd have to perform some changes to the algorithm (e.g. use some dummy winners first and then replace them with some weighted probability). If the replacement of a dummy winner occurs by a new request, you announce to the user he is a winner, else he is not.

The weights of the replacement probabilities could vary in terms of the volume of requests in order to mitigate the risk of leaving dummy winners at the end of the day and also the risk of accepting too many users too early.

I am not quite sure that it could work, but i provide it as an alternative to the already mentioned solutions, hoping it turns out to be helpful.

Improve this answer
-2

That doesn't make sense. If you want two winners per day, and you get four requests the first minute. How are you going to know if those are the only requests you will get through the whole day or if there will be a million more request the next hour? But if you expect the number of requests to be predictable, then your solution is probably ok, even better would be some ML algorithm based on the inflow of request.

Improve this answer
3
  • The number of requests is kind of predictable, but our estimate is still not really specific enough, we're thinking between 5k and 50k. I think some sort of ML might be good here
    – dumazy
    Dec 18, 2017 at 9:44
  • 2
    This answer reads more like a comment.
    – MetaFight
    Dec 18, 2017 at 10:22
  • 3
    I don't think OP has to guarantee daily winners, or else there'd be nothing to discuss. It just has to be very probable. If anything, if daily winners is down one day, it can be increased the following day to make up for it.
    – Neil
    Dec 18, 2017 at 10:39

Not the answer you're looking for? Browse other questions tagged or ask your own question.