Conditional probability (Bayes theorem)

Question

One of the 256 subsets of {1,2,3,4,5,6,7,8} is chosen uniformly at random. Let X be the number of elements of this subset. Let Y be 0 if the subset is empty and be the least element of the subset otherwise. What is Pr(X = 2| Y < 4)?

I found that:

Pr(X=0) = 1/256

Pr(X=1) = 1/32

Pr(X=2) = 7/64

Pr(X=3) = 7/32

Pr(X=4) = 35/128

Pr(X=5) = 7/32

Pr(X=6) = 7/64

Pr(X=7) = 1/32

Pr(X=8) = 1/256

How do find the probability of Y? Does Pr(X = 2| Y < 4)mean that I have to find the probability of the number of elements of this subset being 2, given that the least element of the subset is less than 4? If so, can I have any tips on how to solve this?

Answer 1

1> Use Bayes' Rule and the Law of Total Probability.

2> $Y$ will be less than 4, for a given subset size, if not all of the elements of the subset are selected from the five elements that are more than 3.

Answer 2

We want to find $\mathrm{P}(X = 2| Y < 4)$. By the definition of conditional probability, this is equal to $$\frac{\mathrm{P}(X = 2 \land Y < 4)}{\mathrm{P}(Y < 4)}$$

Equivalently, using the language of the problem statmement, this is equal to $$\frac{\text{# subsets of {1,2,3,...,8} of size 2 with least element less than 4}}{\text{# of subsets of {1,2,3,...,8} with least element less than 4}}$$

We will determine the size of both subsets and divide one by the other to solve the problem.

First, the denominator. The number of subsets of $\{1,2,3,...,8\}$ with least element $4$ or greater is the set of nonempty subsets of $\{4,5,6,7,8\}$. There are $2^5$ such subsets, including the empty set, so $2^5 - 1$ of them are nonempty. There are $2^8$ subsets of $\{1,2,3,...,8\}$ in total, so there are $2^8 - (2^5 - 1) = 225$ subsets of $\{1,2,3,...,8\}$ with least element less than 4.

Now for the numerator. We want the number of subsets of $\{1,2,3,...8\}$ of size 2 and least element less than 4. We will count them by cases. Suppose the least element is 1. Then there are 7 possible 2-element subsets: $\{1,2\}, \{1,3\}, ..., \{1,8\}$. Similarly, if the least element is 2, there are 6, and if the least element is 3, then there are 5: $\{3,4\}, \{3,5\}, \{3,6\}, \{3,7\}, \{3,8\}$. So, in total, there are $7 + 6 + 5 = 18$ subsets of $\{1,2,3,...,8\}$ of size 2 and least element less than 4.

Therefore the desired probability is 18/225, or 8%.

As a double-check, here's a program that calculates the answer by exhaustively checking all 256 subsets of {1,2,3,4,5,6,7,8}: https://go.dev/play/p/-DrrEzd7esN