2
$\begingroup$

I observe a binary string that contains both 0's and 1's like this one 100111101. However the true process that created these strings are either all 1's or all 0's. Due to technical errors and measurement errors I observe a string that contains both 0's and 1's. For example if there are no technical or measurement errors the above example string should have been 111111111 or 000000000. I am interested in inferring whether my observed string is truly all 1's or all 0's. In addition to classifying them into two groups I am also interested in a confidence measure that tells me how confident that it comes from all 1's scenario vs all 0's scenario.

Is there any statistical procedure that I can use to answer this type of question ?

$\endgroup$
4
  • 1
    $\begingroup$ Are the error independent of one another? I mean, can you assume that the occurrence of a error in postion $i$ is not influenced by the presence of error in any other position $j$? $\endgroup$ – Mur1lo Jun 27 '16 at 1:24
  • $\begingroup$ Yes, I assume errors are independent. $\endgroup$ – DKangeyan Jun 27 '16 at 1:40
  • $\begingroup$ Do you know anything about the probability of a error occurring? $\endgroup$ – Mur1lo Jun 27 '16 at 1:47
  • $\begingroup$ No, I don't think so. $\endgroup$ – DKangeyan Jun 27 '16 at 2:10
3
$\begingroup$

I believe you can use the maximum likelihood method to perform the classification.

First you need to have the true value, or a good approximation, of the probability of a error occurring. Lets denote by $p$ this probability.

Lets assume your string of zeros and ones is $\delta = x_1x_2...x_n$. We also adopt the notation: $\theta = 0$ if this sequence would be a sequence of zeros if there were no errors. In the same fashion $\theta = 1$ if this sequence would be a sequence of one if there were no errors.

Now you can check that the log-likelihood of $\theta = 0$ given this string (which can be interpreted as the probability of getting the string when we suppose that it is really a sequence of zeros) is:

$$l(\theta = 0\,|\,\delta) = \log\left[\prod_{i = 1}^np^{x_i}(1-p)^{1-x_i}\right]=(\log p)\sum x_i+\log(1-p)\left(n-\sum x_i\right)$$

When you consider the case $\theta=1$ your log-likelihood is: $$l(\theta = 1\,|\,\delta) = \log\left[\prod_{i = 1}^np^{1-x_i}(1-p)^{x_i}\right]=(\log p)\left(n-\sum x_i\right)+\log(1-p)\sum x_i$$

Now all you have to do is see which log-likelihood is bigger. The bigger one tells you what value of $\theta$ you should choose.

$\endgroup$
5
  • $\begingroup$ This looks like a nice and simple approach. Can this likelihoods or may be likelihood ratio be used as a measure of confidence to say which category a certain string belongs to ? $\endgroup$ – DKangeyan Jun 27 '16 at 2:52
  • $\begingroup$ If I understood you right you want something like the probability of wrong classification. If thats what you want you surely can get it from the likelihood function, but at the price of some time doing calculations. $\endgroup$ – Mur1lo Jun 27 '16 at 3:01
  • 2
    $\begingroup$ +1. Your method could also be generalized to the case where 0s and 1s have different error probabilities. $\endgroup$ – user20160 Jun 27 '16 at 3:27
  • 1
    $\begingroup$ @DKangeyan should take a look at the previous comment. Depending on the particularities of your problem you might want to consider the possibility of using two probabilities of error, one for each value of $\theta$. $\endgroup$ – Mur1lo Jun 27 '16 at 3:35
  • $\begingroup$ That make sense. Essentially if the probability of seeing a zero in a true string with all ones and the probability of seeing a one in a true string with all zeroes then the p in the first likelihood will be different than the p in the second one. $\endgroup$ – DKangeyan Jun 27 '16 at 14:36

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.