Matrix chain multiplication

Following on from supervisions this week, I was wondering about Examples Sheet 1, #1 and the running time of dynamic programming. I found this wiki article about Matrix chain multiplication
https://en.wikipedia.org/wiki/Matrix_chain_multiplication

The article explains how a naive application of dynamic programming results in a run-time that is exponential in the number of matrices, $n$, which is very slow and impractical. That is what I asked about in the examples sheet. However, by remembering partial results, so that the same thing is not computed more than once, the run-time can be reduced to $O(n^3)$. By reducing the problem to one of polynomial triangulation the running time can be made $O(n\log n)$.

Lecture 7

The Gittins index theorem is one of the most beautiful results in the field of Markov decision processes. Its discovery and proof in 1974 is due to John Gittins. The proof I have given in today's lecture is very different to Gittins's original proof. It the simplest way to prove the theorem and was first presented in On the Gittins index for multiarmed bandits. Ann. Appl. Prob. 2, 1024-33, 1992. Proof is pages 1026-27.

For today's lecture I presented some slides on the Gittins Index. You may enjoy looking through the entire talk. It will look better if you download the .pdf file to your computer and read the presentation with a .pdf viewer such as acrobat, rather than try to read within your browser.

The proof of the Gittins index theorem is entertaining, but non-examinable. I would expect you only to know what we mean by a SFABP, the statement of the Gittins index theorem, and how to calculate the indices in simple examples. I thought you would enjoy seeing this beautiful result and how it can be proved. Lectures 1-6 have covered everything you need to know in order to understand the Gittins index. Today's lecture has also been an opportunity to revise ideas that we already met in problems on job scheduling and pharmaceutical trials. 

The prospecting problem in 6.5 and Weiztman's Pandora's boxes problem in 7.5 are really the same problem, and a simple example to which the Gittins index theorem provides the answer.

Lecture 6

Today we looked at some stopping problems. Many problems are like this. They are present in financial mathematics in the theory of option pricing (Black-Scholes). The holder of an American option is allowed to exercise the right to buy (or sell) the underlying asset at a predetermined price at any time before or at the expiry date. The valuation of American options is essentially an optimal stopping problem.

You can read more about Bruss's odds algorithm in his paper: "Sum the odds to one and stop" Annals of Probability, Vol. 28, 1384–1391, (2000). I showed you  how to use this to address the Secretary Problem. A very interesting related problem is the "last arrivals problem". Consider a shopkeeper who would like to go home early just after he has served the last potential customer of the day.

I will say more about the mine prospecting problem of Section 6.5 next time.

Let me finish with some hints about questions on Examples Sheets 1 and 2. Question 6 on Sheet 1 can be solved by realizing that there are only two stationary Markov policies. You simple need to decide which is best. Question 7 is a simple stopping problem that can be solved using a OSLA rule. Question 8 is tricky. You should use Theorem 4.2. 

Question 9 on Sheet 1 is important because it should convince you that it is possible to solve stochastic dynamic programming equations using linear programming (at least if both state space and action space are finite.)  It there are $n$ states and $m$ actions (controls) available in each state then we will have an LP in $n$ variables, with $nm$ linear inequality constraints. 

When on sheet 2 you do Question 1 you might think about using Bruss's Odds Algorithm. Although you cannot apply the algorithm directly, you should be able to solve this problem using the same scheme of proof as we used to prove the optimality of the odds algorithm in this lecture.