Expected number of rounds Assume that we have a bucket containing $n$ different balls. At each round we choose at random a subset of the remaining balls, and remove them from the bucket. We keep doing this until the bucket gets empty. What is the expected number of rounds?
I tried to find the distribution of the number of rounds $m$:
for $m = 1$ the probability is $1/2^{n}$.
for $m = 2$ the probability is $1/2^{n} - 1/2^{2n}$.
But for bigger number of rounds it gets complicated. Is there other way to find the expected number of rounds or at least estimate it?
 A: When you choose a random subset of the balls in the tub, each ball has $\frac 12$ chance to be in that subset.
A: Completely revised.
Let $E_n$ be the expected number of rounds when starting with $n$ balls. Clearly $E_0=0$. For $n>0$ we must have
$$\begin{align*}
E_n&=\frac1{2^n}+\frac1{2^n}\sum_{k=1}^n\binom{n}k(E_k+1)\\
&=1+\frac1{2^n}\sum_{k=1}^n\binom{n}kE_k
\end{align*}$$
and hence
$$(2^n-1)E_n=2^n+\sum_{k=1}^{n-1}\binom{n}kE_k\;.$$
Thus, by straightforward calculation we find that $E_1=2$, $E_2=\frac83$, $E_3=\frac{22}7$, and $E_4=\frac{368}{105}$. 
Checking OEIS for the sequence $\langle 2,8,22,368\rangle$ of numerators, we get one hit, OEIS A158466. This is described as:

Numerators of $EH(n)$, the expected value of the height of a probabilistic skip list with $n$ elements and $p=1/2$

This doesn’t convey anything to me, but the following comment by Geoffrey Critzer does:

$n$ fair coins are flipped in a single toss. Those that show tails are collected and reflipped in another single toss. The process is repeated until all the coins show heads. $H(n)$ is the discrete random variable that denotes the number of tosses required. $\Bbb P\big(H(n)\le k\big) = \left(1-(1/2)^k\right)^n$.

This is clearly the balls and bucket problem in a slightly different guise. The entry goes on to note that
$$\begin{align*}
EH(n)&=\sum_{k>0}k\left(\left(1-\left(\frac12\right)^k\right)^n-\left(1-\left(\frac12\right)^{k-1}\right)^n\right)\\
&=-\sum_{k=1}^n(-1)^k\frac{\binom{n}k}{1-\left(\frac12\right)^k}
\end{align*}$$
but gives no closed form. As a quick check, the last formula gives
$$E_3=\frac3{\frac12}-\frac3{\frac34}+\frac1{\frac78}=6-4+\frac87=\frac{22}7\;.$$
A: Premise revised
If the choice of the balls to extract is done on a yes/no basis, than it corresponds to the "coins re-flipping" mechanism introduced in the other reply. Then the number of balls extracted is not uniformly distributed.
If the choice instead is just on the number of balls to extract, a uniform random value from 1 to the number of balls remaining, then:  

The number of different runs that make the box empty clearly corresponds to the No. of Compositions of $n$ into exactly $m$ parts, which is $\left( \matrix{
  n - 1 \cr  m - 1 \cr}  \right)$, and when summed over $m$ gives the total of $2^{\,n - 1} $.
Re.: https://en.wikipedia.org/wiki/Composition_%28combinatorics%29
So the probability of a $m$-run is $$
\left( \matrix{
  n - 1 \cr 
  m - 1 \cr}  \right)/2^{\,n - 1} 
$$
and the expected value of m is therefore:
$$
\eqalign{
  & E(m)\quad \left| {\;1 \le n} \right.\quad  = {1 \over {2^{\,n - 1} }}\sum\limits_{1\; \le \,m\, \le \,n} {m\left( \matrix{
  n - 1 \cr 
  m - 1 \cr}  \right)}  =   \cr 
  &  = {1 \over {2^{\,n - 1} }}\sum\limits_{1\; \le \,m\, \le \,n} {\left( {\left( {m - 1} \right)\left( \matrix{
  n - 1 \cr 
  m - 1 \cr}  \right) + \left( \matrix{
  n - 1 \cr 
  m - 1 \cr}  \right)} \right)}  =   \cr 
  &  = {1 \over {2^{\,n - 1} }}\left( {2^{\,n - 1}  + \left( {n - 1} \right)\sum\limits_{2\; \le \,m\, \le \,n} {\left( \matrix{
  n - 2 \cr 
  m - 2 \cr}  \right)} } \right) =   \cr 
  &  = {1 \over {2^{\,n - 1} }}\left( {2^{\,n - 1}  + \left( {n - 1} \right)2^{\,n - 2} } \right) = 1 + {{n - 1} \over 2} \cr} 
$$
A: I am using Did's and Ross' interpretation.
For $m=2$, the probability is $$\left(\frac34\right)^n-\left(\frac12\right)^n$$
The first term is the probability that all $n$ coins have been chosen, and the second term is probability that $m\leq1$.  In the same way, the probability that $m=3$ is $$\left(\frac78\right)^n-\left(\frac34\right)^n$$
