Polya urn: Mean number of draws to get a specific sequence of colors?

Question

Polya urn model: At time $0$ an urn initially contains $b$ $\tt{B}$lue balls and $r$ $\tt{R}$ed balls. At time $1$, a ball is drawn uniformly at random (removing it) from the urn, and two balls of the drawn color are added to the urn. This procedure is then repeated at times $2,3,4,\ldots$, each time increasing by one the total number of balls in the urn while randomly changing its composition, as follows:

$$(x,\ y) \longrightarrow\begin{cases} (x+1,\ y), & \text{with probability $x\over x+y$} \\[2ex] (x,\ y+1), & \text{with probability $y\over x+y$} \end{cases}$$

where $x$ (resp. $y$) denotes the number of blue (resp. red) balls.

Let $T_w$ denote the time of the first occurrence of word $w\in\{\tt{B,R}\}^*$ in the sequence of drawn colors. (E.g., $T_\epsilon=0$ always, and in the sequence $\tt{RBRBB}\ldots$, $T_{\tt{B}}=T_{\tt{RB}}=2,\ T_{\tt{BB}}=5$, etc.)

Question: Is there a known closed form for $E(T_w)$ in any case other than $T_{\tt \epsilon}$, $T_{\tt B}$, or $T_{\tt R}$? If so, what is it, and how to derive it?

This was asked on MathSE two weeks ago and remains unanswered. As shown there, it is straightforward (via hypergeometric series properties) that for all integers $r\ge 0$ and $b\gt 1$, $$E(T_{\tt{B}})\ =\ {\Large\sum}_\limits{k=0}^\infty{(r)_k(b)_1\over (r+b)_{k+1}}(k+1)\ =\ 1+{r\over b-1},\tag{1}$$ where the Pochhammer symbols are defined as follows: $$(a)_n = \begin{cases} 1 &\text{ if }n = 0 \\ a(a+1)(a+2)\cdots (a+n-1) &\text{ if } n > 0. \end{cases}$$ However, $E(T_{\tt{BB}})$, for example, seems much less tractable: $$\begin{align}E(T_{\tt{BB}})&={\Large\sum}_\limits{j=2}^\infty{\Large\sum}_\limits{i=j-2}^\infty{(r)_i(b)_j\over (r+b)_{i+j}}\binom{i}{j-2}(i+j)\tag{2}\\[2ex] &={\Large\sum}_\limits{i=0}^\infty{\Large\sum}_\limits{j=0}^i{(r)_i(b)_{j+2}\over (r+b)_{i+j+2}}\binom{i}{j}(i+j+2)\tag{3}\\[2ex] &\overset{??}{=}\ \left(1+{r\over b-1}\right)\left(2+{r\over b-2}\right)\quad(r\ge 0,\ b\ge 3).\tag{4} \end{align}$$

Equation (4) is an unproved conjecture resulting from inspecting, for a variety of $(b,r)$ values, simulations of the urn process, as well as numerical evaluations of the double sums (2) and (3).

Answer 1

The crucial thing you need concerns exchageability properties of the Polya urn.

The following two procedures give the same law:

1. Generate a sequence of $B$s and $R$s using Polya's urn as you describe, starting from $b$ blue and $r$ red balls;
2. First randomly draw $p$ from a Beta$(b,r)$ distribution. Now, given $p$, generate an i.i.d. sequence of $B$s and $R$s in which each entry is an $B$ with probability $p$ and a $R$ with probability $1-p$.

To learn more about this, search for articles about Polya's urn mentioning "exchangeability" or "de Finetti's theorem". (In the simplest case $b=r=1$, $p$ has Uniform$[0,1]$ distribution.)

Then to get the expected occurrence time of a particular word in the Polya's urn sequence, it's enough to understand the expected occurrence time in an i.i.d. sequence with probability $p$, and then average over $p$ from the Beta$(b,r)$ distribution.

For example, given $p$, the first occurrence time of $B$ is geometric with parameter $p$, and so has mean $1/p$. Then $$ E(T_B)=\int_{p=0}^1 p^{-1} \frac{p^{b-1} (1-p)^{r-1}}{B(b,r)}dp =\frac{B(b-1,r)}{B(b,r)}=\frac{b+r-1}{b-1} $$ which agrees with your answer.

For longer words, expected occurrence times in i.i.d. sequences can be obtained in various ways, for instance via martingales (if I remember right, there is a nice treatment of this in Williams' Probability with Martingales), or recursively by conditioning on early entries in the sequence. For example, given $p$, one gets that the expected occurrence time of $BB$ is $1/p + 1/p^2$. Then \begin{align*} E(T_{BB})&= \int_{p=0}^1 (p^{-1}+p^{-2}) \frac{p^{b-1} (1-p)^{r-1}}{B(b,r)}dp \\ &=\frac{B(b-1,r)}{B(b,r)}+\frac{B(b-2,r)}{B(b,r)} \\ &=\frac{b+r-1}{b-1}+\frac{(b+r-1)(b+r-2)}{(b-1)(b-2)} \end{align*} which agrees with your conjecture.