Intereting Posts

Computing $\text{Gal}(\mathbb{Q}^{ab}/\mathbb{Q})$
Gaussian for Grassmann variables
Need help finding closed form of finite product
What is the expected length of the largest run of heads if we make 1,000 flips?
Asymmetric Random Walk / Prove that $T:= \inf\{n: X_n = b\}$ is a $\{\mathscr F_n\}_{n \in \mathbb N}$-stopping time
Why do physicists get away with thinking of the Dirac Delta functional as a function?
Law of Large Numbers, a confusion
Fixed points of contractions in metric spaces
Prove that $\int_0^1\frac{\ln(1-x)\ln^2x}{x-1}dx=\frac{\pi^4}{180}$
Justification for moving a limit outside an indefinite integral
what is the smallest number of rooks that can dominate an n×n×n chessboard?
Is semidirect product unique?
Describe the interior of Cantor set
Is this operator bounded? Hilbert space projection
Syntactically speaking, when can you introduce a universal such that no logical inconsistencies are introduced?

Suppose n people take n hats at random. What is the probability that

at least 1 person has his own hat?

The proposed solution uses inclusion-exclusion principle and gives the answer:

$$\sum^{n}_{r=1} (-1)^{r-1} \frac{1}{r!}$$

- Semantic confusion over the meaning of “order matters/is important”
- If three dice are rolled, what is the probability that all three are the same number?
- What is the average rotation angle needed to change the color of a sphere?
- Conditional Expectation of a Poisson Random Variable
- Binomial random variable with number of trials being a Poisson random variable
- Expected number of couples having same number

But I think there is simpler solution: let’s calculate the complement, i.e. no one gets his own hat.

Total number of ways of distribution hats = number of permutations of hats, i.e. $n!$ Number of ways when no one gets his own hat is calculated as follows: fix a person, he can choose among n-1 hats, then, fix another person, he has n-2 hats at his disposal, and so on. This leads to $(n-1)!$

Therefore, my answer is $1 – \frac{(n-1)!}{n!} = 1 – \frac{1}{n}$ which is wrong. My question is where did I make a mistake?

- PDF of area of convex hull of four random points in square
- Iterated integral question
- Are “most” continuous functions also differentiable?
- How can I do a constructive proof of this:
- Choosing the correct subsequence of events s.t. sum of probabilities of events diverge
- 100 coin flips, expect to see 7 heads in a row
- Mathematical expectation is inside convex hull of support
- $n$ points are picked uniformly and independently on the unit circle. What is the probability the convex hull does not contain the origin?
- Sum of random variable
- A bridge hand void in one suit

… fix a person, he can choose among $n-1$ hats, then, fix another person, he has $n-2$ hats at his disposal

If the first person takes another person’s hat, then another person has $n-1$ different hats at his disposal.

The number you are trying to get is called the number of derangements and is also (most easily, I believe) computed by inclusion-exclusion principle.

The mistake is that the number of possibilities for the second person (and subsequent ones) to pick a hat besides his depends on what’s happened before. For example, if person number 1 picked hat number 2, there will be $n-1$ possibilities. Otherwise, $n-2$. I’m not sure how easy it is to give a proof along these lines that keeps track of these possibilities.

Adding to one other responder’s solution and explaining how to use derrangement in this kind of problem, I have taken n to be equal to 4 to lay down the foundation:

The total number of ways 4 people will receive 4 hats $= 4!$

The total number of ways that none of the person will get his own hat often defined as the derrangement notated by $(!4) = 9$ (Check Wolfram or Wiki).

Thus the probability that none of the 4 people will get their hats back $$= \frac{!4}{4!} = \frac{9}{24}$$

Thus the probability that atleast one person will get his hat back $$ = 1 – \frac{9}{24} = \frac{15}{24}$$

If you evaluate the series in your answer for the problem, you will

$$ = 1 – \frac{1}{2!}+\frac{1}{3!}-\frac{1}{4!} = \frac{15}{24}$$

Thanks

Satish

- Show that $|z_1 + z_2|^2 < (1+C)|z_1|^2 + \left(1 + \frac{1}{C}\right) |z_2|^2$
- Looking for confirmation on probability questions
- In a non-commutative monoid, is the left inverse of an element also the right inverse?
- Given 5 children and 8 adults, how many ways can they be seated so that there are no two children sitting next to each other.
- What does a zero tensor product imply?
- Mean of $k$ highest out of $n$ i.i.d. draws from unit uniform distribution
- Problem on circles, tangents and triangles
- Algebraic Geometry Text Recommendation
- Comparing the growth rates
- Why is the sequential closure not sequentially closed?
- I am confused about the kernel of a matrix and the “kernel”
- How can a piece of A4 paper be folded in exactly three equal parts?
- Find all values of $p$ such that $ax^2+bx+c \equiv 0 (\bmod p)$ have solution
- Are sets and symbols the building blocks of mathematics?
- Special Differential Equation