Return to Answer

At every step, it is optimal to bet your entire fortune on either heads or tails. One optimal strategy is thus to alternately guess heads and tails and always bet your entire fortune. The resulting expected value is $2^n$ times the probability that indeed the coins alternate heads and tails. I can not find a formula for the answer, but I calculated the following values with dynamic programming.

\begin{array}{c|c|c} n&E=&E\approx \\ \hline 2&2&2.00000\ldots \\ 3&4/3&1.33333\ldots \\ 4&40/27&1.48148\ldots \\ 5&13/10&1.30000\ldots \\ 6&4304/3125&1.37728\ldots \\ 7&3632/2835&1.28112\ldots \\ 8&5488768/4117715&1.33296\ldots \\ 9&13651/10752&1.26962\ldots \\ 10&394291456/301327047&1.30851\ldots \\ 100&&1.23219\ldots \\ 200&&1.22844\ldots \\ 300&&1.22720\ldots \\ 400&&1.22658\ldots \\ 500&&1.22621\ldots \\ 1000&&1.22548\ldots \\ 2000&&1.22511\ldots \\ 3000&&1.22498\ldots \\ \end{array}

To prove my claim, for $f_1,\ldots,f_k\in\{H,T\}$ let $E(f_1,\ldots,f_k)$ be the maximum possible expected value if the first $k$ coin flips have outcome $f_1,\ldots,f_k$ and we have $1$ dollar at that point. Let $p$ be the probability that, given the first $k$ coin flips are $f_1,\ldots,f_k$, the next coin flip is $H$.

Betting $x$ dollars on $H$ has outcome \begin{align*} &p(1+x)E(f_1,\ldots,f_k,H)+(1-p)(1-x)E(f_1,\ldots,f_k,T) \\&=pE(f_1,\ldots,f_k,H)+(1-p)E(f_1,\ldots,f_k,T)\\&+x[pE(f_1,\ldots,f_k,H)-(1-p)E(f_1,\ldots,f_k,T)], \end{align*} while betting $x$ dollars on $T$ has outcome \begin{align*} &p(1-x)E(f_1,\ldots,f_k,H)+(1-p)(1+x)E(f_1,\ldots,f_k,T) \\&=pE(f_1,\ldots,f_k,H)+(1-p)E(f_1,\ldots,f_k,T)\\&-x[pE(f_1,\ldots,f_k,H)-(1-p)E(f_1,\ldots,f_k,T)]. \end{align*} It is thus optimal to choose $x$ as large as possible, such that you bet your entire fortune, while betting on $H$ if $pE(f_1,\ldots,f_k,H)-(1-p)E(f_1,\ldots,f_k,T)$ is positive and betting on $T$ otherwise.

This strategy has the consequence that your choices do not matter anymore as soon as you made a wrong guess. You thus might as well predetermine the entire sequence of heads and tails that you want to guess. Then you either win $2^n$ if your sequence was correct, or you are left with $0$ otherwise. The expected value is thus $2^n$ times the probability your sequence is correct. We thus want to optimize the probability that your sequence is correct.

I interpret the fact that Nate is not sure which coin is which as the permutation of coins being uniformly random. Then the probability that your sequence is correct is independent of its permutation, so we only need to consider how many heads and tails you guess.

We have the following probability generating function for the number of heads occurrences. $$\prod_{i=0}^{n-1}\left(\frac{i}{n-1}x+\frac{n-1-i}{n-1}\right)$$ I expanded this product with dynamic programming and took the largest coefficient times $2^n$ to obtain the answers in the table. This largest coefficient was always at the median, meaning $\lfloor n/2\rfloor$ and $\lceil n/2\rceil$, though a simple proof that this must always hold currently eludes me. This corresponds to the strategy of alternating heads and tails.

As a final note, I am interested if anyone can determine if the optimal value converges as $n$ tends to infinity. Numerically, it appears the sequence is decreasing for $n$ even and for $n$ odd separately. The difference between $n$ even and $n$ odd seems to converge to $0$. The sequence does not appear to converge to $1$ however. If I had to take a guess I would go with $11/9$, but this is only based on numeric observation.

EDIT The limit is $\sqrt{3/2}=1.22474\ldots$. I give an incomplete argument for $2n$ coins. Then the generating function for number of $H$ minus number of $T$ is $$\prod_{i=0}^{2n-1}\left(\frac{i}{2n-1}x+\left(1-\frac{i}{2n-1}\right)x^{-1}\right)=\prod_{i=0}^{n-1}\left(\frac{i}{2n-1}x+\left(1-\frac{i}{2n-1}\right)x^{-1}\right)\left(\left(1-\frac{i}{2n-1}\right)x+\frac{i}{2n-1}x^{-1}\right)=\prod_{i=0}^{n-1}\left(\frac{i}{2n-1}\left(1-\frac{i}{2n-1}\right)(x+x^{-1})+1-2\frac{i}{2n-1}\left(1-\frac{i}{2n-1}\right)\right)$$ For $a_i=\frac{i}{2n-1}\left(1-\frac{i}{2n-1}\right)$ we can consider this as a random walk starting in $0$ and for each $i=0,\ldots,n-1$ there is an $a_i$ probability of walking left and an $a_i$ probability of walking right and a $1-2a_i$ probability of staying. Then the expected total number of steps is $$\sum_{i=0}^{n-1}2a_i\sim2n\int_0^1\frac{x}{2}\left(1-\frac{x}{2}\right)dx=\frac13n.$$ There is a probability of $\frac12$ that the number of steps is even, which is necessary and sufficient for it to be possible to end at $0$. If the number of steps is $2k$ then the probability of ending at $0$ is $$\binom{2k}{k}\left(\frac12\right)^{2k}\sim\frac1{\sqrt{\pi k}}.$$ Assuming the number of steps is sufficiently concentrated, the probability we end at $0$ is thus $$\frac1{2\sqrt{\pi\cdot\frac13n/2}}=\sqrt{\frac3{2\pi n}}.$$ By the generating function, this corresponds to the probability that there are an equal number of heads and tails. The probability that we correctly guess the sequence is thus this divided by $\binom{2n}{n}$, which gives an optimal expected value of $$2^{2n}\cdot\sqrt{\frac3{2\pi n}}\div\binom{2n}{n}\to\sqrt{3/2}.$$ Formalizing this proof requires more careful concentration and parity analysis of the random walk. But together with numerical evidence, I feel like it is safe to say this limit is correct.

At every step, it is optimal to bet your entire fortune on either heads or tails. One optimal strategy is thus to alternately guess heads and tails and always bet your entire fortune. The resulting expected value is $2^n$ times the probability that indeed the coins alternate heads and tails. I can not find a formula for the answer, but I calculated the following values with dynamic programming.

\begin{array}{c|c|c} n&E=&E\approx \\ \hline 2&2&2.00000\ldots \\ 3&4/3&1.33333\ldots \\ 4&40/27&1.48148\ldots \\ 5&13/10&1.30000\ldots \\ 6&4304/3125&1.37728\ldots \\ 7&3632/2835&1.28112\ldots \\ 8&5488768/4117715&1.33296\ldots \\ 9&13651/10752&1.26962\ldots \\ 10&394291456/301327047&1.30851\ldots \\ 100&&1.23219\ldots \\ 200&&1.22844\ldots \\ 300&&1.22720\ldots \\ 400&&1.22658\ldots \\ 500&&1.22621\ldots \\ 1000&&1.22548\ldots \\ 2000&&1.22511\ldots \\ 3000&&1.22498\ldots \\ \end{array}

To prove my claim, for $f_1,\ldots,f_k\in\{H,T\}$ let $E(f_1,\ldots,f_k)$ be the maximum possible expected value if the first $k$ coin flips have outcome $f_1,\ldots,f_k$ and we have $1$ dollar at that point. Let $p$ be the probability that, given the first $k$ coin flips are $f_1,\ldots,f_k$, the next coin flip is $H$.

Betting $x$ dollars on $H$ has outcome \begin{align*} &p(1+x)E(f_1,\ldots,f_k,H)+(1-p)(1-x)E(f_1,\ldots,f_k,T) \\&=pE(f_1,\ldots,f_k,H)+(1-p)E(f_1,\ldots,f_k,T)\\&+x[pE(f_1,\ldots,f_k,H)-(1-p)E(f_1,\ldots,f_k,T)], \end{align*} while betting $x$ dollars on $T$ has outcome \begin{align*} &p(1-x)E(f_1,\ldots,f_k,H)+(1-p)(1+x)E(f_1,\ldots,f_k,T) \\&=pE(f_1,\ldots,f_k,H)+(1-p)E(f_1,\ldots,f_k,T)\\&-x[pE(f_1,\ldots,f_k,H)-(1-p)E(f_1,\ldots,f_k,T)]. \end{align*} It is thus optimal to choose $x$ as large as possible, such that you bet your entire fortune, while betting on $H$ if $pE(f_1,\ldots,f_k,H)-(1-p)E(f_1,\ldots,f_k,T)$ is positive and betting on $T$ otherwise.

This strategy has the consequence that your choices do not matter anymore as soon as you made a wrong guess. You thus might as well predetermine the entire sequence of heads and tails that you want to guess. Then you either win $2^n$ if your sequence was correct, or you are left with $0$ otherwise. The expected value is thus $2^n$ times the probability your sequence is correct. We thus want to optimize the probability that your sequence is correct.

I interpret the fact that Nate is not sure which coin is which as the permutation of coins being uniformly random. Then the probability that your sequence is correct is independent of its permutation, so we only need to consider how many heads and tails you guess.

We have the following probability generating function for the number of heads occurrences. $$\prod_{i=0}^{n-1}\left(\frac{i}{n-1}x+\frac{n-1-i}{n-1}\right)$$ I expanded this product with dynamic programming and took the largest coefficient times $2^n$ to obtain the answers in the table. This largest coefficient was always at the median, meaning $\lfloor n/2\rfloor$ and $\lceil n/2\rceil$, though a simple proof that this must always hold currently eludes me. This corresponds to the strategy of alternating heads and tails.

As a final note, I am interested if anyone can determine if the optimal value converges as $n$ tends to infinity. Numerically, it appears the sequence is decreasing for $n$ even and for $n$ odd separately. The difference between $n$ even and $n$ odd seems to converge to $0$. The sequence does not appear to converge to $1$ however. If I had to take a guess I would go with $11/9$, but this is only based on numeric observation.

EDIT The limit is $\sqrt{3/2}=1.22474\ldots$. I give an incomplete argument for $2n$ coins. Then the generating function for number of $H$ minus number of $T$ is $$\prod_{i=0}^{2n-1}\left(\frac{i}{2n-1}x+\left(1-\frac{i}{2n-1}\right)x^{-1}\right)=\prod_{i=0}^{n-1}\left(\frac{i}{2n-1}x+\left(1-\frac{i}{2n-1}\right)x^{-1}\right)\left(\left(1-\frac{i}{2n-1}\right)x+\frac{i}{2n-1}x^{-1}\right)=\prod_{i=0}^{n-1}\left(\frac{i}{2n-1}\left(1-\frac{i}{2n-1}\right)(x^2+x^{-2})+1-2\frac{i}{2n-1}\left(1-\frac{i}{2n-1}\right)\right)$$ For $a_i=\frac{i}{2n-1}\left(1-\frac{i}{2n-1}\right)$ we can consider this as a random walk starting in $0$ and for each $i=0,\ldots,n-1$ there is an $a_i$ probability of walking left and an $a_i$ probability of walking right and a $1-2a_i$ probability of staying. Then the expected total number of steps is $$\sum_{i=0}^{n-1}2a_i\sim2n\int_0^1\frac{x}{2}\left(1-\frac{x}{2}\right)dx=\frac13n.$$ There is a probability of $\frac12$ that the number of steps is even, which is necessary and sufficient for it to be possible to end at $0$. If the number of steps is $2k$ then the probability of ending at $0$ is $$\binom{2k}{k}\left(\frac12\right)^{2k}\sim\frac1{\sqrt{\pi k}}.$$ Assuming the number of steps is sufficiently concentrated, the probability we end at $0$ is thus $$\frac1{2\sqrt{\pi\cdot\frac13n/2}}=\sqrt{\frac3{2\pi n}}.$$ By the generating function, this corresponds to the probability that there are an equal number of heads and tails. The probability that we correctly guess the sequence is thus this divided by $\binom{2n}{n}$, which gives an optimal expected value of $$2^{2n}\cdot\sqrt{\frac3{2\pi n}}\div\binom{2n}{n}\to\sqrt{3/2}.$$ Formalizing this proof requires more careful concentration and parity analysis of the random walk. But together with numerical evidence, I feel like it is safe to say this limit is correct.

At every step, it is optimal to bet your entire fortune on either heads or tails. One optimal strategy is thus to alternately guess heads and tails and always bet your entire fortune. The resulting expected value is $2^n$ times the probability that indeed the coins alternate heads and tails. I can not find a formula for the answer, but I calculated the following values with dynamic programming.

\begin{array}{c|c|c} n&E=&E\approx \\ \hline 2&2&2.00000\ldots \\ 3&4/3&1.33333\ldots \\ 4&40/27&1.48148\ldots \\ 5&13/10&1.30000\ldots \\ 6&4304/3125&1.37728\ldots \\ 7&3632/2835&1.28112\ldots \\ 8&5488768/4117715&1.33296\ldots \\ 9&13651/10752&1.26962\ldots \\ 10&394291456/301327047&1.30851\ldots \\ 100&&1.23219\ldots \\ 200&&1.22844\ldots \\ 300&&1.22720\ldots \\ 400&&1.22658\ldots \\ 500&&1.22621\ldots \\ 1000&&1.22548\ldots \\ 2000&&1.22511\ldots \\ 3000&&1.22498\ldots \\ \end{array}

To prove my claim, for $f_1,\ldots,f_k\in\{H,T\}$ let $E(f_1,\ldots,f_k)$ be the maximum possible expected value if the first $k$ coin flips have outcome $f_1,\ldots,f_k$ and we have $1$ dollar at that point. Let $p$ be the probability that, given the first $k$ coin flips are $f_1,\ldots,f_k$, the next coin flip is $H$.

Betting $x$ dollars on $H$ has outcome \begin{align*} &p(1+x)E(f_1,\ldots,f_k,H)+(1-p)(1-x)E(f_1,\ldots,f_k,T) \\&=pE(f_1,\ldots,f_k,H)+(1-p)E(f_1,\ldots,f_k,T)\\&+x[pE(f_1,\ldots,f_k,H)-(1-p)E(f_1,\ldots,f_k,T)], \end{align*} while betting $x$ dollars on $T$ has outcome \begin{align*} &p(1-x)E(f_1,\ldots,f_k,H)+(1-p)(1+x)E(f_1,\ldots,f_k,T) \\&=pE(f_1,\ldots,f_k,H)+(1-p)E(f_1,\ldots,f_k,T)\\&-x[pE(f_1,\ldots,f_k,H)-(1-p)E(f_1,\ldots,f_k,T)]. \end{align*} It is thus optimal to choose $x$ as large as possible, such that you bet your entire fortune, while betting on $H$ if $pE(f_1,\ldots,f_k,H)-(1-p)E(f_1,\ldots,f_k,T)$ is positive and betting on $T$ otherwise.

This strategy has the consequence that your choices do not matter anymore as soon as you made a wrong guess. You thus might as well predetermine the entire sequence of heads and tails that you want to guess. Then you either win $2^n$ if your sequence was correct, or you are left with $0$ otherwise. The expected value is thus $2^n$ times the probability your sequence is correct. We thus want to optimize the probability that your sequence is correct.

I interpret the fact that Nate is not sure which coin is which as the permutation of coins being uniformly random. Then the probability that your sequence is correct is independent of its permutation, so we only need to consider how many heads and tails you guess.

We have the following probability generating function for the number of heads occurrences. $$\prod_{i=0}^{n-1}\left(\frac{i}{n-1}x+\frac{n-1-i}{n-1}\right)$$ I expanded this product with dynamic programming and took the largest coefficient times $2^n$ to obtain the answers in the table. This largest coefficient was always at the median, meaning $\lfloor n/2\rfloor$ and $\lceil n/2\rceil$, though a simple proof that this must always hold currently eludes me. This corresponds to the strategy of alternating heads and tails.

As a final note, I am interested if anyone can determine if the optimal value converges as $n$ tends to infinity. Numerically, it appears the sequence is decreasing for $n$ even and for $n$ odd separately. The difference between $n$ even and $n$ odd seems to converge to $0$. The sequence does not appear to converge to $1$ however. If I had to take a guess I would go with $11/9$, but this is only based on numeric observation.

At every step, it is optimal to bet your entire fortune on either heads or tails. One optimal strategy is thus to alternately guess heads and tails and always bet your entire fortune. The resulting expected value is $2^n$ times the probability that indeed the coins alternate heads and tails. I can not find a formula for the answer, but I calculated the following values with dynamic programming.

\begin{array}{c|c|c} n&E=&E\approx \\ \hline 2&2&2.00000\ldots \\ 3&4/3&1.33333\ldots \\ 4&40/27&1.48148\ldots \\ 5&13/10&1.30000\ldots \\ 6&4304/3125&1.37728\ldots \\ 7&3632/2835&1.28112\ldots \\ 8&5488768/4117715&1.33296\ldots \\ 9&13651/10752&1.26962\ldots \\ 10&394291456/301327047&1.30851\ldots \\ 100&&1.23219\ldots \\ 200&&1.22844\ldots \\ 300&&1.22720\ldots \\ 400&&1.22658\ldots \\ 500&&1.22621\ldots \\ 1000&&1.22548\ldots \\ 2000&&1.22511\ldots \\ 3000&&1.22498\ldots \\ \end{array}

To prove my claim, for $f_1,\ldots,f_k\in\{H,T\}$ let $E(f_1,\ldots,f_k)$ be the maximum possible expected value if the first $k$ coin flips have outcome $f_1,\ldots,f_k$ and we have $1$ dollar at that point. Let $p$ be the probability that, given the first $k$ coin flips are $f_1,\ldots,f_k$, the next coin flip is $H$.

Betting $x$ dollars on $H$ has outcome \begin{align*} &p(1+x)E(f_1,\ldots,f_k,H)+(1-p)(1-x)E(f_1,\ldots,f_k,T) \\&=pE(f_1,\ldots,f_k,H)+(1-p)E(f_1,\ldots,f_k,T)\\&+x[pE(f_1,\ldots,f_k,H)-(1-p)E(f_1,\ldots,f_k,T)], \end{align*} while betting $x$ dollars on $T$ has outcome \begin{align*} &p(1-x)E(f_1,\ldots,f_k,H)+(1-p)(1+x)E(f_1,\ldots,f_k,T) \\&=pE(f_1,\ldots,f_k,H)+(1-p)E(f_1,\ldots,f_k,T)\\&-x[pE(f_1,\ldots,f_k,H)-(1-p)E(f_1,\ldots,f_k,T)]. \end{align*} It is thus optimal to choose $x$ as large as possible, such that you bet your entire fortune, while betting on $H$ if $pE(f_1,\ldots,f_k,H)-(1-p)E(f_1,\ldots,f_k,T)$ is positive and betting on $T$ otherwise.

This strategy has the consequence that your choices do not matter anymore as soon as you made a wrong guess. You thus might as well predetermine the entire sequence of heads and tails that you want to guess. Then you either win $2^n$ if your sequence was correct, or you are left with $0$ otherwise. The expected value is thus $2^n$ times the probability your sequence is correct. We thus want to optimize the probability that your sequence is correct.

I interpret the fact that Nate is not sure which coin is which as the permutation of coins being uniformly random. Then the probability that your sequence is correct is independent of its permutation, so we only need to consider how many heads and tails you guess.

We have the following probability generating function for the number of heads occurrences. $$\prod_{i=0}^{n-1}\left(\frac{i}{n-1}x+\frac{n-1-i}{n-1}\right)$$ I expanded this product with dynamic programming and took the largest coefficient times $2^n$ to obtain the answers in the table. This largest coefficient was always at the median, meaning $\lfloor n/2\rfloor$ and $\lceil n/2\rceil$, though a simple proof that this must always hold currently eludes me. This corresponds to the strategy of alternating heads and tails.

As a final note, I am interested if anyone can determine if the optimal value converges as $n$ tends to infinity. Numerically, it appears the sequence is decreasing for $n$ even and for $n$ odd separately. The difference between $n$ even and $n$ odd seems to converge to $0$. The sequence does not appear to converge to $1$ however. If I had to take a guess I would go with $11/9$, but this is only based on numeric observation.

EDIT The limit is $\sqrt{3/2}=1.22474\ldots$. I give an incomplete argument for $2n$ coins. Then the generating function for number of $H$ minus number of $T$ is $$\prod_{i=0}^{2n-1}\left(\frac{i}{2n-1}x+\left(1-\frac{i}{2n-1}\right)x^{-1}\right)=\prod_{i=0}^{n-1}\left(\frac{i}{2n-1}x+\left(1-\frac{i}{2n-1}\right)x^{-1}\right)\left(\left(1-\frac{i}{2n-1}\right)x+\frac{i}{2n-1}x^{-1}\right)=\prod_{i=0}^{n-1}\left(\frac{i}{2n-1}\left(1-\frac{i}{2n-1}\right)(x+x^{-1})+1-2\frac{i}{2n-1}\left(1-\frac{i}{2n-1}\right)\right)$$ For $a_i=\frac{i}{2n-1}\left(1-\frac{i}{2n-1}\right)$ we can consider this as a random walk starting in $0$ and for each $i=0,\ldots,n-1$ there is an $a_i$ probability of walking left and an $a_i$ probability of walking right and a $1-2a_i$ probability of staying. Then the expected total number of steps is $$\sum_{i=0}^{n-1}2a_i\sim2n\int_0^1\frac{x}{2}\left(1-\frac{x}{2}\right)dx=\frac13n.$$ There is a probability of $\frac12$ that the number of steps is even, which is necessary and sufficient for it to be possible to end at $0$. If the number of steps is $2k$ then the probability of ending at $0$ is $$\binom{2k}{k}\left(\frac12\right)^{2k}\sim\frac1{\sqrt{\pi k}}.$$ Assuming the number of steps is sufficiently concentrated, the probability we end at $0$ is thus $$\frac1{2\sqrt{\pi\cdot\frac13n/2}}=\sqrt{\frac3{2\pi n}}.$$ By the generating function, this corresponds to the probability that there are an equal number of heads and tails. The probability that we correctly guess the sequence is thus this divided by $\binom{2n}{n}$, which gives an optimal expected value of $$2^{2n}\cdot\sqrt{\frac3{2\pi n}}\div\binom{2n}{n}\to\sqrt{3/2}.$$ Formalizing this proof requires more careful concentration and parity analysis of the random walk. But together with numerical evidence, I feel like it is safe to say this limit is correct.

At every step, it is optimal to bet your entire fortune on either heads or tails. One optimal strategy is thus to alternately guess heads and tails and always bet your entire fortune. The resulting expected value is $2^n$ times the probability that indeed the coins alternate heads and tails. I can not find a formula for the answer, but I calculated the following values with dynamic programming.

\begin{array}{c|c|c} n&E=&E\approx \\ \hline 2&2&2.00000\ldots \\ 3&4/3&1.33333\ldots \\ 4&40/27&1.48148\ldots \\ 5&13/10&1.30000\ldots \\ 6&4304/3125&1.37728\ldots \\ 7&3632/2835&1.28112\ldots \\ 8&5488768/4117715&1.33296\ldots \\ 9&13651/10752&1.26962\ldots \\ 10&394291456/301327047&1.30851\ldots \\ 100&&1.23219\ldots \\ 200&&1.22844\ldots \\ 300&&1.22720\ldots \\ 400&&1.22658\ldots \\ 500&&1.22621\ldots \\ 1000&&1.22548\ldots \\ 2000&&1.22511\ldots \\ 3000&&1.22498\ldots \\ \end{array}

To prove my claim, for $f_1,\ldots,f_k\in\{H,T\}$ let $E(f_1,\ldots,f_k)$ be the maximum possible expected value if the first $k$ coin flips have outcome $f_1,\ldots,f_k$ and we have $1$ dollar at that point. Let $p$ be the probability that, given the first $k$ coin flips are $f_1,\ldots,f_k$, the next coin flip is $H$.

Betting $x$ dollars on $H$ has outcome \begin{align*} &p(1+x)E(f_1,\ldots,f_k,H)+(1-p)(1-x)E(f_1,\ldots,f_k,T) \\&=pE(f_1,\ldots,f_k,H)+(1-p)E(f_1,\ldots,f_k,T)\\&+x[pE(f_1,\ldots,f_k,H)-(1-p)E(f_1,\ldots,f_k,T)], \end{align*} while betting $x$ dollars on $T$ has outcome \begin{align*} &p(1-x)E(f_1,\ldots,f_k,H)+(1-p)(1+x)E(f_1,\ldots,f_k,T) \\&=pE(f_1,\ldots,f_k,H)+(1-p)E(f_1,\ldots,f_k,T)\\&-x[pE(f_1,\ldots,f_k,H)-(1-p)E(f_1,\ldots,f_k,T)]. \end{align*} It is thus optimal to choose $x$ as large as possible, such that you bet your entire fortune, while betting on $H$ if $pE(f_1,\ldots,f_k,H)-(1-p)E(f_1,\ldots,f_k,T)$ is positive and betting on $T$ otherwise.

This strategy has the consequence that your choices do not matter anymore as soon as you made a wrong guess. You thus might as well predetermine the entire sequence of heads and tails that you want to guess. Then you either win $2^n$ if your sequence was correct, or you are left with $0$ otherwise. The expected value is thus $2^n$ times the probability your sequence is correct. We thus want to optimize the probability that your sequence is correct.

I interpret the fact that Nate is not sure which coin is which as the permutation of coins being uniformly random. Then the probability that your sequence is correct is independent of its permutation, so we only need to consider how many heads and tails you guess.

We have the following probability generating function for the number of heads occurrences. $$\prod_{i=0}^{n-1}\left(\frac{i}{n-1}x+\frac{n-1-i}{n-1}\right)$$ I expanded this product with dynamic programming and took the largest coefficient times $2^n$ to obtain the answers in the table. This largest coefficient was always at the median, meaning $\lfloor(n-1)/2\rfloor$ and $\lceil(n-1)/2\rceil$, though a simple proof that this must always hold currently eludes me. This corresponds to the strategy of alternating heads and tails.

At every step, it is optimal to bet your entire fortune on either heads or tails. One optimal strategy is thus to alternately guess heads and tails and always bet your entire fortune. The resulting expected value is $2^n$ times the probability that indeed the coins alternate heads and tails. I can not find a formula for the answer, but I calculated the following values with dynamic programming.

\begin{array}{c|c|c} n&E=&E\approx \\ \hline 2&2&2.00000\ldots \\ 3&4/3&1.33333\ldots \\ 4&40/27&1.48148\ldots \\ 5&13/10&1.30000\ldots \\ 6&4304/3125&1.37728\ldots \\ 7&3632/2835&1.28112\ldots \\ 8&5488768/4117715&1.33296\ldots \\ 9&13651/10752&1.26962\ldots \\ 10&394291456/301327047&1.30851\ldots \\ 100&&1.23219\ldots \\ 200&&1.22844\ldots \\ 300&&1.22720\ldots \\ 400&&1.22658\ldots \\ 500&&1.22621\ldots \\ 1000&&1.22548\ldots \\ 2000&&1.22511\ldots \\ 3000&&1.22498\ldots \\ \end{array}

To prove my claim, for $f_1,\ldots,f_k\in\{H,T\}$ let $E(f_1,\ldots,f_k)$ be the maximum possible expected value if the first $k$ coin flips have outcome $f_1,\ldots,f_k$ and we have $1$ dollar at that point. Let $p$ be the probability that, given the first $k$ coin flips are $f_1,\ldots,f_k$, the next coin flip is $H$.

Betting $x$ dollars on $H$ has outcome \begin{align*} &p(1+x)E(f_1,\ldots,f_k,H)+(1-p)(1-x)E(f_1,\ldots,f_k,T) \\&=pE(f_1,\ldots,f_k,H)+(1-p)E(f_1,\ldots,f_k,T)\\&+x[pE(f_1,\ldots,f_k,H)-(1-p)E(f_1,\ldots,f_k,T)], \end{align*} while betting $x$ dollars on $T$ has outcome \begin{align*} &p(1-x)E(f_1,\ldots,f_k,H)+(1-p)(1+x)E(f_1,\ldots,f_k,T) \\&=pE(f_1,\ldots,f_k,H)+(1-p)E(f_1,\ldots,f_k,T)\\&-x[pE(f_1,\ldots,f_k,H)-(1-p)E(f_1,\ldots,f_k,T)]. \end{align*} It is thus optimal to choose $x$ as large as possible, such that you bet your entire fortune, while betting on $H$ if $pE(f_1,\ldots,f_k,H)-(1-p)E(f_1,\ldots,f_k,T)$ is positive and betting on $T$ otherwise.

This strategy has the consequence that your choices do not matter anymore as soon as you made a wrong guess. You thus might as well predetermine the entire sequence of heads and tails that you want to guess. Then you either win $2^n$ if your sequence was correct, or you are left with $0$ otherwise. The expected value is thus $2^n$ times the probability your sequence is correct. We thus want to optimize the probability that your sequence is correct.

I interpret the fact that Nate is not sure which coin is which as the permutation of coins being uniformly random. Then the probability that your sequence is correct is independent of its permutation, so we only need to consider how many heads and tails you guess.

We have the following probability generating function for the number of heads occurrences. $$\prod_{i=0}^{n-1}\left(\frac{i}{n-1}x+\frac{n-1-i}{n-1}\right)$$ I expanded this product with dynamic programming and took the largest coefficient times $2^n$ to obtain the answers in the table. This largest coefficient was always at the median, meaning $\lfloor n/2\rfloor$ and $\lceil n/2\rceil$, though a simple proof that this must always hold currently eludes me. This corresponds to the strategy of alternating heads and tails.

As a final note, I am interested if anyone can determine if the optimal value converges as $n$ tends to infinity. Numerically, it appears the sequence is decreasing for $n$ even and for $n$ odd separately. The difference between $n$ even and $n$ odd seems to converge to $0$. The sequence does not appear to converge to $1$ however. If I had to take a guess I would go with $11/9$, but this is only based on numeric observation.