So here is what I have done and seems much easier too comprehend: Let´s start with 10 cards. Everytime you draw a card you have a 10% chance to win and a 90% to miss. You might think, that the probability changes whenever you reveal the next card, but this is not true, since the decreasing number of cards which you still have to reveal make up for the increasing chance, that the needed card is already on the table. For example if you reveal the 4th card the chance of hitting the heart 4 is: (probabilty the 4 is already on the table)(chance of getting the 4 in this case)+(probabilty the 4 is not already on the table)(chance of getting the 4 in this case) =(1-(9/10*8/9*7/8))*0+9/10*8/9*7/8*1/7=0+1/10=0.1% Therefore the chance for losing 10 times in a row is 0.9^10=34.9% My result was not that far away from the one of James, but there was still a gap. For 100 cards I calculated: 0.99^100=36.6% This was even closer to his result but still not the same. But now that I have seen the extra footage, I know, that my results are correct, and for a large number of cards, we even get the same solution. What I have done is basically: (1-1/n)^n, where n is the number of cards. And lim n->infinity (1-1/n)^n=1/e Since James always gives the answer 1/e he has a large errror for small n, which decreases with increasing n. But to answer his question: More cards mean a higher probabilty of losing, but never higher than 1/e.
soeinkrankerscheiss Actually, there is a slight error in your solution. for instance, check the case for n=2. It should be 1/2 but your formula gives 1/4. You can't just multiply the possibilities of an n'th card not being at the n'th place since they aren't independent from each other. In the case for n=2, 1st card not being in the first place assures that the 2nd card is at the first place instead.
Thank you very much I finally understand fixpoint, I was scared that my time was wasted because I didn't saw the term fixpoint in the title or description of the video. It wasn't clickbait after all thank you haha. :)
actually finished discrete mathematics this semester and we solved this in one of the lectures. suddenly i feel so competent, knowing what you're talking about
I am reminded of "manotazo", where players take turns laying down cards and have to slap down the pile when the card layer down coincides with name of the card. The names are spoken in order during turns from ace to King and then ace to King again. Last hand on top of the pile takes the pile. You notice derangements quite often during play
When he was saying that exactly numbers of matches were complicated to work out, you should have asked him the probability that you get exactly 9 matching.
I have used a whole deck of cards to play this game with rules where you lose if you call out the number of the next card (numbers 1...13 are repeated four times). Took me probably hundreds of games to finally win the game.
I recently needed to solve a question which seems to relate to a subset of derangements, which contains no rotations of non-derangements (ie for a seed 1234, do not include 2341, 3412, 4123). The problem presented itself in the form of a sort of virtual pass-the-parcel with 6 players and 6 parcels, whereby the goal is that no player passes to the same player twice (following that no player takes a parcel from the same player twice). A solution I found involved simply stepping by increasing factors, and mirroring, like so: 123456 246135 365214 412563 531642 654321
Please also make a video about sterling function in permutation and combination. Or various ways we distribute objects to people. It would be a great help. Thanks
There is a simpler proof: so for the example with n cards in order to lose the first hand has to be anything but 1 and for that to happen the probability is n-1/n. For the second card anything but 2 and so on. So there are n cards and for this to be true it has to be true for all of the cards. So the probability is ((n-1)/n)^n = (1-1/n)^n) but (1 +x/n)^n = e^x so the probability of losing is e^-1
I sometimes play a game with a full deck of 52 cards. I would flip one card at a time, saying ace, 2, 3, 4, 5, and so on. When I get to King, I would start over at Ace again. What is the probability of getting through the entire deck without matching?
what if there was a problem where the 1 thing that matched was instantly visible? then it would always be faster to jsut randomly throw the things together, remove the 1 match and then repeat the process.
I might be wrong, but if instead of a discrete deck of cards you had a "continuous" deck with infinite cards (each having a number between 0 and 1, for example) then you'd always get a fixed point :D Edit: As Donald pointed out, that's wrong since the 'shuffle' function isn't continuous.
Well, given n cards we also have at least n-1 ways of placing each card somewhere else, just covering the most simple (de)arrangement. And if n is infinity or not doesn't really matter... In most calculations where you put infinity in, the answer is "An infinite amount". But that doesn't mean there has to be a fixed point
what you have is a bijection f(x) from [0,1] to itself. you want x st f(x)=x Continuous means a tiny change in x causes a tiny change in f(x). If endpoints are not included then f(x)=x^2 has no fixed point and is continuous. If endpoints are included then all continuous functions have fixed points. However this does not hold for non continuous functions.
I suspect (but could be completely wrong) that the reason this is approximately 1/e instead of exactly 1/e is because it only reaches 1/e at infinity. In other words 5 cards would be close but not quite 1/e. 6 cards would be even closer but still not quite and so on until infinity you get true 1/e. Can anyone confirm this?
I pondered this during my years of watching auto racing, it seemed that every race, at least one of the cars finished in the same position it started in. Never worked out the probability though, but it didn't come as a surprise that it's genuinely over 50%.
So I watched 8 minutes for seeing how he calculates the number of derangements, because that is the hard part in this, but then he explains everything else than that and just throws !n=n!/e at us with no explanation
My guess for the thing in the beginning: 1: Rephrase question - if you can choose freely between all the cards not used, then put it down on a random position (where there hasn't yet been a chance), what chance is it that you'll get one in the right position 2: For any N cards you have a 1/N chance of getting it correct the first draw, other wise go to step 3 with x being 1 3: If it's not correct, choose the card that should have been in that slot, and put it in a random position, this gives you a 1/(N-x) chance of being back at step 1 with the new N being (x+1) less than the original 4: If you didn't go back to step 1, repeat 3 with x one higher than last time, until you run out of cards. We can split this into two states, having n cards and a chance to win, or having n cards and a chance to close a loop: Win: 1: 1/1 chance to win 2: 1/2 chance to win 3: 1/3 chance to win, 2/3 chance to go to Close:2 - 1/3 + 2/3 * 1/2 = 2/3 4: 1/4 chance to win, 3/4 chance to go to Close:3 - 1/4 + 3/4 * 1/2 = 5/8 5: 1/5 chance to win, 4/5 chance to go to Close:4 - 1/5 + 4/5 * 13/24 = 19/30 (....) Close: 2: 1/2 chance to go to Win:1, 1/2 chance to lose 3: 1/3 chance to go to Win:2, 2/3 chance to go to Close:2 - 1/3 * 1/2 + 2/3 * 1/2 = 1/2 4: 1/4 chance to go to Win:3, 3/4 chance to go to Close:3 - 1/4 * 2/3 + 3/4 * 1/2 = 13/24 5: 1/5 chance to go to Win:4, 4/5 chance to go to Close:4 - 1/5 * 5/8 + 4/5 * 13/24 = 67/120 (...) Since both Close:2 and Win:2 have a 50% chance of winning, and all streaks of loss will eventually go to one of those two, we know for certain that there's at least 50% chance of winning with any amount of cards larger than 0. However, continuing like this is boring, and prone to error (I probably did something wrong in all that, actually), so let's look for abstractions. We could consider a game where you start with a stick, and a number N. There's a 1/N chance of you picking up a stick, and an (N-1)/N chance of losing a stick, if you have one. If you manage to get two sticks, you win. This means that you have to get sticks twice in a row, except on the start, meaning we can abstract having 0 sticks to: 1/(N*(N-1)) chance of winning => 1/(N^2 -N) (N-1)/N chance of subtracting one from N => 1-1/N (N-2)/(N*(N-1)) chance of subtracting two from N => 1/(N-1) - 2/(N^2 - N) Then we just start from 10 and add downwards to get the chance of having a specific amount on N: 10: 1/1 9: 9/10 (from 10) 8: 4/45 (from 10) + 9/10 * 8/9 (from 9) = 8/9 7: 9/10 * 7/72 + 8/9 * 7/8 = 623/720 6: 8/9 * 3/28 + 623/720 * 6/7 = 703/840 5: 623/720 * 5/42 + 703/840 * 5/6 = 4841/6048 4: 703/840 * 2/15 + 4841/6048 * 4/5 = 28423/37800 3: 4841/6048 * 3/20 + 28423/37800 * 3/4 = 137897/201600 2: 28423/37800 * 1/6 + 137897/201600 * 2/3 = 527383/907200 1: 137897/201600 * 1/6 + 527383/907200 * 1/2 = 1468457/3628800 Since 1 is the only loss-state, we know that there's a 1-1468457/3628800 = 2160343/3628800 ≃ 0.595332616843 chance of winning, unless I did something wrong. I have no idea what a generic method would be though. EDIT: Okay, turns out I was wrong. EDIT 2: NVM, I was right, I just forgot that I was supposed to start with 1 stick, not 0: 2160343/3628800 * 10/11 + 1/11 = 2523223/3991680 = 0.6321205607664 (though that's for 11 cards)
I thought he would mention this. When you divide n! by e, you get a number between two integers. The closer one is the number of derangements. The other one is the number of permutations with exactly one fixed point. For example 4!/e is about 8.83. 9 derangements and 8 permutations with one fixed point. 5!/e gives you 44.145. 44 derangements and 45 permutations with one fixed point. For n even, the number of derangements is larger. For n odd, it is smaller.
The probability of getting a derrangement with n cards is (n-1/n)^(n-1) which approaches to 1/e. The probability for n=10 is actually 38. 7%. NOT 36. 8% which is 1/e
Really interesting video.. for 10 cards I get 65% chance of winning.. just doing 1 - (.9)^10... so I guess in this case n isnt large enough to get within 1% of 1/e method?
+maitland1007 It took me a while to figure out what (9/10)^10 calculates. It's the probability of not drawing an ace on the first draw, a two on the second, etc, but replacing the already drawn cards each time. What is needed is that same calculation but not replacing the cards on each draw. Dr. Grimes does that calculation in the Numberphile2 video. For n=10, it's 1 - 1/1! + 1/2! -1/3! + 1/4! -1/5! + 1/6! -1/7! + 1/8! -1/9! + 1/10!. 1 minus that will give the probability of at least one match.
It is wrong because you assumed the position of each card is independent of the others'. It is NOT an independent events problem because the position of one card will affect the position of the rest as you draw from one set of cards.
Well, showing the surprise e and not showing the way it came (inclusion, exclusion, inclusion, exclusion and so on, quite mundane logic) was unduly romanticising this topic
This video should have also covered arrangements, which show the number of ways you can arrange n distinct objects, and are essentially the inverse of derangements. The way to work out the number of arrangements is the same as derangements except instead of alternating between adding and subtracting, you just add. For example, for five objects: Number of derangements = 5! - 5(4!) + 10(3!) - 10(2!) + 5(1!) - 0! = 120 - 120 + 60 - 20 + 5 - 1 = 44 Number of arrangements = 5! + 5(4!) + 10(3!) + 10(2!) + 5(1!) + 0! = 120 + 120 + 60 + 20 + 5 + 1 = 326 The interesting thing about this is that the ratio between number of permutations (120) and arrangements (326) is the same as the ratio between the number of derangements and permutations. They both converge to e (~2.718).
I took a class in set theory lately, and I used a general form of the Principle of Inclusion and Exclusion to solve this problem: (Sorry, I can't explain my process properly) Let S(i) denote the set of possible permutations that result in a win in the i-th position. Let x(1) = |S1| = |S2| = |S3| = ... = |Sn| x(2) = |S1 n S2| = |S2 n S3| = |S1 n S3| = ... ... |S1 u S2 u S3 u ... u Sn| = (nC1)x1 - (nC2)x2 + (nC3)x3 - ... + (-1)^(n-1) (nCn)x(n) For this video, n = 10 x(1) = 9! x(2) = 8! ... x(9) = 1! x(10) = 0! Num of possible outcomes: 10! = 3628800 Num of winning outcomes = 10x9! - 45x8! + 120x7! - 210x6! + 252x5! - 210x4! + 120x3! - 45x2 + 10 - 1 = 2293839 P(win) = 2293839 / 3628800 = 63.2% (3 sf)
Wow I made a video on this topic and why the probability in cases like this is 1-(e^(-1)) on my channel a few months ago! I enjoyed watching this nonetheless.
A similar but harder question. Two packs of cards are shuffled together. What is the probability that two identical cards will lie adjacent to each other? Would love to see a solution.
The chance of getting at least one right is approaching 1/e for n going to infinity. The formula for calculating the chance for any number n can be derived from first principles..
When I was a kid I played a game like that with cards, except there were a few differences. First, we used a full deck of cards. Second, we would do 4 cycles of the cards since there are 4 suits. And third, we called getting a match a loss. It was a very hard game to win. I remember spending tons of time playing it over and over trying to get a win without cheating. Exactly what would be the odds in this case?
Just curious, is this the same process in determining the chances of two students in a certain classroom having the same birthday, or was that another Numberphile episode?
You know what's funny? The literal translation of "derangement" in brazilian Portuguese, "desarranjo", is usually used to mean "diarrhea". Hahahahahahahahahahahahaha. So I guess this is the reason we use "chaotic permutation", "permutação caótica", as the name for derangements. Hahahahahaha.
This made me wonder what the probability is of getting one match, two matches etc… Turns out it’s actually quite easy to work out. If you have n objects and want to work out how many ways there are of having exactly (n - k) matches, you need to do !k, since k objects need to be in the incorrect position, then multiply that by n choose k, since that’s how many ways there are to choose k objects. However, !k * nCk can actually be rewritten k!/e * n!/k!(n - k)!. The k! then cancels out and we’re left with n!/e(n - k)!, which is the same as !n/(n - k)!. So, if we have a set of n objects with k objects in the wrong position, we should expect the number of possible ways to be roughly the same when k = n and when k = n - 1, then about half at k = n - 2, then about a sixth at k = n - 3 etc… This checks out for eight objects: 0 fixed points - 14,833 1 fixed point - 14,832 2 fixed points - 7,420 3 fixed points - 2,464 4 fixed points - 630 5 fixed points - 112 6 fixed points - 28 7 fixed points - 0 8 fixed points - 1 This also makes sense because the sum of !n/(n - k)! becomes roughly !n *e as k goes from n to 0. !n/0! + !n/1! + !n/2! + !n/3!… + !n/n! = !n(1 + 1 + 1/2! + 1/3!… + 1/n!) ≈ !n * e = n!.
The answer for the 7:18 question is: The probability of a person get his own hats among "n" hats is: 1/n The probability of a person doesn't get his own hats among "n" hats is: (n-1)/n The probability of "k" persons get their own hats among "n" hats is: (1/n)^(k) The probability of the rest of them doesn't get their own hats is: ((n-1)/n)^(n - k) Then, the probability of "k" persons get their own hats and the others don't is: (1/n)^k * ((n-1)/n)^(n-k) The number of k-combinations in a set has "n" elements is equal to: n!/(k!(n-k)!) So, the probability of only "k" persons gets their own hats is: (1/n)^k * ((n-1)/n)^(n-k) * n!/(k!(n-k)!) Q.E.D.
@Numberphile Where's the error in this? The chance of not getting a single match: 9/10*8/9*7/8*6/7*5/6*4/5*3/4*2/3*1/2 = 0,1. So the chance of hitting at least one match is 1-0,1=0,9
Interestingly, the same 63/37 % applies for the decay in moving average CPU load in UNIX systems calculation (i.e. a 5-minute average CPU load contains 37% of the past and 63% of the past 5 minutes) - according to Wikipedia anyway.
I did similar math that came up with a similar result a while ago. I was doing shiny-hunting in Pokemon by breeding, and figuring out what my chances are. The raw chances are 1/512, so I asked "What's the chance I'd get one within 512 eggs?" Turns out it was the same number, around 64%. So I wondered how much that changed if I played with the numbers. I found out a limit this way, and stumbled across e. Turns out, according to Wolfram|Alpha, the problem spits out like this: 1-((x-1)/x)^x→(e-1)/e, as x→∞. That's your chance of rolling a natural 20 somewhere in 20 d20 rolls, your chance of rolling a natural 100 in 100 d100 rolls. Amazing where e pops up.
If the formula for the probability of a derangement is round(n! / e) / n!, then the formula still applies at n=2, since round(2/e)/2 = 1/2. since 2/e = 0.735758882 and at n=1, round(1/e)/1 = 0, you can't not get a derangement with 1 card, so the formula works for any number in the natural numbers. Also as n increases towards infinity the results approaches 1/e, despite never being exactly 1/e.
Wait, isn't simply the chance of getting 2 or more matches 0,63 * 0,37 ? I mean, you can take out the first match and then you have the same thing. In those 63% you had a match, you have 63% of chance having another match. Then it would theoretically go: No match: 0,37 Exactly 1 match: 0,63 * 0,37 Exactly 2 matches: 0,63 * 0,63 * 0,37 Exactly 3 matches: (0,63)^3 * 0,37 Exactly n matches: (0,63)^n * 0,37 and so on - of course there would appear margin of error eventually, since you're running out of cards.
I have a question on something this reminds me of. (X*(Y-1)+Y)/Y^n=Chance this is incomplete but represents the chance of successfully getting a wanted roll over n rolls. A while ago I was trying to figure out how to create a balanced dnd campaign and needed a way to calculate what would be a fair or reasonable set of rolls to succeed at something. With this if you had a 6 sided die and rolled trying to get at least one 6 then your probability follows: 1/6, 11/36, 91/216, 671/1296, 4651/7776, ... The same works for all other "1/Y" that I've tried and I was working on a simplified version for greater variances of X. Is anyone familiar with this kind of calculation or the name to look it up?
To me it's just seems more easy to do 100*0.9^10 Where 100 is just to have a value in percentage and not in 0.something, 0.9 is the chance of the match not happening (if i have 10 cards and only one i have a 10% of placing that card in the correct place, so 90% of not doing that) and the ^10 so we can calculate the chance of all 10 not be in the "win" position, this give me a 34.86....% in the calculator, so does my way of taking on the "problem" flawed somewere? (probabily is, as the % is similar but not the same >.
Not to, you know, be that guy, but isn't a match in 10 cards 65.1ish percent? not 63? I mean I'm just doing 1-0.9^10 here. Similarly, a match in 4 cards is 68ish percent. Seriously, correct me if I'm wrong.
I don't think the question for exactly k fixed points is much harder; the total number of permutations of n elements having exactly k fixed points should be (n choose k) * !(n-k), which is about n!/k! * 1/e for n large compared to k.
If you want to know the probability of 2 results, 3, etc.. wouldn't it be valid to just multiply that 63% chance N times? I.e., for two coincidental matching positions, .63 * .63 = .3969 or 39.69%.. This should be valid in my mind because if you look at the new set of items to derange as a new problem, there's a 63% chance again (unless you're at
Let me try to clear things up. The probability is technically never exactly .63 but rather just approaches 1-1/e which is approximately .632 and when he says that it is 63% at 4 or above he means that, to the nearest percent, it is 63%. You must use a special formula for binomial probability to find the probability for an exact number of times. I have a video on this on my channel called the "Probability Challenge" that explains this better.
The doggies held a meeting, They came from near and far, Some came by motorcycle, And some by motorcar, And entering the meeting-hall, Each doggie signed the book, And each unshipped his arsehole, And hung it on a hook. One dog was not invited; It sorely raised his ire; He ran into the meeting, And loudly shouted "FIRE!" The place was in confusion; Without a second look, Each doggie took an arsehole, From off the nearest hook. And that's the reason why, Sir, Whene'er two doggies meet, And that's the reason why, Sir, In park, or field, or street, And that's the reason why, Sir, On land, or sea, or foam: They'll sniff each other's arsehole, To find if it's their own. (Same mathematical problem, to the tune of "The Church's One Foundation", from the days of coarse rugby.)
I showed !n = (n - 1) * [!(n - 1) + !(n - 2)] with !0 = 1 and !1 = 0. However, !n = n!/e is a lot nicer than this recursive formula. Also, I think there are (n choose k) * !(n - k) permutations with exactly k fixed points.
But I have read that total no. of rearrangement is something else. Like we have 5 cards numbering 1 to 5 and 5 envelope number 1to 5 then the the total number of way such that no card goes to their respective envelope is 5!(1/0!-1/1!+1/2!-1/3!+1/4!-1/5!)
I tried to tackle this question, what is the probability of winning if the win condition is at least two cards are in the correct position. We see in the video that for at least 1 card in the correct position, the probability is 1-(1/e). The number of ways to arrange n things so that exactly 1 item is in its correct position would be the same as the number of ways to fix a single point which is n, multiplied by the number of ways to make a derangement of the other n-1 points which is !(n-1). n * !(n-1) = n * (n-1)!/e or n!/e. So the probability of two or more fixed points would be (1 - (P 0 fixed points) - (P 1 fixed point)) = 1 - ((n!/e)/n!) - ((n!/e)/n!) = 1-(2/e). If this is not correct, can someone point out where I went wrong.
Extra footage from this interview: ua-cam.com/video/qYAWjIVY7Zw/v-deo.html
I absolutely LOVE when you film with James!
So here is what I have done and seems much easier too comprehend:
Let´s start with 10 cards. Everytime you draw a card you have a 10%
chance to win and a 90% to miss. You might think, that the probability
changes whenever you reveal the next card, but this is not true, since
the decreasing number of cards which you still have to reveal make up
for the increasing chance, that the needed card is already on the table.
For example if you reveal the 4th card the chance of hitting the heart 4
is:
(probabilty the 4 is already on the table)(chance of getting the 4 in this case)+(probabilty the 4 is not already on the table)(chance
of getting the 4 in this case)
=(1-(9/10*8/9*7/8))*0+9/10*8/9*7/8*1/7=0+1/10=0.1%
Therefore the chance for losing 10 times in a row is 0.9^10=34.9%
My result was not that far away from the one of James, but there was
still a gap. For 100 cards I calculated: 0.99^100=36.6%
This was even closer to his result but still not the same. But now that I
have seen the extra footage, I know, that my results are correct, and
for a large number of cards, we even get the same solution. What I have
done is basically:
(1-1/n)^n, where n is the number of cards. And lim n->infinity
(1-1/n)^n=1/e
Since James always gives the answer 1/e he has a large errror for small
n, which decreases with increasing n. But to answer his question: More
cards mean a higher probabilty of losing, but never higher than 1/e.
soeinkrankerscheiss Actually, there is a slight error in your solution. for instance, check the case for n=2. It should be 1/2 but your formula gives 1/4. You can't just multiply the possibilities of an n'th card not being at the n'th place since they aren't independent from each other. In the case for n=2, 1st card not being in the first place assures that the 2nd card is at the first place instead.
The video itself specified only values of n above 4. n=2 does not apply.
soeinkrankerscheiss's solution applies to all positive integers. Likewise 민경효's point applies to all positive integers n as well.
Accidental Derangement would make a great name for a band...
Marc Raccioppo +
Yes!
Imma write that down, if you don't mind
Thank you very much I finally understand fixpoint, I was scared that my time was wasted because I didn't saw the term fixpoint in the title or description of the video. It wasn't clickbait after all thank you haha. :)
actually finished discrete mathematics this semester and we solved this in one of the lectures. suddenly i feel so competent, knowing what you're talking about
Derangement judgment = " We thought you lost, you're actually a genius!"
I am reminded of "manotazo", where players take turns laying down cards and have to slap down the pile when the card layer down coincides with name of the card. The names are spoken in order during turns from ace to King and then ace to King again. Last hand on top of the pile takes the pile. You notice derangements quite often during play
e is that friend you don't like that always shows up when you're going out with your other friends.
When he was saying that exactly numbers of matches were complicated to work out, you should have asked him the probability that you get exactly 9 matching.
The number 37% made me think in conjunction with the structure of the game about the secretary choosing problem...
Called it! I can haz brain.
I have used a whole deck of cards to play this game with rules where you lose if you call out the number of the next card (numbers 1...13 are repeated four times). Took me probably hundreds of games to finally win the game.
I recently needed to solve a question which seems to relate to a subset of derangements, which contains no rotations of non-derangements (ie for a seed 1234, do not include 2341, 3412, 4123).
The problem presented itself in the form of a sort of virtual pass-the-parcel with 6 players and 6 parcels, whereby the goal is that no player passes to the same player twice (following that no player takes a parcel from the same player twice).
A solution I found involved simply stepping by increasing factors, and mirroring, like so:
123456
246135
365214
412563
531642
654321
Please also make a video about sterling function in permutation and combination. Or various ways we distribute objects to people. It would be a great help. Thanks
There is a simpler proof: so for the example with n cards in order to lose the first hand has to be anything but 1 and for that to happen the probability is n-1/n. For the second card anything but 2 and so on. So there are n cards and for this to be true it has to be true for all of the cards. So the probability is ((n-1)/n)^n = (1-1/n)^n) but (1 +x/n)^n = e^x so the probability of losing is e^-1
Damn, why does the math lesson always stop at the interesting point I wanted to know more about? Story of my life
I sometimes play a game with a full deck of 52 cards. I would flip one card at a time, saying ace, 2, 3, 4, 5, and so on. When I get to King, I would start over at Ace again. What is the probability of getting through the entire deck without matching?
what if there was a problem where the 1 thing that matched was instantly visible? then it would always be faster to jsut randomly throw the things together, remove the 1 match and then repeat the process.
can you make a video about Catalan Numbers and Super Catalan Numbers?
wrote some python code for fun to test this out. It really always comes out at about 63% wins.
huh, math is fun sometimes
I always knew he was a tiny person
but did you know he's especially unlucky?
He do looks like Bilbo Baggins.
For some reason, I pictured Dr. James as being taller than me (I'm only 5'10"). I guess big brains makes me picture a giant.😄
TINY HANDS!!?? JAMES IS TRUMP!!!!!!
The correct title for this video is “Parker permutations”
Was looking for this :D
You win.
Did you use word document?
Those left/right quotation marks are strange indeed...
Parker quotations
e is like a Spanish Inquisition
Lucas Preti Nobody expects the Spanish inquisition (first heard of it from MikeBurnFire :3)
Lucas Preti Oh no: Not the comfy chair!
Our 2.718281828... chief weapons are...
I'm past being surprised when e comes up. It's so unpredictable that it's now predictable. When in doubt, use e.
I definitely find these videos interesting, but the main reason I watch them is to see the mathematicians get really, really excited. It's so fun.
Need much more 'surprise e' in my life
All the other professors (and hosts) are really really great (seriously they're awesome) but Dr. James Grime is my absolute favorite.
We did this in class today. If only this video released yesterday...
Lelouch Yagami watch tge video tomorrow, then the video would have been released yesterday...
Well aren't you a helpful chap
What is today but yesterday's tomorrow?
What is tomorrow but today's destination?
isn't it summer break right now?
(Well it is where I live)
Only watching because of James Grime
ZetDude Gaming same
What do you mean old-fashioned? Don't you check your hat at the theatre? What do you do with it? How do the people behind you see the stage?
Fraser McFadyen you get your Hat off...or don't wear one at all
"It looks like you've got the world's smallest hands."
Perhaps James could be President of the United States.
Id vote for him.... if I were American....
@@bwayagnesarchives or if he were american :P
Orange man bad.
Pretty fitting how the title is called "Derangements"...
??
I JUST WATCH THESE VIDEOS TO LOOK SMART
It's a Trap cool...
It's a Trap admittance is the first step to solving your issue
What should I watch to look stupid? Have an idea?
admittance isn't the right word, i think you mean "the first step to solving a problem is admitting you have one"
:)
6:31 #ParkerSquare
I like that because 3 is almost 4
I might be wrong, but if instead of a discrete deck of cards you had a "continuous" deck with infinite cards (each having a number between 0 and 1, for example) then you'd always get a fixed point :D
Edit: As Donald pointed out, that's wrong since the 'shuffle' function isn't continuous.
Well, given n cards we also have at least n-1 ways of placing each card somewhere else, just covering the most simple (de)arrangement. And if n is infinity or not doesn't really matter... In most calculations where you put infinity in, the answer is "An infinite amount". But that doesn't mean there has to be a fixed point
what you have is a bijection f(x) from [0,1] to itself. you want x st f(x)=x Continuous means a tiny change in x causes a tiny change in f(x). If endpoints are not included then f(x)=x^2 has no fixed point and is continuous. If endpoints are included then all continuous functions have fixed points. However this does not hold for non continuous functions.
I suspect (but could be completely wrong) that the reason this is approximately 1/e instead of exactly 1/e is because it only reaches 1/e at infinity. In other words 5 cards would be close but not quite 1/e. 6 cards would be even closer but still not quite and so on until infinity you get true 1/e. Can anyone confirm this?
Isn't this Banach's Fixed Point theorem?
+wingracer 16 Look at the follow up video. He calculates the exact probability for n cards. 1/e shows up only at the limit.
I see what you did there! 1:46 #ParkerSquare
I pondered this during my years of watching auto racing, it seemed that every race, at least one of the cars finished in the same position it started in. Never worked out the probability though, but it didn't come as a surprise that it's genuinely over 50%.
Singingbanana!
Usual answer here would be "Didn't expect to see you here!" but I kind of did :D
Tom Scott!
Andrew Huang!
OBAMA!!
"We're gonna get deranged, let's do that."
Okay?
So I watched 8 minutes for seeing how he calculates the number of derangements, because that is the hard part in this, but then he explains everything else than that and just throws !n=n!/e at us with no explanation
The whole Derangement concept is an application of inclusion exclusion principle. I hope you are familiar with this beautiful principle.
So haven't you watched the second video?
Well that’s what the extra footage is for
( 1- (1/n) ) ^ n = 1/e, as n --> infinity
For an easy example, try 0.9^10 and 0.99^100. Converges toward 0.367
Yay! James Grime!!!
My guess for the thing in the beginning:
1: Rephrase question - if you can choose freely between all the cards not used, then put it down on a random position (where there hasn't yet been a chance), what chance is it that you'll get one in the right position
2: For any N cards you have a 1/N chance of getting it correct the first draw, other wise go to step 3 with x being 1
3: If it's not correct, choose the card that should have been in that slot, and put it in a random position, this gives you a 1/(N-x) chance of being back at step 1 with the new N being (x+1) less than the original
4: If you didn't go back to step 1, repeat 3 with x one higher than last time, until you run out of cards.
We can split this into two states, having n cards and a chance to win, or having n cards and a chance to close a loop:
Win:
1: 1/1 chance to win
2: 1/2 chance to win
3: 1/3 chance to win, 2/3 chance to go to Close:2 - 1/3 + 2/3 * 1/2 = 2/3
4: 1/4 chance to win, 3/4 chance to go to Close:3 - 1/4 + 3/4 * 1/2 = 5/8
5: 1/5 chance to win, 4/5 chance to go to Close:4 - 1/5 + 4/5 * 13/24 = 19/30
(....)
Close:
2: 1/2 chance to go to Win:1, 1/2 chance to lose
3: 1/3 chance to go to Win:2, 2/3 chance to go to Close:2 - 1/3 * 1/2 + 2/3 * 1/2 = 1/2
4: 1/4 chance to go to Win:3, 3/4 chance to go to Close:3 - 1/4 * 2/3 + 3/4 * 1/2 = 13/24
5: 1/5 chance to go to Win:4, 4/5 chance to go to Close:4 - 1/5 * 5/8 + 4/5 * 13/24 = 67/120
(...)
Since both Close:2 and Win:2 have a 50% chance of winning, and all streaks of loss will eventually go to one of those two, we know for certain that there's at least 50% chance of winning with any amount of cards larger than 0.
However, continuing like this is boring, and prone to error (I probably did something wrong in all that, actually), so let's look for abstractions.
We could consider a game where you start with a stick, and a number N. There's a 1/N chance of you picking up a stick, and an (N-1)/N chance of losing a stick, if you have one. If you manage to get two sticks, you win.
This means that you have to get sticks twice in a row, except on the start, meaning we can abstract having 0 sticks to:
1/(N*(N-1)) chance of winning => 1/(N^2 -N)
(N-1)/N chance of subtracting one from N => 1-1/N
(N-2)/(N*(N-1)) chance of subtracting two from N => 1/(N-1) - 2/(N^2 - N)
Then we just start from 10 and add downwards to get the chance of having a specific amount on N:
10: 1/1
9: 9/10 (from 10)
8: 4/45 (from 10) + 9/10 * 8/9 (from 9) = 8/9
7: 9/10 * 7/72 + 8/9 * 7/8 = 623/720
6: 8/9 * 3/28 + 623/720 * 6/7 = 703/840
5: 623/720 * 5/42 + 703/840 * 5/6 = 4841/6048
4: 703/840 * 2/15 + 4841/6048 * 4/5 = 28423/37800
3: 4841/6048 * 3/20 + 28423/37800 * 3/4 = 137897/201600
2: 28423/37800 * 1/6 + 137897/201600 * 2/3 = 527383/907200
1: 137897/201600 * 1/6 + 527383/907200 * 1/2 = 1468457/3628800
Since 1 is the only loss-state, we know that there's a 1-1468457/3628800 = 2160343/3628800 ≃ 0.595332616843 chance of winning, unless I did something wrong.
I have no idea what a generic method would be though.
EDIT: Okay, turns out I was wrong.
EDIT 2: NVM, I was right, I just forgot that I was supposed to start with 1 stick, not 0: 2160343/3628800 * 10/11 + 1/11 = 2523223/3991680 = 0.6321205607664 (though that's for 11 cards)
James Grime 😍😍😍
Is this the problem with Secret Santa when someone gets their own name?
pretty much
JEE aspirant attendance here
The man, the myth, the legend is back. Best videos when you're in them
I thought he would mention this. When you divide n! by e, you get a number between two integers. The closer one is the number of derangements. The other one is the number of permutations with exactly one fixed point. For example 4!/e is about 8.83. 9 derangements and 8 permutations with one fixed point. 5!/e gives you 44.145. 44 derangements and 45 permutations with one fixed point. For n even, the number of derangements is larger. For n odd, it is smaller.
The probability of getting a derrangement with n cards is (n-1/n)^(n-1) which approaches to 1/e. The probability for n=10 is actually 38. 7%. NOT 36. 8% which is 1/e
1:16
"37.....Oh that number again"
Veritasium sound in the background
Really interesting video.. for 10 cards I get 65% chance of winning.. just doing 1 - (.9)^10... so I guess in this case n isnt large enough to get within 1% of 1/e method?
For 10 cards the probability is 63.21205357%
then whats wrong with 1- (9/10)^10, which gives .65?
+maitland1007 It took me a while to figure out what (9/10)^10 calculates. It's the probability of not drawing an ace on the first draw, a two on the second, etc, but replacing the already drawn cards each time. What is needed is that same calculation but not replacing the cards on each draw. Dr. Grimes does that calculation in the Numberphile2 video.
For n=10, it's 1 - 1/1! + 1/2! -1/3! + 1/4! -1/5! + 1/6! -1/7! + 1/8! -1/9! + 1/10!. 1 minus that will give the probability of at least one match.
It is wrong because you assumed the position of each card is independent of the others'. It is NOT an independent events problem because the position of one card will affect the position of the rest as you draw from one set of cards.
Well, showing the surprise e and not showing the way it came (inclusion, exclusion, inclusion, exclusion and so on, quite mundane logic) was unduly romanticising this topic
Everyone: you can't use any symbol anywhere with a proper meaning.
e: hmmm, seriously?
if I'm watching this video, am I deranged?
help.
did you watch it when you were supposed to?
only if you ended the video in a different position from when you started
I just watched a man eat 203 cookies just before this
Cameron
I just watched Tom Scott code the fizz buzz problem
This video should have also covered arrangements, which show the number of ways you can arrange n distinct objects, and are essentially the inverse of derangements. The way to work out the number of arrangements is the same as derangements except instead of alternating between adding and subtracting, you just add. For example, for five objects:
Number of derangements = 5! - 5(4!) + 10(3!) - 10(2!) + 5(1!) - 0! = 120 - 120 + 60 - 20 + 5 - 1 = 44
Number of arrangements = 5! + 5(4!) + 10(3!) + 10(2!) + 5(1!) + 0! = 120 + 120 + 60 + 20 + 5 + 1 = 326
The interesting thing about this is that the ratio between number of permutations (120) and arrangements (326) is the same as the ratio between the number of derangements and permutations. They both converge to e (~2.718).
I loved this explanation for Derangements by Jamie!
Fascinating video! Thank you! Please do more probability videos.
Just watched an ad on the derangements video! Glad we got that sorted. Tims rejoyce.
i see the parker's square when at the back of the cards....
Interesting how both transcendental numbers can be expressed as a ratio of two quantities,
tau : Circumference/radius
e : n!/!n, n->infinity
James Bissonette? Of "History Matters" fame?
I took a class in set theory lately, and I used a general form of the Principle of Inclusion and Exclusion to solve this problem:
(Sorry, I can't explain my process properly)
Let S(i) denote the set of possible permutations that result in a win in the i-th position.
Let x(1) = |S1| = |S2| = |S3| = ... = |Sn|
x(2) = |S1 n S2| = |S2 n S3| = |S1 n S3| = ...
...
|S1 u S2 u S3 u ... u Sn| = (nC1)x1 - (nC2)x2 + (nC3)x3 - ... + (-1)^(n-1) (nCn)x(n)
For this video, n = 10
x(1) = 9!
x(2) = 8!
...
x(9) = 1!
x(10) = 0!
Num of possible outcomes: 10! = 3628800
Num of winning outcomes = 10x9! - 45x8! + 120x7! - 210x6! + 252x5! - 210x4! + 120x3! - 45x2 + 10 - 1
= 2293839
P(win) = 2293839 / 3628800
= 63.2% (3 sf)
Wow I made a video on this topic and why the probability in cases like this is 1-(e^(-1)) on my channel a few months ago! I enjoyed watching this nonetheless.
Gonna pretend like I know what's going on
As soon as he said 37% I knew e was coming!
A similar but harder question. Two packs of cards are shuffled together. What is the probability that two identical cards will lie adjacent to each other? Would love to see a solution.
The chance of getting at least one right is approaching 1/e for n going to infinity. The formula for calculating the chance for any number n can be derived from first principles..
"It looks like you got the world's smallest hands!"
Donald Trump approves this message.
0:17
Aaaahahah! He was making the same joke as I was making it! Wonderful!
The title of this video hurts my delicate sensibility. DEMONITIZED!
James Grimes + Mathematics has just taken the No 1 spot in my all time list of best things I have ever watched.
When I was a kid I played a game like that with cards, except there were a few differences. First, we used a full deck of cards. Second, we would do 4 cycles of the cards since there are 4 suits. And third, we called getting a match a loss. It was a very hard game to win. I remember spending tons of time playing it over and over trying to get a win without cheating. Exactly what would be the odds in this case?
James is the most interesting person on numberphile. Change my mind
I absolutely love these videos
thanks
Surprise "e"! should compite against Surprise Lightsaber!
I just think that James would be the best doctor who certainly except tennant
The gasp when he says "divided by e" hahahaha
2:04 Right before he said "What of it's 2 cards? I had it in my mind... Cool!
Who would have thought Donald Trump was good at maths!?
Then again, I suppose the video is about derangement, soooooo
Just curious, is this the same process in determining the chances of two students in a certain classroom having the same birthday, or was that another Numberphile episode?
I will act like I already knew the answer since I knew it has something to do with combinatorial analysis!
You know what's funny? The literal translation of "derangement" in brazilian Portuguese, "desarranjo", is usually used to mean "diarrhea". Hahahahahahahahahahahahaha. So I guess this is the reason we use "chaotic permutation", "permutação caótica", as the name for derangements. Hahahahahaha.
7:28 *m a t h e m a t i c a l w e a p o n s*
This made me wonder what the probability is of getting one match, two matches etc… Turns out it’s actually quite easy to work out. If you have n objects and want to work out how many ways there are of having exactly (n - k) matches, you need to do !k, since k objects need to be in the incorrect position, then multiply that by n choose k, since that’s how many ways there are to choose k objects.
However, !k * nCk can actually be rewritten k!/e * n!/k!(n - k)!. The k! then cancels out and we’re left with n!/e(n - k)!, which is the same as !n/(n - k)!. So, if we have a set of n objects with k objects in the wrong position, we should expect the number of possible ways to be roughly the same when k = n and when k = n - 1, then about half at k = n - 2, then about a sixth at k = n - 3 etc… This checks out for eight objects:
0 fixed points - 14,833
1 fixed point - 14,832
2 fixed points - 7,420
3 fixed points - 2,464
4 fixed points - 630
5 fixed points - 112
6 fixed points - 28
7 fixed points - 0
8 fixed points - 1
This also makes sense because the sum of !n/(n - k)! becomes roughly !n *e as k goes from n to 0. !n/0! + !n/1! + !n/2! + !n/3!… + !n/n! = !n(1 + 1 + 1/2! + 1/3!… + 1/n!) ≈ !n * e = n!.
“the grime 10 card derangement”
e is like ur old girlfriend. she keeps occasionaly showing up in front of you, but by total accident.
The answer for the 7:18 question is:
The probability of a person get his own hats among "n" hats is:
1/n
The probability of a person doesn't get his own hats among "n" hats is:
(n-1)/n
The probability of "k" persons get their own hats among "n" hats is:
(1/n)^(k)
The probability of the rest of them doesn't get their own hats is:
((n-1)/n)^(n - k)
Then, the probability of "k" persons get their own hats and the others don't is:
(1/n)^k * ((n-1)/n)^(n-k)
The number of k-combinations in a set has "n" elements is equal to:
n!/(k!(n-k)!)
So, the probability of only "k" persons gets their own hats is:
(1/n)^k * ((n-1)/n)^(n-k) * n!/(k!(n-k)!)
Q.E.D.
@Numberphile
Where's the error in this?
The chance of not getting a single match: 9/10*8/9*7/8*6/7*5/6*4/5*3/4*2/3*1/2 = 0,1.
So the chance of hitting at least one match is 1-0,1=0,9
Interestingly, the same 63/37 % applies for the decay in moving average CPU load in UNIX systems calculation (i.e. a 5-minute average CPU load contains 37% of the past and 63% of the past 5 minutes) - according to Wikipedia anyway.
I did similar math that came up with a similar result a while ago. I was doing shiny-hunting in Pokemon by breeding, and figuring out what my chances are. The raw chances are 1/512, so I asked "What's the chance I'd get one within 512 eggs?" Turns out it was the same number, around 64%. So I wondered how much that changed if I played with the numbers. I found out a limit this way, and stumbled across e. Turns out, according to Wolfram|Alpha, the problem spits out like this: 1-((x-1)/x)^x→(e-1)/e, as x→∞. That's your chance of rolling a natural 20 somewhere in 20 d20 rolls, your chance of rolling a natural 100 in 100 d100 rolls. Amazing where e pops up.
If the formula for the probability of a derangement is round(n! / e) / n!, then the formula still applies at n=2, since round(2/e)/2 = 1/2. since 2/e = 0.735758882 and at n=1, round(1/e)/1 = 0, you can't not get a derangement with 1 card, so the formula works for any number in the natural numbers. Also as n increases towards infinity the results approaches 1/e, despite never being exactly 1/e.
Wait, isn't simply the chance of getting 2 or more matches 0,63 * 0,37 ? I mean, you can take out the first match and then you have the same thing. In those 63% you had a match, you have 63% of chance having another match. Then it would theoretically go:
No match: 0,37
Exactly 1 match: 0,63 * 0,37
Exactly 2 matches: 0,63 * 0,63 * 0,37
Exactly 3 matches: (0,63)^3 * 0,37
Exactly n matches: (0,63)^n * 0,37
and so on - of course there would appear margin of error eventually, since you're running out of cards.
I have a question on something this reminds me of.
(X*(Y-1)+Y)/Y^n=Chance
this is incomplete but represents the chance of successfully getting a wanted roll over n rolls.
A while ago I was trying to figure out how to create a balanced dnd campaign and needed a way to calculate what would be a fair or reasonable set of rolls to succeed at something.
With this if you had a 6 sided die and rolled trying to get at least one 6 then your probability follows: 1/6, 11/36, 91/216, 671/1296, 4651/7776, ...
The same works for all other "1/Y" that I've tried and I was working on a simplified version for greater variances of X. Is anyone familiar with this kind of calculation or the name to look it up?
To me it's just seems more easy to do 100*0.9^10
Where 100 is just to have a value in percentage and not in 0.something, 0.9 is the chance of the match not happening (if i have 10 cards and only one i have a 10% of placing that card in the correct place, so 90% of not doing that) and the ^10 so we can calculate the chance of all 10 not be in the "win" position, this give me a 34.86....% in the calculator, so does my way of taking on the "problem" flawed somewere? (probabily is, as the % is similar but not the same >.
Not to, you know, be that guy, but isn't a match in 10 cards 65.1ish percent? not 63?
I mean I'm just doing 1-0.9^10 here.
Similarly, a match in 4 cards is 68ish percent.
Seriously, correct me if I'm wrong.
Exactly speaking, NO number of cards has the probability of 63%. The probability just CONVERGES to somewhere near 63%.
I don't think the question for exactly k fixed points is much harder; the total number of permutations of n elements having exactly k fixed points should be (n choose k) * !(n-k), which is about n!/k! * 1/e for n large compared to k.
If you want to know the probability of 2 results, 3, etc.. wouldn't it be valid to just multiply that 63% chance N times? I.e., for two coincidental matching positions, .63 * .63 = .3969 or 39.69%.. This should be valid in my mind because if you look at the new set of items to derange as a new problem, there's a 63% chance again (unless you're at
Let me try to clear things up. The probability is technically never exactly .63 but rather just approaches 1-1/e which is approximately .632 and when he says that it is 63% at 4 or above he means that, to the nearest percent, it is 63%. You must use a special formula for binomial probability to find the probability for an exact number of times. I have a video on this on my channel called the "Probability Challenge" that explains this better.
I'm still waiting for the episode on numberwang
The doggies held a meeting,
They came from near and far,
Some came by motorcycle,
And some by motorcar,
And entering the meeting-hall,
Each doggie signed the book,
And each unshipped his arsehole,
And hung it on a hook.
One dog was not invited;
It sorely raised his ire;
He ran into the meeting,
And loudly shouted "FIRE!"
The place was in confusion;
Without a second look,
Each doggie took an arsehole,
From off the nearest hook.
And that's the reason why, Sir,
Whene'er two doggies meet,
And that's the reason why, Sir,
In park, or field, or street,
And that's the reason why, Sir,
On land, or sea, or foam:
They'll sniff each other's arsehole,
To find if it's their own.
(Same mathematical problem, to the tune of "The Church's One Foundation", from the days of coarse rugby.)
I showed !n = (n - 1) * [!(n - 1) + !(n - 2)] with !0 = 1 and !1 = 0. However, !n = n!/e is a lot nicer than this recursive formula.
Also, I think there are (n choose k) * !(n - k) permutations with exactly k fixed points.
But I have read that total no. of rearrangement is something else. Like we have 5 cards numbering 1 to 5 and 5 envelope number 1to 5 then the the total number of way such that no card goes to their respective envelope is 5!(1/0!-1/1!+1/2!-1/3!+1/4!-1/5!)
I tried to tackle this question, what is the probability of winning if the win condition is at least two cards are in the correct position.
We see in the video that for at least 1 card in the correct position, the probability is 1-(1/e).
The number of ways to arrange n things so that exactly 1 item is in its correct position would be the same as the number of ways to fix a single point which is n, multiplied by the number of ways to make a derangement of the other n-1 points which is !(n-1). n * !(n-1) = n * (n-1)!/e or n!/e.
So the probability of two or more fixed points would be (1 - (P 0 fixed points) - (P 1 fixed point)) = 1 - ((n!/e)/n!) - ((n!/e)/n!) = 1-(2/e).
If this is not correct, can someone point out where I went wrong.