# Looking to generalize a binomial tree with some constraints.

I've got a set of sample data and I'm looking to see if it's possible to generalize a binomial formula to give a closed form solution to this. If not, would it be possible to write a program to do this? Apologies in advance if it isn't really clear, but I just have the data and I'm trying to build the rules around it.

Background: Basically all time periods are split in two, for example two days of the week, Monday and Friday. So, The first time period is Monday, second is Friday, third is Monday, fourth is Friday etc...

Each day an event occurs, say a coin flip where Heads is a win and Tails is a loss. There are different payoff systems depending on what day the coin is flipped.

On Monday the coin is flipped.

If the coin wins (heads) on a Monday, there is a payoff of M1 (one day starting on monday).

The coin is flipped again on Friday, if it wins again, there is a payoff of M2 (two days in a row, starting on) but if it loses there is a payoff of F1 (one day starting on friday.

So each time the coin loses, it is reset to 1 of the current day (M1 or F1) and the series starts again from there.

Total payoff is the sum of payoffs at each period.

I'm trying to think of the best way to work with this, but as an example of they way I've been trying it, the possible outcomes for a 5 period game with 4 coin tosses (or is this a 4 period game...) that starts on Monday are:

Payoffs when no wins (4 Choose 0 solutions):

(M1 + F1 + M1 + F1 + M1)


Payoffs with one win (4 Choose 1 solutions):

(M1 + F1 + M1 + F1 + F2),
(M1 + F1 + M1 + M2 + M1),
(M1 + F1 + F2 + F1 + M1),
(M1 + M2 + M1 + F1 + M1)


Payoffs with two wins (4 Choose 2 solutions):

(M1 + F1 + M1 + M2 + M3),
(M1 + F1 + F2 + F3 + M1),
(M1 + M2 + M3 + F1 + M1),
(M1 + M2 + M1 + M2 + M1),
(M1 + F1 + F2 + F1 + F2),
(M1 + M2 + M1 + F1 + F2)


Payoffs with three wins (4 Choose 3 solutions):

(M1 + M2 + M3 + M4 + M1),
(M1 + F1 + F2 + F3 + F4),
(M1 + M2 + M3 + F1 + F2),
(M1 + M2 + M1 + M2 + M3)


Payoffs with four wins (4 Choose 4 solutions):

(M1 + M2 + M3 + M4 + M5)


So that's it... It seems a bit confusing so I might not have explained it well, but will answer any questions. If it's hard to understand I can make a Tree image that might make more sense, let me know.

Thanks!

-
Unless I missed it somewhere, you forgot to say what it is you're trying to calculate. – joriki Mar 27 '12 at 16:10
That's very possible... whoops. I'm trying to get the expected value of this game. I have the payoffs M1, M2, F1 etc. and I know the probabilities of arriving at each final node. I can work it out manually for games like this, but when the number of periods gets bigger i'll need a formula or algorithm. – Gerry Mar 27 '12 at 16:30

Your description of the payoffs is somewhat confusing and contradicts the consistent example you give (in which "If the coin wins (heads) on a Monday, there is a payoff of M1" is clearly not true), so I'll generalize from the example instead.

The expected value of the game is a linear combination of the payoffs $M_1$ through $M_n$ and $F_1$ through $F_n$. To get the coefficient for a payoff, consider on which days it may occur. For instance, the payoff $F_2$ can occur on any Monday that is at least the second day. More generally, for even/odd $k$ the payoff $F_k$ can occur on any Monday/Friday that is at least the $k$-th day, and the other way around for $M_k$.

Now except for a slight complication at the beginning, on any day on which the payoff $F_k$ or $M_k$ can occur, it occurs with probability $2^{-k}$ (assuming a fair coin), since the previous $k$ coin throws must have been tails followed by $k-1$ heads. Thus the coefficient of each payoff is just $2^{-k}$ times the number of days on which it can occur.

The slight complication comes about because of the special way you seem to be treating the first day. The payoffs $M_1$ through $M_n$ are twice as likely on the first day on which they can occur than they usually are (apparently because they don't have to be preceded by a tails), so you have to add an extra day for each of these.

Thus, in your example the expected value is

$$2^{-1}(4M_1+2F_1)+2^{-2}(3M_2+2F_2)+2^{-3}(3M_3+1F_3)+2^{-4}(2M_4+F_4)+2^{-5}(2M_5)\;.$$

-
Thanks for this, really helped in thinking about it. I managed to write a script to get the job done, it's not elegant but it seems to work. – Gerry Mar 28 '12 at 15:50