## You have a bucket that initially contains n red balls and n blue
## balls.
##
## At each round, you draw a ball at random and flip a coin.
##
## Then, depending on what color ball you drew, and what the result of
## the coin toss was, you do the following:
##
## Red ball, head: replace the ball you drew with a blue ball
## Red ball, tail: replace the ball you drew with two red balls
## Blue ball, head: remove the blue ball and replace it with nothing
## Blue ball, tail: return the blue ball to the bucket
##
## Use simulation to estimate the probability that the bucket becomes
## empty before it contains 20 balls.



## Number of simulation replications.
nrep = 1e3

## Initial number of red and blue balls.
n = 10


##
## Version 1: use an array to represent the urn.
##

## Store the results of each replication.
T1 = NULL

for (k in 1:nrep) {

    ## Initial configuration of the urn.  Use 1 to denote blue and 0
    ## to denote red.
    U = array(0, 2*n)
    U[(n+1):(2*n)] = 1

    j = 0
    while (TRUE) {

        ## Keep track of the number of turns.
        j = j+1

        ## Draw from a random position in the urn.
        ii = ceiling(runif(1, max=length(U)))

        ## The coin flip (1=head, 0=tail).
        coin = ceiling(runif(1, max=2))

        ## A blue ball was drawn.
        if (U[ii] == 1) {
            if (coin == 1) { U = U[-ii] }  ## remove the blue ball            
        } 

        ## A red ball was drawn.
        else {
            if (coin == 1) { U[ii] = 1 } ## Replace red with blue.
            else { U = c(U[-ii], 0, 0) }
        }

        if ((length(U) == 0) | (length(U) >= 20)) { break }
    }

    T1[k] = 1*(length(U) == 0)
}



##
## Version 2: keep track only of the red/blue totals.
##

## Store the results of each replication.
T2 = NULL

for (k in 1:nrep) {

    ## Initial configuration of the urn.
    nred = n
    nblue = n

    while (TRUE) {

        ## The coin flip (1=head, 0=tail).
        coin = ceiling(runif(1, max=2))

        ## A blue ball was drawn.
        if (runif(1) < nblue/(nred+nblue)) {
            if (coin == 1) { nblue = nblue-1 }  ## remove the blue ball
        }

        ## A red ball was drawn.
        else {
            if (coin == 1) { 
                nred = nred-1
                nblue = nblue+1
            }
            else { nred = nred+1 }
        }

        ntot = nred + nblue
        if ((ntot == 0) | (ntot >= 20)) { break }
    }

    T2[k] = 1*(ntot == 0)
}