Problem 10: All Decked Out
The card game "Dominion" is based on building up your deck of cards during gameplay. There are three types of cards: "Action" cards, "Treasure" cards, and "Victory" cards. Treasure cards have a number of coins on them, while Victory cards have a number of victory points on them.
A player's turn goes as follows. First, he draws five cards from his deck. Then, he plays up to one action card. Action cards can have one or more of the following effects:
"+X Cards" - Immediately draw X more cards.
"+X Actions" - You may play up to X more actions on this turn. (This allows you to create long chains of actions if you play +action cards and then use your new actions to play more +action cards.)
+1 Buy" - Increases the number of cards you can buy in the Buy Phase (See below) by 1.
"+X Coins" - Add X coins to the number of coins you have available in the Buy Phase (see below.)
After you finish playing actions you go into the Buy Phase. You add up the number of coins on all the treasure cards in your hand plus any +coins action cards you played. That is how many coins you have available to buy another card to put into your deck, and better cards cost more gold.
The way you win the game is by having the most victory points worth of Victory Cards in your deck at the end. ut of course Victory Cards are useless when you draw them, so they dilute your deck - and a key strategic element is when to start buying victory cards.
Here is the problem. Consider a simplified version of the game where you have an unlimited number of actions per round (you can keep playing action cards until you run out) and action cards only have the effects "+X cards" and "+X coins". Give a formula that can be used to calculate, given the composition of your deck, the expected number of coins you will have available to spend at the end of each turn.
You may make the following simplifying approximations:
1. All draws are independent - i.e. if 1/3 of your deck consists of treasure cards with a value of 2 coins, then each time you draw a card, you have a 1/3 chance of getting a treasure card with a value of 2 coins.
2. There is no chance of running out of cards to draw. (In the actual game, once you run out of cards to draw you can reshuffle your deck. It is possible to draw your entire deck in one turn, but that is rare.)
The answer is here.