Expected value (mean) of function from polyline

Question

Suppose we have a polyline that has such properties:

1. It consists of n segments
2. First segment's ends are (0, 0) and (1, 0).
3. 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?

Answer 1

Finally, I have managed to solve this.

Solution:

Let

1. $z = \cos \alpha + i \sin \alpha$
2. $S_{(i_1,...,i_n)}$ = $1 + z^{i_1} + z^{i_1 + i_2} + ... + z^{i_1 + ... + i_n}$
3. $H_n = \sum_{(i_1,...,i_n)\in\{-1,1\}^n} (S_{(i_1,...,i_n)} + \bar{S}_{(i_1,...,i_n)})$
4. $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}$