Skip to main content
Post Undeleted by ofer zeitouni
added 12 characters in body
Source Link
ofer zeitouni
  • 7.5k
  • 1
  • 22
  • 38

This is related to the coupon collector problem. Let $T_i$ be a geometric variable with parameter $1-i/n$, so that $ET_i=1/(1-(i-1)/n)$. You are asking about $K=\min\{k:\sum_{i=1}^k T_i>n\}.$ Since $E \sum_{i=1}^k T_i=n(1/n+1/(n-1)+...+1/(k-1))\sim n\log (n/k)$$E \sum_{i=1}^k T_i=n(1/n+1/(n-1)+...+1/(n-k+1))\sim n\log (n/n-k+1)$, we get from concentration that $\log n/K\sim 1$$\log (n/(n-K))\sim 1$, i.e $K\sim n/e$$n-K\sim n/e$. But $E_n=E(n-K+1)/n\sim 1-1/e$$E_n=E(n-K+1)/n\sim 1/e$.

This is related to the coupon collector problem. Let $T_i$ be a geometric variable with parameter $1-i/n$, so that $ET_i=1/(1-(i-1)/n)$. You are asking about $K=\min\{k:\sum_{i=1}^k T_i>n\}.$ Since $E \sum_{i=1}^k T_i=n(1/n+1/(n-1)+...+1/(k-1))\sim n\log (n/k)$, we get from concentration that $\log n/K\sim 1$, i.e $K\sim n/e$. But $E_n=E(n-K+1)/n\sim 1-1/e$.

This is related to the coupon collector problem. Let $T_i$ be a geometric variable with parameter $1-i/n$, so that $ET_i=1/(1-(i-1)/n)$. You are asking about $K=\min\{k:\sum_{i=1}^k T_i>n\}.$ Since $E \sum_{i=1}^k T_i=n(1/n+1/(n-1)+...+1/(n-k+1))\sim n\log (n/n-k+1)$, we get from concentration that $\log (n/(n-K))\sim 1$, i.e $n-K\sim n/e$. But $E_n=E(n-K+1)/n\sim 1/e$.

Post Deleted by ofer zeitouni
Source Link
ofer zeitouni
  • 7.5k
  • 1
  • 22
  • 38

This is related to the coupon collector problem. Let $T_i$ be a geometric variable with parameter $1-i/n$, so that $ET_i=1/(1-(i-1)/n)$. You are asking about $K=\min\{k:\sum_{i=1}^k T_i>n\}.$ Since $E \sum_{i=1}^k T_i=n(1/n+1/(n-1)+...+1/(k-1))\sim n\log (n/k)$, we get from concentration that $\log n/K\sim 1$, i.e $K\sim n/e$. But $E_n=E(n-K+1)/n\sim 1-1/e$.