Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Suppose I have a binary vector $v$ that is copied twice by two separate machines $M$ and $N$, resulting in two new vectors $x$ and $y$.

Both machines are faulty in the sense that they both might fail to copy each character correctly. More formally, $M$ has an associated vector $e_M$ of length $|v|$, where $(e_M)_i$ is the probability that bit $i$ in $M$'s input will be inverted in $M$'s output (and $N$ has a similarly defined, but not necessarily identical, associated vector $e_N$).

Questions:

  1. if the only information I receive is $x$, $y$, and two real numbers $p$ and $q$ describing the probabilities that a mistake has been made in producing $x$ and $y$ (i.e. $p$ is the probability that $M$ made an error when producing $x$ from $v$, and $q$ is the probability that $N$ made an error when producing $y$ from $v$), is there a way to reconstruct, or approximate $e_M$ and $e_N$?

  2. does the answer to question 1 depend on $|v|$ (which is of course assumed to be at least $2$ for this question to make sense), and if so, how?

(all apologies if the question is trivial, and if I'm not using the right terms)

share|improve this question

1 Answer 1

up vote 0 down vote accepted

$1-p$ gives you the product of $(1-(e_M)_i)$ over $i$ and similarly for $1-q$. If you only have one set of $x$ and $y$ and don't know anything about the $(e_M)_i$ and $(e_N)_i$ there is no hope. Even if you get a lot of $x,y$ pairs but don't get any information of what is the truth all you can tell is the combination of error rates per bit. The chance of disagreement at a given bit is $e_M+e_N-e_M*e_N$ but you can't sort out any more than that.

share|improve this answer
    
OK, that's the kind of bad news I was expecting... thanks. –  Anthony Labarre Oct 14 '10 at 11:12

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.