What is the expected length of the largest run of heads if we make 1,000 flips? Is there a way to calculate on average, the maximum amount of times we can expect a coin to land heads during 1,000 flips?
So the answer (and formula if one exists) I am looking for would be something like: during 1,000 flips we can expect a maximum run of 12 heads in a row.
 A: If you can calculate the probability of getting no more than $k$ heads in a row, call it $P_k$, then the probability that the maximum number of heads in a row is exactly $k$ is $P_k - P_{k-1}$. Then your expectation is
$$\sum_{k=1}^{1000} k(P_k - P_{k-1}) = 1000P_{1000} - \sum_{k=0}^{999} P_k$$
So it suffices to calculate all the $P_k$. Fortunately there is an easy way to do this with a recurrence on the total number of flips $n$. Let $Q_{k,m}(n)$ be the number of ways to have $n$ flips so that there are no more than $k$ heads in a row, and the flips end with a sequence of $m$ heads in a row. Then
$$Q_{k,0}(n+1) = \sum_{m=0}^k Q_{k,m}(n)$$
and
$$Q_{k,m}(n+1) = Q_{k,m-1}(n)$$
for all $m$ between $1$ and $k$, and your desired $P_k$ (as a function of $n = 1000$) is $P_k = (1/2^{1000}) \sum_{m=0}^k Q_{k,m}(1000)$.
You can calculate the $Q$ values in order of increasing $n$ up to 1000, fairly quickly, and then $P_k$ is as described. With a computer program code this would compute all $P_k$, and hence your expectation, in a fraction of a second.
A: You can also attack this problem using generating functions. If we give a sequence of n coin throws a weight of $x$, then the generating function for a single string of at most $n$ heads is:
$$G_n(x) = \frac{1-x^{n+1}}{1-x}$$
A general sequence of coin throws such that there are at most $n$ heads in any sequence of heads, can consist of any arbitrary number of such sequences, the generating function $f(x)$ is obtained by summing over all possible ways to join together such sequences with a singe tail inbetween:
$$f(x) = G_n(x) + G_n(x) x G_n(x) +  G_n(x) x G_n(x) x G_n(x)+\cdots$$
We thus have:
$$f(x) = G_n(x)\sum_{k=0}^{\infty}x^kG_n^k(x) = \frac{G_n(x)}{1-x G_n(x)}=\frac{1-x^{n+1}}{1-2x+x^{n+2}}$$
The coefficient of $x^r$ can be written as:
$$c_r = \frac{1}{2\pi i}\oint_C\frac{1}{z^{r+1}}\frac{1-z^{n+1}}{1-2z+z^{n+2}}dz$$
where the contour $C$ is a small counterclockwise circle around the origin that avoids the poles of $f(z)$. Since the contour integral over a circle of radius $R$ with center the origin will tend to zero in the limit of $R\to\infty$, the sum of all the residues of the integrand equals zero, therefore $c_r$ is equal to minus the sum of all the resides at all the poles other than the one at the origin. The dominant contribution to $c_r$ for large $r$ comes from the pole near $z=\frac{1}{2}$. To evaluate it, one can write the zero of the denominator as $\frac{1}{2} + t$ expand to first order in $t$ and solve for $t$. The pole $p$ is then found to be approximately located at:
$$p \approx \frac{1}{2} + \frac{1}{2^{n+3} - 2 n -4}$$
This then yields:
$$c_r\approx 2^r \left(1+\frac{1}{2^{n+2} -n-2}\right)^{-(r+1)}\frac{1-p^{n+1}}{1-\frac{(n+2)}{2} p^{(n+1)}}$$
The probability for there being a sequence of at most $n$ heads is thus approximately:
$$P_n \approx \exp\left(-\frac{r+1}{2^{n+1}-n-2}\right)\frac{2^{n+1}-1}{2^{n+1}-\frac{n+2}{2}}$$
A: A quick approximation (works asymptotically) would be to model that the succesive runs as iid geometric variables, say $r_n \sim Geom(1/2)$, so $E(r_n)=2$, so we'd have approximately $N/2$ runs, $N/4$ being head runs. Then the problem would be equivalent to finding the maximum of $N/4$ iid geometric rv... which is not an easy problem. Using the (again, approximate) results of the linked answer, we'd get
$$E[\max_{N/4}\{ r_n\}] \approx \frac{1}{2} + \frac{1}{\log 2} H_{N/4}\approx \frac{1}{2} +\frac{\log(N/4) +\gamma}{\log 2}  \approx \log_2(N) $$
For a biased coin with heads probability $p$, we have approximately $M=pq N$ head runs, and the expected maximum is
$$E[\max_{M}\{ r_n\}] \approx \frac{1}{2} - \frac{1}{\log q} H_{M}\approx \frac{1}{2} -\frac{\log(N p q) +\gamma}{\log q}  $$
A: Some intuition about what you can expect can be found here: Longest Run of Heads.
Let the random variable $L_n$ be the largest contiguous heads sequence in $n$ coin tosses (suppose the coin is biased with heads probability $p$).
In the paper you can find the following intuitive approximation to the expectation of $L_n$:
denote by $N_k$ the expected number of heads sequences having length$\ge k$. Since each tails outcome is a possible beginning of a heads sequence(ignoring edges), the expected number of heads sequences with length$\ge 1$ is $N_1\approx n(1-p)p$. Similarly, for length$\ge 2$ sequences the expectation is $N_2\approx n(1-p)p^2$ and generally $N_k\approx n(1-p)p^k$. Now you can approximate the expectation of $L_n$ by the solution to $N_k=1$ and this yields: $L_n$
$\langle L_n\rangle\approx -\log_pn(1-p)=\log_\frac{1}{p}n(1-p)$.
Although this appears extremely loose, it gives you an idea about the asymptotic behaviour $\langle L_n\rangle$ (logarithmic growth).
More accurately, you have $\frac{L_n}{\log_\frac{1}{p}n} \rightarrow 1$ in probability, i.e. 
$\forall \epsilon>0 \lim\limits_{n\to\infty}\mathbb{P} \left(\left|\frac{L_n}{\log_{1/p}n}-1\right|>\epsilon \right)=0$.
You may want to look at the following plot I got a while back. For $1\le n\le 1000$ $\langle L_n\rangle$ is calculated using $1000$ trails of $n$ unbiased coin tosses:

