ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let SS be a finite string of heads and tails, let ss be its total number of heads and tails, and let E(S)E(S) denote the expected number of fair-coin flips needed to produce SS. Assume

S∉{Hk,Tk}.S\notin\{\mathrm{H}^k,\mathrm{T}^k\}.

Powers-of-two conjecture. The expected value E(S)E(S) equals 2s2^s possibly plus some lower positive powers of 22; asymptotically, E(S)E(S) is about 2s2^s.

The paper proves this form of behavior for strings with at most four maximal runs or for alternating strings, and the conjecture proposes it for arbitrary ending strings. An intuitive explanation for the resulting sums of powers of 22 remains to be found.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.