Binomial tree simple array manipulation

Mr_Hide

New Member
Joined
Jan 18, 2014
Messages
5
Hi guys,

I hope this is for some of you really easy stuff and you can help me out.

I have the following problem, I made a binomial tree or better to say multiple, and I need the code to for example
compare the value at c(1,2) with c(1,1)+p(1,2) and store or use the smaller of those two in f(1,2), know comes for me
the tricky part I need it to compare f(1,2) with c(1,3) and if f(1,2)=c(1,2) just add p(1,3) and then compare those two values, but if f(1,2)=c(1,1)+p(1,2) compare c(1,1)+(p(1,2)+p(1,3)) with c(1,3) and store the smaller one.

I hope it is clear this is what I managed so far, but I think I need at least two more if or loops:

ReDim final(n, n)
final(1, 1) = cost(1, 1)
For t = 2 To n
For i = 1 To n
If cost(i, t) <= cost(i, t - 1) + ud(i, t) * 10 Then

final(i, t) = cost(i, t)
Else
final(i, t) = cost(i, t - 1) + ud(i, t) * 10
End If
Next i
Next t

Im really stuck, would be nice if someone could help me out since it is for school, and very important.

Thank you in advance
 

Excel Facts

Convert text numbers to real numbers
Select a column containing text numbers. Press Alt+D E F to quickly convert text to numbers. Faster than "Convert to Number"
Welcome to the Forum!

A couple of questions please, so that someone can point you in the right direction:

1. Can you explain what the actual problem is? You say you've made a binomial tree, but it's not clear why, unless we know what the problem is that you're trying to solve?

2. Hopefully, (1) will explain what cost, final, ud, n etc mean, and also why you've hard coded a value of 10?

3. Can you provide your full VBA code?
 
Upvote 0
Welcome to the Forum!

A couple of questions please, so that someone can point you in the right direction:

1. Can you explain what the actual problem is? You say you've made a binomial tree, but it's not clear why, unless we know what the problem is that you're trying to solve?

2. Hopefully, (1) will explain what cost, final, ud, n etc mean, and also why you've hard coded a value of 10?

3. Can you provide your full VBA code?

Sorry for that,

what I try to do is apply option theory to a investment project, so not derivatives but a real project. The hardcoded stuff are just some example values

1)first I make a binomial tree for the biggest risk factor in the project lets call it D
2)then I translate this risk factor into costs, so I get different scenarios for the costs
3)then I have to first set the cost of the project at every node which is smaller then c(1,1) initial costs, equal to that value since I assume that the costs in the down nodes can actually not get smaller but rather stay constant.
4) I need to calculate the difference of D between every up node and its previous node so c(i,t+1)-c(i,t)
5)I translate this difference of D into some social costs
6) now comes the part where I'm stuck, a) I need the code to compare the value of c(i,t) at each up node with the value of the previous c + these social costs(ud), and to sore the lower one of them, then as above described.
 
Upvote 0
I don't pretend to understand your assignment, but that's OK. If we can distil it down into an algorithm, then we can help you code the VBA. And I suspect, given the nature of binary trees, that this code might be recursive.

I am still a little confused about what you're trying to code ... A binomial tree of order N has 2^N nodes. instead, you seem to trying to work with N^2 values?

Are we working with a single tree? Are you numbering the nodes? Or the levels? i.e. what do you mean by i and by t, and how do these relate to up, down and previous?

It would also probably really help if we could see all your code.
 
Upvote 0
I don't pretend to understand your assignment, but that's OK. If we can distil it down into an algorithm, then we can help you code the VBA. And I suspect, given the nature of binary trees, that this code might be recursive.

I am still a little confused about what you're trying to code ... A binomial tree of order N has 2^N nodes. instead, you seem to trying to work with N^2 values?

Are we working with a single tree? Are you numbering the nodes? Or the levels? i.e. what do you mean by i and by t, and how do these relate to up, down and previous?

It would also probably really help if we could see all your code.

I'm really sorry for my vage problem description i thought if i say (i,j) its clear that I mean an array value and those are the labels of the nodes.The assignment changed I need to expand with fixed costs of 1500000 and 5000 human units Capacity. Well my code is at the beginning, and I forgot to completely consider the nonrecombining option.

My code is doing nothing yet because it is all just wrong.

My algorithm in words would be:
1) compute up and down factors, based on the volatillity I get from historical population data, formula u=exp(volatility*sqrt(delta_t))d=1/u, where delta_t= Time to maturity/ by number of steps. Compute risk-neutral probabilities p and (1-p) p= exp(riskfreerate*delta_t), these are real options so still donno which probabilities to use since water is not tradeable.
Costs fixed plant= 28 million
Starting Demand=50000
Starting capacity variable 55000 human units
Costs of this project 1 5million
T= 30 years
2)compute demand tree Demand(0,0)=50000 all values until now are seen as input for this function so that they are changeable

3)starting from Demand(0,0) or (1,1) doesn't matter,


SO now comes the great part were I'm stuck i think there should be just to much if statements or if-and statement.and the indexing so the (i,t)'s kill me

4) Compare capacity with demand as you go along the demand tree, so if demand > capacity choose min(expansion costs, penalty) if expansion add capacity and costs of expansion to initial values otherwise add penalty costs don't change capacity. The penalty cost is just a function which represents some opportunity costs for not treating the demand but also the angriness of the people who doesn't get water for drinking or showering etc. I set it in such a way up that the costs exponentially increase because not expanding and thus always paying penalty shouldn't be rational. so so if demand > capacity, Penalty=if((demand-capacity)/demand>0.02;exp((demand-capacity)/demand+1)*x*(demand-capacity);0), x is the penalty factor and is in this example 100. And unsatisfied demand of 2%=0.02 can be tolerated.
If demand < capacity then costs and capacity stay the same but are those from the previous nodes, values.

SO that would be the approach if the first path is a up node so demand increases, but if I go from the path down I'll get a different value for example for node (2,4) or (3,4), so the costs and I think the capacity to will be an non recombining tree,

and at the end nodes my payoff is costs max(fixed plant-costs flexible;0) at every node, and then backwards induction to (0,0) to get the option value.

I hope it is clear now,
here is my code so far but it doesn't make sense because I have to do it differently but here it is: I think it is even easier with fixed expansion costs and fixed additional capacity.

Sub DrawBinomialTree() '''''''''''''''''''''''''''''''''''''''
Dim stock() ' Declaring Variables
Dim cost() '''''''''''''''''''''''''''''''''''''''
Dim ud()
Dim final()
Dim i As Integer
Dim t As Integer
n = 4
u = 1.2
P0 = 100
d = 0.6
costflex = 20000000
CP = (costflex / P0)


ReDim stock(n, n)
Worksheets("Sheet2").Activate
Worksheets("Sheet2").Cells.ClearContents
stock(1, 1) = P0


For t = 2 To n
stock(1, t) = stock(1, t - 1) * u
For i = 2 To t
stock(i, t) = stock(i - 1, t - 1) * d
Next i ' this loop start from for 1-2 to t or from T-2 to n
Next t




For t = 1 To n 'output of the tree in excel
For i = 1 To n
Cells(2 * n - i, n - t + 1) = stock(n - i + 1, n - t + 1) 'Cells(20 - i, 10 - t + 1) = stock(10 - i + 1, 10 - t + 1)
Next
Next


ReDim cost(n, n) 'cost tree
cost(1, 1) = costflex
For t = 2 To n
cost(1, t) = stock(1, t) * CP
For i = 2 To t
cost(i, t) = stock(i, t) * CP
Next i ' this loop start from for 1-2 to t or from T-2 to n
Next t


For t = 1 To n 'output of the cost tree in excel
For i = 1 To n
Cells(4 * n - i, n - t + 1) = cost(n - i + 1, n - t + 1) 'Cells(20 - i, 10 - t + 1) = stock(10 - i + 1, 10 - t + 1)
Next i
Next t


'Calculating unsatisfied demand for all up nodes '''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
For t = 2 To n 'If I remove this part I get also demand on intermediate nodes'
For i = 1 To t '''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
If stock(i, t) < stock(1, 1) Then '
stock(i, t) = stock(1, 1) '
Else '
stock(i, t) = stock(i, t) '
End If '
Next i '
Next t


For t = 1 To n 'output of the cost tree in excel
For i = 1 To n
Cells(6 * n - i, n - t + 1) = stock(n - i + 1, n - t + 1) 'Cells(20 - i, 10 - t + 1) = stock(10 - i + 1, 10 - t + 1)
Next i
Next t






ReDim ud(n, n)
ud(1, 1) = 0


For t = 2 To n
ud(1, t) = WorksheetFunction.Max((stock(1, t) - stock(1, t - 1)), 0)
Next t


For t = 2 To (n - 1)
For i = 2 To t
ud(i, t + 1) = WorksheetFunction.Max((stock(i, t + 1) - stock(i, t)), 0)
Next i
Next t




For t = 1 To n 'output of the unsatisfied demand in excel
For i = 1 To n
Cells(6 * n - i, n - t + 1) = ud(n - i + 1, n - t + 1)
Next
Next


'Choosing whether to pay the penalty or to expand


ReDim final(n, n)
final(1, 1) = cost(1, 1)
For t = 2 To n
For i = 1 To n
If cost(i, t) <= cost(i, t - 1) + ud(i, t) * 10 Then

final(i, t) = cost(i, t)
Else
final(i, t) = cost(i, t - 1) + ud(i, t) * 10
End If




Next i
Next t


For t = 1 To n 'output final tree
For i = 1 To n
Cells(8 * n - i, n - t + 1) = final(n - i + 1, n - t + 1)
Next
Next




End Sub
 
Upvote 0
And the penalty has to be cumulative for example if I pay the penalty today (paying penalty means not expanding thus staying at same capacity) and the demand tomorrow grows the Penalty is not Penalty=if((demand-capacity)/demand>0.02;exp((demand-capacity)/demand+1)*x*(demand-capacity);0) but Penalty=if((demand-capacity)/demand>0.02;exp(((demand-capacity)/demand)+((demand-capacity)/demand)+1) of the previous one*x*(demand-capacity+(demand-capacity of the previous one));0)

well a demand tree would be a simple binomial tree for the demand, but the capacity and costs change and should be stored in an different array so another binomial tree which is not recombining. not recombining means that instead of (1,1) [up (1,2) or down(2,2)] [upup (1,3) updown(2,3) downdown(3,3)] you get [upup(1,3) updown(2,3) downup(2,3) downdown(3,3)] so the path on the tree up-down leads not to the same value as down-up. that is my biggest problem. do you have an idea how to solve this problem? That is my problem with the array indexing.

Regards,
Nyle
 
Upvote 0
Thanks for explaining further ...

If I can summarise the problem (just to make sure I've got it clear):

- Water demand should be modelled binomially.

- The capacity for water supply is "lumpy", and will increase from time to time only in large increments, e.g. when a decision is made to build a new pipe-line or pumping station.

- The decision whether or not to invest in new infrastructure is determined in an economically (but not socially!) efficient way as:

= MIN(Penalty, Expansion Costs).

My guess is that we can assume a simplistic one-period investment time-horizon, e.g. we would prefer to pay penalties of $800 over three successive periods rather than investing $1,000 in infrastructure, because $800 this period is cheaper than $1,000 this period? Only when the penalty this period exceeds $1,000 do we spend on infrastructure?

I would expect the exercise to be asking you to measure the total exposure to future costs, i.e. penalties and/or infrastructure? (In a real-world exercise, I'd also expect to see some allowance for future cost inflation, and interest rate(s) to discount to the present date, but I assume we can ignore that here).

On the face of it, we simply need to sum, over all possible nodes:

(Probability of hitting that node) x MIN(Penalty, Expansion Costs).

However, the difficulty, as you identify, is that the demand tree will be recombinant, but supply won't be. For example, an up/up/down demand scenario over t = 1,2,3, is the same as a down/up/up, but the former may have triggered an infrastructure investment at t = 2, whereas the latter would not.

A naive question perhaps, but can't you simplify the looping by assuming that demand is non-recombinant? i.e. instead of having:
1 --> 2 --> 3 --> 4 demand nodes, you have
1 --> 2 --> 4 --> 8 nodes.

In practice, there will be some duplication of demand nodes, e.g. at t=2 when there are 4 nodes, demand nodes 2 and 3 will be identical. But the bifurcation will allow for the possibility of node 2 including an infrastructure increase, and node 3 having no increase?
 
Upvote 0
Thanks for explaining further ...

If I can summarise the problem (just to make sure I've got it clear):

- Water demand should be modelled binomially.

- The capacity for water supply is "lumpy", and will increase from time to time only in large increments, e.g. when a decision is made to build a new pipe-line or pumping station.

- The decision whether or not to invest in new infrastructure is determined in an economically (but not socially!) efficient way as:

= MIN(Penalty, Expansion Costs).

My guess is that we can assume a simplistic one-period investment time-horizon, e.g. we would prefer to pay penalties of $800 over three successive periods rather than investing $1,000 in infrastructure, because $800 this period is cheaper than $1,000 this period? Only when the penalty this period exceeds $1,000 do we spend on infrastructure?

I would expect the exercise to be asking you to measure the total exposure to future costs, i.e. penalties and/or infrastructure? (In a real-world exercise, I'd also expect to see some allowance for future cost inflation, and interest rate(s) to discount to the present date, but I assume we can ignore that here).

On the face of it, we simply need to sum, over all possible nodes:

(Probability of hitting that node) x MIN(Penalty, Expansion Costs).

However, the difficulty, as you identify, is that the demand tree will be recombinant, but supply won't be. For example, an up/up/down demand scenario over t = 1,2,3, is the same as a down/up/up, but the former may have triggered an infrastructure investment at t = 2, whereas the latter would not.

A naive question perhaps, but can't you simplify the looping by assuming that demand is non-recombinant? i.e. instead of having:
1 --> 2 --> 3 --> 4 demand nodes, you have
1 --> 2 --> 4 --> 8 nodes.

In practice, there will be some duplication of demand nodes, e.g. at t=2 when there are 4 nodes, demand nodes 2 and 3 will be identical. But the bifurcation will allow for the possibility of node 2 including an infrastructure increase, and node 3 having no increase?

Roughly correct
but the penalty is cumulative meaning If I haven't expanded today(capacity today 55000 < demand today 60000 so penalty for 5000) I will pay next period if the demand grows again a penalty (capacity still 55000 < demand 63000, penalty for 8000 demand units)
The problem is not in time =1 step, it has to be for 20 or 30, it is exactly what you said that would be my next step to transfer the recombining demand tree to a 1--->2--->4--->8 tree but I can't come up with an algorithm for that. And the decision algorithm will be huge because I have these simultaniuos paths, for example Monte Carlo produces just one path and then it is easy along the path to decide what to do, but a non recombining tree ?

Well I don
 
Upvote 0
Thanks for explaining further ...



In practice, there will be some duplication of demand nodes, e.g. at t=2 when there are 4 nodes, demand nodes 2 and 3 will be identical. But the bifurcation will allow for the possibility of node 2 including an infrastructure increase, and node 3 having no increase?

That is true but I dont know how to translate the values from the recombinant tree into a non recombinant, it shouldn't matter that the some nodes are identical because of the fact some trigger an investment and others dont, I need the paths to be independent thats the point.

I can't think of an algorithm which translates the values from the recombinant to the non recombinant,

or I looked how to construct a non recombinant demand tree but there just some fancy approaches like moment matching and don't know if I can apply that to only 40 years of annually population data?

Does some one has an idea how to construct an non recombining tree?
 
Last edited:
Upvote 0

Forum statistics

Threads
1,213,531
Messages
6,114,172
Members
448,554
Latest member
Gleisner2

We've detected that you are using an adblocker.

We have a great community of people providing Excel help here, but the hosting costs are enormous. You can help keep this site running by allowing ads on MrExcel.com.
Allow Ads at MrExcel

Which adblocker are you using?

Disable AdBlock

Follow these easy steps to disable AdBlock

1)Click on the icon in the browser’s toolbar.
2)Click on the icon in the browser’s toolbar.
2)Click on the "Pause on this site" option.
Go back

Disable AdBlock Plus

Follow these easy steps to disable AdBlock Plus

1)Click on the icon in the browser’s toolbar.
2)Click on the toggle to disable it for "mrexcel.com".
Go back

Disable uBlock Origin

Follow these easy steps to disable uBlock Origin

1)Click on the icon in the browser’s toolbar.
2)Click on the "Power" button.
3)Click on the "Refresh" button.
Go back

Disable uBlock

Follow these easy steps to disable uBlock

1)Click on the icon in the browser’s toolbar.
2)Click on the "Power" button.
3)Click on the "Refresh" button.
Go back
Back
Top