Math Problem

[Crow]

We have a program at my job which is supposed to populate work rosters at random.

There are 31 spots on the roster, and a person may be assigned only one each day.

You work 15 days. What is the probability of being placed in the same roster position on 6 of those days?

[Livius]

Is the question at least 6 days of the 15 or exactly 6 days of the 15?

For at least 6 of 15, just choose 6 of the 15 days to get the same job. Probability = ( 15 choose 6 ) / ( 2^15 ) = 0.1527 = 15.27%

For exactly 6 of 15 days, it's the same as above, but multiplied by 30/31 for each of the 9 other days you get a different job. Probability = ( 15 choose 6 ) / ( 2^15 ) * (30/31)^9 = 0.1137 = 11.37%

[Crow]

I'm looking for exactly 6, or greater than/equal to 6.

To get any specific spot, I'm already looking at 1 in 31 to start, so .032

I'm not sure your figures are correct. I guess another way to put it is if I had a roulette wheel with 31 slots, what are my chances of landing on the same number 6 times in 15 attempts?

[Razanir]

You're interested in a binomial distribution.

Suppose you have n trials, and the probability of a success (getting placed in said roster position, in this case) is p.

The probability of x successes is C(n,x)*p^x*(1-p)^(n-x), where C(n,x)=n!/(x!(n-x)!) is combinations of n choose x.

P(Binom(15,1/31) = 6) = C(15,6) * (1/31)^6 * (30/31)^9 = 5005*30^9/31^15 = .000004198

Or if you want at least 6 days, the probability is .000004384

Either way, it's incredibly unlikely.

[Livius]

You're interested in a binomial distribution.

Suppose you have n trials, and the probability of a success (getting placed in said roster position, in this case) is p.

The probability of x successes is C(n,x)*p^x*(1-p)^(n-x), where C(n,x)=n!/(x!(n-x)!) is combinations of n choose x.

P(Binom(15,1/31) = 6) = C(15,6) * (1/31)^6 * (30/31)^9 = 5005*30^9/31^15 = .000004198

Or if you want at least 6 days, the probability is .000004384

Either way, it's incredibly unlikely.

This is right. Somehow when I did it I decided to divide by 2^15 instead of 31^5. I'm not actually sure why I thought that worked, since, by inspection, it shouldn't be very likely.

[Knaight]

Or if you want at least 6 days, the probability is .000004384

Either way, it's incredibly unlikely.

It is worth noting that the probability goes up substantially if it's about somebody doing this over some 15 day stretch, and it happening in one of many 15 day intervals. I don't know what the underlying question behind wanting to know the statistics is, but that could be a factor.

[Khedrac]

For exactly 6 of 15 days, it's the same as above, but multiplied by 30/31 for each of the 9 other days you get a different job. Probability = ( 15 choose 6 ) / ( 2^15 ) * (30/31)^9 = 0.1137 = 11.37%

Not necessarily, because 6 is less than half of 15 if you just use (30/31)^9 then you could end up with 6 to 9 of them being on a different same assignment.

The question therefore gets more complex - do we mean "exactly 6 days and all other assignments for fewer days" or what?

[Fortuna]

Not necessarily, because 6 is less than half of 15 if you just use (30/31)^9 then you could end up with 6 to 9 of them being on a different same assignment.

The question therefore gets more complex - do we mean "exactly 6 days and all other assignments for fewer days" or what?

While this is true, to the OP: If you're interested in this for any practical purpose, you can ignore this post, because the contribution of that factor to your probability is going to be negligible.

[Radar]

In the given situation we need to consider a few more factors:
1. There is more then one person within the work rooster.
2. It is randomised every few weeks (I guess from the 15 days of work).

In essence, we are not looking at a single random arrangement, but at an outlier in a larger statistical sample. To make the predictions accurate, we would need to calculate the probability of anyone in the company getting a given task at least 6 times during the full work period. Then we could also predict, how often would it happen in a longer time span.

Thus: does the ammount of tasks match the ammount of workers?

[Crow]

The roster is supposed to be populated randomly each day. Every day is separate from the next. Overall, we have somewhere to the order of about 200 people.

I'm not sure how many have gotten 6 of the same post in 15 days, I know of only one. Several have gotten the same post 4 to 5 times in the 15 day period though. The company says the program is working properly, and that rosters are being populated at random. I contend that it is not.

[factotum]

I contend that it is not.

On what basis? The critical thing to remember about randomness is that it tends to clump together. If you stand there flipping coins, getting head-tail-head-tail all the time might be the most *even* distribution of results, but it sure as heck ain't the most random! That being the case, seeing occasional clumps where some guy gets the same post 5 or 6 times in a row certainly doesn't prove it's not random--technically, even someone getting the same post 15 times in a row wouldn't prove that, because the probability of that actually occuring is non-zero (albeit very small).

[Radar]

Ok, so the proper question is: what is the probability of at least one person out of 200 people getting any task (out of 31) 6 times in 15 days.

It is important to stress, that it could be anyone and it could be any given task. I assume, that each task is equally probable or in other words requires the same ammount of workers.

1. The probability of a specific person getting any given task 6 times in 15 days is obtained as follows:
the total number of possible arrangements is (disregarding the ordering) (15+31-1)!/(15! (31-1)!). The total number of combinations (with repetitions) of situations with any task repeating itself at least 6 times is: (10+31-1)!/(10! (31-1)!). You basicaly need to force the outcome on 5 days. By dividing the latter by the former we obtain the probability: 13/5289 or 0.25%. Not as low as estimated earlier.

2. The probability of at least a single person out of 200 getting any task 6 times in a 15 day period is most easily calculated as "1 - probability of noone getting 6 identical tasks". This gives us 1 - (1-13/5289)^200, which is about 39%.

Answer: it is quite likely for someone out of 200 wokers to get 6 identical tasks in a 15 day period and this is for a single 15 day period.

[Crow]

On what basis? The critical thing to remember about randomness is that it tends to clump together. If you stand there flipping coins, getting head-tail-head-tail all the time might be the most *even* distribution of results, but it sure as heck ain't the most random! That being the case, seeing occasional clumps where some guy gets the same post 5 or 6 times in a row certainly doesn't prove it's not random--technically, even someone getting the same post 15 times in a row wouldn't prove that, because the probability of that actually occuring is non-zero (albeit very small).

You can't prove conclusively that it isn't occuring at random, but when this is happening with several people at the same time, you can make the case that there is something wrong with the random algorithm. I get what you're saying, but even with a short sample time (15 days), with so many officers, we should be seeing something close to an even distribution without so many statistical outliers.

I am getting what this fellow got using binomial distribution:

You're interested in a binomial distribution.

Suppose you have n trials, and the probability of a success (getting placed in said roster position, in this case) is p.

The probability of x successes is C(n,x)*p^x*(1-p)^(n-x), where C(n,x)=n!/(x!(n-x)!) is combinations of n choose x.

P(Binom(15,1/31) = 6) = C(15,6) * (1/31)^6 * (30/31)^9 = 5005*30^9/31^15 = .000004198

Or if you want at least 6 days, the probability is .000004384

Either way, it's incredibly unlikely.

I'm not sure your .25 number is accurate.

[ChristianSt]

The roster is supposed to be populated randomly each day. Every day is separate from the next. Overall, we have somewhere to the order of about 200 people.

I'm not sure how many have gotten 6 of the same post in 15 days, I know of only one. Several have gotten the same post 4 to 5 times in the 15 day period though. The company says the program is working properly, and that rosters are being populated at random. I contend that it is not.

Have all 31 posts equal probability? And are different peoples posts independent from each other (e.g. is it possible that on a given day all people could get the same post)?

[Crow]

They are supposed to have equal probability. One man, one post.

[Radar]

I'm not sure your .25 number is accurate.

It's much more accurate for a number of reasons:

1. The quoted calculations assume, that you get a specific task 6 times - not any task 6 times.
2. They also assume, you get this task exactly 6 times - not at least 6 times.
3. I'm not even sure the binomial distribution is the right tool for the job here, because there are 31 possible outcomes and one should not simplify the system like that. That's exactly why I calculated the probability from first principles.

I might have even underestimate the probability, because there is still a degree of freedom in the 5 forced outcomes, but it's difficuilt to retrieve, so I neglected it.

[ChristianSt]

You can't prove conclusively that it isn't occuring at random, but when this is happening with several people at the same time, you can make the case that there is something wrong with the random algorithm. I get what you're saying, but even with a short sample time (15 days), with so many officers, we should be seeing something close to an even distribution without so many statistical outliers.

The problem is that 15 is a really low number while 200 is a (while still not that large) is larger. The imo only useful test you could make is to see whether posts are distributed with equal probability. So if you ask all people and count how often each post gets distributed, you should get roughly equal amounts.

To compare that: say you have a d100. Rolling two times 100 with it, is a rather small odd (0.0001 to be precise). Yet if you have enough people some of them are guaranteed to roll two 100 in a row. If you have 200 people the chances to have at least one such person are 1-(0.9999)^200]. Which is 0.0198, so around 2%.

I am getting what this fellow got using binomial distribution:

I'm not sure your .25 number is accurate.

It is not .25 but .25% which is 0.0025. To be honest I have no clue what Radar is trying to do. Or it is clear what he wants to do (since he says it), but I have no idea how he arrives at the numbers he uses. The amount of different post distributions is rather trivial (31^15 = 2,34x10^22]). The amount of valid combination is not that easy to figure out. (And yes, 0.0025 seems a bit high for me)


I'm also sceptical of the numbers Razanir arrived at. At least the first, with" P(Binom(15,1/31) = 6) = C(15,6) * (1/31)^6 * (30/31)^9 = 5005*30^9/31^15 = .000004198" is certainly correct. But "Or if you want at least 6 days, the probability is .000004384" seems rather low to me.
Mainly because of the same reasons Radar said in his most recent post: it is only the probability of gaining one specific post exactly 6 times. (It might be that .000004384 is correct for getting one specific post 6 or more times, but imo it seems to be too low).

I'm not sure how to arrive at the exact number, but as an estimate I would multiple .000004198 with 31, resulting in 0.000130138, which is even a higher probability than my example with getting two times 100 on a d100. Yes I know that it is wrong (since I don't factor in more than 6 days the exact task and some distributions are counted twice (6 days post 1 and 6 days post 2 for example), but I think the effects should at least cancel out each other a bit), but imo it should be in the right magnitude, which would result in a single-digit % for it happening.


Unfortunately your numbers are too big for an enumeration . Otherwise this would be the easiest way to get the result.

[Radar]

It is not .25 but .25% which is 0.0025. To be honest I have no clue what Radar is trying to do. Or it is clear what he wants to do (since he says it), but I have no idea how he arrives at the numbers he uses. The amount of different post distributions is rather trivial (31^15 = 2,34x10^22]). The amount of valid combination is not that easy to figure out. (And yes, 0.0025 seems a bit high for me)

I simply calculated the number of combinations with repetitions for the total number of relevant states - that's why I didn't use 31^15 (which would be valid, only if we were concerned with the ordering) as the total number of states. I don't think, I made a mistake in that part, since it's pretty much a textbook example, but if I did make one, I sure would like to know.

My estimation of the situations involving a single task being given at least 6 times is obtained in a similar way, but it's not entirely accurate - it's the lower bound on the total number of relevant situations. The idea behind the estimation is that to ensure that a task is given at least 6 times, we need to enforce the outcome 5 times to be equal to any other task already given. Therefore I again calcualated the number of combinations with repetitions for picking 10 random tasks out of 31, since the remaining 5 won't be random. What I did not take into account is that we most often can chose between a number of possible outcomes to enforce, which would make the overal probability even higher.

After that I did falsy assume, that work schedule for each person is an independent random variable, because the real situation (constant ammount of workers for each job) is a real pain to consider in full detail.

At any rate, if you see any fault in my reasoning, then I would be grateful for an explanation.

[NichG]

I wrote up a quick simulation and I got Radar's numbers for 5 days, not for 6 days. For 5+ days I measure a cumulative chance of 0.00249 out of 100k trials, which means a 40% chance that at least one employee would have the same task for 5 days out of 15. For 6+ days I measure a cumulative chance of 0.00014 (out of 100k trials) - consistent with ChristianSt's result - which means that for 200 employees there's about a 3% chance that at least one of them would get the same task for 6 days out of 15.

3% is not that rare, really. Also given that we're not taking into account hidden constraints that a business might have, I think its more likely that the algorithm isn't precisely what you think it is, but may also be trying to satisfy some constraint like 'at least 3 people are doing each task each day' which would give different results than these numbers.

[Chen]

The roster is supposed to be populated randomly each day. Every day is separate from the next. Overall, we have somewhere to the order of about 200 people.

I'm not sure how many have gotten 6 of the same post in 15 days, I know of only one. Several have gotten the same post 4 to 5 times in the 15 day period though. The company says the program is working properly, and that rosters are being populated at random. I contend that it is not.

Wait you have 200 people but only 31 posts? Does this mean some people don't get a post? Or can posts have multiple people on them? Is it possible some of the spots are constrained in the number of people that can work at them? That might throw the probability off some.

[ChristianSt]

I simply calculated the number of combinations with repetitions for the total number of relevant states - that's why I didn't use 31^15 (which would be valid, only if we were concerned with the ordering) as the total number of states. I don't think, I made a mistake in that part, since it's pretty much a textbook example, but if I did make one, I sure would like to know.

My estimation of the situations involving a single task being given at least 6 times is obtained in a similar way, but it's not entirely accurate - it's the lower bound on the total number of relevant situations. The idea behind the estimation is that to ensure that a task is given at least 6 times, we need to enforce the outcome 5 times to be equal to any other task already given. Therefore I again calcualated the number of combinations with repetitions for picking 10 random tasks out of 31, since the remaining 5 won't be random. What I did not take into account is that we most often can chose between a number of possible outcomes to enforce, which would make the overal probability even higher.

After that I did falsy assume, that work schedule for each person is an independent random variable, because the real situation (constant ammount of workers for each job) is a real pain to consider in full details.

At any rate, if you see any fault in my reasoning, then I would be grateful for an explanation.

Ah, I see. Honestly I have still not clue how your numbers are supposed to work. But in any case I can say that your approach is not correct.

Because the approach "# valid/# total" is only a simplification/shorthand of P(valid)/P(total)=P(valid), iff all events have equal probability.
While ordering is certainly not relevant to the question, it is relevant for the odds.

Let consider the similar (at least from style, not from numbers) problem of flipping a coin three times (basically 3 days with 2 posts), interesting in events with 3 times heads or 3 times tails.
If you count the total number of cases without accounting for ordering, there are 4 cases: "3 heads" / "2 heads, 1 tails" / "1 heads, 2 tails" / "3 tails". There are 2 interesting cases, yielding a "result" of 50%.

Yet that number is just wrong! (And hopefully it should be pretty clear that the probability to throw 3 times heads or 3 times tails in a row is not 50%)

The problem is that P("3 heads") and P("2 heads, 1 tails) isn't equal. There are 8 different results, each falling into one of those 4 cases:

0	0	0	"3 heads"
0	0	1	"2 heads, 1 tails"
0	1	0	"2 heads, 1 tails"
0	1	1	"1 heads, 2 tails"
1	0	0	"2 heads, 1 tails"
1	0	1	"1 heads, 2 tails"
1	1	0	"1 heads, 2 tails"
1	1	1	"3 tails"

This table enumerates all possibly different events, each having the same probability (=1/8), yielding the result of P(Having 3 heads or 3 tails with 3 coin flips)=0.25




@NichG: While I like the idea of simulating, if the OP is concerned with the randomness of the "original experiment", I don't think the randomness of (probably another) PRNG is much better . And yes, I have the feeling that it is rather likely that we use assumptions that are not valid (hence the questions about it I had earlier).



It is also possible to solve this using a Markov Chain, though I'm not sure yet, which states to use. I'm tinkering a bit and will post it if I have something.

[Radar]

Ah, I see. Honestly I have still not clue how your numbers are supposed to work. But in any case I can say that your approach is not correct.

Because the approach "# valid/# total" is only a simplification/shorthand of P(valid)/P(total)=P(valid), iff all events have equal probability.
While ordering is certainly not relevant to the question, it is relevant for the odds. (things of relevance)

Thank you!

That's what I get for oversimplifying the situation.

[Crow]

Wait you have 200 people but only 31 posts? Does this mean some people don't get a post? Or can posts have multiple people on them? Is it possible some of the spots are constrained in the number of people that can work at them? That might throw the probability off some.

These people work different shifts and days off. There is never more than one person assigned to perform a task. 31 posts, 31 people, no exceptions. Every person is eligible to work every post.

Basically, we're looking for the chance of any one person working the same post 6 times in one 15-day period....since we've only been running this program for 15 days (minus days off, so about 21, at time of posting).

[The Walrus]

So, if I'm understanding correctly, on any day where a person is working, that person has an equal chance of being assigned any given post (theoretically), and will only work at that one post for that day, but that person won't necessarily be working all 15 days?

[Crow]

They will be working all 15 days.

[Razanir]

it is relevant for the odds.

PROBABILITY! (Sorry, I'm practically majoring in stats, so it irritates me to no end when people use the two interchangeably)

They will be working all 15 days.

I'm even more confused now. So there are 200 people to be assigned to 31 posts, with only one person assigned to each post, and yet we're saying that this arbitrary person IS working all 15 days?

It's two different probabilities. Working the same post 6/15 days is easy. It's just a binomial probability. Being chosen out of 200 people to work, and STILL working the same post 6/15 days is a bit tougher. That one (I think) would require a hypergeometric probability to see if you're even chosen a particular day.

[NichG]

@NichG: While I like the idea of simulating, if the OP is concerned with the randomness of the "original experiment", I don't think the randomness of (probably another) PRNG is much better . And yes, I have the feeling that it is rather likely that we use assumptions that are not valid (hence the questions about it I had earlier).

I don't believe in encouraging superstition. People really need to get over their issues with PRNGs. If it were this easy to tell that the data came from a PRNG rather than a true random source, you wouldn't need to generate trillions of numbers and run them through exhaustive statistical suites. An actual software bug is more likely, but I'd posit that given the span of answers given by people in this thread, its easier to make a short program that gets it right than to actually do the math correctly

But yes, invalid assumptions cannot be fixed by code or math.

[Crow]

On any given shift, there are 31 slots that a person can be assigned, one person, one slot, no exceptions. Forget the 200 people part. First we need to find the actual probability of a single person being assigned the same post 6 times in a 15 day period.

There are only 31 people to choose from during a single shift (the others work different shifts/days off/etc). On this single shift, one person has gotten the six. However several have gotten 5 of the same position in this 15 days as well, but I'm interested in the probability of the six.

Anyhow, once we have determined that, rather than trying to figure out the intricacies of our scheduling and shift setup (which is a mess anyways), let us just treat the 200 people as 200 separate 15-day periods and work from there to find out how likely it is for the one person from earlier to work 6 given 200 15-day periods.

Does this make sense?

I appreciate everybody's help. If this thing is working, that is fine. It just seems very suspicious, especially taking into account how many people have managed to do 5 of the same post so far.

[Razanir]

OAnyhow, once we have determined that, rather than trying to figure out the intricacies of our scheduling and shift setup (which is a mess anyways), let us just treat the 200 people as 200 separate 15-day periods and work from there to find out how likely it is for the one person from earlier to work 6 given 200 15-day periods.

Except it doesn't quite work that way. If the person has to be chosen out of 200 to work, then that changes the probabilities.

[NichG]

Okay, I've used the following algorithm to simulate that.

Take 31 people. For each day of the 15 day period, I have 31 slots. For each slot, pick a random person to fill that slot, but if I pick a person who already is assigned to a slot, pick again randomly until I pick someone who is not yet assigned.

Out of that set of 31 people, the measured chance of one of them getting the same slot 6 times is 0.0037. So that's a little smaller than what you'd get if you assumed that people were being assigned completely randomly (e.g. slots could be left open).