independently and uniformly selected numbers

Question

This question came in my exam. Two numbers are chosen independently and at random from set $\{1,2 \ldots 13\}$. Find the probability that the 4-bit unsigned binary representatives have the same most significant bit.

My doubt is that independently here means that one number is chosen, then it is replaced and then next number is chosen, is my inference correct?

Answer 1

If it says that $X$ and $Y$ are chosen "independently" over the set $\{1, ..., 13\}$ then it means $X$ and $Y$ are independent random variables: $$ P[X=i,Y=j]=P[X=i]P[Y=j] \quad \forall i, j \in \{1, ..., 13\} \quad (Eq. 1)$$

If $X, Y$ are both uniform over that set then $$ P[X=i]=P[Y=i]=1/13 \quad \forall i \in \{1, ..., 13\} \quad (Eq. 2)$$ So it is possible to have $X=Y$. The equations (1)-(2) are consistent with the numbers $X,Y$ being chosen in a sampling with replacement experiment where all $13^2$ combinations are equally likely.

---

It would be impossible to get equations (1)-(2) in a sampling without replacement experiment. In particular, if we first pick $X$, and we next pick $Y$ from a set that depends on $X$ to ensure $Y\neq X$, then it means $Y$ is dependent on $X$. Indeed $$P[Y=1]=1/13, P[Y=1|X=1]=0$$

The sampling without replacement scenario can be described without the concept of independence: We first pick $X$ uniform over $\{1, ..., 13\}$. Then for each $i \in \{1, ..., 13\}$, given that $X=i$, we choose $Y$ with a conditional distribution that is uniform over the set $\{1, ..., 13\} - \{i\}$. (Or, more simply, choose two distinct numbers over the set $\{1, ..., 13\}$, with all possibilities equally likely). I agree with JMoravitz that it is also a good scenario to solve for, but that situation does not seem (to me) to have "independence" anywhere (as Saulspatz also notes). In particular, for that situation, I cannot find two events that are independent of each other.

Answer 2

Let's see the binary representation of numbers from 1 to 13.

1 = 0001
2 = 0010
3 = 0011
4 = 0100
5 = 0101
6 = 0110
7 = 0111
8 = 1000
9 = 1001
10 = 1010
11 = 1011
12 = 1100
13 = 1101

There are two sets of numbers that have same significant bit. First set contains numbers from 1 to 7 and has 0 as the most significant bit, Second set contains numbers from 8 to 13 and has 1 as the most significant bit.

Two numbers are picked independently and at random, So one can be picked from the first set or other can be picked from the second set or both of them can be picked from one of the two sets.

So, The solution is, (7/13 * 7/13) + (6/13 * 6/13)