Spoiler for It seems to me...that for each digit in the binary representation, if your coin flip is not the outcome representing the digit, you stop. So 50% chance of needing another coin flip at any point in the process.
So there's a 50% chance of it taking only 1 flip.
There's a 25% chance of it taking 2 flips.
There's a 12.5% chance of it taking 3 flips.
So the infinite sum for the average flips needed is the sum from i=1 to infinity of i/(2^i).
f(y) = sum x=1 to inf xy^-x
f(y)/y = sum x=1 to inf xy^-(x+1)
integrate (f(y)/y) + c = sum x=1 to inf -y^-x
-integrate (f(y)/y) + c = (1/y)/(1-(1/y))
-integrate (f(y)/y) + c = (1/y)/((y-1)/y)
-integrate (f(y)/y) + c = 1/(y-1)
integrate (f(y)/y) + c = -1/(y-1)
f(y)/y = d(-1/(y-1))/dy
f(y)/y = d(-(y-1)^-1)/dy
f(y)/y = (y-1)^-2
f(y) = y(y-1)^-2
Plugging in 2 for y gives f(y)=2.
So it takes 2 flips on average.
Of course, it would be easier to formulate it this way...
All need at least 1 flip.
50% need at least an additional 1 flip.
25% need at least an additional 1 flip.
So 1 + .5 + .25 + .125 + ... = 2.
Great solve. It is indeed surprising how efficient bonanova's and your algorithm is.