Coin flips and substrings.

I ran across a fun question: Given a set of conditions regarding a sequence of coin flips $S$, what’s the “best” subsequence of coin flips $b$ to choose to maximize profits (assuming you get paid out for each occurrence of $b$, which can overlap, within $S$).

The first question is whether any decision strategy first-order stochastically dominates all the other strategies. A quick calculation using indicator variables shows that this is not the case.

This is when things start to get a bit more interesting. How do these distributions look? And how many distinct strategies are there? To explore these questions, I wrote up a Jupyter notebook looking into it. Take a look here!

Addenda.

NB: The original context of betting and payoff strategies suggests that one should look at some measure of expected utility from the payoff. But if we’re using an expected utility framework, the utility curves of the payoff $U(P)$ would be relatively simple transformations of $P$ itself, so I focused on the distributions of $P$.

NB2: This setup is an isomorphism of looking at binary strings and substrings – hence this post’s title.