Probability That 1 Was Selected Given Increasing Order
You draw $r$ integers one at a time, without replacement, uniformly at random from $\{1, 2, \dots, n\}$. Someone tells you that the numbers came out in increasing order. Given that information, what is the probability that $1$ was among the numbers selected?
Derive a general formula in terms of $r$ and $n$, then compute the answer for $r = 5$ and $n = 100$.
Hints
- Conditioning on the draws coming out in increasing order is equivalent to choosing a uniformly random $r$-element subset -- there is exactly one increasing arrangement per subset.
- Use counting directly: the denominator is $\binom{n}{r}$ (all size-$r$ subsets), and the numerator counts those that include $1$.
- Fix $1$ in the subset and choose the remaining $r-1$ elements from the other $n-1$ integers: the numerator is $\binom{n-1}{r-1}$, giving $P = r/n$.
Worked Solution
How to Think About It: The conditioning event -- "the draws came out in increasing order" -- sounds like it changes things dramatically, but it is actually just a clean way to select a random $r$-element subset. There is exactly one increasing arrangement for any subset, so conditioning on increasing order is equivalent to asking: pick a uniformly random $r$-element subset of $\{1, \dots, n\}$; what is the chance $1$ is in it? That collapses the whole problem into a single counting ratio.
Quick Estimate: For $r = 5$, $n = 100$: you are picking 5 elements out of 100 at random. The chance any specific element (like $1$) gets picked is roughly $5/100 = 0.05 = 1/20$. So the answer should be $1/20$ -- and the formal derivation will confirm this exactly.
Approach: Use counting rather than manipulating probabilities directly. Since sampling is uniform, $P(A) = |A| / |\Omega|$ for any event $A$, so we just need to count favorable vs. total outcomes.
Formal Solution:
Let $I$ be the event that the $r$ draws come out in increasing order, and $O$ be the event that $1$ is among the selected numbers. We want $P(O \mid I)$.
By definition:
$$P(O \mid I) = \frac{P(O \cap I)}{P(I)}$$
Since every subset of size $r$ has exactly one increasing arrangement, the total number of increasing sequences is $\binom{n}{r}$ -- one per subset. So:
$$P(I) = \frac{\binom{n}{r}}{n^{\underline{r}}}$$
where $n^{\underline{r}} = n(n-1)\cdots(n-r+1)$ is the number of ordered draws. But these factors cancel cleanly -- we can work directly in the space of ordered draws and count.
Equivalently, think of it this way: in the space where we condition on $I$, every $r$-element subset of $\{1, \dots, n\}$ is equally likely. The denominator is $\binom{n}{r}$ (all size-$r$ subsets). For the numerator, count subsets that include $1$: fix $1$, then choose the remaining $r-1$ elements from $\{2, 3, \dots, n\}$, giving $\binom{n-1}{r-1}$ subsets.
Therefore:
$$P(O \mid I) = \frac{\binom{n-1}{r-1}}{\binom{n}{r}} = \frac{\dfrac{(n-1)!}{(r-1)!\,(n-r)!}}{\dfrac{n!}{r!\,(n-r)!}} = \frac{r}{n}$$
Answer: $P(1 \text{ selected} \mid \text{increasing order}) = \dfrac{r}{n}$.
For $r = 5$, $n = 100$: $\dfrac{5}{100} = \dfrac{1}{20}$.
Intuition
The elegant surprise here is that conditioning on "increasing order" strips away all the ordering complexity and leaves you with a pure subset-selection problem. Once you recognize that each $r$-element subset has exactly one increasing arrangement, the conditional distribution over subsets is uniform -- and the probability that any fixed element is in a uniformly random size-$r$ subset is simply $r/n$. The conditioning did not actually give you new information about which specific elements were chosen; it just collapsed ordered draws into unordered ones.
This pattern -- where a symmetry argument reduces a complex conditional probability to a simple counting ratio -- shows up constantly in quant interviews. The instinct to reach for Bayes' theorem is right, but the real skill is recognizing when the counting is trivial once you frame the sample space correctly. In this case, the answer $r/n$ also has a direct interpretation: it is exactly the marginal probability that $1$ appears in a size-$r$ sample without replacement, confirming that the conditioning event carries no information about whether $1$ is present.