Suppose that we have a Bernoulli r.v. $\Theta\in\{0,1\}$ with PMF $$p_\Theta(\theta)=\pi_1^\theta(1-\pi_1)^{1-\theta}$$ i.e. $p_\Theta(1)=\pi_1$ and $p_\Theta(0)=1-\pi_1$

We send the above value $N$ times.

We observe it after corruption by a Bernoulli process $\mathbf{W}=\begin{bmatrix} w[0]&w[1]&...&w[N-1]\end{bmatrix}^T$ with probability of $1$ that changes every time i.e. $$p_{W[n]}(w[n])=p_n^{w[n]}(1-p_n)^{1-w[n]}$$

i.e. $p_{W[n]}(1)=p_n$ and $p_{W[n]}(0)=1-p_n$ The corruption is of the following form:

$$X[n]=(\Theta+W[n])\text{ mod }2$$

Our goal is to infer $\Theta$. So I want to calculate the posterior analytically and then find the MAP estimator for $\Theta$.

Hence, the likelihood is \begin{eqnarray*} p_{\mathbf{X}|\mathbf{\Theta}}(\mathbf{x}|\mathbf{\theta})&=&P(\mathbf{X}=\mathbf{x}|\mathbf{\Theta}=\mathbf{\theta})\\ &=&P(\mathbf{\theta}\oplus\mathbf{W}=\mathbf{x})\\ &=&P(\mathbf{W}=\mathbf{x}\oplus\mathbf{\theta})\\ &=&p_0^{x[0]\oplus\theta}(1-p_0)^{1-x[0]\oplus\theta}\cdots p_{N-1}^{x[N-1]\oplus\theta}(1-p_{N-1})^{1-x[N-1]\oplus\theta} \end{eqnarray*}

and hence the posterior

\begin{eqnarray*} p_{\theta|\mathbf{x}}(\theta|\mathbf{x})&\propto&p_{\mathbf{x},\theta}(\mathbf{x},\theta)\\ &\propto&p_{\mathbf{x}|\theta}(\mathbf{x}|\theta)p_\theta(\theta)\\ &\propto&p_0^{x[0]\oplus\theta}(1-p_0)^{1-x[0]\oplus\theta}\cdots p_{N-1}^{x[N-1]\oplus\theta}(1-p_{N-1})^{1-x[N-1]\oplus\theta}\pi_1^\theta(1-\pi_1)^{1-\theta} \end{eqnarray*}

but I cannot reach a tractable expression out of this that I can maximize w.r.t. $\theta$. By the way, I was given the hint that $$ \hat{\theta}_{MAP}(\mathbf{x}) = \left\{ \begin{array}{ll} 1\text{, if $\sum\limits_{n=0}^{N-1}q_nx[n]\geq\gamma$}& \\ 0\text{, otherwise} & \end{array} \right. $$

for a threshold $\gamma$ and weights $q_n$ that do not depend on $\pi_1$.

  • $\begingroup$ If this is homework, add the [self-study] tag. $\endgroup$ – Kodiologist Apr 5 '17 at 18:25

This problem has been extensively studied in the information theory literature where it is called something like "error probability for two codewords". The standard model in the information theory literature has all the $p_n$'s the same but extensions to the case of varying $p_n$ have also been considered. Here, the question is made more difficult to understand due to the extreme formalism of the notation, and I will try to give a more accessible solution.

A communication system wishes to convey the value of one bit $\Theta$ (a $0$ or a $1$) across a channel (with binary inputs and binary outputs) that is prone to making errors, that is, sometimes a channel input bit (a $0$ or a $1$) gets flipped (to a $1$ or a $0$ respectively) at the output. More specifically, what the channel does is a series of mutually independent events with the $i$-th transmitted bit being flipped with probability $p_i$. Thus, if $D[i]$ denotes the $i$-th transmitted bit, then $X[i]$, the $i$-th received bit, can be expressed as $$X[i] = \left(D[i] + W[i]\right) \bmod 2$$ where the $W[i]$ are independent Bernoulli random variables with parameters $p_i$.

$\Theta$, the bit whose value the communication system wants to convey across the channel, is also a Bernoulli random variable with parameter $\pi_1$ and is independent of all the $W[i]$'s. Because the channel makes errors, the communication system transmits $n$ copies of $\Theta$ (that is, $\mathbf D =(D[1],D[2],\cdots, D[n])$ equals $(1,1,\cdots, 1)$ with probability $\pi_1$ and equals $(0,0,\cdots, 0)$ with probability $1-\pi_1$. The received vector is $\mathbf X = (x[1],x[2],\cdots, x[n]) = \left(\mathbf D + \mathbf W \right)\bmod 2$. Let $\Gamma_k$, $k = 0, 1$ be the set of indices $i$ such that $x[i]=k$. If $\Theta = 1$, then the channel flipped bits in the positions $\Gamma_0$ while if $\Theta = 0$, then the channel flipped bits in the positions $\Gamma_1$. Thus, the likelihood of observing $\mathbf X$ when $\Theta = 1$ is $$L(\mathbf X, 1) = \prod_{i\in \Gamma_0}p_i \prod_{j\in \Gamma_1}(1-p_j) = \prod_{i=1}^np_i \prod_{j\in \Gamma_1}\frac{1-p_j}{p_j} = A_1 \prod_{j\in \Gamma_1}\frac{1-p_j}{p_j}$$ while the likelihood of observing $\mathbf X$ when $\Theta = 0$ is $$L(\mathbf X, 0) = \prod_{i\in \Gamma_0}(1-p_i) \prod_{j\in \Gamma_1}p_j = \prod_{i=1}^n(1-p_i)\prod_{j\in \Gamma_1}\frac{p_j}{1-p_j} = A_0\prod_{j\in \Gamma_1}\frac{p_j}{1-p_j}$$ From this, we get that the likelihood ratio is $$LR(\mathbf X) = \frac{L(\mathbf X, 1)}{L(\mathbf X, 0)} = \frac{A_1}{A_0}\prod_{j\in \Gamma_1}\left(\frac{1-p_j}{p_j}\right)^2$$ while the log likelihood ratio \begin{align}LLR(\mathbf X) = \ln\left(\frac{A_1}{A_0}\right) + 2\sum_{j\in \Gamma_1} \ln\left(\frac{1-p_j}{p_j}\right) \end{align}

It is a standard result in decision theory that the MAP decision rule for deciding between two hypotheses $H_0$ and $H_1$ with prior probabilities $1-\pi_1$ and $\pi_1$ respectively can be expressed as $$\ln\left(\frac{\pi_1}{1-\pi_1}\right)+ LLR(\mathbf X)~\begin{array}{c}H_1\\\gtrless\\H_0\end{array}~ 0$$ and I leave it to the OP to write $\displaystyle\sum_{j\in \Gamma_1} \ln\left(\frac{1-p_j}{p_j}\right)$ as $\displaystyle\sum_{i=1}^n \delta_i x[i]$ and to show that the MAP decision rule is equivalent to estimating that the value of $\Theta$ is $1$ if $\displaystyle \sum_{i=1}^n q_ix[i]$ exceeds a threshold $\gamma$ which is what the hint that he has been provided is telling him is the right answer.


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.