<img src="https://sb.scorecardresearch.com/p?c1=2&amp;c2=22489583&amp;cv=3.6.0&amp;cj=1">

Key (part 2): Throwback to my lonely days

Author's Avatar
Noir 07/07/20
10
5

Hello again. This will be the second part of the key to the challenge.

Key (part 2): Throwback to my lonely days-[C]Hello again. This will be the second part of the key to the challenge.

[IMG=HAJ
Almost there for my sorry christmas lol

We've proved before:

Key (part 2): Throwback to my lonely days-[C]Hello again. This will be the second part of the key to the challenge.

[IMG=HAJ

Where d_k = D(k) is the amount of derangements of {1, ..., n}.

It naturally comes the strong induction relationship, by isolating the last term of the sum:

Key (part 2): Throwback to my lonely days-[C]Hello again. This will be the second part of the key to the challenge.

[IMG=HAJ

--------------------------------------------

The question is... Do we have a simpler form of D(n)?

Hmmm...

Let's try to get other forms of D(n).

The idea to build a derangement of {1, ...n} is to pick a certain amount of fixed points, and do a derangement of the rest of the points. In particular, to build a derangement σ of Sn...

Pick i∈ {2, ..., n} (n-1 possible choices)

Case 1: Either σ(i) = 1

Then you will surely have σ(1) =/= 1.

Do a derangement of the rest (without 1): there are D(n-2) possible choices.

Case 2: Either σ(i) =/= 1

Do a derangement with the rest (with 1): D(n-1) possible choices.

So, since there are n-1 possible choices for i...

D(n) = (n-1)(D(n-1) + D(n-2))

--------------------------------------------------

Okay.

What do we do with this relationship as well?

Well... Let's see. The forms are quite look-alike if you attempt to put D(n) and D(n-1) together,  because:

D(n) - nD(n-1) = -D(n-1) + (n-1)D(n-2)

So, with U(n) = D(n) - nD(n-1):

U(n) = -U(n-1)

So: U(n) = U(2)*(-1)^(n-2) = U(2)*(-1)^n

With U(2) = D(2) - 2D(1) = 1 because D(2) = 1 and D(1) = 0

D(n) = nD(n-1) + (-1)^n

Key (part 2): Throwback to my lonely days-[C]Hello again. This will be the second part of the key to the challenge.

[IMG=HAJ

--------------------------------------------------

So now, we can finally start talking about probabilities.

By taking Sn with the uniform distribution over every permumtation, the probability of a derangement on Sn is given by:

Key (part 2): Throwback to my lonely days-[C]Hello again. This will be the second part of the key to the challenge.

[IMG=HAJ

Because n! = Card Sn.

The second relationship, divided by n!, gives:

Key (part 2): Throwback to my lonely days-[C]Hello again. This will be the second part of the key to the challenge.

[IMG=HAJ

Keep in mind this is true for all n, so it will be true if you plug k < n instead of n.

Now by doing a bit of telescoping...

Key (part 2): Throwback to my lonely days-[C]Hello again. This will be the second part of the key to the challenge.

[IMG=HAJ

Now, note that the term in k = 0 is 1/0! = 1 and the term in k = 1 is -1/1! = -1, so they cancel out if you add them together.

-------------------------------------------------------------

And at last!!!

Key (part 2): Throwback to my lonely days-[C]Hello again. This will be the second part of the key to the challenge.

[IMG=HAJ

To recap, pn is the probability of picking a derangement in Sn. In other words, it's the probability that no student gets their own gift.

The probability of someone getting their own gift is 1 - pn.

1 - pn ~ 0.63

So... actually, isn't that pretty big??

Feelsbad, never do those Secret Santa events if you don't plan to compute the redistribution of gifts... That's a pretty sad christmas for everyone.

Key (part 2): Throwback to my lonely days-[C]Hello again. This will be the second part of the key to the challenge.

[IMG=HAJ

And that's all for my sad memories! Thank you for spending time and effort in trying to figure answers!

Props to Phi Guy for figuring the right answer...

===================================================

Post Scriptum

On a side note, pn converges to exp(-1) as n approaches infinity and very fast on top of that (the quality of convergence is stronger than just geometric here), so with n = 41, a fair approach of p(41) is 1/e.

Key (part 2): Throwback to my lonely days-[C]Hello again. This will be the second part of the key to the challenge.

[IMG=HAJ
Power series that defines exp(x). It converges uniformally on R. Just apply it at x = -1.
Likes (10)
Comments (5)

Likes (10)

Like 10

Comments (5)

Hello Grey.

The binomial law is invalid here because the n-1 students and I aren't taking our presents independantly. The amount of presents decreases when a student takes one, so it's not the same experiment repeated 41 times.

Your result coincidentally gets close to the wanted result numerically because the amount of students n is large enough. It wouldn't work for small values such as 3 or 4 students.

Let me show you why our probabilities are asymptotically the same.

Read more
1 Reply 07/11/20

Our probabilities converge to the same value as n approaches infinity...

Read more
0 Reply 07/11/20

Ohh ok that makes sense. I’ll have another think if I have any time after my ridiculous exam revision. Also ty for calling this an awkward moment

Read more
1 Reply 07/13/20

Last row for cumulative probability to save everyone’s time

Read more
0 Reply 07/11/20

Sorry for being late to the party. I’m not a math genius so I didn’t really get the rigorously pure proof you gave, but a fairly simplistic idea I had was that since there were 41 gifts and 41 peeps, the probability of anyone getting their own gift is 1/41, so I thought this would follow a binomial distribution with X~B(41,1/41). I used a binomial calculator and boom P(X>0)~0.63 too (it rounds to 0.64 but hey it’s close enough right). Is there anything wrong with using a binomial model and is it just a coincidence

Read more
1 Reply 07/11/20
    Community background image
    community logo

    Into Maths Amino? the community.

    Get Amino

    Into Maths Amino? the community.

    Get App