Probability of 0 in Binary Sequence

Question

A random binary sequence is produced as follows. The first coordinate equals $0$ with probability $0.6$ and equals $1$ with probability $0.4$. For any positive integer $n$, the $(n+1)^\text{th}$ coordinate is the same as the $n^\text{th}$ coordinate of the sequence, with probability $0.7$, and equals the opposite of the $n^\text{th}$ coordinate with probability $0.3$.

Calculate the probability that the $n^\text{th}$ coordinate is $0$ and also the limit of this probability as $n \to \infty$.

Progress: I rewrote this as a recurrence relation using the law of total probability and then tried to solve it using a characteristic polynomial of a first-order difference equation. This resulted in me getting a probability of $0.5$ as $n \to \infty$. I don't know if this is right, but I wanted to get the input of the MSE community.

Answer 1

Let $x_n$ be the value of the $n^\text{th}$ coordinate. We know, conditional on $x_{n-1}$, that $x_n = x_{n-1}$ with probability $0.7$, and $x_n = 1 - x_{n-1}$ with probability $0.3$.

It is easy to see that

$$ \Pr(x_n = 0) = 0.7 \Pr(x_{n-1} = 0) + 0.3 \Pr(x_{n-1} = 1). $$

Denote $p_n = \Pr(x_n = 0)$. We thus have that

$$ p_n = 0.7p_{n-1} + 0.3(1-p_{n-1}) =0.4p_{n-1} + 0.3. $$

along with the initial condition that $p_1 = 0.6$. Hence,

$$ p_n = 0.4^{n-1}p_1 + 0.3\sum_{k=1}^{n-1} 0.4^{k-1}. $$

I'll leave the rest of the problem to you.

Answer 2

Starting from an initial $0$ (prob. $=0.6$) then in the following $n-1$ you must have an even number ($2k$ ) of changes to end with a $0$.
Starting with $1$ instead (prob. $=0.4$), you must have $2j+1$ changes.

That means $$ \eqalign{ & P_{\,0} (n) = 0.6\sum\limits_{0\, \le \,k\, \le \,\left\lfloor {\left( {n - 1} \right)/2} \right\rfloor } {\left( \matrix{ n - 1 \cr 2k \cr} \right)p^{\,2k} q^{\,n - 1 - 2k} } + \cr & + 0.4\sum\limits_{0\, \le \,j\, \le \,\left\lfloor {\left( {n - 2} \right)/2} \right\rfloor } {\left( \matrix{ n - 1 \cr 2j + 1 \cr} \right)p^{\,2j + 1} q^{\,n - 2 - 2j} } = \cr & = 0.5\left( {\sum\limits_{0\, \le \,k\, \le \,\left\lfloor {\left( {n - 1} \right)/2} \right\rfloor } {\left( \matrix{ n - 1 \cr 2k \cr} \right)p^{\,2k} q^{\,n - 1 - 2k} } + \sum\limits_{0\, \le \,j\, \le \,\left\lfloor {\left( {n - 2} \right)/2} \right\rfloor } {\left( \matrix{ n - 1 \cr 2j + 1 \cr} \right)p^{\,2j + 1} q^{\,n - 2 - 2j} } } \right) + \cr & + 0.1\left( {\sum\limits_{0\, \le \,k\, \le \,\left\lfloor {\left( {n - 1} \right)/2} \right\rfloor } {\left( \matrix{ n - 1 \cr 2k \cr} \right)p^{\,2k} q^{\,n - 1 - 2k} } - \sum\limits_{0\, \le \,j\, \le \,\left\lfloor {\left( {n - 2} \right)/2} \right\rfloor } {\left( \matrix{ n - 1 \cr 2j + 1 \cr} \right)p^{\,2j + 1} q^{\,n - 2 - 2j} } } \right) = \cr & = 0.5 + 0.1\left( {\sum\limits_{0\, \le \,k\, \le \,n - 1} {\left( \matrix{ n - 1 \cr k \cr} \right)\left( { - 1} \right)^{\,k} p^{\,k} q^{\,n - 1 - k} } } \right) = \cr & = 0.5 + 0.1\left( { - p + q} \right)^{\,n - 1} = 0.5 + 0.1\left( {0.4} \right)^{\,n - 1} \cr} $$ A check using Markov matrices confirms that.

So, for $n \to \infty$ the probability tends to $1/2$.