# hint on a solved old exam question on probabilistic methods calcualation

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}).

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?

**

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$$.

• I am using the common English meaning, this is not a technical term. $C_1$ is distributed on the range $[-0.5, 0.5]$. This is narrower than the range $[-1,1]$ on which $C_2$ is distributed. This is narrower than the range $[-2,2]$ on which $C_3$ is distributed. This is narrower than $[-4,4]$, and so on. Jan 6 at 15:58
• It looks right, and it looks the same as what I'm doing. They've just split it up more. They're saying "the probability of error is $0$ when $\mathbf X \sim C_1$, $\frac12$ when $\mathbf X \sim C_2$, $\frac12$ when $\mathbf X \sim C_3$, and so on, so overall it's $\frac1k \cdot 0 + \frac1k \cdot \frac12 + \frac1k \cdot \frac12 + \dots$. I've combined the last $k-1$ cases into one, since they're all the same. Jan 6 at 16:14
• @DaviedZuhraph That drawing is already in the question - it didn't seem to help. (The shaded area represents the error.) Jan 6 at 16:22