# Probability of MSB=1 for a n-bit discrete random variable while we have a noisy estimate for it

Problem

Let $X$ be a $n$-bit random variable and $s$ be the known estimated value for $X$. Our estimation has an error with normal distribution. In other words, $X|s \sim \mathcal{N}(s,\sigma_z^2)$.

We want to calculate $p\left(B_1(X)=1|s\right)$ numerically where $B_1(X)=1$ means the first bit of $X$ equals to $1$.

A Solution

In the page 4 of this paper the authors have calculated this probability as follows:

$$p\left(B_1(X)=1|s\right) = \int_{\{x|B_1(x)=1\}} p(x|s) dx \\ = \frac{1}{2} \sum_{i=-\infty}^{+\infty} \left[ erfc\left( {\frac{(i-1/2)d_{min}-s}{\sqrt{2}\sigma_z}} \right) - erfc\left({\frac{id_{min}-s}{\sqrt{2}\sigma_z} }\right)\right]$$

Questions

1. What have they done? I can't understand why there is a $\Sigma$ over $erfc$ functions. Apparently CDF of a gaussian distribution is an error function. Maybe that's because $X$ is from a discrete space. In addition, how they have included the $B_1(X)=1$ condition in their answer?
2. Why they have calculated the integral analytically? As $X \in \{0,1\}^n$ (let say $n=8$) and we just want the numeric value of $p\left(B_1(X)=1|s\right)$, we can enumerate over all $x$'s with $B_1(x)=1$ (e.g. 128 possible $x$ for $n=8$), put them in $p(x|s)$ and sum up the probabilities to get $p\left(B_1(X)=1|s\right)$. Is there anything wrong with this approach?

More details:

While my problem is related to channel coding and LDPC codes, I try to explain it without going into much detail:

I am trying to use a LDPC encoder and decoder to transfer $X$. LDPC let me to reduce the bitrate by providing the decoder an estimate of incoming $X$. Let say I have found a way to calcuate $s$ as an estimation of incoming $X$ (we can imagine we observe $X$ from a virtual noisy channel). The problem is the LDPC decoder cannot benefit from this estimation directly, but I have to feed it with the probability of each bit of $X$ being 0 or 1 given $s$. In other words, the $s$ is not enough by itself to guess incoming $X$ and we should also consider the dependence between $X$ and $s$.

In practice, it is supposed that our estimation has a gaussian noise. In other words, we observe $X$ from a virtual channel with gaussian noise. Therefore, we can say that $X|s \sim \mathcal{N}(s,\sigma)$ which means: knowing $s$, $X$ is distributed around $s$ with variance $\sigma^2$.

Now, all I have to do is to calculate the probability of each bit of $X$ being 1 or 0 given $s$ (instead of feeding the decoder directly with $s$ bits). Therefore, for MSB I should calculate $p(B_1(X)=1|s)$, for the next MSB I should calculate $p(B_2(X)=1,B_1(X)|s)$ in similar way, etc.

One obscure point is the $d_{min}$ parameter. As I know, $d_{min}$ is the minimum hamming distance between two coded symbols (i.e. minimum hamming distance of LDPC encoder output for all possible $X$'s). I think what Dilip Sarwate said about $d_{min}$ is correct but I am not still sure.

In conclusion, I know this problem is a little complicated and needs a good knowledge on both probability theory and channel coding to be fully understood. Anyway, I just want to know why author of mentioned paper have calculated the probability analytically? From probability point of view, can I just compute the summation over all possible $X$'s that meet $B_1(X)=1$ condition (as I asked above in Question #2).

• Hi Isaac. Is there a little more precise way of stating the model you are considering? Perhaps I am misunderstanding but to say you have an "$n$-bit random variable $X$" and then say that $X|s \sim \mathcal N(s,\sigma_z^2)$ seems a bit at odds with one another. Also, I assume that $B_1(X)$ is the most significant (left-most) bit in the representation of $X$, correct? – cardinal Mar 8 '12 at 13:48
• You have given a reference to a paper on ieeeexplore which generally requires a subscription to view. Could you give more details in your question instead? – Dilip Sarwate Mar 8 '12 at 14:03
• The sum seems to be the probability that some Gaussian random variable with mean $s$ is in the union of intervals $$\left(i\cdot d_{\min} - \frac{1}{2}d_{\min}, i\cdot d_{\min} \right), ~~ -\infty < i < \infty$$ but what minimum distance $d_\min$ is and how it relates to the most significant bit being $1$ is not clear. Obviously the MSB flips from $1$ to $0$ at integer multiples of $d_\min$ and from $0$ to $1$ at half-multiples of $d_\min$, but why? – Dilip Sarwate Mar 8 '12 at 14:45
• @cardinal: I've added some details to the question to make the problem more clear. – Isaac Mar 8 '12 at 16:05
• @DilipSarwate: Sorry about the restricted paper. I am not sure but is it okay if I upload it somewhere and give a link to it? – Isaac Mar 8 '12 at 16:07