Find the normalizing constant for $\exp\left(\theta\sum_{i=1}^{n-1}x_ix_{i+1}\right)$ Let $X_i,i=1,...,n$ be random variables assuming the values $1$ and $-1$. Suppose that the joint distribution of $X_1,...,X_n$ is given by
$$\Pr(X_i=x_i,i=1,...,n)\propto \exp\left(\theta\sum_{i=1}^{n-1}x_ix_{i+1}\right):=h$$
for $x_i\in\{1, -1\}$, where $\theta\in\mathbb R$.
(a) Find the normalizing constant $Z_n(\theta)=\sum_{x_1,...,x_n}h$
Ans:
If n=2, we have the normalizing constant to be $e^{\theta1(1)}+e^{\theta(-1)}+e^{\theta(-1)}+e^{\theta1(1)}$
1 1
1 -1
-1 1
-1 -1

If n=3 the normalizing constant is $e^{\theta(2)}+e^{\theta(-2)}+e^0+e^0+e^0+e^0+e^{\theta(-2)}+e^{\theta(2)}$
1 1 1
-1 1 -1
1 -1 -1
...
1 1 1

I couldn't list all the combinations for n=4. Is there a combinatorial trick? I don't think it's supposed to be particularly difficult, so maybe I'm calculating it wrong.
Also, part (c) says, is $X_t$ a markov chain? If so, determine its transition matrix. I have not yet wrapped my head around what shape or form this markov chain is hidden in.
 A: Given $x_1, \ldots, x_n$, you can define $z_1=x_1$ and $z_i = x_i / x_{i-1}$ for $i \ge 2$. The intuition is that $z_i = -1$ iff $x_i$ has the opposite sign of $x_{i-1}$.

Example: If $(x_1, x_2, x_3, x_4) = (1, 1, -1, 1)$ we have $(z_1, z_2, z_3, z_4) = (1, 1, -1, -1)$.

You can check that this mapping $(x_1, \ldots, x_n) \mapsto (z_1, \ldots, z_n)$ is a bijection from $\{-1, 1\}^n$ to $\{-1, 1\}^n$. Furthermore, $\sum_{i=1}^{n-1} x_i x_{i+1} = \sum_{i=1}^{n-1} x_i^2 z_{i+1} = \sum_{j=2}^n z_j$. Thus,
$$\sum_{x_1, \ldots, x_n} \exp\left(\theta \sum_{i=1}^{n-1} x_i x_{i+1}\right)
= \sum_{z_1 ,\ldots, z_n} \exp\left(\theta \sum_{j=2}^n z_j\right)
= 2 \sum_{z_2,\ldots, z_n} \exp\left(\theta \sum_{j=2}^n z_j\right).$$
If we split into cases by how many of the $z_2,\ldots,z_n$ equal $1$ (call this $k$) so that $\sum_{j=2}^n z_j = 2k -(n-1)$, then we have
$$2e^{-(n-1)\theta} \sum_{k=0}^{n-1} \binom{n-1}{k} e^{2k\theta}
= 2 e^{-(n-1)\theta} (1 + e^{2\theta})^{n-1} = 2 (e^\theta + e^{-\theta})^{n-1}.$$
This seems to match your computations for $n=2,3$.
The final expression looks quite simple, so I am wondering if I completely missed a more direct way of obtaining it...

Regarding the Markov chain, you can check that
$$P(X_n=x_n \mid X_{n-1} = x_{n-1}, \ldots, X_1=x_1)$$
does not depend on the value of $x_{n-2}, \ldots, x_1$.
