1
$\begingroup$

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)

1 Answers 1

0

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

  • 0
    OK, that's the kind of bad news I was expecting... thanks.2010-10-14