A nonlinear polya urn model

130 Views Asked by At

We have $b$ black balls and $w$ white balls at time $t$. At the time $t+1$, we generate two uniformly distributed random variables $X,Y$ in $[0,1]$. If $bX \ge wY$, we add a black ball; otherwise, we add a white ball.

It is easy to get when $b<w$, $\Pr[\text{win a black ball}] = \frac{b}{2w}$, and $\Pr[\text{win a white ball}] = 1 - \frac{b}{2w}$

Take an example, when $b=w$, we win a black ball with probability $\frac{1}{2}$. It is slightly different from the classical Polya urn model. I compare these two in the following figure. enter image description here

Is there a way we can acquire the distribution of the number of black balls after n rounds?

Lets say $\{X_1,X_2...X_n\}$, $X_{i} \in \{0,1\}$ is the sequence of winner. This question looks so similar to the Polya urn model. But the difference is that the sequence in this problem is not exchangeable. So I get stuck here.

Then I found Nonlinear Polya Urn process. The author uses exponential embedding. I think it's probably what I need but here I can not split $\frac{b}{2w}$ into two i.i.d. exponential r.v.

I don't know what should I try now. Any advice?

==============Previous question==========

Consider a nonlinear Polya urn model: We have $b$ black balls and $w$ white balls at time $t$. At the time $t+1$, we draw an additional black ball with probability $\Pr[b,w] = \frac{b}{2w}$ and draw a white ball with probability $1 - \frac{b}{2w}$.

Is there a way we can acquire the distribution of the number of black balls after the n-th draw?