N Objects Probability Problems
This paper summaries some \(n\) objects probability problems.
N Objects Pairing
These problems are mainly about pairing \(n\) objects to another \(n\) objects. Here are some examples.
- We have \(n\) keys and \(n\) locks mixed. One key can open only one lock. Now we randomly assign each lock a key. What is the expectation of number of locks to be open?
- In the same scenario as Q1, what is the probability that every key is paired with a wrong lock?
Solutions:
- Each key can open \(\frac{1}{n}\) lock. In total there are \(n\) keys, which means the expectation of total locks open is \(1.\)
- \[P(\text{no match}) = 1 - P(\text{at least one match}) = 1-P(\cup_{i=1}^n A_i).\] Here \(A_i\) means that \(i\) key matches. By the inclusion-exclusion formula we have \[ \begin{aligned} P(\cup_{i=1}^n A_i) &= \sum_{i}P(A_i) - \sum_i\sum_{j>i}P(A_iA_j) + ... +(-1)^{n+1}P(A_1A_2...A_n) \\ &= \sum_{i}\frac{1}{n} - \sum_i\sum_{j>i}\frac{1}{n(n-1)} + ... +(-1)^{n+1}\frac{1}{n!} \\ &= n\frac{1}{n} - \frac{n(n-1)}{2!}\frac{1}{n(n-1)}+... +(-1)^{n+1}\frac{1}{n!} \\ &= 1 - \frac{1}{2!} + \frac{1}{3!}-...+(-1)^{n+1}\frac{1}{n!} \end{aligned} \]Combine the Taylor series of \(e^{-x}\) we know that \(\lim_{n \rightarrow \infty}P(\cup_{i=1}^n A_i) = e^{-1}.\)
N Objects Placement
These problems are placing \(n\) objects on some shape. Here are some examples:
- Given \(n\) points randomly drawn on the circumstance of a circle, what is the probability that all of them within a semicircle?
- If we place \(n\) points on a \(d\) dimensional sphere, what is the probability that all of them within a semi-sphere?
Solutions:
See solution to Q2.
Here we first provide a solution \[P(d,n) = \frac{2\sum_{i=0}^n C_{n-1}^i}{2^n}.\]The way to understand this solution is as follows. We finish it by constructing a sample space. We denote \(n\) points as \(p_1, p_2, ... p_n.\) For each point \(p_i\), we construct another symmetrical point \(\hat{p}_i\) laying on the line determined by \(x_i\) and \(o\) where \(o\) is the center of sphere. Now we have \(n\) pairs \(\{ p_i, \hat{p_i} \}\) with points in the same pair located at different semi-sphere. Now the problem turns to be "If we select one point form each pair, in total \(n\) points, what is the probability of these \(n\) points in the same semi-sphere?" You may find this transformation confusing. One may ask: "What if I totally select \(n\) points different than these \(2n\) points?" The fact is that, whatever \(n\) points you selected, each point will ultimately located in one of the semi-sphere determined by a pair. Then one may ask: "What if a point located at the boundary of two semi-sphere determined by a pair?" Luckily, these cases are zero measure, which means we can ignore them in sample space. Therefore, the problem turns to find how many selections are there to have the \(n\) points selected in the same semi-sphere? As we know that there are \(2^{n}\) selections in total(for each pair, you can select one of them), we count out the number of selections that \(n\) points in the same semi-sphere and divide it by \(2^n\) we should have received the final result.
So how should we count them? Each pair of semi-sphere is determined by a \(d-1\) dimensional plane passing center \(o.\) In total, the \(n\) pairs will correspond to \(n\) planes passing through the center \(o.\) Now we denote \(z_n\) as the number of regions separated by these \(n\) planes. By induction we have \[ z_n = 2\sum_{i=0}^d C_{N-1}^i. \]Now what is the connection between this number of regions and the number of selections such that all \(n\) points in the same semi-sphere? They are equivalent! Because if \(n\) points are in the same semi-sphere, their corresponding semi-sphere are overlapped and determined uniquely by a region. If you select one of the region from \(z_n\) regions, it is uniquely overlapped by \(n\) semi-spheres, which is a selection. Therefore, we have the final result as\[p = \frac{z_n}{2^n} = \frac{2\sum_{i=0}^n C_{n-1}^i}{2^n}.\]
cite:
A practical Guide to quantitative finance interviews