1
$\begingroup$

I'm new at this topic and I didnt understand how can I solve that kind of problem:

A center which can call 0 or 1 may be reverted with prob. 0.01 as it travels btw 2 successive centers. Let Xn be the digit received by the n'th center on the communication system.

$\endgroup$

1 Answer 1

1
$\begingroup$

I will assume here that a digit being 'reverted' means a digit being 'flipped', e.g., a 0 may turn into a 1, and vice versa. I am otherwise unfamiliar with the term.

Let's define a state $x=[p_0, p_1]$, where $p_0$ is the probability of your digit being in state 0 and $p_1$ is the probability of your digit being in state 1. In your case, the initial state $x_0 = [1,0]$.

Now, we send it off to the next link in the communication chain. Each digit has a probability $0.01$ of being flipped in transit. We can represent this as a transition matrix $T$: $$ T=\begin{bmatrix}.99&.01\\.01&.99\end{bmatrix} $$

Multiplying the transition matrix into your initial state yields the probability of finding each digit after that first step:

$$ x_1 = T\cdot x_0=\begin{bmatrix}.99&.01\\.01&.99\end{bmatrix}\cdot \begin{bmatrix}1\\0\end{bmatrix}= \begin{bmatrix}0.99\\0.01\end{bmatrix} $$

We see that after one transmission, the odds of finding that your digit is 0 are 0.99, and the odds of finding your digit is 1 are 0.01.

For the $n^{th}$ station, we can find the transition probability as:

$$ x_n = T^n\cdot x_0=\begin{bmatrix}.99&.01\\.01&.99\end{bmatrix}^n\cdot \begin{bmatrix}1\\0\end{bmatrix} $$

Let's solve this problem for n=3 in python:

import numpy as np

x_i = [1, 0]
T = np.matrix([[.99, 0.01],[0.01,.99]])
T_3 = np.linalg.matrix_power(T, 3)
print(np.dot(T, x_i))

We find (rounding to two digits for clearer presentation).

$$ x_3 = T^3\cdot s_0=\begin{bmatrix}0.97\\0.03\end{bmatrix} $$

In other words, the probability that the third center receives the same digit is 0.97.

It's also good to check our intuition in the extreme case that $n\rightarrow\inf$. If we have some chance of flipping our digit at every station, then after enough stations we might expect equal odds of seeing a 0 or a 1, whatever our original input. Let's try:

trans_mat_1000 = np.linalg.matrix_power(trans_mat, 1000)
print(np.dot(T, x_i))

Indeed, we find:

$$ x_{1000} = T^{1000}\cdot x_0=\begin{bmatrix}0.50\\0.50\end{bmatrix} $$

This should give us some comfort in our implementation.

$\endgroup$

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