2
$\begingroup$

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?

**

$\endgroup$
2
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ Jan 6 at 15:58
  • 1
    $\begingroup$ 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. $\endgroup$ Jan 6 at 16:14
  • $\begingroup$ @DaviedZuhraph That drawing is already in the question - it didn't seem to help. (The shaded area represents the error.) $\endgroup$ Jan 6 at 16:22

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.