Secret Santa SURPRISING Probability Result
Вставка
- Опубліковано 7 жов 2024
- A group of N people place their names into a hat. Each person draws a name at random (this is the person to give a gift). What is the probability no one draws his or her own name?
Blog post (text derivation)
wp.me/p6aMk-4p2
Inclusion-exclusion principle
en.wikipedia.o...
If you like my videos, you can support me at Patreon: / mindyourdecisions
Connect on social media. I update each site when I have a new video or blog post, so you can follow me on whichever method is most convenient for you.
My Blog: mindyourdecisio...
Twitter: / preshtalwalkar
Facebook: / 168446714965
Google+: plus.google.co...
Pinterest: / preshtalwalkar
Tumblr: / preshtalwalkar
Instagram: / preshtalwalkar
Patreon: / mindyourdecisions
Newsletter (sent about 2 times a year): eepurl.com/KvS0r
My Books
"The Joy of Game Theory" shows how you can use math to out-think your competition. (rated 4/5 stars on 23 reviews) www.amazon.com...
"The Irrationality Illusion: How To Make Smart Decisions And Overcome Bias" is a handbook that explains the many ways we are biased about decision-making and offers techniques to make smart decisions. (rated 5/5 stars on 1 review) www.amazon.com...
"Math Puzzles Volume 1" features classic brain teasers and riddles with complete solutions for problems in counting, geometry, probability, and game theory. Volume 1 is rated 4.5/5 stars on 11 reviews. www.amazon.com...
"Math Puzzles Volume 2" is a sequel book with more great problems. www.amazon.com...
"Math Puzzles Volume 3" is the third in the series. www.amazon.com...
"40 Paradoxes in Logic, Probability, and Game Theory" contains thought-provoking and counter-intuitive results. (rated 4.9/5 stars on 7 reviews) www.amazon.com...
"The Best Mental Math Tricks" teaches how you can look like a math genius by solving problems in your head (rated 4.7/5 stars on 3 reviews) www.amazon.com...
"Multiply Numbers By Drawing Lines" This book is a reference guide for my video that has over 1 million views on a geometric method to multiply numbers. (rated 5/5 stars on 1 review) www.amazon.com...
Just for fun i proved this...
The number of successful draws (where everyone gets a different gift) is a sequence starting with the values (0,1):
F(n) = (F(n-1)+F(n-2))*(n-1)
and that's true for every n.
That's like a generalized Fibonacci sequence if you take the (n-1) product out of the formula.
That's quite a fascinating solution. Do you want to give it a try?
Hold on! At 3:07 into the video you state that the number of ways that at least one person gets theiir own name is C(n,1). Stop right there. Divide this by n! and you have the probability that at least one person gets their own name. Subtract from 1.0 and you have the probability that no one gets their own name. This would be 1 - 1/n!
I think something's wrong in your explanation.
You're damn right "something" is wrong in his explanation.
Read the text solution on his home-page instead (mindyourdecisions.com) - it's way more informative!
it should be "number of ways where at least person #1 gets their own name". We multiply by n to add "number of ways where at least person #2 gets their own name" and so on up to person #n, but then we have to subtract, because we double-counted ways where for example #1 and #2 both got their own names.
just spotted the same...
yes this is true, this seems to be the real brain teaser of this video, I can just say MindYourDecisions which youtube videos you believe ;)
I think he missed some details. Suppose we chose A to pick his own name and then arranged remaining 3 . These arrangements will include a case in which B(for example B chooses B , C chooses D and D chooses C) picks B . So, we have A as well as B picking their own names. Now, suppose we chose B initially, we will then have a case in which A chooses his name from arrangements of the remaining 3 (say, A chooses A, C chooses D and D chooses C) . That's repetition, we can use inclusion exclusion principle to handle all the repetitions and get correct answer.
If there was 2 people (DUH Just for the sake of maths) The probability noone draws his/her own name is 50/50 not 37%
2 people is too small a sample size to generalize. I believe he was stating that for a general n, the 37% is true. For such small sample sizes, the deviation will be much greater. As n gets sufficiently large, the percentage should drop to 37% and stay around there.
The formula is always true. The formula converges to 1/e for sufficiently large n
You can check it in this link: www.wolframalpha.com/input/?i=(sum+(-1)%5En+*+(1%2Fn!)),+n%3D0+to+infinity
Here I put "(sum (-1)^n * (1/n!)), n=0 to infinity" in wolfram alpha and it shows how the answer to the question converges to 1/e, when the sample n increases. Indeed for n = 2, it's 50% and for n = 1 it's 0% (because you will always be unsuccessful in picking another name out of a box containing 1 paper with your name on it :p). For n = 3 it's 33.33% (1/3), for n = 4 it's 37.5% (3/8) etc.. to 1/e (~36.79%). Funny that even for n = 0, the answer is 100%, which is true that for 0 people, nobody will pick a (and not their own) name out of the (empty) box, so this will always work successfully. You can try it yourself if you don't believe me ;p.
You can change the "infinity" to the sample n for which you want to know the chance that it will be drawn successfully.
What he said was somewhere between wrong and imprecise. The percentage CONVERGES to about 37%. In the case of n=4 the percentage of a successful game is 3/8=37.5%
I think today found the limits of my ability to follow your videos. Interesting though.
I had 37.5% just by using logic. Person A draws a name, they have a 3/4 chance of not getting their own name. Let's assume that is the case. Say they draw person B, person B then draws a name. If they draw A (closing the loop), then there is a 50% shot of Person C drawing their person D giving a probability of this route of 3/4 x 1/3 x 1/2=1/8. If person B drew person C, then we go to person C who has a 50% chance of drawing D (draw A and person D must pick themselves) and vice versa, so we have 3 lots of 1/8 or 3/8 in total.
This looks much, much more complicated than you really need it to be. I solved it a different way.
Step 1: Define the group as having n people.
Step 2: Note that the probability of the first person not drawing his own name is (n-1)/n.
Step 3: Note that, by using probability distributions, the probability of the second person not drawing his own name is (the probability his name has already been drawn times 1) plus (the probability his name hasn't been drawn yet times the probability he does not draws his own name). Simplify this to (1/n)*1 + ((n-1)/n)*((n-2)/(n-1)), which equals (n-1)/n.
Step 4: Repeat for subsequent people as many times as you like; the result is always the same ((n-1)/n).
Step 5: Conclude that the probability of none of the n people picking their own names is ((n-1)/n)^n.
Step 6: Use a standard limit to find that as n approaches infinity, the probability of no one picking their own name approaches 1/e.
+Denny Chen Your formula actually performs poorly for small n though. Consider n=2. Your answer claims probability of success is (1/2)^2=.25, when clearly the result should be .5.
Quinton Baker I see the problem. The probability that the last person does not draw his/her own name given no one else has drawn their own names, is 1. This means the formula should be ((n-1)/n)^(n-1), which still has the same limit as n goes to infinity.
Thanks for the heads-up.
Right, but now look at n=3. Your formula has a probability of success of (2/3)^2=4/9, but really it is only 2/3!=1/3. The two successful draws are when people pass their name to the person to the left, or two the right. Any of the other 4 permutations are invalid.
...That's weird. Would you mind helping me find my mistake?
+Denny Chen Lets assign:
event A = the first person did not draw his/her own name
event B = the second person did not draw his/her own name
event C = the first person drew the second person's name
P(A) = probability that event A occurred
P(A and B) = probability that both events A and B occurred
P(B|A) = conditional probability that event B occurred provided that event A occured
In step 2 you have determined correctly that P(A) = (n-1)/n
In step 3 you have calculated that P(B) = P(A). This is not surprising - each person has the same probability of drawing his/her own name.
Now you want to calculate P(A and B). If the events A, B were independent, then you could use P(A and B) = P(A) * P(B), however they are not, so a more general formula has to be used:
P(A and B) = P(A) * P(B|A)
P(B|A) = P(B and C|A) + P(B and not C|A)
Because B and C = C, we have
P(B and C|A) = P(C|A) = 1/(n-1)
P(B and not C|A) = P(not C|A) * P(B|A and not C) = (n-2)/(n-1) * (n-2)/(n-1)
This gives
P(B|A) = (n^2 - 3n + 3) / (n-1)^2
P(A and B) = (n^2 - 3n + 3) / (n(n-1))
I am afraid that if you try to continue for the next persons, you will go mad. ;-)
1/e is the same probability of obtaining a deck of cards where no card is in the correct position :)
"did you figure it out" yyyea no. I should've but has been ages since I did maths.
Use two hats. Randomly and secretly assign people to put their name in either hat 1 or hat 2. Then have everyone secretly draw a name from the other hat. Probability no one draws his or her own name increases to 1.0000.
This series does not equals 1/e for all n but for n tending to infinity.
Probably something like Poisson Approximation of Binomial. For large values of N where N > ??? (depending on accuracy desired).
Why is my calculation wrong ? 1st person has Probability of 3/4 to pick a name not his. 2nd person 2/3 and 3rd, 1/2. The product is the Probability of all three events = 6 / 24 = 1/4. It is a conditional probability problem similar to drawing balls from a bag without replacement.
+Paul Freda it isnt wrong
+Paul Freda It is wrong. The problem is that you don't know if the name of the 2nd person is still in the hat when he is picking a name. So if the first guy picked the name of the second person, then the 2nd has 100% chance to pick a "good" name. However, if the first guy didn't pick the name of the 2nd, then it has a probability of ⅔ to be a bad draw as you said. And this logic happens to all the next guys. You have to seperate the two cases, whether their name has already been picked or not
Your calculating for 4 people. You are suppose to do it for n people.
+Zyph_Legend Yes, but even if you solve for n=4, his math is still wrong. where n=4, the probability is 9/24.
Liquicitizen Kemkyrk is correct about why he's wrong. He forgot to equate for scenarios in which a previous person had already drawn the name of the person currently drawing. The chance of each person drawing a successful name changes depending on what was drawn by each previous person.
The comparison does not work because the colour of the balls would be different from each of the perspectives from the people.
Thanxx man! Really helpful. That too when you have a test on permutations/combination the next day!
I found a "straightforward" solution (assuming knowledge about permutations and group theory). It is very impractical but I found it interesting:
For n people, each possible draw of names is a particular permutation of n objects. The permutations that result in succesful draws are those in conjugacy classes without 1-cycles. Therefore, the probability is the sum of the sizes of those classes, divided by n!
For example, if n=8:
Partitions of 8 with no 1s: 8 = 2+6 = 3+5 = 4+4 = 2+2+4 = 2+3+3 = 2+2+2+2
Each one of those partitions corresponds to a conjugacy class of succesful draws. The formula for the size of each conjugacy class has an 8! in the numerator, so we can find the probability using only the denominators of the formula:
P = 1/8 + 1/(2*6) + 1/(3*5) + 1/(4^2*2!) + 1/(2^2*2!*4) + 1/(2*3^2*2!) + 1/(2^4*4!)
= 1/8+1/12+1/15+1/32+1/32+1/36+1/384 = 2119/5760 ≃ 0.368
I find interesting that the truncated series for 1/e can be written as these weird sums of reciprocals of integers.
Your video is sadly misleading. Your final answer is correct, you are correcting for double-counting... but you never explained where that double-counting is or why it happened. You even said "at least k people get their own name: n!/k!" without mentioning that this is technically an incorrect calculation as the result includes double-counting.
Yes I also think like that.. can you please help me to explain where the double counting is? or did you have another way to solve this problem?
Well the the probability of success (for this problem - n=4) will be 9/24=37.5%.
Another way to work it out is to write down all 24 possible combinations and rule out the ones that at least one of the 4 people gets a present to themselves. It's quite easy and more practical, though it wouldn't work for big n's cause it would be too time consuming.
5:22 you can't say at least K. you have to say exactly K.
Another great video! Thanks. I think I would need a visual to help understand more clearly, especially when you discuss the inclusion/exclusion principle.
it has to be %37.5 which is n is number of people; 1- [(C(n,n) + c(n,n-1) + ..... C(n,1))/n!)]. In our case 1- [(1+4+6+4)/24] = 9/24--> %37.5 Note that C(n,n) + c(n,n-1) + ..... C(n,1) = 2^n -1 which is 2^4-1 =15
n!/k! is NOT the number of draws where at least k people get their own name. There is double-counting in that calculation too. The final formula is correct, but the explanation should be different. Other than that, great video! :)
alright
A has a 3/4 chance of not messing it up
Then B has a 2/3, however, A might have drawn B, so 3/4*2/3
Then C has a 1/2, however, B might have drawn C, or A might have drawn C. Thats 3/4*2/3*1/2
Then D has a 1 chance, however, A, B, Or C might have drawn the card, so 3/4*2/3*1/2*1
So in the end
((3/4)^4)
*
((2/3)^3)
*
((1/2)^2)
but like he said solve for N people
so 0.0234375 for n = 4.
i guess n times with n - 1 each one,
((n-1/n)^n)
I wonder if im right
+mebezaccraft Nope
Once B has its card, there's a possibility that A first chose the card C and that B chose the card D. In this case, the game would end up successful no matter what C and D choose!
100/n is chance of 1 being bad.
n! is how many could be chosen.
n!*100n = 100n Gamma[1 + n] is chance
Put in values for n.
Actually the e^x expansion has infinite terms. So we can't generalise the solution to 1/e. Hence for different values of n we get different answers. If there are infinitely many people we get 1/e.
However great video!!!
At 4:20 why do u need the probability of exactly k people? Doesn't at least k=1 give you the sum of all possible k?
+Mbhound wtf????????????????????????????????????????????????????????????????????????????????????
+kg583 You are right, the number of unsuccessful draws is the number of draws where at least one person gets his own name. However, n!/k! is NOT the number of draws where at least k people get their own name, as +Mike D has explained.
There is a formula for n people (derangement - no one will get his/her)
number of possible derangements =
nif(n!/e)
where nif(x) is the nearest integer function of x (simply rounding to the nearst integer)
and e is the Euler's constant = 2.718...
Another interesting question: What is the chance that a drawing constitutes a cycle containing all n participants as opposed to multiple smaller cycles?
If there were
2 hats= (Successful draws) 50%
If 3 hats= 33.33%
If 4 hats = 37.5%
Can anybody explain why the answer at once is going down and then up?
some ten years ago i faced a similar problem when trying to estimate how long i'd have to spend in a dungeon in a mmorpg to get the drop i wanted.
i knew more or less how many monsters per hour i could kill, and all i needed was what was the chance of dropping it after being in the dungeon long enough to kill a thousand monsters so i could have an idea of what to expect.
the chance of dropping the item was 0,1%.
i just did 0,999^1000 and came up with the result of 36,7% of me NOT dropping it after a thousand monsters (so, roughly 63% chance of dropping it), which was really close to my gut felling of "about a two thirds chance".
i had a feeling the answer to this was even closer to my calculated chance of NOT dropping it. i was right again. 36,7% is roughly 37% after all.
I don't really think, that the logic used in this video is correct. Now I am talking (well, writing to be exact) about the way the number of at least k people taking their own name is calculated. Let's now say that k=1. If I fix the one person, who takes his or her own name, then the rest will have (n-1)! possibilities of taking other names. But now I can't simply multiply by n (or c(n,k) for higher k) to count that any person could be that fixed person, because for example a scenario, where the first and the second person take their own name and others take different names, would ber counted twice. And this error only becomes larger, as k gets bigger. For example, if n=2, then the number of ways at least one person takes his or her own name is 1, but according to your formula, it should be 2. Another problem I see is with the "inclusion-exclusion" method. If I take the number of scenarios, when at least 1 person takes his or her own name, and I subtract the number of scenarios, when at least two people take their own names, I should end up with the number of scenarios when exactly 1 person takes his or her name. But then I should do the same for exactly two people. But your formula (if the formulae for the number of ways at least k people choose their own name were correct) would not count the number of ways when exactly an even number of people take their own name. It might be possible that these two errors cancel each other out, because the final formula seems to work, I haven't checked this, because I can't find the correct formulae, but then still the statements said in the video are misleading.
As the problem is stated, it would take an average of 3 draws to get a successful draw, and may take more. This means collecting all the slips and drawing again at least twice on average, which would be difficult to administer, especially, let's say, for a group of 100 people. From a practical point of view, it would make better sense for each person to draw a slip, check for their own name, and, if it is, have the moderator hold on to it while that person draws again. The moderator would place back any slip being held before having the next person draw. The next person draws a slip and the same procedure is followed if they draw their own name. No person would draw more than twice and the moderator doesn't have to deal with collecting slips from everyone for subsequent draws. (The people who got names of people that they want to give gifts to are not going to want to turn their slips back in!) What is the probability that no one draws their own name? I believe that the answer is the same as what Presh calculated.
1) Why is p(successfull) not equal to just 1-p(at least one person gets their own name)?
2) If 3:43 were right, then p(at least one person gets their own name) would be C(n,1)*(n-1)!/n!=n!/(n-1)!*(n-1)!/n!=1 which certainly isn't true
24 total possibilities for the draw
Unsuccessful cases:
1 own name drawn : a,b,c,d (4)
2 own names drawn : ab,cd,ad,bc,ac,bd (6)
3 own names drawn : abc, abd, acb, bcd (4)
4 own names drawn : abcd (1)
15 unsuccessful cases for 24 possibilities = 62.5% fail = 37.5% success
Not as hard as it seems.
3 own names drawn cannot happens because if a b and c get their own name d get also his own name.
So there are 4 unsuccessful draw less.
Also 8 possibilities for 1 own drawn name and not 4, 2 for each like : aa bc cd db /aa bd cb dc
Both of your mistakes cancel each one out you are luck, but i counted 20 possibilities total not 24 so to me it is 25% success.
Also if you have only 3 people the probablility is 33.3% so it seems to me that it tends to go to 37% but it is not an absolute number.
Bien vu, en effet. C'était trop facile pour être vrai 😂
hmm I also got the result of 15 unsuccessful cases, but I don't understand how the hell your counting method is good xD
...well, i did at least figure out that you needed to count the amount of unsuccessful draw... that was about as far as i gotten correct, but i'm proud of it
Ha ha, in the Czech Republic we call this problem "Problém šatnářky" (The Cloakroom Attendant Problem) - what is the probability, when N men come to the theater and give their hats to the cloakroom attendant, that no one will get his own hat back, given that the cloakroom attendant hands out the hats randomly.
my friend group actually had to figure this out. in the end one of our non-participating friends handed them out to us.
Ok I understood it, but u should provide more detail on how the double counting could occur:
For example:
If A have 6 occurrence he can pick his name, and B the same, two of them are counted twice :
AB(CD OR DC)
and you should explain how you avoid double counting:
"To know how much each choose his name at east once, you should:
-add when A,B,C,D choose their names (4*3!)
-remove when AB(A choose A, and B choose B), AC, AD, BC, BD are chosen, because we counted them twice:" once when A is chosen at least once and once when B is chosen at least once." and so on ...: 6*2! (=n!/k!=4!/2!) because 6=n!/ (k!(n-k)!)
-but this way ABC,ABD, ACD, BCD are counted 3 times (step 1: A, B, C) the removed 3 times (step 2: AC and AB and BC), so we need to add one time: 4*1! (=4!/3!)
-but this way we counted ABCD 4 times at step 1, then removed 6 times at step 2, then added 4 times at step 3, so we must remove once ABCD: 1*1! (=4!/4!)
I thought it would be a hard puzzle. It's just discrete math. :(
Of course immediately I thought of combination but too lazy to work it out.
I got a similar answer with a different process but I would like to potentially refute this answer. I certainly can understand why the power series for 1/e popped up in your calculations but the definition of probability is the number of favorable outcomes divided by the total outcomes. Since e is a very irrational number it doesn’t make sense how favorable divided by total would equate to 1/e. Rather I analyzed this problem by finding the probability of the first person not picking his own name then the next person not picking his own name given the first person didn’t pick his own name and so on. With this solution I got 0.375 which is very close to your answer but rational unlike 1/e.
3/8 because I watched Numberphile’s derangements video.
So, are the names picked in a certain order, i.e. A, B, C, then D?
I ask because I'm doing this with "brute force". So far I have:
A. (n-1)/n= 3/4❎A
A✅B{1/n= 1/4}: (n-1)/(n-1)= 3/3= 1❎B
B <
A❎B{(n-1)/n= 3/4}: (n-2)/(n-1)= 2/3❎B
I don't need to include the probability that C✅B or D✅B, right?
Yup, I think you're right
The probability that B didn't pick his name, when A didn't pick A's name is 2/3
szymecio
Unless A picks B.
See my python script above.
I did !n/n! So if there were 5 people that would be 44/120 = 0.3666666667 4 people would be .375 2 people would be .5
and I thought it was a simple festive activity...
I tried for a long time and got nowhere close haha
(3/4)*(2/3)*(1/2)*1
so (n-1/n)*(n-2/n-1)...(1)
I don't see how anyone could possibly follow this explanation...plus I don't think it's right anyway..if you exclude the possibility of someone's name being chosen before you get to them then the answer is just 1 over n
You can just divide subfactorial of n which was mentioned on the 3 3 3 = 10 problem by the number of arrangements or permutations of n people or n factorial
I gave the puzzle a try, and I came up with the formula ((n!-(n-1)!)/2)/n!, if you plug in 4 it gives 0.375 which is as you said 37%, but as n gets larger and larger, it very slowly approaches 0.5, and I don't get why my formula is wrong as it makes absolute sense to me. Send me a message if you want to know how I came up with it, or reply and explain what's wrong. Interesting solution anyways :D
There are many ways to solve probability questions. This how i did it.
As the number of people in the draw is small, simple probability will suffice. Also since the order of people drawing names does not affect the result, we can use this to our advantage.
The first person will have a 3/4 chance of drawing a valid name.
Now since order does not matter. We find out who the first person drew and let that guy be the 2nd person to draw. Remember that his name was already picked so there is no way that he can pick his own name.
There are actually only 2 possibility here.
1. He picks the first person's name. So whoever is the 3rd person will have 1/2 chance of picking a name which will make the entire draw successful given the previous 2 were successful.
This happens 1/3 of times.
2. He picks the other 2's name. In this case, the 3rd person will once again have a 1/2 chance of making a successful overall draw given the previous 2 person were successful. (This part is difficult to visualise)
This happens 2/3 of times
If we multiply up the probability of each of the draw, we get 3/4 * ( 1/3 * 1/2 + 2/3 *1/2)= 3/8= 37.5%
Or simply 3/4 *1/2 = 37.5% (by accounting for the fact that probability of 2nd person being successful given 1st is successful = 1)
whoops its just name
where'd that CV come from
+Wang Mingrui I don't understand your logic.
It seems to me that by your system, we could also assume the 2nd person's name hasn't been drawn yet, and instead your equation becomes 3/4 * 2/3 * 1/2 * 1 = 25%, which the incorrect answer.
Yes, you got the correct answer, but not in a way that makes sense. Can you explain your logic as applied to a group of n people?
sk8rdman The first guy picked the 2nd guy's name. It's not possible for the 2nd guy to pick his own name.
sk8rdman But it's true that my grammar is poor. I'll edit the answer.
Wang Mingrui
It is possible for the 2nd guy to pick his own name when the 1st guy hasn't picked it, and you didn't equate for those scenarios.
If you're assuming that the 1st person always draws the 2nd person's name, then your formula becomes 1 * 1 * 1/2 * 1 = 50%
The first person can't draw his own name if he always draws the 2nd person's name.
Also, how does your logic apply to a group of n people?
This was good!
But what happens when everyone pics up names chit together from the hat?
Not one by one. But together at once.
But isn't "At least 1 person" the same as *exactly 1 + ex. 2 + ex. 3 + ... + ex. n* ?
I am perplexed.
+Anston [Music] Exactly what I'm thinking too!!
+Anston [Music] Apparently there is a mistake in the video. The number n!/k! is not the number of ways at least k people draw their own name
Indeed. The answer should be the same as "at least 1 person draws his own name", but that is not what the given expression that he started with actually is.
No. the at least one calculation in the vid double counts a whole lot of cases thats why you need to use incl-excl principle to get the correct number of cases
After a bit of thinking you can notice that each state is described by one number and one bit - the number of people that names in the hat and whether there is a name in the hat that does not belong to any of the people that have not drawn. It is not very hard to devise a recurrent function that calculates the result. Here is the code to a small program I wrote: github.com/indjev99/Small-Projects/blob/master/Probability-and-Combinatorics/Secret-Santa.cpp
+indjev99 I get error 404
+Petr Matas I had renamed the file. Anyway, I edited the comment. It has the correct link now.
+indjev99 Thanks!
Wow! The Stickpicker! (Stickman picker)
Great video! I'm curious if the way I did had something right to it. I found a different formula by just doing the probability of one person not getting it's on name. it's n-1/n. Then, I just remembered that when you have to stack probabilities, they multiply (like when you roll 2 dices trying to get the same number out of both, chances are 1/36). Doing that I found the formula: (n-1/n)^n. I tried applying it and I noticed that the bigger the number of people, the closest the result gets to 37% chance! (Ex: with 100 people you get (100-1/100)^100 witch equals aproximately 0.366, so it's around 36,6% chance.) Is it valid?
Or at least could I say that it is equal to: lim n->infinity of (n-1/n)^n ?. Witch is virtually 37%. (and sorry if I misspelled anything)
+Raphael Antunes The limit as n approaches infinity of (n-1/n)^n is indeed 1/e. Good job.
Denny Chen
Thanks :D
+Raphael Antunes Sorry to burst your bubble, but your equation is incorrect.
Your equation effectively shows the probability that if something with a 1/n chance of occurring is attempted n times, that it won't occur on any of those attempts. For example, if I roll a 6 sided die 6 times, the chance that it won't come up as a 6 on any of those rolls.
Yes, both of these equations approach 1/e, but in radically different ways. Although you did find the correct limit, your formula is not appropriate to this problem. If you solve for n=4, for example, you will get radically different results from your equation, in comparison to the correct equation.
+sk8rdman because the results for small numbers are different it doesn't mean the formula is totally incorrect. It could be that it's inneficient or just incomplete. But I get your point. And also, even though the formulas aproach the problem in different ways, it doesn't mean that they're wrong either. Some problems can be solve by different methods. I was not trying to find the videos answer, I was trying to come up with my own. There's a chance I was totally wrong, yes. But, it could be just that my formula isn't polished enough.
Number of cases at least one matching his name is n!/1! = n! This is the number of total cases so its wrong u double counting in this equation
what's wrong with my thoughts?
1st person has a 3/4 chance of not picking his/her own name
2nd person has a 2/3 chance of not picking his/her own name
3rd person has a 1/2 chance of not picking his/her own name
4th person has no choice
so multiplying all of them yeilds a 1/4 chance of a successful draw?
You are right for the first person. But the second person has 2 paths. If the first person draws the 2nd person's name, then the 2nd person CAN'T draw their own name. So the chance that the 2nd person draws there own name depends on which names are left. That's no hard by itself, but for the 3rd person, you have to look at their chance of drawing their own name for all the possible combinations of draws for person 1 and 2 (if 1 draws 3's name, 3 can't. If 2 draws 3's name, 3 can't. Otherwise, there's a 1/2 chance 3 draws own name).
Also, you can see a flaw in your logic because you say that person 4 has no chance. So for all the possible combinations of choices, person 4 never picks their name, but the example from the video shows the last person doing just that.
04:07 It should be "exactly 1 person getting their own name" instead of "exactly k people getting their own name".
It is (1- 1/n)^n
Obviously converges to 1/e for large n.
This seems rather intuitive as well. Can't this be arrived at from the problem defn as well? The probability that one person doesn't draw own name is (1 - 1/n), probability of all n people doing so is (1 - 1/n) ^n, problem solved. No? The approach taken in the video seems rather convoluted in comparison. What am i missing?
N=2. Prob is 50%. Fail
+AA SS you need to count up to 1/n! term, not up to n-th term, So in this formule for n=2 it'll be 1/2!=1/2 -> 50%. So it works.
Seven scenarios where each one has a chance of existing out of seven scenarios.
if the number of draws where AT LEAST one person got their name (and not EXACTLY one) is indeed C(n,1) times (n-1)! then why would you procede to calculate the number of draws where at least two got their own name? surely the number of draws where at least one gets their name is equal to number of draws where exactly one draws their name plus the number of draws where at least two draw their names (which you can then further divide into cases with exactly 2 drawing their name and those where 3 or more draw their names) meaning you allready counted all those cases in the first step. also having at least one person get their name is all that you need for the draw to be unsuccessfull you say so yourself right before you start calculating. so the probability of unsuccessfull draw would be C(n,1) times (n-1)! divided by n! (and probability of successfull draw is simply one minus that). but the more i think about it the more it seems to me that something is wrong with this formula (or your wording on which cases that represents is wrong)
+AVAruls the more i think about it the more it seems to me that if you look at successfull draws instead of unsuccessfull draws you get that the first person has (n-1) possibilities because he must not draaw his own name the second has (n-2) possibilities since he must not draw his name and also cant draw the one that the first person drew and following this you would get to (n-1)! possible successfull draws out of n! draws total, but it is 2 a.m. right now so i might not be thinking straight :P
It is not the number of unique ways at least one can get the draw. Due to the (n-1)! different ways of selecting the last names some of them can be picked correctly that was already accounted by one of the different combinations. This will give you 2 different ways included that can have 2 names correct. 3 different ways for 3 things and so on.
He removes those cases since they would be excluded in the selection for at least 2 as well, but only one time. The 3 different ways would be included 3 times in the at least 2 cases as well. Thus using his method he will eliminate all the double counting. It is basically using a bit of Pasquales triangle.
The way he mention it is a bit weird though.
P(N) =
if N>1 then : (N-1)/N * P(N-1)
else : 1
... its been a while sense i've done statistics.. so i did it in pseudo-code
wait.. no
P = ((N-1)/N)^N
thank you!
im far from being politically correct, but why bother saying "his or her name" at the beginning if youre just going to say "his name" for basically the rest of the video? i totally understand not wanting to say "his or her" every single time. do you really think the people who possess the logic to understand your videos will be offended if you just said "his name" throughout? i like the video, but i also think more consistency would make it even better.
If I have 2 people, then the probability is 50%
+Amazingmandan333 Yes, but the probability quickly approaches 1/e as n increases.
for n=1; 0/1 or 0%
for n=2; 1/2 or 50%
for n=3; 2/6 or 33.3%
for n=4: 9/24 or 37.5%
for n=5: 44/120 or 36.7%
isn't n=5 going to be 48/120?
First i calculated the amount of possibilities the first person had to draw his/her own name and gave it a name (@):
i have calculated it as ((n-1) x (n-2) x (n-3) ... (n=1)) = @
With knowing this the rest is easy. There are n-1 more scenarios then the ones calculated for @, and i have found that for every alternative scenario, the chance of atleast 1 person drawing their own name is @/2.
so the answer becomes @ + (@/2 x (n-1)) = chance someone get's their name. invert that number from the total amount of possibilities (n x @) and you get your answer.
David Rassers
Rather than put together a formula for it, I literally wrote out all of the possible permutations that work, and took that out of the total number of permutations possible.
This guarantees that I have the right number. You must have made a mistake somewhere in your formula.
In case you want to check for yourself, here are the 44 cases that do work. Each person has a number, and the numbers are pulled in these orders:
21453
21534
23154
23451
23514
24153
24513
24531
25134
25413
25431
34152
35124
31254
34251
35214
31452
35412
35421
31524
34512
34521
43512
45213
41523
43521
45123
41532
45132
45231
41253
43152
43251
53421
54231
51432
53412
54132
51423
54123
54213
51234
53124
53214
25%
As has been pointed out in several of the preceding comments, your answer is correct but your logic isn't. For example, your claim that the number of ways that at least
n-1 (out of n) people could draw their own name is
n!/(n-1)! = n when it's clearly 1. The Wikipedia article "Derangement" makes the same error. Thanks for your enjoyable videos.
Number of derangements..
Yashwanth Reddy Yup. N subfactorial, or n!/e. Hey look! 1/e!!!
Just to clarify does gamma always pan out to be x!/x ???
I am very sorry for you, but this is wrong. Because there is no chance that there are exactly 3 persons wrong. For example:
A B C D
a b c ?
So there are 24 possibilities and only 11 of them don't work. So the solution is 13/24=54.16666%
+Thomas P For four people there are indeed 24 possibilities, but only 9 of them work. So the probability for this case is 9/24, which is already very close to 1/e.
AaBbCcDd
AaBbCdDc
AaBcCbDd
AaBcCdDb
AaBdCbDc
AaBdCcDb
AbBaCcDd
AbBaCdDc*
AbBcCaDd
AbBcCdDa*
AbBdCaDc*
AbBdCcDa
AcBaCbDd
AcBaCdDb*
AcBbCaDd
AcBbCdDa
AcBdCaDb*
AcBdCbDa*
AdBaCbDc*
AdBaCcDb
AdBbCaDc
AdBbCcDa
AdBcCaDb*
AdBcCbDa*
Could you please make videos explaining concepts like this choose thingie. Im not an MIT student
en.wikipedia.org/wiki/Combination#Number_of_k-combinations
Hey presh talwakar can you please explain about gödens incomplete theorem simply
That's neat that it works out to 1/e...but for 2 people is it not 1/2?
+Dan Kelly It approaches 1/e as n goes to infinity. The thing is, it approaches it really fast, so it's pretty accurate for almost all values of n.
gregslife7 Ah the author misled me.He made me think it's 1/e period, but I thought what the hell, it's a discrete problem.
+Dan Kelly It is misleading, but Gregslife7 is right. It approaches 1/e very quickly. Here are some examples of n to show how quickly it approaches 1/e.
I did not simplify the fractions, because I wanted to show the exact values of the number of successful permutations, and total permutations.
for n=1; 0/1 or 0%
for n=2; 1/2 or 50%
for n=3; 2/6 or 33.3%
for n=4: 9/24 or 37.5%
for n=5: 44/120 or 36.7%
For each odd n, the chance is slightly under 1/e, and for each even n, the chance is slightly over 1/e, as long as n is, say, 3 or greater.
+sk8rdman no! if n=1 it is 1/1 or 100%
Ronniece Aquino
If there is one person randomly selecting from only one name (their own) there is a 0/1 or 0% chance that they don't draw their own name.
Odd numbers approach from below 1/e, and even numbers approach from above 1/e.
But 0! = 1.
is it different to limit of (n-1/n)^n? im just asking i didnt solve this.
+Misiok89 The limit is correct, however for finite n the result will be incorrect.
I love your topics and stuff you do, but I feel like your approach in unappealing
50%, n=2
3!/4!
or n-1!/N! shouldnt that be the answer for success
+snehit k (el Dúderínò) (n-1)! / n! = 1/n. That is wrong.
I know
3/8?
no, no I did not figure it out
holey shit, that was a good video
he Presh, i really like your videos and i have watched almost every video. but you should really stop making videos with probability problems. all your recent videos are probability problems. i think it is high time you make videos of other sort of problems! i mean it!
I'd just make it easy:
Person A has 1/4 chance of getting his own name, if he does you start over.
If Person A picks for exaple C, then person C will be the next to pick, he gets D. then Person D picks B, and B gets A. If one gets a name already picked the rest start over.
Secret Santa is supposed to be secretive
+Renax the Man watch the "Assassin's Problem" on yt. There is a great solution to do it in secret and ensuring nobody get's himself ^^ very interesting!
Hello anyone with me
6
4!/e
H
i think the part about the probability being tge same for all is incorrect. so, if there are only two people it is obviously 50% chance: 50% that person A will pick card A, but if he picks card B then person B has 100% chance of picking card A.
+Kusalin Thanyakullsajja The proper claim should be that the probability quickly approaches 37% as the number of participants increases. You could argue that 50% is kind of close to 37%... at any rate, why are just two people doing Secret Santa? There's no secret at all!
its good to get your own name - then you can get a really cool expensive item for yourself, and this annoys the other people