How to win Matt Parker's jackpot - finding the median of the following distribution

The probability to get $10$ consecutive switch flips can be modelled as a Markov chain, with the states corresponding to the number of consecutive switch flips in the immediate past. The state in which $10$ consecutive switch flips have been encountered is absorbing. The stationary distribution with eigenvalue $1$ has probability $1$ at this absorbing state. There is a quasi-stationary distribution in which each state has half the probability of the one with one less switch flip and probability "leaks out" into the absorbing state at a rate of roughly $2^{-10}$. The median is the least integer $a$ for which $\textsf P(X\le a)\gt\frac12$. The time it takes for $\frac12$ to leak out is roughly given by $a\cdot2^{-10}=\log2$, or $a=2^{10}\log2\approx 710$.

Here's Java code that follows the evolution of the distribution of the process until the probability for $10$ switch flips exceeds $\frac12$. The median turns out to be $712$. The precision of the above estimate is in part gratuitous, since the process takes $10$ steps to equilibrate before probability starts leaking into the absorbing state. Nevertheless, the agreement shows that the quasi-stationary model is quite good, so $P(X\le x)\approx1-\left(1-2^{-10}\right)^t\approx1-\mathrm e^{-2^{-10}t}$ should be a good approximation.

Regarding the game-theoretic aspect of the problem, this is related to the ice-cream vendor problem, where the flip numbers are mapped to the beach using the cumulative distribution function $P(X\le x)$. However, the conclusion in the continuous case that there is no equilibrium for $3$ players doesn't go through in the discrete case.

Let $a^k_{n}$ denote the number of zero-one sequences of length $n$ with longest zero run non-exceeding $k$, and $a^k_{n,m}$ denote the number of such sequences with $m$ trailing zeros, $m=0,\dots,k$.

Then $$ a^{k}_{n,m} = a^{k}_{n-m,0},\ m = 1,\dots,k, n\ge m, $$ and $a^k_{n,0} = a^k_{n-1}$, $n\ge 0$. Therefore, $$ a_n^k = \sum_{m=0}^k a^k_{n,m} = a^k_{n-1} + \sum_{m=1}^{k} a^k_{n-m,0} = \sum_{j=1}^{k+1} a^k_{n-j} \tag{1} $$ for $n\ge k+1$. (In other words, take a sequence and remove all trailing zeroes and preceding one; you'll end up with a sequence whose longest zero run does not exceed $k$.)

The initial values are $a_n^k = 2^n, n\le k$. Therefore, it easy to see that the generating function $A^k(z) = \sum_{n=0}^\infty a_n^k z^n$ is equal to $$ A^k(z) = \frac{\sum_{j=0}^k z^j}{1-\sum_{j=1}^{k+1} z^j} = \frac{1-z^{k+1}}{1-2z+z^{k+2}}. $$

Writing the partial fraction expansion for $A^k(z)$, it is possible to derive an explicit formula for $a_n^k$.

Now, denoting $T_m$ the number of throws to get $m$ heads, we have $$ P(T_m>n) = \frac{1}{2^n}P(\text{at most $m-1$ consecutive heads in the first $n$ throws}) = \frac{a^{m-1}_n}{2^n}. $$

However, for $m=9$ (which corresponds to $10$ alternating flips, as you've explained) there is nothing very exciting, as the roots can be computed only approximately. Nevertheless, using the recurrent formula (1) gives an efficient way to compute the required number of sequences.

A good rough approximation is $a_n^{8} \sim C_\tau \tau^{-n-1}$, where $\tau = 0.500493118286\dots$ is the unique positive root of the polynomial $f(\tau) = \sum_{j=1}^{9}z^{j} -1$ (alternatively, the root of $z^{10}-2z+1$ inside $(0,1)$), and $$ C_\tau = \frac{\sum_{j=0}^{8} \tau^j}{f'(\tau)} = 0.503980275733\dots $$ Indeed, since $A^8(z)$ is rational, and $f$ does not have double roots, it has a partial fraction expansion $A^8(z) = \sum_{\zeta: f(\zeta) = 0} \frac{C_\zeta}{\zeta - z}$. Therefore, the sequence is of the form $a_n^8 = \sum_{\zeta: f(\zeta) = 0} C_\zeta \zeta^{-n-1}$. In particular, since $\tau$ is the root with the smallest absolute value, $a_n^8\sim C_\tau \tau^{-n-1}$. Moreover, the norms of other roots are bigger than $1.11$, so the relative error of this approximation is of order $r^{-n}$ with $r>2$. This is especially good for our problem, since we will be interested with very large values of $n$.

So the probability we need is approximately $$ P(T_9>n)\sim \frac{C_\tau}{\tau (2\tau)^n}, $$ and this is very sharp (up to some exponentially small relative error). In order to find the median, one should find the smallest $n$ such that $P(T_9>n)< 1/2$. This gives the value $$n= \lceil- \log(4C_\tau)/\log(2\tau)\rceil-1 = 711$$ for the median, which agrees with joriki's calculations.