Expected time to pick up n things when I can drop them each round?

Question

Why Can't I Hold All These Limes?

Suppose I wanted to hold $n$ limes. Each time step, I pick up a lime. But limes are hard to hold, so I also have a probability $p$ to drop a lime on each step which depends on how many limes I am holding. I may drop more than one lime on each time step, but the limes will drop independently.

How long should I expect to be picking up limes before I am holding all $n$?

I'm not exactly sure how to be rigorous here, but I suppose that if $E(t)$ is my expected number of limes at time $t$, then I am asking for a solution to $E(t) = n$ in terms of $p$.

Hints, instead of full solutions, are very welcome.

Answer 1

Hint: You can come up with a recurrence for the expected waiting time assuming you have $m$ limes, in terms of the expected waiting time when you have $m' < m$ limes for all $m'$. $E(t) = n$ will not have a finite solution for the expected number of limes held at time $t$ because at any point in time there is always a chance you will have less than $n$ limes. Also that is not quite the right set up to solve the problem.

Answer 2

This can be solved numerically as a Markov Chain with an absorbing state (all limes picked). Assuming that at each step one has $0<x_t<n$ limes, and a number of those limes are dropped (according to a Binomial with $p=g(x)$) and a lime is picked (and hence one is always holding at least one lime), an example for $n=6$ and $p = x/24$ (arbitrary), one can construct the transition matrix as

n=6   % total number of limes
px = [1:n]/(n*4)  % probabilites of dropping each lime, as a function of the number of holded limes 
P=eye(n); % transition matrix
for n1=1:n-1 ; 
   for n2=1:n1+1;
      d = n1+1-n2; % dropped
      P(n1,n2)= px(n1)^d * (1-px(n1))^(n1-d)*nchoosek(n1,d); % binomial
   endfor
endfor

which gives

px =
  0.04166   0.08333   0.12500   0.16666   0.20833   0.25000
P=
  0.04167   0.95833   0.00000   0.00000   0.00000   0.00000
  0.00694   0.15278   0.84028   0.00000   0.00000   0.00000
  0.00195   0.04102   0.28711   0.66992   0.00000   0.00000
  0.00077   0.01543   0.11574   0.38580   0.48225   0.00000
  0.00039   0.00746   0.05667   0.21535   0.40916   0.31097
  0.00000   0.00000   0.00000   0.00000   0.00000   1.00000

And then the mean time to reach the absorbing state is given by

m=n-1;
Q = P(1:m,1:m); % transient submatrix
N=inv(eye(m)-Q);
N*ones(m,1)   % mean time starting from given limes

ans =
   12.2256
   11.1821
    9.9834
    8.4107
    5.8649

Hence, starting from 1 lime one has to wait for $12.2$ steps in average ($13.2$ if starting with no limes).