Let $X$ be uniformly distributed over a finite set $\mathcal{X}$. Given a sequence $A_1$, $A_2$, ... of subsets of $\mathcal{X}$ we ask a sequence of questions of the form $X \in A_1$, $X \in A_2$, etc.
Suppose we randomly (i.i.d. and uniformly) draw the sequence of subsets from the power set of $\mathcal{X}$. Fix $x,y \in \mathcal{X}$. Conditional on ${X = x}$:
(i) What is the probability that $x$ and $y$ are indistinguishable after the first $k$ random questions?
(ii) What is the expected number of elements in $\mathcal{X} \setminus \{x\}$ that are indistinguishable from $x$ after the first $k$ questions?
This is indeed - as you may be thinking - a question from an exercise sheet I have been given. I have access to the solutions though, and they are from an Information Theory course that uses entropy and Shannon codes to solve this. This seems to me to be overkill, so I was wondering whether an elementary probability solution could be suggested.
For example, it seems to me that (i) could be solved along the lines of: $$ \begin{align} \mathbb{P}(x,y \text{ indistinguishable after } A_1)&=\mathbb{P}(\{x\in A_1 \cap y\in A_1\}\cup\{x\in A_1^c \cap y\in A_1^c\}) \\ &= \mathbb{P}(x\in A_1)\mathbb{P}(y\in A_1)+\mathbb{P}(x\in A_1^c)\mathbb{P}(y\in A_1^c) \\ &= \frac{1}{|A_1|^2} + \frac{1}{|A_1^c|^2} \end{align} $$
So that overall, by independence, we have:
$$ \mathbb{P}(x,y \text{ indistinguishable after } A_k)=\prod_{i=1}^k{\left(\frac{1}{|A_i|^2} + \frac{1}{|A_i^c|^2}\right)} $$
This feels wrong though, and I feel like given the amount of independence and uniform distribution assumptions we are making we should be able to get to a simpler solution.