$X_1 = 1$ or $-1$ (0.5 chance each), $X_i = -X_{i-1}$ in $\frac{1}{n}$ of the times and $X_{i-1}$ in the rest.
What is $\mathbb E [X_1 X_n]$?
A)~$\frac{1}{e} $
B) $<0$
C)~ $\frac{1}{2}$
D) None of the mentioned answers
So $X_1X_n$ is either $1$ or $-1$. Let's calculate the probability that it's $1$:
$$P(X_1X_n = 1) =P(X_1X_n = 1 | X_1 = 1)*0.5 +P(X_1X_n =1|X_1 = -1)*0.5$$ $P(X_1X_n=1|X_1=1)$has a solution that looks like $(1-\frac{1}{n})^n +(1-\frac{1}{n})^{n-2}*\frac{1}{n^2}*{n\choose2}+...$.
The first element goes to $\frac{1}{e}$ and $P(X_1X_n = 1|X_1=-1)$ has a first element that goes to $\frac{1}{2e(1-\frac{1}{n})}=\Theta(\frac{1}{e})$ So in conclusion $P(X_1X_n = 1) = \Theta(\frac{1}{e})$.
I'm not sure how to proceed from here. I understand that in this case $\mathbb E [X_1X_n] = Cov(X_1,X_n)$ and intuitively I understand that they are correlated, I'm just not sure how.