Expected deviation of a coin that obeys the gambler's fallacy Suppose a magical coin $C$ comes up heads with probability $\frac12$ on the first flip, and thereafter comes up heads with probability $\frac t{h+t}$, where $h$ and $t$ are the number of heads and the number of tails flipped so far.  For for example if the first four flips include three heads and one tail, the probability of $C$ coming up heads on the fifth flip is $\frac 14$.  The probability of obtaining heads on the sixth flip is then either $\frac 15$ or $\frac 25$, depending on whether the fifth flip was a head or a tail.
Let $H(n)$ be the random variable counting the number of heads obtained in the first $n$ flips of coin $C$.
A simple symmetry argument shows that the mean of $H(n)$ is $\frac n2$.  (Dan Schmidt also points out that there is an easy inductive proof.)

How can I calculate the standard deviation of $H(n)$? It seems clear that it must be strictly less than $\frac12\sqrt n$, which is the standard deviation of for a fair coin, but how much less?

 A: To simplify the calculations, let's consider the difference between the number of heads and tails, i.e. we count heads as $+1$ and tails as $-1$ and consider the sum of the results. Then the expected sum is $0$ by symmetry, and in view of the comments we want to prove that the variance is $\frac n3$ for $n\ge3$.
The process can be modeled by a sort of inverse Pólya urn model. Each coin flip corresponds to uniformly randomly drawing a ball of value $\pm1$ from the urn. Whereas in a Pólya urn we add a ball of the same type as the one just drawn after replacing it, here we add a ball of the opposite type. The balls in the urn after the $n$-th step are the opposite of the $n$ results obtained, so the variance of their sum is the variance of the sum of the results and we can calculate this variance instead.
So let $S_n$ be the sum of the balls in the urn, and $Q_n=\mathsf{Var}(S_n)=\mathsf E(S_n^2)-\mathsf E(S_n)^2=\mathsf E(S_n^2)$ the variance. When we add the $(n+1)$-th ball with value $X_n$, we have $S_{n+1}=S_n+X_{n+1}$ and thus
$$
Q_{n+1}=\mathsf E\left(S_{n+1}^2\right)=\mathsf E\left(S_n^2+2S_nX_{n+1}+X_{n+1}^2\right)=Q_n+2\mathsf E(S_nX_{n+1})+1\;.
$$
Since $X_{n+1}$ is the opposite of a ball randomly chosen among the existing balls, whose sum is $S_n$,
$$
\mathsf E(S_nX_{n+1})=-\frac1nE(S_n^2)\;,
$$
and thus
$$
Q_{n+1}=Q_n\left(1-\frac 2n\right)+1\;.
$$
Since $Q_n=\frac n3$ is true for $n=3$ and is preserved by the recurrence, it follows by induction that it's true for all $n\ge3$.
