I'm assisting with the design of an algorithm over the next week to fit the following use case:

A person walking in a store has a tablet and approaches possible customers to notify them of a competition. When a customer enters their details, upon completion of the form - a request is sent to the server, and the customer will be randomly drawn (at that point in time) for a prize.

A maximum of 4 customers are chosen, the number of customers walking into the store is not known. The store is open from 8am until 4pm.

Would there be any other way (other than the ones stipulated) to solve something like this without knowing the average customers visiting the store?

Solution 1

I was thinking a normally distributed probability is used, where the parameters could be tweaked over time to fit this allowing customers to be selected (more or less) equally through out the day.

Solution 2

Similar to solution 1, but the time throughout the day is partitioned into segments. Between the hours of 8am and 12pm, a maximum of 2 people can be chosen.

I don't quite like the idea of doing this because if a majority of the customers come in the morning, this could lead to less than the 4 prize hand out expected of the day.

  • 1
    $\begingroup$ Candidate solution: Don't choose any winners. OK, I'm not seriously proposing that, but it meets all of your requirements, which suggests that some requirements are missing before this becomes a well-defined question about algorithms. $\endgroup$ – D.W. May 21 '18 at 16:20

There is no way to ensure that exactly 4 people win, and that all people have an equal likelihood of being chose.

For instance, suppose you see 100 people during from 8am-3pm, and have given out 3 awards. Then, if 500 people all show up in the last hour, you have at most one more award to give out, so those people will have a much lower chance of winning. Alternatively, suppose you see 100 people from 8am-3pm and have given out 0 awards. Then, if 4 people show up the last hour, the only way to give out exactly 4 awards is to give each of them an award, so those people will have a much higher chance of winning.

As a result, there probably is no perfect solution -- you will just be trading off different kinds of imperfection.

One solution is to not give anyone an award, but that's not very useful.

A practical solution is probably to get some data beforehand on the estimated number of people who show up per day, and use that to choose the probability of winning for each person. Once you've given out 4 awards, stop. For instance, suppose on average 100 people show up per day. Then as each person arrives, with probability $0.04$, given them an award. If you hand out 4 awards, no one else gets one for the rest of that day. That ensures that the expected number of awards handed out is a bit less than 4; that you won't hand out more than 4 awards; and that everyone's probability of winning is close to the same.

If you don't need to determine in real time whether each person has won, you can use reservoir sampling.

  • $\begingroup$ I suppose that's the sad reality of it, there's quite a few different scenarios which I can't quite cater for - so I'll have to poach for some more info on it. Appreciate the solid answer $\endgroup$ – jarodsmk May 22 '18 at 6:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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