Expected length of a run in a finite number of coin flips Consider a sequence of fair coin flips. A run of length $k$ is $k$ consecutive flips that are all the same. (e.g. HTTHH has a run of length 1 and two runs of length 2). Define the random variable $R_n$ as the result of the following process: generate a sequence of $n$ fair coin flips, list the lengths of its runs, and then sample from this list uniformly at random. I am trying to find $\mathbb{E}[R_n]$.
From trying small cases, the answer seems to be $2-\frac{1}{2^{n-1}}$:

*

*If $n=1$, there is always one run of length 1

*If $n=2$, there are two runs of length 1 half of the time, and one run of length two half of the time, for an average of $\frac{1}{2}\cdot 1+\frac{1}{2}\cdot 2=\frac{3}{2}$

*If $n=3$, you get AAA format $\frac{1}{4}$ of the time, AAB or BAA format $\frac{1}{2}$ of the time, and ABA format $\frac{1}{4}$ of the time, giving $\frac{1}{4}\cdot 3 + \frac{1}{2}\cdot \frac{3}{2} + \frac{1}{4}\cdot 1 = \frac{7}{4}$.

*If $n=4$, you get a run of length 4 with probability $\frac{1}{8}$, runs with lengths 3 and 1 with probability $\frac{1}{4}$, runs with length 2 and 2 with probability $\frac{1}{8}$, runs with lengths 1,1,2 with probability $\frac{3}{8}$, and runs with lengths 1,1,1,1 with probability $\frac{1}{8}$. This gives $\frac{1}{8}\cdot 4+\frac{1}{4}\cdot 2+\frac{1}{8}\cdot 2+\frac{3}{8}\cdot \frac{4}{3} + \frac{1}{8}\cdot 1 = \frac{15}{8}$.

This also makes sense because intuitively, the distribution of $R_n$ should be approximated by a geometric RV of probability $\frac{1}{2}$, which has EV 2. The difference is that runs are necessarily finite, while a geometric RV can be infinite. This means $\mathbb{E}[R_n]$ must be less than $2$ and approaching $2$ for large $n$.
In fact, if we define $G_n$ to be a 'truncated' geometric RV which has distribution $\mathbb{P}[G_n=i] = 2^{-i}$ for $1\leq i\leq n-1$ and $\mathbb{P}[G_n=n]=2^{-n+1}$, then $\mathbb{E}[G_n] = 2-\frac{1}{2^{n-1}}$, which looks promising (and possibly there is even a direct combinatorial argument that $\mathbb{E}[G_n]=\mathbb{E}[R_n]$). However I can't find a way to use this to find $\mathbb{E}[R_n]$.
 A: Approach 1
In the same random experiment, let $\mathbf X_n$ be the number of runs. Each coinflip after the first independently starts a new run with probability $\frac12$, so we have $\Pr[\mathbf X_n = k] = \binom{n-1}{k-1} (\frac12)^{n-1}$. (In other words, $\mathbf X_n - 1$ is $\text{Binomial}(n-1, \frac12)$.)
We have $\mathbb E[\mathbf R_n \mid \mathbf X_n = k] = \frac nk$. If there are $k$ runs, then (no matter how they are split up) the expected length of a randomly picked run is going to be equal to the average length of a run.
Therefore $\mathbb E[\mathbf R_n] = \mathbb E[\frac{n}{\mathbf X_n}]$, which we can find by definition of expected value:
$$
   \mathbb E\left[\frac{n}{\mathbf X_n}\right] = \sum_{k=1}^n \frac nk \binom{n-1}{k-1} \left(\frac12\right)^{n-1} = \sum_{k=1}^n \binom nk \left(\frac12\right)^{n-1} = \frac{2^n - 1}{2^{n-1}} = 2 - \frac1{2^{n-1}}.
$$
Approach 2
We can prove that actually, the distribution of a randomly chosen run is the same as the distribution of the first run, which is precisely the truncated geometric $\mathbf G_n$. In particular, $\mathbb E[\mathbf R_n] = \mathbb E[\mathbf G_n] = 2 - \frac1{2^{n-1}}$.
Say that two outcomes are equivalent if their run patterns are the same up to cyclic permutation. For example, HHTHHHTT has run pattern $(2,1,3,2)$ and TTTHHTTH has run pattern $(3,2,2,1)$, so they are equivalent.
Within an equivalence class of outcomes, the distribution of a random run is the same as the distribution of the first run, because choosing a random run is the same as choosing the first run in a random cyclic permutation of the run pattern. So $\mathbf R_n$ and $\mathbf G_n$ have the same distribution on each equivalence class, which means they have the same distribution overall.
A: WLOG only consider all possible $n$ length sequences that start with heads.
Consider the positive integer solutions to the equation
$$\sum_{i=1}^k a_i=n$$
We can biject these solutions to all possible sequences that start with heads and have $k$ runs by making a sequence starting with heads so that the $i^\text{th}$ run in the sequence has length $a_i$. This means that the runs of length $a_{2i-1}$ will be composed of heads and the runs of length $a_{2i}$ will be composed of tails.
A particular solution will biject to a sequence with $k$ runs that have length $a_1,a_2,\ldots a_k$. Since each of these runs have probability $\frac{1}{k}$ of being picked, the expected length of a run for any sequence with $k$ runs will be
$$\sum_{i=1}^k \frac{a_i}{k}$$
$$=\frac{1}{k}\sum_{i=1}^k a_i$$
$$=\frac{n}{k}$$
Using stars and bars, we get that the number of positive integer solutions to
$$\sum_{i=1}^k a_i=n$$
$$\sum_{i=1}^k (a_i-1)=n-k$$
is $\binom{n-k+k-1}{k-1}=\binom{n-1}{k-1}$
Hence, the probability that a randomly chosen sequence which starts with heads has $k$ runs will be
$$\frac{1}{2^{n-1}}\binom{n-1}{k-1}$$
Since the expected value of the length of the chosen run is $\frac{n}{k}$ for any sequence with $k$ runs, the total expected randomly chosen run length is
$$\mathbb{E}[R_n]=\sum_{k=1}^n \frac{1}{2^{n-1}}\binom{n-1}{k-1}\frac{n}{k}$$
$$=\frac{n}{2^{n-1}}\sum_{k=1}^n \binom{n-1}{k-1}\frac{1}{k}$$
$$=\frac{n}{2^{n-1}}\sum_{k=0}^{n-1} \binom{n-1}{k}\frac{1}{k+1}$$
To compute this sum, we use the binomial theorem, which states that
$$f(x)=(1+x)^{n-1}=\sum_{k=0}^{n-1} \binom{n-1}{k}x^k$$
Taking the integral from $0$ to $1$ wrt $x$ of both sides yields
$$\int_0^1 (1+x)^{n-1}\,\mathrm{d}x=\int_0^1\sum_{k=0}^{n-1}\binom{n-1}{k}x^k\,\mathrm{d}x$$
$$\frac{1}{n}(2^n-1)=\sum_{k=0}^{n-1}\int_0^1 \binom{n-1}{k}x^k\,\mathrm{d}x$$
$$\frac{1}{n}(2^n-1)=\sum_{k=0}^{n-1}\frac{1}{k+1}\binom{n-1}{k}x^k$$
Hence,
$$\mathbb{E}[R_n]=\frac{n}{2^{n-1}}\cdot\left(\frac{1}{n}(2^n-1)\right)$$
$$=\boxed{2-\frac{1}{2^{n-1}}}$$
