Understanding derivation in Robbins (1952) I was trying to read Herbert Robbins' 1952 paper "Some Aspects of the Sequential Design of Experiments" (projecteuclid, DOI) and I have got really, annoyingly stuck on formula (2).  I cannot, for the life of me, understand how one shows in the described setting that
$$
p_{i+1} = (\alpha + \beta - 1)p_i + (\alpha + \beta - 2\alpha\beta).
$$
The surrounding section is very readable, but to save the reader effort: $\alpha$ and $\beta$ are the probabilities of two coins $A$ and $B$, respectively, coming up heads; $p_i$ is the probability of flipping heads on flip $i$.  There is a reward of one dollar for every heads, so the goal is to balance the sampling of $\alpha$ and $\beta$ with the exploitation of the coin corresponding to $\max(\alpha, \beta)$.  Robbins is discussing a "rule" $R_1$ (policy, in the language of today's bandit literature) which stipulates switching coins when the current coin comes up tails, and sticking with the current coin when it comes up heads.  Given this context, I think I understand the second term:
$$\alpha + \beta - 2\alpha\beta = (1-\alpha)\beta + (1-\beta)\alpha. $$
This is the probability of getting tails at flip $i$, switching coins as the rule requires, and getting a heads on the opposite coin at time $i+1$.  But I simply cannot wrap my head around the first term.  Robbins constrains that $0 < \alpha, \beta < 1$, so that $|\alpha + \beta - 1| < 1$, however the first term does not contain the absolute value.  I don't understand how we ensure that $p_{i+1}$ is a probability if the first term may be negative.  More importantly, I just cannot figure out what event $(\alpha + \beta - 1)$ is supposed to represent.  I have not been able to produce a derivation that satisfyingly explains it.  Either of an intuitive explanation or a derivation would be very helpful (I don't suspect that the derivation is long, I'm just clearly missing something).
Thank you so much!
 A: Struggled with the expression for the last couple of days, very frustrating but in the end rewarding since I think the derivation below shows how to get the recursion. Unfortunately I do not have an intuitive explanation for the recursion...
Define the events
$H_i := \text{"heads in flip } i$",
$A_i := \text{"coin $A$ is used in flip $i$"}$ and
$B_i := \text{"coin $B$ is used in flip $i$"}$. Then you get the following:
\begin{align*}
p_{i+1} &= \mathbb{P}(H_{i+1}) \\
&= \mathbb{P}(H_{i+1} | H_i, A_i)\mathbb{P}(H_i|A_i)\mathbb{P}(A_i)
+ \mathbb{P}(H_{i+1} | H_i^c, A_i)\mathbb{P}(H_i^c|A_i)\mathbb{P}(A_i)\\
& \enspace \enspace \enspace \enspace + \mathbb{P}(H_{i+1} | H_i, B_i)\mathbb{P}(H_i|B_i)\mathbb{P}(B_i)
+ \mathbb{P}(H_{i+1} | H_i^c, B_i)\mathbb{P}(H_i^c|B_i)\mathbb{P}(B_i) \\
&= \alpha^2\mathbb{P}(A_i) + \beta (1-\alpha)\mathbb{P}(A_i) + \beta^2\mathbb{P}(B_i) +
\alpha(1-\beta)\mathbb{P}(B_i) \\
&= \alpha^2\mathbb{P}(A_i) + \beta^2\mathbb{P}(B_i) + \beta(1-\alpha) + \alpha(1-\beta) -\mathbb{P}(B_i)\beta(1-\alpha) - \mathbb{P}(A_i)\alpha(1-\beta)\\
&= \alpha\mathbb{P}(A_i)(\alpha + \beta - 1) + \beta\mathbb{P}(B_i)(\alpha + \beta - 1) + \beta(1-\alpha) + \alpha(1-\beta) \\
&= (\alpha + \beta - 1)(\alpha \mathbb{P}(A_i) + \beta \mathbb{P}(B_i)) + \beta(1-\alpha) + \alpha(1-\beta) \\
&= (\alpha + \beta - 1)p_i + \beta(1-\alpha) + \alpha(1-\beta)
\end{align*}
A: delivery101 has answered the original question wonderfully.  I wanted to contribute an explanation of the next equation in the paper as well since while one could accept it as the consequence of the algebra like Eq. (2), justification is useful and I have already done the tedious work.
The next equation states without demonstrating why that the recursion relation justified in the accepted answer implies the following:
$$ p_i = (\alpha + \beta - 1)^{i-1}\Big[p_1 - \frac{\alpha + \beta - 2\alpha\beta}{2 - (\alpha + \beta)}\Big] + \frac{\alpha + \beta - 2\alpha\beta}{2 - (\alpha + \beta)}.$$
By equating this with Eq. (2) of the paper I observed that
$$ (\alpha + \beta - 1)p_1 - \frac{(\alpha + \beta - 1)(\alpha + \beta - 2\alpha\beta)}{2 - (\alpha + \beta)} + \frac{(\alpha + \beta - 2\alpha\beta)}{2-(\alpha + \beta)} = (\alpha + \beta - 1)p_1 + (\alpha + \beta - 2\alpha\beta)$$
$$\implies \frac{1-(\alpha + \beta - 1)}{2 - (\alpha + \beta)}(\alpha + \beta - 2\alpha\beta) = \frac{2 - (\alpha + \beta)}{2 - (\alpha + \beta)}(\alpha + \beta - 2\alpha\beta) = \alpha + \beta - 2\alpha\beta$$
which demonstrates the key substitution.
Let $\pi = \alpha + \beta - 2\alpha\beta$, let $\lambda = \alpha + \beta - 1$, and  let $\phi = \frac{\alpha + \beta - 2\alpha\beta}{2 - (\alpha + \beta)}$.  Let's try to unfold $p_3$ according to equation (2).  We see that
\begin{align} p_4 &= \lambda[\lambda[\lambda p_1 + \pi] + \pi] + \pi \\ 
&= \lambda[\lambda[\lambda p_1 + \phi - \lambda\phi] + \pi] + \pi \\
&= \lambda[\lambda[\lambda p_1 + \phi - \lambda\phi] + \phi - \lambda\phi] + \pi \\
&= \lambda[\lambda[\lambda p_1 + \phi - \lambda\phi] + \phi - \lambda\phi] + \phi - \lambda\phi \\
&= \lambda[\lambda^2[p_1 - \phi] + \lambda\phi + \phi - \lambda\phi] + \phi - \lambda\phi \\
&= \lambda[\lambda^2[p_1 - \phi] + \phi] + \phi - \lambda\phi \\
&= \lambda^3[p_1 - \phi] + \lambda\phi + \phi - \lambda\phi \\
&= \lambda^3[p_1 - \phi] + \phi
\end{align}
which generalizes to equation (3) as intended.
