Expected value (mean) of function from polyline Suppose we have a polyline that has such properties: 


*

*It consists of n segments

*First segment's ends are (0, 0) and (1, 0).

*Every other segment is previous segment rotated by α or -α
The problem is to find average (of all such polylines) square of distance between start point and end point. How to solve that?
 A: Finally, I have managed to solve this.
Solution:
Let 


*

*$z = \cos \alpha + i \sin \alpha$

*$S_{(i_1,...,i_n)}$ = $1 + z^{i_1} + z^{i_1 + i_2} + ... + z^{i_1 + ... + i_n}$

*$H_n = \sum_{(i_1,...,i_n)\in\{-1,1\}^n} (S_{(i_1,...,i_n)} + \bar{S}_{(i_1,...,i_n)})$

*$D_n = \sum_{(i_1,...,i_n)\in\{-1,1\}^n} |S_{(i_1,...,i_n)}|^2$


What we want to find is $D_n\over{2^n}$.
It is obvious, that $S_{(i_1,...,i_n)}$ = $1 + z^{i_1}S_{(i_2,...,i_n)}.$
So $$
\begin{equation}
\begin{split}
H_n 
&= \sum_{(i_1,...,i_n)\in\{-1,1\}^n} (S_{(i_1,...,i_n)} + \bar{S}_{(i_1,...,i_n)}) \\ 
&= \sum_{(i_1,...,i_n)\in\{-1,1\}^n} (1+z^{i_1}S_{(i_2,...,i_n)} + 1 + \bar{z}^{i_1}\bar{S}_{(i_2,...,i_n)}) \\
&= 2^{n+1} + \sum_{(i_2,...,i_n)\in\{-1,1\}^{n-1}} (zS_{(i_2,...,i_n)} + \bar{z}\bar{S}_{(i_2,...,i_n)} + \bar{z}S_{(i_2,...,i_n)} + z\bar{S}_{(i_2,...,i_n)}) \\
&= 2^{n+1} + (z+\bar{z})\sum_{(i_2,...,i_n)\in\{-1,1\}^{n-1}} (S_{(i_2,...,i_n)} + \bar{S}_{(i_2,...,i_n)}) \\
&= 2^{n+1} + H_{n-1}2\cos\alpha
\end{split}
\end{equation}
$$
By induction we can prove, that $H_n = 2^{n+1}\sum_{k=0}^{n} cos^k\alpha=2^{n+1}\frac{\cos^{n+1}\alpha - 1}{\cos\alpha - 1}$
Also 
$$
\begin{equation}
\begin{split}
D_n
&= \sum_{(i_1,...,i_n)\in\{-1,1\}^n} |S_{(i_1,...,i_n)}|^2 \\
&= \sum_{(i_1,...,i_n)\in\{-1,1\}^n} (1+z^{i_1}S_{(i_2,...,i_n)})(1+\bar{z}^{i_1}\bar{S}_{(i_2,...,i_n)}) \\
&= \sum_{(i_1,...,i_n)\in\{-1,1\}^n} (1 + z^{i_1}S_{(i_2,...,i_n)} + \bar{z}^{i_1}\bar{S}_{(i_2,...,i_n)} + |S_{(i_2,...,i_n)}|^2) \\
&= 2^n + 2D_{n-1} + \sum_{(i_1,...,i_n)\in\{-1,1\}^n} (z^{i_1}S_{(i_2,...,i_n)} + \bar{z}^{i_1}\bar{S}_{(i_2,...,i_n)}) \\
&= 2^n + 2D_{n-1} + \sum_{(i_2,...,i_n)\in\{-1,1\}^{n-1}} (zS_{(i_2,...,i_n)} + \bar{z}\bar{S}_{(i_2,...,i_n)} + \bar{z}S_{(i_2,...,i_n)} + z\bar{S}_{(i_2,...,i_n)}) \\
&= 2^n + 2D_{n-1} + (z+\bar{z})\sum_{(i_2,...,i_n)\in\{-1,1\}^{n-1}} (S_{(i_1,...,i_n)} + \bar{S}_{(i_1,...,i_n)}) \\
&= 2^n + 2D_{n-1} + H_{n-1}2\cos\alpha = 2D_{n-1} + H_n - 2^n
\end{split}
\end{equation}
$$
By induction we can prove, that $D_n = 2^n\frac{2\cos\alpha(\cos^{n+1}\alpha - 1) - (n+1)(\cos^2\alpha - 1)}{(\cos\alpha - 1)^2}$
So the answer is $\frac{D_n}{2^n} = \frac{2\cos\alpha(\cos^{n+1}\alpha - 1) - (n+1)(\cos^2\alpha - 1)}{(\cos\alpha - 1)^2}$
