# Let $X_1,\dots,X_{20}$ be a sample without replacement from $\{1,\dots,100\}$, find $P(X_3>X_{10})$

Problem: Let $$X_1,\dots,X_{20}$$ be a sample without replacement from $$\{1,\dots,100\}$$. Find the probability that $$X_3>X_{10}.$$

Thoughts: Since we are sampling without replacement it follows that $$\sum_{i,j}P(X_i where $$i,j\in\{1,\dots,20\}$$. Again, since we sample without replacement, we have that the random variables are exchangeable, which implies that $$1=\sum_{i,j}P(X_1 and thus it follows by exchangeability that $$P(X_{10}

Do you agree with my work above? I am not confident in my approach because at no point do I use the assumption that we are sampling from the set $$\{1,\dots,100\}$$, which intuitively seems different from sampling, say, from the set $$\{1,\dots,32\}.$$

• This is not clear. Why isn't it just $\frac 12$? – lulu Apr 7 '20 at 20:39
• Also, the sum you mention is much greater than $1$. After all, given any pair $X_i, X_j$ with $i\neq j$ we must have exactly one of $X_i<X_j$ or $X_j<X_i$ so $P(X_i<X_j)+P(X_j<X_i)=1$ Thus your sum is $\binom {20}{2}=190$ – lulu Apr 7 '20 at 20:44
• @lulu Following your comments, we have that $P(X_3<X_{10})+P(X_{10}<X_3)=\frac{1}{2}$. Then by exchangeability, $P(X_3<X_{10})=P(X_{10}<X_3)$, so that $P(X_{10}<X_3)=\frac{1}{2}$. Do you agree with this line of reasoning? And thanks a lot for your help – Stackman Apr 7 '20 at 20:51
• The sum $P(X_3<X_{10})+P(X_{10}<X_3)=1$, not $\frac 12$. But, yes. By symmetry, both must be $\frac 12$. Note: it is important that you are choosing without replacement. Otherwise you'd need to deal with $P(X_3=X_{10})$. – lulu Apr 7 '20 at 20:56
• As an aside, the whole bit about having chosen twenty numbers and that we are talking about $X_3$ and $X_{10}$ specifically rather than some other pair of chosen numbers is a red herring and entirely irrelevant. It might as well have been choosing only two numbers and asking if the first number was smaller than the second. – JMoravitz Apr 7 '20 at 21:33

Here, a uniformly random sample means that each of the $$100$$ numbers are equally likely to appear in any given selection. It follows from symmetry, then, that $$P(X_i for any pair of indices with $$i\neq j$$.
But, since we are choosing without replacement, we must have $$P(X_i and we can then deduce that $$\boxed {P(X_i
Note: if we were working with replacement then we still have the equality $$P(X_i by symmetry but now we'd have $$P(X_i
Since it is clear that, in that case, we have $$P(X_i=X_j)=\frac 1{100}$$ we would deduce that, with replacement: $$P(X_i
The answer is (obviously) 1/2. An elegant reasoning is as follows. Construct a bijection from the events $$A$$ in which $$X_3>X_{10}$$ to the set $$B$$ where $$X_{10}>X_3$$ by simply replacing between the values of the two. This bijection shows that the two sets of events have equal cardinality, since they form a partition of the entire probability space C, i.e., all possible draws without repetition of 20 numbered balls from a 100 ball basket, one finds that $$|A|=|B|$$, and $$|A|+|B|=|C|$$, and therefore $$\mathbb{P}(X_3 > X_{10}) = \dfrac{|A|}{|C|} = \dfrac{1}{2}.$$