0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ It is open to interpretation whether or not this selection is done with replacement or without replacement. My initial reaction is that it would be done with replacement and so there is a chance that both numbers selected are the same, but I encourage you to try to answer both interpretations. $\endgroup$ – JMoravitz Feb 21 at 16:28
  • 2
    $\begingroup$ That's how I would interpret it. If a pair of numbers is chosen at random, then there is only one event, so what can "independent" mean? $\endgroup$ – saulspatz Feb 21 at 16:29
  • $\begingroup$ @saulspatz it isn't unheard of for someone to describe the selection of two cards from a deck to be accomplished by first selecting a card uniformly at random and then independently selecting a second card from those remaining uniformly at random. This avoids silly situations like "shuffling" by merely putting the top card onto the bottom in which case the order of the cards remains constant and so knowledge of the first card directly implies what the second card is. $\endgroup$ – JMoravitz Feb 21 at 16:34
  • 1
    $\begingroup$ You can understand that "choosing" a number does not consume it, replacement is implicit. $\endgroup$ – Yves Daoust Feb 21 at 17:03
  • 2
    $\begingroup$ Alternatively: If you do not replace a number after selection, then the selection of two numbers cannot be independent - as the selection of the second number will surely depend on what number is no longer available. $\endgroup$ – Graham Kemp Feb 21 at 22:59
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ don't you think the language of the question is ambiguous as saulspatz said in one of the comment. would you please look at the response given here and verify if it is correct: math.stackexchange.com/questions/3105898/… $\endgroup$ – mohandwivedi Feb 22 at 4:07
  • $\begingroup$ @mohandwivedi : I find the question is unclear because it says "chosen independently and at random from the set" rather than "chosen independently and uniformly over the set." I suppose the question should have also been worded better to emphasize the intended meaning. For example some people think of "independent" the same as "mutually exclusive" when these are very different concepts. If you think "mutually exclusive" you might interpret as "sampling without replacement" but, thinking more, it is hard to identify where the mathematical definition of "independence" might apply in that model. $\endgroup$ – Michael Feb 22 at 15:49
0
$\begingroup$

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)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.