Suppose one has the following path in a graph: $$x_1 \rightarrow x_2 \rightarrow \dots \rightarrow x_n,$$ where $x_i \in \{-1,1\}$.
I want to calculate $$p(x_n = 1 \mid x_1=1) = p(x_2 \mid x_1 = 1) p(x_3 \mid x_2) \cdots p(x_n=1 \mid x_{n-1}).$$
I know that $$p(x_i = -1) = p(x_i = 1) = \frac{1}{2},\\ (X_{i+1} \mid X_i = 1) \sim (q_{-1}, q_1),\\ (X_{i+1} \mid X_i = -1) \sim (q_1, q_{-1}),$$ where the left side of the distribution is the chance that $X_{i+1} = -1$.
The funny thing here is that this chain looks a lot like the binomial distribution. However when signs change the succes/fail distribution seems to change as well. Since if the predecessor is a $-1$ the distribution differs than when your predecessor is a $1$. Suppose we look at a sequence with $n = 5$: $$1,-1,1,-1,1,$$ then with the above knowledge we get $\dfrac{1}{2} q_{-1}^4$, which is obviously different than when one looks at the binomial distribution.
I was wondering if there is an easy way to calculate $p(x_n=1 \mid x_1=1)$. I tried looking at the Poisson binomial distribution like in:
https://en.wikipedia.org/wiki/Poisson_binomial_distribution
However this did not help me much further.
I did also look at the Beta-bionomial distribution which seemed a better alternative for this problem. However i don't seem to understand how to choose $\alpha$ and $\beta$:
https://en.wikipedia.org/wiki/Beta-binomial_distribution
The eventual goal is to understand the behavior of tree graphs so let $G$ be a graph, an assume that each node has one incoming edge except the center node which has no incoming edges. Then the new chain will look like this: $$X_0 \rightarrow X_1 \rightarrow X_2 \rightarrow \dots \rightarrow X_n,$$ where $X_0 \in \{-1,1\}$, and $X_i \in \{-1,1\}^{k_i}$ where $k_i$ is the amount of nodes with distance $k_i$ from $x_0$. Is there a way to calculate certain components like $$P(X_n = \{1,1,\dots,1\} \mid X_0 = 1)?$$
Under the given condition, $\{X_k\}$ is a Markov process and$$ P(X_{k + 1} = X_k) = q_1,\ P(X_{k + 1} = -X_k) = q_{-1}. \quad \forall 1 \leqslant k \leqslant n - 1 $$ Because $x_1 = 1$, then the equivalent condition for $x_n = 1$ is that there are exactly even number of indices $k \in \{1, \cdots, n - 1\}$ such that $X_{k + 1} = -X_k$. Note that for any $0 \leqslant m \leqslant \left[ \dfrac{n - 1}{2} \right]$, if a sequence $\{x_k\}_{k = 2}^n \in \{\pm 1\}^{n - 1}$ changes signs for $2m$ times, then $x_n = 1$ and$$ P(X_2 = x_2, \cdots, X_n = x_n \mid X_1 = 1) = q_{-1}^{2m} q_1^{n - 1 - 2m}. $$ Also, there are exactly $C(n, 2m)$ sequences $\{x_k\}_{k = 2}^n \in \{\pm 1\}^{n - 1}$ that change signs for $2m$ times. Therefore,$$ P(X_n = 1 \mid X_1 = 1) = \sum_{m = 0}^{\left[ \frac{n - 1}{2} \right]} C(n, 2m) q_{-1}^{2m} q_1^{n - 1 - 2m}. $$