If you look at the probabilities of needing more than $2n$ tosses when $p=\frac12$, this suggests you get an expectation of $$\sum_{n=0}^\infty 2^{a(n)-n}$$ where $a(n)$ is the number of $1$s in the binary representation of $n$, OEIS A000120.
This is $$2^{0-0}+2^{1-1}+2^{1-2}+2^{2-3}+2^{1-4}+2^{2-5}+2^{2-6}+2^{3-7}+2^{1-8}+\cdots \\ \,\\ \approx 3.40147099057$$
which is also $\sum\limits_{n=0}^\infty \frac{1}{b(n)}$ where $b(n)$ is the largest power of $2$ that divides $n!$, OEIS A060818
but I do not see an obvious closed form.
Investigating further, this improvement of about $0.5985$, compared with the expectation of $4$ tosses from the traditional procedure you describe, turns out to be the best improvement from the traditional expectation of $\frac{1}{p(1-p)}$.
As the coin becomes more biased, the improvement of your method reduces towards $0.5$.
Here is some R code calculating the expectation:
expectedrounds <- function(p){
q <- 1 - p
maxrounds <- 2 ^ ceiling(log(40 / -log(max(p,q), 2), 2))
unresolvedH <- 0
probresolved <- numeric(maxrounds)
for (round in 1:maxrounds){
potential <- c(unresolvedH, unresolvedH + 1)
resolvedH <- potential[duplicated(potential)]
probresolved[round] <- sum(2 * p^resolvedH * q^(round - resolvedH))
unresolvedH <- potential[! potential %in% resolvedH]
}
expectedrounds <- sum(probresolved * (1:maxrounds)) +
sum(p^unresolvedH * q^(round - unresolvedH)) * (maxrounds + 1/p/q)
return(expectedrounds)
}
giving for example
> expectedrounds(0.5)
[1] 3.401471
The number of expected rounds for some different probabilities of heads are:
probability Heads expectedrounds traditional improvement
0.5 3.4014710 4.0000000 0.5985290
0.49 or 0.51 3.4031325 4.0016006 0.5984681
0.4 or 0.6 3.5741042 4.1666667 0.5925625
0.25 or 0.75 4.7684595 5.3333333 0.5648738
0.1 or 0.9 10.5851114 11.1111111 0.5259997
0.01 or 0.99 100.5075887 101.0101010 0.5025123
0.001 or 0.999 1000.5007509 1001.0010010 0.5002501
By constant you mean nonrandom ? If there is a deterministic bound $n$ on the number of flips you need, then your coin is a random variable $X$ defined on $\{0,1\}^n$ and necessarily $p = P(X=1) = 2^{-n} \mathrm{Card}\{\omega \in \{0,1\}^n, X(\omega) = 1\}$ is a multiple of $2^{-n}$ so the binary representation terminates.
Regarding your randomized algorithm, when $p$ is non-dyadic it is optimal in expectation as explained by Lumbroso in appendix B of this paper https://arxiv.org/pdf/1304.1916.pdf (Lumbroso makes a small mistake : his computation does not work when $p$ is dyadic in which case you can stop the procedure after $2^{-n}$ steps for a small gain.
His optimality bound comes from the wonderful results of Knuth and Yao about the optimal generation of general discrete random variables from coin tosses (which they call DDG trees). I put the reference below, you can find it on libgen, it is a real gem and a great read. Lumbroso's paper also describes a neat optimal way do generate discrete uniform variables.
If you want many independent samples of your biased coin, you can get a performance boost up to $H(p) = p \log(1/p) + (1-p)\log(1/(1-p))$ expected bits per sample by reusing randomness from one sample to the next. https://arxiv.org/pdf/1502.02539.pdf $H(p)$ is the Shannon entropy of the distribution and is a hard lower bound. Lumbroso also does this in his paper for the discrete uniform case.
Knuth, Donald E.; Yao, Andrew C., The complexity of nonuniform random number generation, Algorithms and Complexity, Proc. Symp., Pittsburgh 1976, 357-428 (1976). ZBL0395.65004.
Best Answer
Based on your comments, I would suggest revising the concepts of expectation values before attempting this question. Nevertheless, I have provided a solution below with some references and definitions to guide you towards the correct path. I haven't provided the explanation for everything so that you spend some time understanding the concepts and finally figure it out on your own(if you need some more explanation or are stuck somewhere, please reach out via the comment section). Hope it helps.