# Recursive expected value when ending state is up to the player

I am wanting to improve my understanding of solving expected value through recursion. I understand how to perform some problems (such as expected number to get X heads in a row).

However, I am lost when the ending condition is up to the player. I think someone going through an example like the one below would be very helpful.

For example, suppose a game where you flip 6 coins and the number of heads determines your payout. If you do not like your flip of 6 coins, then you can pay one dollar and reflip all 6 coins again. You can do this as many times as you like but once you choose to reflip, even if the new result is worse, you cannot go back to a previous flip. In other words, once you choose to reflip, you lose another dollar and “forget all flips before.” Once you decide to take the payout the game ends and you win # of heads on last set of 6 flips - #rerolls * cost to reroll.

Now I know that the expected value of heads is 3. So if I get something less than 3, I may be inclined to reroll, but I am pretty confident that this depends on the cost of a reroll. I can imagine that if it costed 5 dollars to reroll you would only play once.

How can I determine 1) expected value and 2) at what # of heads or less should I reroll?

This is just a specific example I have come across when practicing (I found no solution though). Any other resources for problems like these (with solutions) would be super helpful.

Clearly, your strategy should be a cutoff strategy: reflip for less than $$a$$ heads, stop for $$a$$ heads or above. Let $$x$$ be the expected value of the game. Then the expected value should solve the following equation:
$$x=\tfrac{1}{6}\sum\limits_{i=1}^{a-1} (x-1) + \tfrac{1}{6}\sum\limits_{j=a}^6 j$$
Where the first part is lower results which require reflipping, the right side is the better results for which you start. You can write the $$\Sigma$$s explicitly, then solve for $$x$$ and get something of the sort $$x=f(a)$$. For each $$a$$ you can compute $$x$$ and choose the one that maximizes $$x$$.