In a stochastic optimization problem, assume a scenario-tree with N nodes spread out in T stages. Let prob(k) denote the probability that node 'k' will realize. Let cost(k) denote the cost associated with node 'k'.

According to wikipedia, the total expected cost is the sum of cost(k)*prob(k)/T because it can be viewed as the weighted average cost, with the prob(k) being the weight.

Most of us know that the expected cost is just the sum of cost(k)*prob(k) across all k = 1..N.

Which interpretation do you use?

asked 25 Sep '14, 19:32

spyimp's gravatar image

accept rate: 0%

could you tell us which wikipedia page you are referring?

(25 Sep '14, 22:55) ksphil

It is assumed that one of the outcomes must be revealed at each stage. So the sum of unconditional probabilities over all the nodes at each stage is 1. Thus the division by T for the average cost per period.

Think of the two-stage problem as the simplest example: You account for the first-stage costs (a single scenario with probability one), plus the second stage costs, which are a weighted sum product of the costs realized under that scenario by the probability of that scenario. If you want to report the average cost per period you would divide the total objective by two.

I am not sure exactly to which Wikipedia article you refer. I can edit this answer and make it more useful if you can add a little bit more mathematical rigor to the question, as well as an example.


answered 25 Sep '14, 20:06

Leo's gravatar image

accept rate: 8%

edited 26 Sep '14, 09:55

Assume the 3-stage scenario tree. The first stage consists of node 1. The second stage consists of node 2 and node 3. There is 50% change of ending up at node2, and then 50% chance of ending up at node3. The third stage consists of nodes 4,5,6,7. So we have four scenarios: a) 1 --> 2 --> 4 b) 1 --> 2 --> 5 c) 1 --> 3 --> 6 d) 1 --> 3 --> 7 . Ie if node 2 occurs, then there is 50% chance that node 4 will occur, and 50% chance that node 5 will occur. On the other hand, if we are at node 3, then there is 50% chance that node 6 will occur and 50% chance that node 7 will occur.







So, the probability that node 4 will occur is 50% * 50% i.e. 25%. Similarly, the probability of node 5 occurring is 50% * 50% = 25%. Same for node 6 and node 7. Whereas, the probability that node 2 will occur is 50%.

Each node is associated with a certain cost. So node2 has a cost of cost(2), while node3 has a cost cost(3). Same for cost(4), cost(5), cost(6), cost(7).

To find the total expected cost, we do: prob(1)cost(1)+ prob(2)cost(2) +... + prob(7)*cost(7).

The question among some mathematicians is whether we need to divide this sum by 3 , ie by the number of stages.

This is the wikipedia article:
This article says that the expected value of random variable X , is equal to (p1x1+p2x2+...+pk*xk)/(p1+..+pk), where x1,x2,..,xk are the values that random variable X can take, with probabilities p1,p2,...,pk respectively.

Hence, if we assume that in our scenario tree we have one random variable X, then its expected value will be [ prob(1)cost(1)+....+prob(7)cost(7) ] / (prob(1) +....+prob(7) ) .

What are your opinions on this ?


answered 27 Sep '14, 03:25

spyimp's gravatar image

accept rate: 0%

edited 27 Sep '14, 03:27

If there are 7 different outcomes can occur. Then, Prob(1)+...+Prob(7) = 1 . 'Dividing by 1' means nothing.

The reason that Wikipedia shows ..../(prob(1)+..+prob(7)), is to show that expected value is nothing but weighted average using probability as weight.

What you saying is, at the first stage, there will be a cost(1) and then it can go to 2 or 3, and at second stage you will pay cost(2) or cost(3). and keep going. right? This example has only four different outcomes. 1-2-4,1-2-5,1-3-6,1-3-7.

Yes, then your total sum of weights will be 3. So, you should divide it by 3 if you want to get average cost per stage. First stage probability would be 1. For total expected value , no need to divide by 3.

Or if you want you can calculate cost in different way, four possible paths.

For example, path 1, 1-2-4, cost(path1) = cost(1)+cost(2)+cost(4)

And then you can use what you know without dividing by 3.

The answer of your example would be Cost(1) +0.5Cost(2) + 0.5Cost(3)+0.25Cost(4)+0.25Cost(5)+0.25Cost(6)+0.25Cost(7)

This is the same as 0.25 x (cost(path1)+cost(path2)+cost(path3)+cost(path4)).


answered 27 Sep '14, 04:16

ksphil's gravatar image

accept rate: 14%

edited 27 Sep '14, 04:44

Well, Prob(1)+...+Prob(7) = 3, and not 1. It is prob(1) = 1 , prob(2)= 0.5 , prob(3) = 0.5 , prob(4) = 0.5*0.5=0.25 = prob(5) = prob(6) = prob(7).

How did you come up with the Prob(1)+...+Prob(7) = 1 ?


answered 27 Sep '14, 14:10

spyimp's gravatar image

accept rate: 0%

I know that Prob(1) = 1, Prob(2) =0.5, Prob(3) =0.5, Prob(4)=0.25 and so on.

That's why it is confusing, I guess.

Usually, the sum of all probabilities is 1. No need to worry about dividing by some number.

IF there is 7 different possible outcomes BY ONE RANDOM EVENT, Prob(1)+..+Porb(7) =1.

Your description of the problem seems there are 7 possible outcome and sum of all probabilities is 3.

I would say that is not wrong, but, it is confusing way.

Again, you problem has 4 possible outcomes. path1, path2, path3, path4 if we consider that it happens by one random event.

Or it is like this every stage you toss a coin, stage 1, no matter what, you pay cost(1), and then toss the coin again, head: cost(2), tail: cost(3), and then toss it again.

Then, how many times did you toss the coin? Three times. (that's why you get 3 as sum of probability) There are three random events.

But, Total Expected cost is the sum of the results of three coin tosses(random events).

Total expected cost = Expected cost of stage 1 + expected cost of stage 2 + expected cost of stage 3 (apply expected cost three times)

or Total expected cost = prob(path1)x total cost of path1 + prob(path2) x total cost of path 2 + prob(path3) x total cost of path 3 + prob(path4) x total cost of path 4 .


answered 27 Sep '14, 14:40

ksphil's gravatar image

accept rate: 14%

edited 27 Sep '14, 14:53

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported



Asked: 25 Sep '14, 19:32

Seen: 1,326 times

Last updated: 27 Sep '14, 14:53

OR-Exchange! Your site for questions, answers, and announcements about operations research.