Everyday I (and probably everyone else) am faced with decisions that we have to make, some of them are small, some of them are big. At least for me there are two aspects governing the decisions I want to make. I want to make the best decision and I am making the decisions without knowing everything. This is exactly what stochastic optimization and what I work with in my daily job.
But now I have found a really good example from real life which I am facing often and which have some really interesting characteristics. It involves something I know that several people have been thinking about when walking in a city: How can we come from point A to point B in the most effective way.
I wont be getting into details of how to formulate any of this in a mathematical setting. You can find lots of text books on that. I just want to introduce you to some of the concepts and ideas of it.
The problem and the assumptions
I often have to walk from a parking lot to the shops in the city where I usually shop. I can choose two routes as you can see on the attempt to draw an image to the left.
From the parking lot I start by having to cross the road at a t-junction. I can cross it one way or the other. In this case I assume that one of them will always be red and one of the green, and there is 50% chance of the outcome.
If I cross what would be a left move on the picture, (route 2) then I can walk almost to the shop and then I have to cross another road. Once again I will assume that there is a 50% chance of a red light and 50% chance of the green light.
I will also assume that there are no correlation between then two traffic lights, so even if the first one is green to the left, then there is still a 50/50 chance of the second light being green.
If I cross upwards from the start to choose route 1, then I wont have to cross another road and I can just stroll leisurely to the shops that I need to go to.
In my mind either route is a good choice, one of them might be a bit longer but the other one is a bit hilly, so the two are comparable. So the goodness of the decision is affected only by the state of the traffic lights. And I don’t like to wait, so I really want to minimize the waiting time.
So which way do I choose?
Making a decision before leaving the car
Let us assume that I am the kind of guy that likes to make a plan and then stick to it. So even before I leave the car I would like to know which route I should take. How do I make this decision?
If I knew the state of both traffic lights when I would arrive at them then it would be pretty easy to make a decision. However I don’t have that knowledge, but I have to make a decision anyway. So I will base my decision on the expected value of the traffic light. The formula for the expected value tells us to sum up the value of the event times the probability of that event happening. We are trying to count the number of red lights, so let us assign the value 0 to a green light and the value 1 to a red light.
In this case the expected value of route 1 is
So does that mean I will face 0.5 red lights? Of course not. I will meet 0 or 1 red lights. But, if I walk this route an infinite number of times, then I would hit a red light 50% of the times.
The calculation for route two is a bit more complex, since we have two events. However we can just enumerate every case, which is both lights are green, first light is green, second is red, and so on. And since the two events are uncorrelated then the total probability is just the probaility of one event times the probaility of the other event. This gives us the following table
|Scenario||Value||Probability first||Probability second||Total probability|
|First green, second red||1||0.5||0.5||0.25|
|First red, second red||1||0.5||0.5||0.25|
Which in turn gives us the expected value
Meaning that on average I will face 1 red light if I go that way.
So if I make the decision in the car then the choice is pretty obvious. I should pick route 1. There is a chance that I will meet a red light, but the chances that I walk straight to the shop is bigger than with route 2.
Delaying the decision
I can tell you that I do not plan this kind of things. I usually make the decision at the first traffic light. In that case I know the state of that traffic light and as we shall see my decision will now depend on the state of this light.
Scenario 1: Green to route 1
If the light is green to route 1 I think most of us can see that in this case I can just cross and walk straight to the shop without stopping. If I choose route 2 I will certainly face at least one red light and possibly 2.
Scenario 2: Red to route 1
The interesting decision comes when it is green to route 2. Should I choose that, or should I wait for the green light to route 1? In this case I will let the expected value decide for me again.
Route 1 has no uncertainty I will surely face 1 red light and that is the expected value. Route two has a second unknown light with a 50/50 chance of being green. So in this case I will have an expected value of 0.5. Or in other words there is a good chance that I am better off by choosing route two.
In this case there is a 50% probability that I will face 1 red light even though I choose route 2 and thereby wont be better off than having picked route 1. But on the other hand there is also a 50% chance that I will be better off.
I will wrap up for now. I hope this gave you a bit of an introduction on how we can make good decisions even if we don’t know everything. As long as you know the probabilities you can make decisions by using the expected value and then say something about the likelihood of you making a good decision. Even though I haven’t mentioned it until now, this field of mathematics have very strong ties into the financial world, where every investor is faced with a decision of buying stocks or other financial instruments without knowing the future outcome of the decision.
I will post something later on about risk. Something we can introduce in this example as well, and something which has strong ties into the financial world as well.
The blog post image was taken by Tilemahos Efthimiadis and shared under the Creative commons license.