Flipping $n$ coins until they're all heads Suppose you have $n$ (fair) coins: You flip them until they're all heads in the following sense:
Suppose you flip all of them first and get $k$ heads. This is round $1$
You remove these heads from the board and now you flip the remaining $n- k$ heads. This is round $2$. Suppose you get $k_1$ heads.
You remove these heads and flip the remaining $n- k - k_1$ heads. This is round $3$. And so on.
Continue doing this until you've got an empty board/all the coins have reached heads.
Now there's two quantities I want to observe:

*

*Expected value of total number of flips performed from start to finish.

2. The number of rounds. In particular I want to see that with high probability the # of rounds is $\leq c \log n$ for some constant $c$ (This is the one I'm more interested in)
I sort of have an idea for 1 and am struggling with 2.
For $1$ we define $X_i = \#$ of flips coin $i$ needs to get to heads. So $\mathbb{P}[X_i = j] = 0.5(1-0.5)^{j-1} = 0.5^j$ and $\mathbb{P}[X_i \leq j] = \sum_{k = 1}^j0.5^k = 1 - 0.5^{j+1}$
Then the thing we're looking for is $X = \max X_i$ and so $\mathbb{P}[X \leq j] = (1-0.5^{j + 1})^n$ (independence).
From this finally we get that $\mathbb{P}[X = j] = (1- 0.5^{j + 1})^n - (1-0.5^j)^n$. This I think is right, but given this expression I can't find a neat way to express $\mathbb{E}[X]$. Is this the best I can hope for?
But what I'm more interested in is 2
I want to see that with high probability the number of rounds is $\leq c \log n$. I'm not sure where to begin with this one. Is it just a matter of saying that roughly every round we half the number of coins on the table and so we take $\log_2 n$ turns? Is this a way to make this more rigorous ("with high probability")
 A: Let's consider the possible outcomes for a single round where you have $n$ coins. The probability of exactly $k$ coins flipping tails is given by:
$$\dbinom{n}{k}\left(\dfrac{1}{2}\right)^n$$
Let $E[X_n]$ be the expected number of flips required for $n$ coins to be removed. We can write a recursive function:
$$\begin{align*}E[X_n] & = \sum_{k=0}^n \dbinom{n}{k}\left(\dfrac{1}{2}\right)^n(E[X_k]+1) \\ & = 1 + \sum_{k=1}^n \dbinom{n}{k}\left(\dfrac{1}{2}\right)^nE[X_k]\end{align*}$$
Solving for $E[X_n]$ gives:
$$E[X_n] = \dfrac{\displaystyle 1 + \sum_{k=1}^{n-1}\dbinom{n}{k}\left(\dfrac{1}{2}\right)^nE[X_k]}{1-\left(\dfrac{1}{2}\right)^n}$$
From this, we can start recursively looking for a pattern.
$$E[X_0] = 0 \\ E[X_1] = \dfrac{1}{\dfrac{1}{2}} = 2 \\ E[X_2] = \dfrac{1+1}{\dfrac{3}{4}} = \dfrac{8}{3} \\ E[X_3] = \dfrac{1+\dfrac{3}{8}(2)+\dfrac{3}{8}\cdot \dfrac{8}{3}}{\dfrac{7}{8}} = \dfrac{22}{7} \\ E[X_4] = \dfrac{1+\dfrac{4}{16}(2)+\dfrac{6}{16}\cdot \dfrac{8}{3}+\dfrac{4}{16}\cdot \dfrac{22}{7}}{\dfrac{15}{16}} = \dfrac{368}{105} \\ E[X_5] = \dfrac{1+\dfrac{5}{32}(2)+\dfrac{10}{32}\cdot \dfrac{8}{3}+\dfrac{10}{32}\cdot \dfrac{22}{7}+\dfrac{5}{32}\cdot \dfrac{368}{105}}{\dfrac{31}{32}} = \dfrac{2470}{651} \\ E[X_6] = \dfrac{7880}{1953} \\ E[X_7] = \dfrac{150266}{35433}$$
I'm not seeing an easy to spot pattern, but here are links to the OEIS database for the numerators of this sequence and denominators of this sequence.
A: I think it is better to use recursion to attack both questions.  I will let $f(n)$ denote the expected number of flips, and $g(n)$ denote the expected number of rounds of flips.
Then, $f(1) = (1/2) + (1/2)[f(1) + 1] \implies f(1) = 2.$
The idea is that $(1/2)$ the time, you will be in the same position as at the start, but with one extra flip.
Similarly,
Then, $g(1) = (1/2) + (1/2)[g(1) + 1] \implies g(1) = 2.$

At this point, my (Probability-Theory ignorant) crude approach will simply be to examine the data for $f(n),g(n)$, for $n \in \{2,3,4\}$.
Then, I will use the data to form a hypothesis, and then prove the hypothesis.
So, $f(2) = (1/4)[2] + (1/2)[2 + f(1)] + (1/4)[2 + f(2)] \implies $
$f(2) = (1/2) + (1/2)(4) + (1/2) + (1/4)f(2) \implies $
$(3/4)f(2) = 3 \implies f(2) = 4.$
At this point, it is reasonable to shortcut the formation of a hypothesis around $f(n)$ because you can visualize the expectation for $n$ coins to be sum of the expectations for each coin.
That is, when computing the expectation of each coin, it is irrelevant whether the coins are processed together.  Coins don't speak to each other.  For each individual coin, $f(1) = 2$ represents the number of coin flips that that particular coin will require.
Therefore, you must have that $f(n) = 2n$.

$g(1) = 2.$
So, $g(2) = (1/4)[1] + (1/2)[1 + g(1)] + (1/4)[1 + g(2)] \implies $
$g(2) = 1 + (1/2)(2) + (1/4)g(2) \implies $
$(3/4)g(2) = 2 \implies g(2) = (8/3).$

$g(3) = (1/8)[1] + (3/8)[1 + g(1)] + (3/8)[1 + g(2)] + (1/8)[1 + g(3)] \implies $
$g(3) = 1 + (3/8)(2) + (3/8)(8/3) + (1/8)g(3) \implies $
$(7/8)g(3) = (11/4) \implies g(3) = (22/7).$

Rather than speculate on a hypothesis, it seems worth it to manually pursue $g(4)$.
$g(4) = (1/16)[1] + (4/16)[1 + g(1)] + (6/16)[1 + g(2)] + (4/16)[1 + g(3)] + (1/16)[1 + g(4)]\implies $
$\displaystyle (15/16)g(4) = \frac{368}{7 \times 16}.$
At this point, I despair in finding an obvious pattern.  It is not counter-intuitive that (like Bernoulli numbers), the expression for $g(n)$ is recursive rather than closed form.
So,
$$g(n) = \frac{1}{2^n} + \sum_{k=1}^n \left\{ ~\left[\frac{\binom{n}{k}}{2^n}\right] \times [1 + g(k)] ~\right\}.$$
