2
$\begingroup$

Imagine you are receiving a message over and over via a lossy data path. The path causes bit errors but does not affect the length of the message (or shift any bits). You don't know the actual message but you will get many copies of it so you can reconstruct it (e.g. with a median filter). You want to estimate the error rate of the channel by observing the sequence of messages.

I solved this problem a while ago by "learning" the expected message and counting errors as $\text{population}(\text{learned} \oplus \text{current})$. Today it struck me that the learning component may be unnecessary: For low error rates you could approximate the rate as $\frac{\text{population}(\text{previous} \oplus \text{current})}{2}$. That is effectively measuring the previous frame against the current and vice versa simultaneously. At low error rates half of the errors can be expected to be due to $\text{previous}$ and half due to $\text{current}$.

My assumption about the independence of the errors in $\text{previous}$ and $\text{current}$ breaks down as the error rate increases and repeated errors become more likely. How does the actual error rate impact the rate given by my estimation?

$\endgroup$
11
  • $\begingroup$ Can you explain the definition of your notation please? It sounds like you're discussing something a little related to a well-known result but your notation is unfamiliar to me (and I expect to most people here), so I can't be sure what you're actually saying. $\endgroup$ – Glen_b Aug 17 '13 at 21:10
  • $\begingroup$ Messages are sequences of bits. The XOR operation $\oplus$ is 1 where bits differ and 0 where they are the same. The population of a set of bits is the count of 1 bits. $\endgroup$ – Ben Jackson Aug 17 '13 at 22:05
  • $\begingroup$ Thanks; useful. Actually, I knew what a XOR was, I just didn't know that's what the $\oplus$ symbol was in this case (it has a variety of possible meanings). What does the operator "$\text{population}(.)$ do? $\endgroup$ – Glen_b Aug 17 '13 at 22:29
  • $\begingroup$ The population of a set of bits is the count of 1 bits. Also "popcnt" and the bitwise Hamming weight. Lots of applications in Chess AI programming have explored population count algorithms. $\endgroup$ – Ben Jackson Aug 17 '13 at 22:38
  • $\begingroup$ Oh, okay. I now understand that you had already answered that, but I didn't understand the explanation before because the word population means something utterly different to us here, and I misunderstood what you were even saying the first time (that is, this: 'The population of a set of bits is the count of 1 bits' didn't mean to me what you hoped it did. I got it now.) $\endgroup$ – Glen_b Aug 17 '13 at 22:42
2
$\begingroup$

I believe I now follow enough to understand that your alternative estimate is wrong, because if the two messages are independent (in the probability sense), then the expected number of observed differences in two messages won't be twice the expected difference between the learned message and the current one.

It won't even be twice the expected difference between the actual message and the current one.

That's because both the current and previous message can flip the same bit. You have to subtract that off the sum.

If we assume that the probability that a bit gets flipped is always $p$ (here $p$ is a population - in the statistical sense - parameter) and all flips are mutually independent, then the expected probability two corresponding bits differ between two messages is

\begin{eqnarray} P(\text{two messages disagree on a given bit}) &=& 1-P(\text{two messages agree there}) \\ &=& 1- P(\text{both unflipped or both flipped}) \\ &=& 1-[(1-p)^2 + p^2] \\ &=& 1-[1 - 2p +2p^2]\\ &=& 2p-2p^2 \end{eqnarray}

So you have to solve a quadratic: $2p^2 - 2p +q = 0$

which implies that $p = \frac{1}{2} \pm \sqrt{\frac{1}{4}-\frac{q}{2}}$.

Your question implies the error rate is low. If you know it's below 0.5, you take the smaller answer:

$p = \frac{1}{2} - \sqrt{\frac{1}{4}-\frac{q}{2}}$

bit error / message difference relationship

That in turn suggests the MLE

$\hat p = \frac{1}{2} - \sqrt{\frac{1}{4}-\frac{\hat q}{2}}$

Let me see if I can translate that into your terms:

$\frac{1}{2}-\sqrt{\frac{1}{4}-\frac{\text{population}(\text{previous} \oplus \text{current})}{2\text{size}(\text{current})}}$

is the estimate of the per bit error rate. You'd then multiply the whole expression by $\text{size}(\text{current})$ to estimate $\text{population}(\text{actual} \oplus \text{current})$.

Incidentally, it should be possible to put standard errors on/give confidence intervals for the various estimates of quantities if you need them. (As $q$ gets anywhere twoard 0.5, the uncertainty in $p$ grows rapidly.)

$\endgroup$
3
  • $\begingroup$ Your first three paragraphs accurately reflect the flaw I perceive and tried to describe in my question. The remainder of your answer takes the form I'd expect (higher $p$ makes the estimate worse) but I'll have to study it to understand what you're saying. $\endgroup$ – Ben Jackson Aug 17 '13 at 23:06
  • $\begingroup$ I believe your translation is exactly what I was looking for! Better, even, because I assumed that higher $p$ would describe an increasingly poor error bound for the estimate. I didn't expect it could "feed back" and be used to correct the estimate. $\endgroup$ – Ben Jackson Aug 17 '13 at 23:13
  • $\begingroup$ Thanks for the attempted edit. It didn't work because I was already editing the answer to include the plot (which took longer than it ought for me to get right), but I had noticed the problem already. $\endgroup$ – Glen_b Aug 17 '13 at 23:27

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.