hint on a solved old exam question on probabilistic methods calcualation

Question

In my note I have some previous exam solved question as follows in Probabilistic methods section:

Example: We have $k$ classes $C_1, C_2,...,C_k$ where each $C_i$ has uniform distribution over $-(2^{i-2})<x<2^{i-2}$.

by using maximum likelihood ratio test, then $ \lim_{k\rightarrow \infty} $P$(error)= \frac{1}{2}$

$ \frac{1}{2}$ is Calculated by following idea:

**

My challenge is I couldn't understand the logic of this answer. is there any intuitive idea to better understand here?

**

Answer 1

If we observe a random variable $\mathbf X$ which could be sampled from any of the $k$ distributions $C_1, C_2, \dots, C_k$ with equal probability, then the maximum-likelihood guess for which it was always goes with the narrowest option that could explain the value of $\mathbf X$.

For example, if we observe $\mathbf X = 5$, then this could have come from $C_5$ (distributed on $[-8,8]$), $C_6$ (distributed on $[-16,16]$) or any of $C_7, \dots, C_k$, but it could not have come from $C_1, C_2, C_3, C_4$. The maximum-likelihood guess is $C_5$.

If in fact $\mathbf X$ came from $C_1$ (which happens with probability $\frac1k$) then $C_1$ will always be the narrowest option explaining $\mathbf X$, so the probability of error is $0$.

Otherwise, suppose $\mathbf X$ came from $C_i$ with $i>1$, which is distributed uniformly on $[-2^{i-2}, 2^{i-2}]$.

• For half that range, $[-2^{i-2}, -2^{i-3}) \cup (2^{i-3}, 2^{i-2}]$, the narrowest option explaining $\mathbf X$ is $C_i$, so the maximum-likelihood guess is correct.
• For the other half of the range, $[-2^{i-3}, 2^{i-3}]$, $C_{i-1}$ could also explain $\mathbf X$, and will be preferentially guessed over $C_i$. (Closer to $0$, $C_1, \dots, C_{i-2}$ could become even better guess, but that doesn't change anything.) The maximum-likelihood guess is wrong.

Therefore in the $i>1$ case the probability of error is $\frac12$.

The overall probability of error is $\frac1k \cdot 0 + (1 - \frac1k) \cdot \frac12 = \frac{k-1}{2k}$. As $k \to \infty$, this approaches $\frac12$.