0
$\begingroup$

Suppose there are $N$ balls in an urn, with $X$ white balls and $N-X$ black balls. We perform $k$ iterations of the following process:

  1. Choose a random ball form the urn.
  2. If the ball is white, we put it back with an additional white ball and discard a black ball.
  3. If the ball is black, we simply put it back.
  4. When there are no more black balls, we will always pick white balls. We then return the chosen white ball with an additional white ball as done previously. At this stage, the number of balls increases by $1$ with each iteration.

Denote by $\bar{S}$ the average number of white balls after $k$ iterations, and by $\bar{k}$ the average number of iterations required to have $S$ white balls in the end.

Why is the number of white balls after $\bar{k}$ iterations not equal to $\bar{S}$?


Additional info

The number of iterations it takes on average to fill the urn with $N$ white balls is given here, and is $$N\cdot (H_{N-1} - H_{X-1})$$ where $H_n$ is the $n^{th}$ harmonic number.

I know that the number of white balls after $\bar{k}$ iterations is not equal to $\bar{S}$ through simulations I did in Matlab. Code included below:

% How many iterations to get S white balls?

% Initialise variables
X = 1;              
N = 100;
k = 0;              
urn = zeros(1,N);
% Let 1 = white ball, 0 = black ball.
urn(1:X) = 1;
nSims = 30000;      % nSims is the number of simulations that we average over

% Begin simulations
ksum = 0;
for i = 1:nSims
    X = 1;
    k = 0; 
    urn = zeros(1,N);
    urn(1:X) = 1;
    while(sum(urn) < N) % iterates when there are still black balls
        choose = urn(randi(N)); % choose an element of the urn
        if choose == 1
            X = X + 1;
            urn(1:X) = 1;
        end
        k = k+1;
    end
    ksum = ksum + k;
end
kavg = ksum/nSims;

fprintf("It took %.3f iterations to fill up the urn with %d white balls on " + ...
    "average.\n",kavg,N)
% How many white balls after k iterations?

% Initialise variables
N = 100;
nSims = 30000;
% msum is the total sum of no. of white balls after S iterations
S_sum = 0;
% K is the number iterations
K = 517;
% Begin simulations
for i = 1:nSims
    X = 1;
    urn = zeros(1,N);
    % Let 1 = white ball, 0 = black ball.
    urn(1:X) = 1;
    for k = 1:K
        choose = urn(randi(N)); % choose an element of the urn
        if choose == 1
            X = X + 1;
            urn(1:X) = 1;
        end
    end
    S_sum = S_sum + X;
end
Savg = S_sum/nSims;
fprintf("There were %.3f white balls on average in %d trials. \n",Savg,K)
```
$\endgroup$
6
  • $\begingroup$ This is a direct consequence of Jensen's Inequality or, almost equivalently, of the AM-HM inequality. $\endgroup$
    – whuber
    Jan 25 at 23:30
  • $\begingroup$ Could you please elaborate on that? I am aware of the AM-HM inequality, but I do not understand how to fit this problem into that context. Thank you for the help. $\endgroup$ Jan 26 at 11:36
  • $\begingroup$ Would I be able to use the number of iterations required to calculate the number of white balls at the end? $\endgroup$ Jan 26 at 11:38
  • $\begingroup$ Working through a simple example with tiny numbers should make this purely arithmetical phenomenon apparent. $\endgroup$
    – whuber
    Jan 26 at 15:24
  • $\begingroup$ Sorry, but it is not obvious to me, since the error vanishes for large values of $S$ and $k$ compared to $N$. For example, let $N=100,X=1$. Then it takes $\hat{k} \approx 517$ iterations to have $S=100$ balls at the end. Now, with $N=100,X=1$, if we iterate $k=517$ times, we have $\hat{S} \approx 124.5$ white balls on average at the end. But if $N=100,X=1$, it takes $\hat{k} \approx 1017$ iterations to fill the balls with 600 white balls, and if we iterate $k = 1017$ times, there are $\approx 600$ balls at the end. $\endgroup$ Jan 26 at 20:43

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.