Average of an autocorrelation

Question

I am struggling with a random process problem. I have a sequence of random variables, $a_i$, where $a_i$ is either -1 or 1 with 50% probability. I am studying realisations of the magnitude of the autocorrelation, eg.: $$\mathbf{A}=\begin{bmatrix} 1 & 1 & -1 & -1\\ \end{bmatrix},\quad R_A= \begin{bmatrix} -1 & -2 & 1 & 4 & 1 & -2 & -1\\ \end{bmatrix} \mathrm{and} \quad\left|R_A\right|= \begin{bmatrix} 1 & 2 & 1 & 4 & 1 & 2 & 1\\ \end{bmatrix}. $$ My main objective is to develop a relationship that gives the average value of each element of the magnitude autocorrelation. For this question, I can find via brute force that the average is, $$\begin{bmatrix} 1 & 1 & \frac{3}{2} & 4 & \frac{3}{2} & 1 & 1\\ \end{bmatrix}.$$ I would appreciate any pointers on how to show this.

Answer 1

If the vector has length $m$ then the central correlation is always $m$.
Otherwise it depends on the number, say $n$, of overlapping $A_i$.
If $n$ is even, then the final term is equally likely to increase or decrease $R_A$, so the average value is the same as for $n-1$.
If $n$ is odd, it is similar, except if the sum of the first $n-1$ terms is zero, in which case the final term increases $R_A$. This happens with probability $\frac1{2^{n-1}}{n-1\choose (n-1)/2}$, so the average is that much bigger.
$$S_n=\sum_{k=0}^{\lfloor (n-1)/2\rfloor}4^{-k}{2k\choose k}$$