Sampling with Partial Replacement

Question

Assume 1 red ball and $n$ blue balls are in a bag. We sequentially draw $n$ balls out of the bag, one ball at a time.

If we get a red ball, put it back into the bag; if we get a blue ball, don't put it back.

Calculate the expectation of blue balls we get when $n \rightarrow \infty$.

Can you prove that $\lim_{n\rightarrow \infty}\frac{\mathbb{E}[\text{Blue balls we get}]}{n} = 1$ ?

# R code for reference
    n = 1000000
    blue_no = n
    record = 0
    for(i in 1:n){
      ball = sample(blue_no + 1, 1)
      if(ball>1){
        blue_no = blue_no - 1
        record = record + 1}
    }
    print(record/n)

Answer 1

The probability the first ball is blue is $1-\frac1{n+1}$.

The probability the second ball is blue is either $1-\frac1{n+1}$, or it is $1-\frac1n$, depending on whether the first ball chosen was red or blue. But either way, the probability is at least $1-\frac1n$.

Continuing in this fashion, the probability the $k^\text{th}$ ball drawn is blue is at least $1-\frac1{n+2-k}$, for each $k\in \{1,\dots,n\}$. Using linearity of expectation, the expected number of blue balls drawn is $$ E[\text{# blue balls}]=\sum_{k=1}^nP(\text{$k^\text{th}$ ball drawn is blue})\ge \sum_{k=1}^n\left(1-\frac1{n+2-k}\right)=n-(H_{n+1}-1). $$ where $H_m$ is the $m^\text{th}$ harmonic number. Since $H_{n+1}\sim \log n$, this proves $$ \lim_{n\to\infty}\frac{E[\text{# blue balls}]}{n}\ge \lim_{n\to\infty}\frac{n-H_{n+1}+1}{n}\to 1. $$

Answer 2

Let $X_i=1$ if the $i-$th ball was blue.

Let $Z_i= \sum_{k=1}^{i-1} X_i$ (number of blue balls before $i$). Obviously, $0 \le Z_i \le i -1$, or $\frac{1}{n+1}\le \frac{1}{n+1-Z_i}\le \frac{1}{n+2-i}$

Now, $$E[X_i] =E[E [ X_i | Z_i]] = E\left[1-\frac{1}{n+1-Z_i}\right]=1-E\left[\frac{1}{n+1-Z_i}\right]\ge 1- \frac{1}{n+2-i}$$

and

$$E[Z_{n+1}] \ge n - \sum_{i=1}^n \frac{1}{n+2-i}$$

For the rest, see Mike Earnest's answer.