Probability: there are $n$ rooms, and $m$ meetings, $m \leq n$, what's the probability of all meetings scheduled to a different room

Question

Quite new in stats... definitely not my strong area. I came across this probability question, and I am not sure how to do this!

The question goes:

pretend that there's this meeting scheduling engine used by this company and is not synced in real time, so when people schedule their meetings online to book a room, there may be overlaps. let's say there are $N$ rooms, and $M$ meetings, where $M \leq N$, what is the probability that all meetings scheduled to a different room?

My thought was that, the first meeting doesnt matter, can be in any room; then the 2nd meeting has $\frac{1}{N-1}$ chance of being in a room. so for two rooms not colliding, the chance of them being in separate rooms is $\frac{1}{N-1}$. Right? I am not confident about this one neither...

Any hint/advice/guidance helps!

update to clarify:

1) each room can only host up to one meeting
2) one meeting can only happen in one room

It depends on how the meetings are scheduled. Can two meetings be scheduled for the same room? — copper.hat, Jan 06 '17 at 00:30
Hi @copper.hat, no, as stated in the title, all the meetings are scheduled to a different room. so no 2 meetings in a same room. hope that clarifies. — alwaysaskingquestions, Jan 06 '17 at 00:33

score 3 · Answer 1 · answered Jan 06 '17 at 00:33

3

The total number of ways to distribute meetings to rooms is $N^M$, because for example the first meeting can take place in $N$ rooms, the second also in $N$ rooms, and so on.

Let's calculate the number of favorable situations. The first meeting has $N$ choices. The second has $N-1$ choices and so on. So the probability of all meetings are in different rooms is $$\frac{N(N-1)\cdots(N-M+1)}{N^M}$$

answered Jan 06 '17 at 00:33

msm

7,147

Hi msm, thanks so much for trying to help! i misinterpreted your answer. my apology. i do have a question regarding the N^M, how did you come up with that? – alwaysaskingquestions Jan 06 '17 at 00:52
You want to assign rooms to meetings. For the first meeting there are $N$ options. For the second meeting there are also $N$ options. So for each of the $M$ meetings there are $N$ options, which means $N^M$ choices. – msm Jan 06 '17 at 01:00
ah okay. that make sense! but why did you use (N-M+1) as the last element for the numerator? why +1? – alwaysaskingquestions Jan 06 '17 at 01:05
The first term ($N$) is for the first meeting. $N-1$ for the second meeting, $N-2$ for the third meeting. So for the $M$'th meeting the corresponding term is $N-(M-1)=N-M+1$ – msm Jan 06 '17 at 01:13
so your answer is basically N!/(N^M)? – alwaysaskingquestions Jan 06 '17 at 01:15
No. if you want to write it using factorial, it is $$\frac{N!/(N-M)!}{N^M}$$ – msm Jan 06 '17 at 01:17
Let us continue this discussion in chat. – alwaysaskingquestions Jan 06 '17 at 01:17

score 3 · Accepted Answer · edited Jan 06 '17 at 00:50

3

If you are not talking about scheduling (for which time overlap would an issue), but instead talking about just where the meeting takes place, then there are $N^M$ possible assignments of meeting rooms. There are $\binom{N}{M}$ ways to choose $M$ different rooms for the meetings and $M!$ ways to assign the $M$ meetings to those rooms, so the probability is ${\binom{N}{M}M! \over N^M}$.

edited Jan 06 '17 at 00:50

Brian M. Scott

616,228

answered Jan 06 '17 at 00:35

copper.hat

172,524

You need to multiply that by $M!$ to account for the ways the meetings can be permuted amongst the $M$ rooms chosen. – Brian M. Scott Jan 06 '17 at 00:41
Thanks! I realized that but my train arrived before I had a chance to edit, stuck on phone for now. – copper.hat Jan 06 '17 at 00:43
If you like, I can make a quick edit; just let me know. – Brian M. Scott Jan 06 '17 at 00:45
That would be much appreciated, otherwise I will get to in an hour and a bit. Thanks! – copper.hat Jan 06 '17 at 00:46
Done! (And now +1.) – Brian M. Scott Jan 06 '17 at 00:50
@BrianM.Scott: Much appreciated! – copper.hat Jan 06 '17 at 01:16
can i please ask why multiply by M! ? i thought the (N M) will take care of assigning M meeting rooms to N total rooms already? – alwaysaskingquestions Jan 06 '17 at 01:58
@alwaysaskingquestions: That was my original omission, which Brian fixed. There are $\binom{N}{M}$ ways of choosing $M$ rooms, but this does not take into account the $M!$ ways of assigning these rooms. – copper.hat Jan 06 '17 at 02:00
@copper.hat but (N M) already take into account when M rooms are ordered differently right? it calculates all the possible ways of choosing M rooms from N rooms total. i am not seeing how its different from M! ways of choosing the rooms? (thanks for being patient with me!) – alwaysaskingquestions Jan 06 '17 at 02:02
@alwaysaskingquestions: No. At an extreme, there is exactly one way of choosing $N$ out of $N$ rooms, but there are $N!$ ways of assigning $N$ meetings to $N$ rooms. – copper.hat Jan 06 '17 at 02:04
1

@copper.hat ohhh i see. b/c (N M) does not count the orders of assigning the rooms. am i right? okay that make sense now! – alwaysaskingquestions Jan 06 '17 at 02:08

score 2 · Answer 3 · answered Jan 06 '17 at 01:01

2

Same solution as the others with a slightly different perspective (somewhat in line with the reasoning you tried to provide).

Let $E_i$ be the event that room $i$ does not collide with rooms $1,2,3,...,i-1$.

As you noted the first room does not matter.

$$P(E_1)=1$$

For the second room, there are $N-1$ rooms we can pick out of the $N$ total taking into account the first room was chosen:

$$P(E_2|E_1)=\dfrac{N-1}{N}$$

Similarly,

$$P(E_3|E_2,E_1)=\dfrac{N-2}{N}$$

And the pattern continues in this fashion.

$$P(E_i|E_{i-1},E_{i-2},\cdots ,E_1) = \dfrac{N-i+1}{N}$$

You seek

$$P(E_1\cap E_2\cap \cdots\cap E_m) = P(E_1)P(E_2|E_1)P(E_3|E_2,E_1)\cdots P(E_m|E_{m-1},E_{m-2},\cdots,E_1)$$

$$=1\cdot \dfrac{N-1}{N}\cdot \dfrac{N-2}{N}\cdots \dfrac{N-m+1}{N}$$

answered Jan 06 '17 at 01:01

David P

12,320

ah, your answer totally make sense to me! thanks for going off my thought process, its easier for me to follow. can i ask why you use (N-M+1) as the last element for the numerator? why +1? – alwaysaskingquestions Jan 06 '17 at 01:06
Notice for $E_2$ the numerator was not $N-2$ but $N-2+1$ or $N-1$. And the numerator for $E_3$ was $N-3+1$ or $N-2$. When we are choosing the $m^{th}$ room, there are only $m-1$ taken up so there are $N-(m-1)$ rooms left to choose from. $N-(m-1)=N-m+1$. – David P Jan 06 '17 at 01:09
1

omg thank you so much! okay that totally make sense now. thank you very very much! i missed the pattern – alwaysaskingquestions Jan 06 '17 at 01:12

Probability: there are $n$ rooms, and $m$ meetings, $m \leq n$, what's the probability of all meetings scheduled to a different room

3 Answers3