RK's Musings

The Age of Big Data

Via TP:

What is Big Data? A meme and a marketing term, for sure, but also shorthand for advancing trends in technology that open the door to a new approach to understanding the world and making decisions. There is a lot more data, all the time, growing at 50 percent a year, or more than doubling every two years, estimates IDC, a technology research firm. It’s not just more streams of data, but entirely new ones. For example, there are now countless digital sensors worldwide in industrial equipment, automobiles, electrical meters and shipping crates. They can measure and communicate location, movement, vibration, temperature, humidity, even chemical changes in the air.

Link these communicating sensors to computing intelligence and you see the rise of what is called the Internet of Things or the Industrial Internet. Improved access to information is also fueling the Big Data trend. For example, government data — employment figures and other information — has been steadily migrating onto the Web. In 2009, Washington opened the data doors further by starting Data.gov, a Web site that makes all kinds of government data accessible to the public.

Link : Big Data

Zipf’s law

An old NY Times article on the surprising ubiquity of Zipf’s law :

---

Math and the City

One of the pleasures of looking at the world through mathematical eyes is that you can see certain patterns that would otherwise be hidden. This week’s column is about one such pattern. It’s a beautiful law of collective organization that links urban studies to zoology. It reveals Manhattan and a mouse to be variations on a single structural theme.

The mathematics of cities was launched in 1949 when George Zipf, a linguist working at Harvard, reported a striking regularity in the size distribution of cities. He noticed that if you tabulate the biggest cities in a given country and rank them according to their populations, the largest city is always about twice as big as the second largest, and three times as big as the third largest, and so on. In other words, the population of a city is, to a good approximation, inversely proportional to its rank. Why this should be true, no one knows.

Even more amazingly, Zipf’s law has apparently held for at least 100 years. Given the different social conditions from country to country, the different patterns of migration a century ago and many other variables that you’d think would make a difference, the generality of Zipf’s law is astonishing.

Keep in mind that this pattern emerged on its own. No city planner imposed it, and no citizens conspired to make it happen. Something is enforcing this invisible law, but we’re still in the dark about what that something might be.

Many inventive theorists working in disciplines ranging from economics to physics have taken a whack at explaining Zipf’s law, but no one has completely solved it. Paul Krugman, who has tackled the problem himself, wryly noted that “the usual complaint about economic theory is that our models are oversimplified — that they offer excessively neat views of complex, messy reality. [In the case of Zipf’s law] the reverse is true: we have complex, messy models, yet reality is startlingly neat and simple.”

After being stuck for a long time, the mathematics of cities has suddenly begun to take off again. Around 2006, scientists started discovering new mathematical laws about cities that are nearly as stunning as Zipf’s. But instead of focusing on the sizes of cities themselves, the new questions have to do with how city size affects other things we care about, like the amount of infrastructure needed to keep a city going.

For instance, if one city is 10 times as populous as another one, does it need 10 times as many gas stations? No. Bigger cities have more gas stations than smaller ones (of course), but not nearly in direct proportion to their size. The number of gas stations grows only in proportion to the 0.77 power of population. The crucial thing is that 0.77 is less than 1. This implies that the bigger a city is, the fewer gas stations it has per person. Put simply, bigger cities enjoy economies of scale. In this sense, bigger is greener.

The same pattern holds for other measures of infrastructure. Whether you measure miles of roadway or length of electrical cables, you find that all of these also decrease, per person, as city size increases. And all show an exponent between 0.7 and 0.9.

Now comes the spooky part. The same law is true for living things. That is, if you mentally replace cities by organisms and city size by body weight, the mathematical pattern remains the same.

For example, suppose you measure how many calories a mouse burns per day, compared to an elephant. Both are mammals, so at the cellular level you might expect they shouldn’t be too different. And indeed, when the cells of 10 different mammalian species were grown outside their host organisms, in a laboratory tissue culture, they all displayed the same metabolic rate. It was as if they didn’t know where they’d come from; they had no genetic memory of how big their donor was.

But now consider the elephant or the mouse as an intact animal, a functioning agglomeration of billions of cells. Then, on a pound for pound basis, the cells of an elephant consume far less energy than those of a mouse. The relevant law of metabolism, called Kleiber’s law, states that the metabolic needs of a mammal grow in proportion to its body weight raised to the 0.74 power.

This 0.74 power is uncannily close to the 0.77 observed for the law governing gas stations in cities. Coincidence? Maybe, but probably not. There are theoretical grounds to expect a power close to 3/4. Geoffrey West of the Santa Fe Institute and his colleagues Jim Brown and Brian Enquist have argued that a 3/4-power law is exactly what you’d expect if natural selection has evolved a transport system for conveying energy and nutrients as efficiently and rapidly as possible to all points of a three-dimensional body, using a fractal network built from a series of branching tubes — precisely the architecture seen in the circulatory system and the airways of the lung, and not too different from the roads and cables and pipes that keep a city alive.

These numerical coincidences seem to be telling us something profound. It appears that Aristotle’s metaphor of a city as a living thing is more than merely poetic. There may be deep laws of collective organization at work here, the same laws for aggregates of people and cells.

The numerology above would seem totally fortuitous if we hadn’t viewed cities and organisms through the lens of mathematics. By abstracting away nearly all the details involved in powering a mouse or a city, math exposes their underlying unity. In that way (and with apologies to Picasso), math is the lie that makes us realize the truth.

---

Pricing the Future : Summary

Any book that promises a journey spanning 300 years is bound to focus on events that / people who made the maximum impact for the development of option pricing formula. If one were to pause and think about the option pricing formula, one would come up with questions like

• Pretty naïve question to start with, Why is there a need for options, in the first place? How were the traded historically? Were they precursor to some other instruments?
• What factors drive option prices? Can one mathematically pin down a few factors, assuming others are constant?
• Option by default depends on the movement of the underlying security. So , how to mathematically describe the underlying security?
  • Should one form an equation for the price?
  • Should one form an equation for price increments?
  • Should one assume a discrete process or a continuous process, after all traded price series is a discrete time series?
• Given a specific process for the underlying security, How does one go about figuring out the price of option?

This book in a way traces all the developments leading to Black Scholes equation like the Brownian motion, Ito’s calculus, Kolmogorov forward and backward equations,etc. and leading up to the most important idea of option prices, “replication”. Each of these ideas are described chapter wise. Let me summarize briefly, the chapters in this book.

Flowers and Spices

The book starts off describing Tulip mania of 1630’s and the reason it talks about Tulip mania is this : It was the first instance when government, in order to come out of a crisis, converted forward contracts to options contracts. The chapter then talks about Dutch East India company that dealt in Spices. The history of this company is closely linked to the emergence of the first formal market for options. Dutch East India company (VOC) became a powerful company in Netherlands just a few years from its inception. The shares of the company became valuable and a futures market emerged. Subsequently to cater to various kinds of demands, options market emerged for VOC shares. VOC finally got bogged down in corporate politics, corruption and became bankrupt. The period of 1680s was also the time when there was a need for communicating to general public about the ways to trade and understand options. To clarify the various terms and mechanics of options, Joseph de la Vega wrote extensively in his book,“Confusion of Confusions”. De la Vega was the first to describe in writing the workings of the stock market, in particular the trading of options. His work is held at such a high esteem that, since the year 2000, the federation of European Securities exchanges sponsor an annual prize for “outstanding research paper related to the securities markets in Europe”.

In the Beginning

This chapter contains some important developments that happened in the financial markets between 1694 and 1885.The chapter starts off in 1694 with John Law advising French king on restoring the financial stability of the country. John Law started a firm in France that printed paper money. It was the first attempt in Europe to replace metal coins with paper money as legal tender. The bank, forerunner of France central bank, guaranteed that the notes would always be worth as much as the metal coins on which they were based. Law also convinced the king to grant him powers for a natural resource trading company so that he can bring in more revenues in to the country. Law's company became very popular and there was a mad scramble amongst people to buy shares of the company. Like any bubble, the printing machine idea flopped by 1720 and France was facing an imminent financial disaster again. However the taste of trading and speculation activity that Law gave to French citizens was still in full force. Unofficial trading of various other instruments increased. So, finally in 1724, the government decided to bring some order in to this situation and an official Bourse was created. The whole system ran well until the French revolution in 1789 after which chaos ensued. There were few more developments that lead to the reopening of Paris Bourse and this time everybody was allowed to trade. Again forwards were outside the regulation but it did not stop the increasing volumes in the instruments and soon became the hub of speculators. Also with the collapse of a big investment bank, France went in to a recession. Out of all these developments, there was one positive development,legalization of forward market in 1885.

From Rags to Riches

This chapter talks about the life of Jules Regnault. It is a classic rags to riches story. Why is the story relevant to the book or options pricing ? Well, Jules Regnault was the first person at least as per the book who deduced square root of time law. He not only tried proving it using math, but also used the law in the stock markets to retire rich. He started his work life at the age of 23 as a broker assistant. His living conditions were miserable but he managed to improve his living conditions by working hard in the broker's office. Regnault was the first person to try to understand the workings of the stock exchange in mathematical terms, and his explanations had all the trappings of a scientific theory. Regnault managed this with hardly any formal education system. After a full day's work at the Bourse, he would sit in a small room under the attic and do quant. Truly inspiring life. Remember this was in 1860s and he was investigating concepts such as random walks, role of information in stock markets, useful/harmful sides of speculation, insider information, factors that drive the valuation of an instrument, ways to calculate fair value of an instrument etc. An admirable quality about Jules Regnault's life is that he never shied away from applying things in the stock market. He used all his principles at the Bourse and retired at the age of 47 after making a ton of money. In one sense, Jules Regnault can be called the first quant who made a fortune in the market.

The Banker's Secretary

In any introductory book on options theory, you are likely to see payoff diagrams for various options and option strategies. This chapter talks about the first person to use these diagrams for communicating option positions, Henri Lefevre. Lefevre was a personal secretary to business tycoon James de Rothschild. Lefevre did not participate in speculation or trading activities but was a keen observer and educator of markets. He published various books and articles, thanks to the fact that he was a secretary to Rothschild and could influence the publishers. He made two main contributions to options theory. First contribution was his mental model of comparing economy and the flows of capital and goods with the human body and its organs. In Lefevre model of economy, stock exchange is like the heart that keeps blood moving through the veins, government is like a brain that thinks, combines and regulates the flow, Speculation is like the nervous system that provides the momentum that keeps commodities and capital in continuous motion. His second contribution was in 1873 and 1874 through his books. In those books he introduced a method of analysis that we are all familiar with, the pay off diagrams. The pay off diagrams for individual options might be very simple and a use of such a diagram to explain things could be a stretch. The real power of payoff diagrams comes in to play when you are analyzing a set of option positions. The final payoff diagram for a set of option positions, at once provides the price ranges where the entire position makes or loses money. Lefevre's method and his extensive publications in the form of books , papers, articles, etc. helped the common masses understand options and options based investing in a better way.

The Spurned Professor

Louis Bachelier

The study of financial markets began in earnest at the turn of twentieth century. The first underpinnings of a mathematical theory were developed in the doctoral thesis of a thirty-year-old French student , Louis Bachelier. In 1900 Bachelier defended his PhD thesis and the committee composed on Poincare, Appell and Boussinesq awarded the thesis as “somewhat better than okay”. This evaluation haunted Bachelier through out his life as he could not secure a faculty position without a “real distinction” on his PhD. One of the reasons for Bachelier's theory not getting attention was that it was incorrect. He analyzed price movements as a specific random walk ( an Arithmetic Brownian motion ) which allowed for stock prices to take negative values. So, the thesis that was probably the first step towards a mathematical treatment of financial markets lay dormant for a long time.

Botany, Physics and Chemistry

The first observation about the jiggle movement of particles was by a Dutch Scientist Jan Ingenhousz. However the credit goes to Robert Brown for the name. I find Robert Brown's life very inspiring. He made use of his free time and did all the observations and work after work hours. He never socialized or dined out. Basically he was a guy who kept to himself and did outstanding work. He observed that Brownian motion never ceases though he never knew the reason for Brownian motion. Remember this was 1827 and molecular/atomic theory was not established. Then came along Einstein , aptly named as the father of atomic theory. He hypothesized and predicted the Brownian motion behavior. He also formulated the square root law by clarifying that one must not analyze a single drunkard's walk but an ensemble of drunkard walks. In 1906 Marian Smoluchowski , another scientist made important contributions to understanding Brownian motion when he postulated that , the observed jittery motions are the displacements due to the unobservable zigzag movements that are a result of huge number of impacts. He concluded this after analyzing the speed of the particles at various resolutions. He saw that the velocity of the particles increased at higher resolutions. This made him conclude that whatever action that is seen in the microscope is basically the displacement. This book provides a fantastic analogy to Brownian motion which one will never forget after reading once. The books says it in a beautiful way:

Imagine the dance floor of a studio. Flashing strobe lights highlight the seemingly jerky movements of the dancers, Of course, even the coolest dancers do not disappear in to thin air between the flashes. They move contiguously through time and space, but their movements are hidden during the dark periods between flashes. In fact, there could be different dance steps that give rise to identical positions during the strobe flashes. This is the key point. Particles pushed around by the molecules in a liquid describe a continuous path, and the jerky motion we see under the microscope is just a sample of the entire movement.

In the next chapter, the book gives an account of Norbert Weiner's life who proved that even for the jerkiest observations, it is practically certain that continuous paths exists which give rise to them. Typically these historical developments give so much meaning to what one gets to read on a pure mathematical text on Brownian motion. Brownian motion is continuous. “Oh! ok! ” was my first reaction when I studied stochastic calculus. However books such as these give so much context to mathematical properties that learning math becomes that much more interesting.

Disco Dancers and Strobe Lights

It was in 1880 that physicist John William Strutt discovered random walk in a completely different context, super imposition of waves of equal amplitudes, equal periods but random phases ? He came to the conclusion that amplitude was proportional to the square root of number of vibrations( variant of square root rule). Thorvald Nicolai Thiele, another scientist also worked on the random walk , while developing concepts in computational techniques. He used Gauss method of least square to conclude that an ensemble of particles following random walk would have an average displacement proportional to the square root of number of steps. Some 80 years later, this was picked up by another scientist Kalman and today we know a ton of applications of Kalman filter. Karl Pearson, the famous statistician added in a bit with his article in “Nature” magazine. Despite all these efforts, Brownian motion was not on sound mathematical foundation. It was Norbert Weiner who formally defined the process, proved its existence in a 40 page paper in 1923. In 1948, Paul Levy, considered as the founding father of probability theory , defined and constructed another class of random walks called Levy processes. In the last 60 years, more and more scientists studied various classes of random walks such as reflecting random walks, loop-erased random walks, biased random walks, random walks with drifts etc. In 2006, the prestigious Fields Medal, the Nobel prize equivalent in mathematics, was awarded to a French mathematician, Wendelin Werner, for his work on random walks.

The Overlooked Thesis

Regnault had brought Statistics , Lefevre Geometry and Bachelier Calculus to understanding options. This chapter highlights some of the important elements of Bachelier's PhD thesis that shows how the thesis was so far removed from the traditional way of analyzing finance. The section mentions the following from the thesis

• The thesis referred to the efficient market hypothesis and formulates the mathematical equivalent of the same.
• It departs from the tradition of describing economic phenomenon verbally and uses mathematical equations to describe things.
• It showed that fluctuations of the stock price around true price follows Gaussian distribution.
• It showed two justifications for the square root of time law.
• It used Fourier methodology to derive heat equation in the context of price probabilities
• It showed that Options value depends on the security's volatility and time
• It used reflecting principle to reduce the complexity involving Brownian motion calculations.

One of the offshoots of Bachelier thesis was Chapman-Kolmogorov equation that ties in the probability distribution of a variable at the end of a discrete Markov chain to its intermediate probabilities. Books such as these should be made required reading for a student before he/she gets exposed to math relating to Brownian motion. If you learn square root of time law using math and with no prior exposure to the rich history behind the development, you might learnt it but not appreciate the beauty that lies behind it. Similarly you might prove that Brownian path is nowhere differentiable but you will feel the result in a completely different way after reading Theoder Svedberg experiments about calculation of velocity of particles. All said and done, I strongly believe that historical developments about concepts/formulas are very important, sometimes more important than merely knowing a few ways to derivation of Black-Scholes equation.

Another Pioneer

Developments in science tend to be non-linear and controversy laden. Examples of plagiarism accusations are rampant. In such a context, it is but obvious that option pricing formula also has , in its history , some people whom we can only speculate that, they knew about a way to value options much before anyone else. One such individual mentioned in this chapter is Vincenz Bronzin. His work was accidentally discovered by Swiss historian Wolfgang Hafner, who later sent it to Prof Zimmermann. Both concluded that Vincenz Bronzin work in early 1920s had all the necessary math and concepts relating to pricing an option and in fact Bronzin’s work ends up deriving the same formula as Bachelier's. The fact that his work was never popular/ recognized shows that historical development of any concept is tough to attribute to individuals. You never know that some person who never published stuff might have known the concept right through. Vincenz Bronzin work on option pricing was so advanced that some of the concepts looked similar to what the final Black-Scholes formula looked like, decades later.

Measuring the Immeasurable

I loved this section where various historical figures are mentioned in the development of probability and stochastic processes. Firstly, what has a stochastic process got to do with pricing of options. What's wrong with using / trying to use a deterministic process ? Well, the basic difference between a stochastic process and deterministic process is, in the latter case you can pin point the result and in the former case, you can only get a probability distribution for the result. So, all diffusion processes, arithmetic random walks and geometric random walks are all nothing but a way to summarize the particle movement and any computations on it will likely result in a probability distribution. Ok, let me get back to summarizing this chapter. This chapter talks about Kolmogorov, the father of modern probability. Picking on one of the Hilbert's 23 problems that were announced in 1900, Kolmogorov developed a full-fledged axiomatic theory of probability in 1933. In doing so, he heavily relied on the works of Henri Lebesgue, George Cantor and Bachelier. Henri Lebesgue is credited for his revolutionary method of integration called the Lebesgue Integration that is applicable to a wide range of functions and sets of points. Lebesgue benefited from Cantor's work on real line and introduced the concept of measure. Well , the development of Lebesgue integration is  in itself is a fantastic story and “The Calculus Gallery” covers it in a splendid way. Kolmogorov also derived Fokker Planck equation in his monograph, unaware that the PDE was developed in 1913 and 1914 by two physicists Adriaan Fokker and Max Planck to describe the time evolution of a variable's probability distribution. The variable could be a particle's position in a fluid or distribution of stock price. I liked this section because of a nice analogy that gives the difference between Chapman Kolmogorov and Fokker Planck equation. I love analogies as they are the first things that come to your mind than the raw equations. I paraphrase the author's words here

The Chapman-Kolmogorov equation gives the probability of jumping from A to Z by investigating the probabilities for two consecutive jumps, say from A to P and then from P to Z, or from A to Q followed by a jump from Q to Z, and so on. It is like driving from New York in any direction and ending up in San Francisco. What are the chances of that happening ? Well, you could drive via Dallas, Texas, Via Witchita, Kansas, via Rapid City, South Dakota or via any other route. The probability of ending up in San Francisco is then computed by adding the probabilities of all possible routes. This is what the Chapman-Kolmogorov equation does. The Fokker-Planck equation goes one step further. It develops the whistle stop tours in to a distribution of probabilities of ending up anywhere on the West Coast, be it San Francisco, Santa Barabara, Los Angeles, or Tijuana, Mexico

After formulating the PDE, Kolmogorov found that the solution to the PDE was Chapman-Kolmogorov equation. He then turned the situation around: starting with a parabolic PDE, he pondered on the question whether it had a solution. If the answer was yes, then the solution could be none other than the Chapman-Kolmogorov equation. Thus he proved that Chapman-Kolmogorov equation indeed existed and was not merely a figment of imagination. Further development was needed in this area as there were strict conditions that one had to impose on Kolmogorov's PDE describing Brownian motion so that it had a solution.

Accounting for Randomness

Kiyoshi Ito

This section talks about the contribution of Kiyoshi Ito. Since the Brownian motion is jagged and jittery at any resolution, one can't calculate the velocity of the particles, as Marian Smoluchowski concluded in 1905. So how does one go about analyzing any Brownian path if the usual Riemann and Lebesgue Calculus cannot be applied ? Karl Weierstrass was the first mathematician who came up with such a nowhere differentiable function. How does one work with such functions? There is no way to slice the paths and handle it in the usual way. Whatever slice you look at , there will be jaggedness. What's the way out? Here is where Ito comes in. In 1942 Ito published a paper that contained the mathematical machinery to handle such functions or paths. He used Taylor series expansion and found that the first three terms of the expansion were all that mattered for a stochastic process and thus ignored the rest to come up a forecast of probability distributions. Today Ito's calculus is synonymous with “framework for handling Stochastic Differential equations”. Ito lived for 93 years and contributed immensely to field of Stochastics. In his Kyoto-Prize address, he says that he devised stochastic differential equations, after painstaking , solitary endeavors. For those who think that Solitude drives people crazy and must be avoided, Ito is a classic example of the tremendous possibilities of Solitude in life.

The Sealed Envelope

Wolfgang Doblin

This section talks about Wolfgang Doblin, a young mathematician who commits suicide while serving in the army to avoid getting killed by Germans. Before his death, he sends a sealed envelope to Academy of Paris. There is a big history behind the sealed envelopes that one can read from this section. The sealed envelope was supposed to be opened in 2040 but thankfully it gets opened in 2000. The math that Doblin sent to the academy had a framework to deal with Stochastic PDEs in such a way that one could lessen the restrictions imposed on it. Mathematicians wonder that if Doblin had not served in the army and had not met the fatal outcome, option pricing would have developed much earlier. In any case, a reader gets a glimpse in to this young genius,thanks to this book. Doblin's life revolved around math and it served as a way to get him out of his gloomy and depressing environment. Though he only had the rare hour to focus entirely on math, usually during the night shifts hidden away in the telephone station that he was guarding and that provided some heat, his preoccupation with mathematical problems alleviated the dreariness and kept him from falling in to depression In one of his letter to his professor he writes,

Fortunately, my mathematical work helps me fight despair. As I am not interested in alcohol, I do not have the luxury of getting drunk like others.

The Utility of Logarithms

Paul Samuelson

This chapter talks about Paul Samuelson who relooked at Bachelier's thesis and improvised on it. Instead of considering plain vanilla Brownian motion, Samuelson insisted on geometric brownian motion because of couple of reasons

• Share values are always positive in GBM scenario
• Price jumps, in percent, are equally distributed
• Model is in accordance with human nature, as displayed by Weber and Fechner's psychology
• Data observed on stock exchanges fit GBM than Arithmetic Brownian motion

The chapter also mentions M.F.M.Osborne, a Physicist, who claimed in 1958, that log values and not the changes in stock prices are normally distributed. He was motivated to analyze the behavior after reading the works of psychologists Weber and Fechner. This observation is the same utility argument made by Daniel Bernoulli in 1713 while solving St.Petersburg Paradox.

The Nobelists -  The Three Musketeers

  

Fischer Black – Myron Scholes – Robert Merton

The next two chapters talk about Fischer Black, Myron Scholes and Robert Merton. MIT was one of the common denominators for all the three people. Fischer Black and Myron Scholes worked together on consulting projects for financial firms and thus were aware of markets and the places where quant techniques could be applied. They developed a good working rapport as Black's forte was theory and Scholes was good at implementation. Robert Merton had worked on pricing warrants along with his MIT professor Samuelson. Warrants were similar to Options but for some technical differences. Before the trio cracked the formula, there were quite a number of scholars who came close to cracking it. In 1961, a graduate student in economics, Case Sprenkle made some headway. He assumed GBM for prices and allowed drift. But his approach was faulty as he posited that investor's utility function would be revealed in prices. Also he ignored time value of money. In 1962, James Boness another student from Chicago also attempted and improvised on Sprenkle's model by incorporating time value of money. However there were some problems with his theory as he assumed, all stocks on which the options are traded are defined to be of the same risk class and all investors are indifferent to risk. So, all attempts of Thorp, Case Sprenkle, James Boness, Robert Merton and Samuelson had shortcomings. But they all carried seeds of the eventual solution.

Somewhere in 1968 Fischer Black tried formulating the option price as PDE but faced a tough time solving the PDE. So, he filed it in his cabinet and went on with his work. However in 1969 , while conversing with his sole associate of his company, Myron Scholes, Black got a chance to start the work again. The key idea that was used in cracking the formula was “Portfolio hedging and replication” . If the option is deep in the money, then delta or the hedge ratio is 1. This means you can perfectly hedge a long call option by shorting one share of the underlying contract. If the option is not deep in the money but near ATM, then the hedge ratio is definitely not 1. It must be less than 1. If you represent the hedge ratio as x, then the combination of call and hedge position is basically a risk free portfolio growing at risk free rate. With the unknown hedge ratio as a variable, Black and Scholes wrote an equation describing option pricing.

With the PDE in hand, Black-Scholes made an educated guess that turned out to be the solution for option pricing formula. The solution to Black-Scholes PDE surprisingly did not have stock return component at all. This was totally unexpected from the prevailing notion that option price should somehow contain the return of the underlying instrument as one of its components. But Black-Scholes proved it otherwise. Robert Merton arrived at the same solution using Ito's calculus. Initially Black had a lot of difficult publishing the paper in academic journals. It was only in 1973 that Black and Scholes managed to publish it under the title,”The Pricing of Options and Corporate Liabilities”, in Journal of Finance and Journal of Political Economy. According to a study undertaken in 2006, the paper garnered 2589 citations, making it the sixth most cited paper in all of economics. In the paper they acknowledged the fact that Merton had worked out a different approach and arrived at the same solution, thus kind of validating their final solution to option pricing.

The Higher They Climb ...

This section highlights the lives of the three musketeers before the Nobel Prize award in recognition to the work. There are some people who believe that Texas Instruments was solely responsible for the tremendous marketing of Black Scholes formula by incorporating it in the module in its calculator. Traders did not need to know anything about the formula except the inputs. So, they happily traded away the options at CBOE that is today one of the biggest derivative exchanges in the world. Black joins Goldman at the age of 46 , becomes a partner with in two years and dies at the age of 56 (1995) because of cancer. Scholes and Merton land up at LTCM a fund using quant stuff to manage money. The principals get their recognition in the form of a Nobel Prize in 1997.

...The Harder They Fall

This section talks about the fall of LTCM. The LTCM bust is basically a `leverage' lesson for all money managers.If one needs to read in detail about the demise of LTCM, the book by Roger Lowenstein is spot on. This section does not fit the flow of the book.

The Long Tail

The last chapter talks about the problems behind Black-Scholes formula such as assuming volatility constant, assuming GBM that has normal distribution at it's core. The books ends by saying

So, there are pitfalls and they can and do lead to spectacular failures like the LTCM crash, crisis of 2007, demise of Lehman Brothers. But to fault Black, Scholes and Merton and their equations for such aberrations would be utterly wrong. This would be like accusing Issac Newton and the laws of motion for fatal traffic accidents.

 

Takeaway

”What risk premium should be used for option pricing” was a stumbling block for developing the option pricing formula. The answers given by Black-Scholes-Merton surprised everyone : no risk premium at all. This book traces the historical developments leading to option pricing formula and in doing so, weaves an entertaining and a gripping narration of all the mathematical developments that were a precursor to Black-Scholes formula.

How I became a Quant : Summary

The purpose of this post is to summarize the various stories mentioned in this book. This write up is a result of a marathon writing on this weekend. Actually it took more time to write than read the entire book!. In the process of summarizing, I have tried listing down some of the statements/remarks/suggestions(under the heading, learning's) made by these quants that are worth pondering upon.

David Leinweber

David Leinweber graduates from MIT and Harvard with a bachelors and PhD respectively. He lands up at RAND corporation to work on AI. After working many years on classified stuff, he moves to LISP machines Inc. Once the market turned harsh towards hardware firms, David moved to Inference Corporation, a software-only AI firm where he starts working on AI applied to finance. LISP, with its garbage collection mechanism is not really suited to real time financial trading applications. So, David goes on to start his own firm, Integrated Analytics where AI is used for stock picking. He launches, Market Mind, an AI based tool for equity trading. Soon after this startup success, he joins First Quadrant, a Quantitative investment management firm where his group starts managing $6 Billion. After First Quadrant, he starts another firm Codexa which doesn't take off. Subsequently he lands up as a faculty at Berkley.

Learning's:

• Markets are not instantaneously and perfectly efficient. Insights, and the ability to execute them rapidly in ever-faster electronic markets, will continue to be rewarded.
• There are secretive firms that consistently show up on lists of the highest-volume traders reported by the exchanges. Founders of these firms show up on lists of billionaires. Are they just the lucky typing monkeys? Are they the investment equivalent of the lady in Jersey who won the lottery three times? Probably not. They make too many separate bets, thousands every day. And they do too well, too consistently. To attribute their success purely to chance strains credulity.
• Stocks are stories, Bonds are mathematics
• The PhD quants think the technicians are essentially examining tea leaves and goat entrails. The technicians think that PhDs are hopeless geeks who wouldn't know a good trade if they sat next to it on a bus.

Ronald N Kahn

This story is about the quant Ronald N . Kahn who is generally known amongst practitioners through his popular book, Active Portfolio Management. Kahn graduates from Harvard with a PhD and joins BARRA in 1970s , a firm that was revolutionizing the area of finance at that time. Kahn learns every thing about finance and quantitative applications to finance from BARRA. It was an ideal play ground for an academic as the team mostly comprised PhDs who walked away from their own field and came to finance. One of the leaders at the firm, Richard Grinold offers Kahn to sit through his course at Berkley. Soon, they start collaborating on many projects and one of their outputs is the book on active portfolio management. After doing tons of quant work at BARRA, Kahn joins BGI, following his boss steps. His experience at BGI managing money turned out to be an equally a rewarding experience. So, in one sense Ronald N. Kahn followed the ideal path for a quant, i.e , do research for a couple of years and apply quant techniques in managing money.

Learning's:

• Undergraduates learned from their professors. But the role of a graduate student is to teach their advisor new things. I wonder if such a thing should be applied to our usual work place reviews. Imagine that a yearly review is based on, not only the contributions that XYZ makes to the firm, but also on what his/her colleagues learn from him/her over the past one year. Imagine there was strong incentive system in firms to impart skills/knowledge to coworkers. Indeed such a place would be great place to work.
• Important communication should always be in writing and limited to one page
• Success in finance would require one to acquire much more intuition and insight into the basic problems faced by investors and to build up a toolkit for analyzing those problems.
• My approach to quant finance was very different from what a formal education in this area would involve. Basically, I tried to master specific areasâlike interest rate optionsâand then branch out and master new areas, through new projects. It was a patchwork quilt approach. I hoped I could build enough sufficiently large patches that they would eventually form a substantial quilt.
• Is quant revolution over ?. Certainly much of the relevant theoretical underpinnings are in place. At the same time, there exist even today significant issues in need of rigorous quantitative analysis. Present-day debates over liability-driven investing prove that fundamental issues remain unresolved among investment professionals Other areas worthy of further research include hedge funds and, more generally, optimal leverage and shorting. Between these remaining fundamental issues and the never-ending competition amongst active managers for out performance, the need for quants has never been greater. There is plenty more to do in this challenging, interesting, and rewarding field.

Gregg E. Berman

This is the story of a quant who doesn't want to be called a quant. Quant is sometimes used pejoratively on Wall Street as in, `He is ONLY a quant'. After graduating from Princeton with a PhD , Berman realized that he was not cut out for academics. His first few jobs were at hedge funds where he wrote automated trading strategies for commodity futures and trades those strategies.In the first few years he was so fascinated by coding that he programmed even on 2 hour train daily commute. The years at hedge fund helped him understand markets, psychology of trading, the type of statistics that can be used, etc\dots He traded futures for a couple of years and did not particularly enjoy it during a bear market phase. He felt that trading was an activity where luck played a significant role in the success and his academic bent of mind, where hard work and smartness fetch results, was not accepting the vagaries of trading. He remarks,

I also found that that I had less of a stomach for the huge ups-and-downs of trading than I had previously believed. This was a hard lesson for me to acknowledge. After all, many people claim that if they just had some money to start with they could use it to make a fortune. Well, I had millions in potential capital at my discretion and was asked to do just that. But I couldn't. I very much wanted to, but I just couldn't come up with any systems or strategies that would make fortune in the commodities markets. The more I wracked my brain, the more I realized I liked the detailed analytical parts of my job much more than the trading parts

The big change in the career came when he moved to RiskMetrics and did a lot of quant work at JPMorgan. At JPMorgan he donned quit a few hats and became a true quant in Wall Streetish sense. The big takeaway from Berman's story is that quant is not a job but an attitude that one must develop, to do well in finance, and more so in today's tech driven finance.

Evan Schulman

This is the story of a quant, Evan Schulman, whose belief in efficient markets got strengthened in his initial years of work at a trust company analyzing pension accounts. After developing quant tools that helped portfolio managers focus on their stock selection , he came to believe that quantitative skills can improve trade processes, if not generate alpha. He subsequently joined Keystone group at Boston to develop quant stuff like `Implementation shortfall 'models.

After his stint at Keystone, he moved to Batterymarch and that was a key step in his career. At Batterymarch, the entire firm was working hard to lower commissions and to keep the market impact of trades to a minimum.Schulman executed the first program trade while at Keystone Funds. Lot of people on the Street know Schulman because of this first program trade thing. He not only helped computerize the firm-front, middle and back office-but also introduced an innovative trading system at Batterymarch. Schulman let brokers access its orders via computer to trade. He left Batterymarch to start Lattice Trading, a firm that offered an electronic trading product that was a forerunner to today's algorithmic trading.

What was Lattice core idea ? It was multi-broker system to allow for the fact that institutions tended to use several brokers in the conduct of business. Lattice became very popular and was bought by State Street. Evan then left to start another firm , Upstream technologies in 1999.In his earlier firm, the work was mostly for the institutional side. At Upstream, he and his co-founder Mark Hoffman decided to apply the tools, discipline, quality control to individual accounts, even the small ones. Upstream uses quant stuff to work on individually managed accounts that dominate mutual funds. As Evan remarks

Optimization is ideal for the accounts of individuals.

Today, Upstream technologies is a success story on Wall Street.

Learning's:

• A quant who believes in efficient markets can still add tremendous value to improving the investment process itself, be it on the institutional side or the retail side.
• Compound returns equal a function of the average return less half the variance. Meaning, the longer the time horizon, the greater the difference between arithmetic return and geometric return on investment
• Not all problems can be solved by throwing more bodies in to a mix. The performance and productivity of quants varies a lot. Sometimes just one or two quants can bring in radical changes to the business. I am reminded of Dragan Skoko and his tremendous contribution to the success of Batterymarch

Leslie Rahl

Leslie Rahl graduates from MIT in 1972 with a degree in Electrical engineering and realizes that she has no aptitude for circuit boards, electricity, or the mechanical facets of electrical engineer's trade. In a totally random combination of events, she lands up in Citi and spends 19 years doing trading and risk management. Starting from a job of trading options for a prop book, she starts handling interest rate trading book and eventually swap business. In 1994, she leaves Citi to start her own company, Capital Markets Risk Advisors and since then has grown her company to a decent size on Wall Street.

Her belief is that models are useful for trading and not valuation. This comes from a quant who has traded for 19 odd years , so there could be a bias in her statement. What surprises me is that she starts a risk management company where you are typically valuing something under extreme events. So, how is that she has spent the last 15 years on something she doesn't believe. Anyways, when asked how she became a quant ? , she replies ,`I was born a quant' and adds that being a quant helped her not only with solving quantitative problems, but has taught her an analytic framework for problem solving that applied equally well to non quantitative problems.

Learning's:

• It is better to run your own business / work for a smaller company/ startup than working in a big firm . When you count everything, Positives outnumber the negatives .

Thomas C. Wilson

Thomas Wilson, a graduate from Berkley and Stanford is not sure whether he would consider himself a quant or not. He believes in `asking the right question' as being crucially important than any mathematical technique. You ask the right question and then go about looking/ creating/developing/copying the mathematical techniques to solve the question. He remarks

I put on the other end of the continuum individuals whose contributions were driven more by âtheâ question, or the intuitive interpretation of the observed economic and financial phenomena, rather than by the quantitative techniques that were used to represent their intuition. For individuals at this end of the spectrum, phrasing the question seemed more important than the techniques used to find the answer. In this camp, I put such individuals as Akerlof, Stiglitz, Lucas, Diamond, and Dybvig, individuals whom I judge to have contributed more through the intuition behind the question then the actual quantitative techniques they used.Who can argue that the intuition and insights behind Akerlof âs market for lemons outshadows the relative simplicity of the algebra usedf to prove the point?

He is extremely honest in confessing that he has lesser mathematical expertise than the quants who get cited in finance papers, media. In his career, he has stumbled on three questions and has learnt/developed mathematical tools to answer the questions. In this book, Thomas Wilson lists some of the most important questions he has answered in his career.

Market Risk Era ( Early 1990's)

• Is it possible to calculate VaR for nonlinear portfolios from local risk information \verb#(e.g., deltas and gammas)#, which are readily available on the trading floor?
• How many independent factors are practically required to capture the risk of a multicurrency fixed income trading book?
• What happens to the tails of our VaR calculations if we have only estimates of volatilities and correlations and not their exact values?

Credit Risk Era ( Late 1990's)

• Do equity markets alone provide sufficient information to characterize the contemporaneous correlations between average sector default rates and migrations?
• How useful are other factors such as the level of real economic behavior as measured by GDP, interest rates as a surrogate for debt coverage, or foreign exchange rates for sectors with international competitors in explaining sector defaults and their correlations?
• Do equity markets, which react instantaneously to new information, effectively describe the autocorrelated time series properties of credit cycles?
• How can retail portfolios and large corporate exposures be integrated into the same portfolio model consistently?
• How can default only portfolio models be expanded to a mark-to-market approach comparable to market VaR?

Strategy Debate ( Late 1990's to Today)

• What are the inherent theoretical biases, and is it possible to make adjustments to correct for the biases?
• What is the appropriate cost of capital, by line of business, if capital is allocated based on the standalone risk of each underlying business? And, what role does earnings volatility play in the valuation of a bank or insurance company?

Learning's:

• Build your intuition before building your model
• Trust your intuition
• Challenge your intuition
• Be as good at your communication as you are at the theory
• The model is always wring - but that doesn't make it useless.

Neil Chriss

This is the story of Neil Chriss, known for this book `Black Scholes and beyond'. Neill Chriss received his PhD from Chicago University. In the initial few pages of this story, he gives a few reasons for leaving academia, especially leaving pure math for industry. He compares pure academic mathematicians to Explorers whereas applied mathematicians/practitioners to Mountain Climbers. Explorers take risk with out any guarantee that it will pay off. Mountain Climbers have a fixed goal, i.e the top of a mountain and thus spend their time getting there. Explorers have a different personality than Mountain Climbers, though in one's life it is very difficult to sometimes clearly demarcate one from another. In the case of Neil Chriss, he clearly says that he did not have that `passionate,ever thinking,every imagining' mathematical interest.

After his PhD from Chicago, he moves to University of Toronto to join the math department. Here he develops an interest in derivatives and writes a paper on `Option Pricing formula with volume as variable'. This paper gives way to interactions with Goldman team, mainly Derman and Kani from Quantitative Strategies group. He then ends up doing a summer job at Goldman and then receives a post doc at Harvard. However Wall Street appears more exciting to him and he lthus eaves Harvard for a job at Morgan Stanley. At Morgan Stanley, he starts collaborating with leading quants like Robert Almgren,Peter Muller etc.He finally moves to GSAM( Goldman Sachs Asset Managment) and starts managing money for the firm. He also becomes NYU Courant's math fin program director. This unique place offers him to meet many more quants like Jim Gatheral, Steve Allen, Peter Fraenkel, Nassim Taleb etc.

He ends his story with a prediction about the usage of quantitative techniques in finance. This book was written before the crash of 2008. So , the tone of the author is overtly optimistic in one sense where he predicts that quantitative asset management will dramatically change asset management business. Well, one might take that statement with a pinch of salt , after the massive beating that most of hedge funds took , in the past few years. Over all , I found the story of Neil Chriss very interesting as he has managed to do things in academia as well as Wall Street, despite declaring himself as a mountain climber. Well, he seemed to have climbed a lot of mountains to make up for not taking up a explorer's job

Learning's:

• You have to deeply care about math to become a full time mathematician( Explorer)
• Came to know of this book titled,`The Glass bead game'. Should read it someday
• You have to enjoy working with computers to become a productive quant
• Neil Chriss learnt probability , stochastic processes from scratch after joining as a faculty in math. Its never too late to learn stuff in one's life .You just have to have the right attitude.
• Take regular feedback of your work from other people
• Historically mathematicians had more interaction with the real world. Hence there is nothing to be embarrassed about leaving academics to pursue work in industry.
• Having a strong background in technology , having had the experience of writing tens of thousands of lines of code, was an advantage. To do anything largescale in quantitative finance requires good technology. Everything from the storage and retrieval of trade data to the execution of trades increasingly relies on technology that is efficient and reliable. Knowing how to build systems that work well now and can be maintained and grown is an important asset because as a business grows in complexity, the technology that drives it has to grow with it. It is all too easy to build a small system that works well but find that as it grows it grows out of control in complexity and becomes difficult to manage.

Peter Carr

After pursuing an undergraduate degree in accounting and economics from University of Toronto, Peter Carr heads to UCLA for a Phd in Finance and then follows it up with a Postdoc at Princeton.He mentions that his choice of UCLA was particularly helpful as it gave him time to pick up math and make up for his lack of formal training in mathematics.Obviously what he means by lack of enough math skills, is a relative statement. His time at Princeton proved important. His meeting with Dilip Madan changes his course of life and he heads to Wall Street and spends a successful quant career at Morgan Stanley, Bank of America and Bloomberg.His remarks about quants and quant career in general , are particularly encouraging. He remarks

Learning's:

• Although many academics think otherwise, mathematical finance is in its infancy with lots of low-hanging fruit to savor. If you want to be a quant, my advice is to see it as a calling, not a job. The money is incidental. It comes and goes. A good idea never goes away and if you are lucky, you’ll have a few before we all fade away into obscurity.
• Academics use English words to describe mathematical concepts and that one should never confuse the everyday meaning with its mathematical definition.
• Read and work voraciously to make up for a lack of formal training. Sometimes you end up doing a better job than people who are trained formally.

Mark Anson

With a PhD from Columbia University , Mark Anson proceeds to law school and then begins his career. While practicing law he realizes that his first love was always direct application of quantitative techniques and gets back to doing a quant role. One of his remarks he makes in this book, that needs to be kept in mind I guess by any aspiring quant is,

Quantitative skills are like a foreign language.The more you use the skills, the more honed they become. Conversely,failure to apply the skills on a regular basis leads to a slow dissipation

It is often that we learn some skill set/techniques in school or in a specific project and , we then move on. It is like storing something in the working memory and deleting it. Unless specific skills are put to repeated use in one form or the other, quants run a risk of losing them.

Mark Anson sees the uncertainty in the markets as a good breeding ground for sophisticated, innovative quant solutions. In the US context, he mentions that quant skills need to applied to avert the pension crisis, that will be a certainty by 2050, if nothings done in a proactive way.

Learning's:

• Be less concerned with dazzling audiences with quantitative skills or technical jargon and more concerned with understanding the empirical relationship between economic variables
• Math is a tool to apply to financial markets. You have decide whether you have to make it blunt or refined, based on the context, problem, etc.
• Traditional fundamental research will be less important in the future because the goal will not be to find undervalued stocks or bonds, but instead, to focus on financial outcomes.
• Love to embrace uncertainty as that is the reason quants are employed in the first place.

Bjorn Flesaker

Bjorn Flaseker starts off his quant story with a reference to Garbage Can Model and its relevance in a sell-side derivatives quant group. He remarks

I have personally found the Garbage Can Model to provide a useful framework for understanding and interpreting the behavior of organizations where I have worked, including, but not limited to, the importance of solutions looking for a problem, the importance of decision making opportunities, and the significant degree of randomness in actual choices made.

After doing Bachelors at Norway, he is told by his faculty members that he should look to do a PhD.Subsequently Flaseker joins UCLA for a PhD in finance. A chance attendance of a seminar on HJM model gives him a problem to work on , as a part of PhD thesis and so begins his quant journey. In his 5 years at Berkley, he meets a lot of other quant researchers (including his future wife).He subsequently moves to Illinois at Urbana-Champaign to take up a faculty job. During his stay at Urbana-Champaign, he works on various derivative models, early exercise models etc. In 1992, he gets a chance to present his work at Merill and subsequently is offered a job. His quant career begins at Merill and takes off.

Learning's:

• Collaboration matters. People matter in quant work (unlike the popular perception that quant is some lonely creature working on some arcane models)
• Revisit basics from time to time
• Make a business impact with your model from time to time. It need not be some sophisticated out of the world model. A straight forward model that solves a business problem is better than complicated pie-in-the-sky model.
• You never know when a model will become useful . In this context, the binomial trees that Flaseker worked on in the university was immensely helpful in making the first contribution at Merill

Peter Jäckel

Peter Jackel graduates with a PhD from Oxford, then ends up in a post-doc role at which point of time , he realizes that he had enough of short-term employment phase( post-doc). Typically as the post-doc position nears, one writes proposals for research grants, or looks for another post-doc position in some other university. Peter Jackel instead opts out of this race and looks out for a job in the industry. At the time of applying for these jobs, he claims that he had no knowledge of stochastic calculus, derivatives ,market knowledge etc. After a few interviews at various places, he lands up a job at Nikko securities where he is taken in as a model validation quant. He gets lucky here as he gets to meet Bruno Dupire and thus his real learning begins. In a matter of weeks, he learns about finite differencing solvers, forward Kolmogorov equations, Monte Carlo simulation techniques, and general derivatives replication theory..all the techniques that is today offered as a part of 18 to 24 month MFE program!. It is truly amazing that he learnt all of this in just a few weeks time.

Then after 17 months, Nikki securities goes through a major restructuring and he loses his job. This turned out to be another fortunate random event, as lands up in NatWest where he gets to meet Riccardo Rebanato. He learns a ton of stuff from him and implements a whole lot of model validation code. It is during this phase of life that he starts thinking about a proposal from John Wiley and sons , that he write a book on MonteCarlo methods. Well, as it turns out he was not all that interested in it except that he wanted to dispel one myth that was prevalent amongst every one using monte carlo methods, i.e Sobol numbers. There was a opinion that was taken for granted that Sobol numbers are suitable only for low dimensional problems. However Peter Jackel found that he could easily scale the dimensionality problem by using suitable initial conditions . Sobol numbers were perfect for his back testing and this lead him to write a book on MonteCarlo, that is now the staple diet of any MFE program.

After another rejig of teams at NatWest, Peter Jackel is moved to front desk where he is a part of team which builds a structured product quant library from scratch. His 3.5 years of work of coding the library taught him many more things from an implementation perspective. This is kind of reminder to any quant who doesn't want to program. The real learning of quant fin comes from programming, is the biggest takeaway from this story.

Learning's:

• Build your models transparently and to the highest standards so that you don't have to be afraid to be open about them; and bear in mind that you don't own the models you build for the company you work for- in fact, as quants, we own nothing, not even the paper we write on. We deliver a service to our employers. The company may have to share part of what we develop with other teams in the company and is at liberty to do so. The company may be obliged to share what we are doing with regulators. Always be aware that what we develop and implement may be subject to scrutiny.
• Anyone who wants to make it as a quant to spend some time in a model validation group: you get a lot more time to dedicate to analysis and learning than in the front office where there is a constant and relentless pressure for delivery of directly usable analytics
• Collaboration matters a lot in quant work
• Get the right balance between a general and a bespoke approach for any individual project
• Every thing you do as a quant is cumulative. No piece of code that you write is trivial. It will be used in some future work of yours. This also means that you should not be sloppy in your coding . Doing proper documentation matters. Following the right design pattern matters.
• Coding something from ground up is a wonderful experience and one must never hesitate to take up such a job, despite the risks that it might entail.

Andrew Davidson

This story of Andrew Davidson, is filled with the theme, `I am not a quant' in almost every other sentence that he writes. Having an undergraduate education from Harvard and MBA from Chicago, Andrew Davidson's first job was Exxon. The bureaucracy got to him and he left the firm to work at Merill and finally started his own company Andrew Davidson\& Co. The story is about Andrew's skepticism about

models used in the mortgage industry. He cites specific instances where disregarding theory sometimes better. He points at a number of places where he does not possess the skills of a true quant and infact revels in the fact that it is not needed to survive and make a successful quant career

Learning's:

• How traders and other participants describe the operation of the market, and how it truly operates, are two different things.
• A clear conceptual picture often is better solution than a mathematical model that misses a key component

Andrew B. Weisman

After graduating from Columbia with a PhD, Andrew B Weisman's takes up a consulting job with Lehmann where he immediately realizes the big gap between theory and practice.

In this book he remarks

I had my first epiphany as a quant researcher; it consisted of the fundamental realization that most of the trading that occurs on an interbank trading desk takes place on a timescale that, for the most part, defies fundamental economic analysis.In truth, longer-term market convictions based on well-structured,defensible analysis are apt to get in the way. Such speculative activity is more akin to playing Pong.1 It is primarily a reflexive activity,with the trader operating under no imperative to distinguish Margaret Thatcher from Terry Hatcher. In many cases, doing so would have been a tall order.

There is one statement that he makes which left me little surprised. Andrew remarks

The market tends to place a significant premium on complexity. Basically, one should never explain a simple concept or procedure in simple terms, or it will be robbed of its marketability. Keep the curtain firmly in place and crank the devil out of your thunder machine

Why have a curtain? Why should one not be transparent about the model ? Somehow makes me feel little uncomfortable as the above statement asks you to remain secret about your model. As long as the strategy is making money, shouldn't it be good enough to market it to clients ?

Learning's:

• Mean Variance Optimization in its plain form is dangerous and should not be used for portfolio allocation
• VaR is an ordinal measure and not a cardinal measure. It is easy to confuse between the two and sleep in peace until one day when the portfolio evaporates. Much like the thanksgiving turkey mentioned by Taleb, which until the day of its death feels good about the fact that it is being fed healthy food on a regular basis.

Clifford S. Asness

At the outset, Clifford Asness , says `Luck' has played a significant role in his success. After graduating with a PhD from Chicago, he joins GSAM and starts

working on building portfolio models as well as manging money. With in a few years with 4 models, his group starts managing $7 billion. Humbly, he attributes the good chunk of initial success at GSAM to luck. Subsequently he leaves GSAM to start AQR with a $1 Billion. The first two months of his startup are some of the worst times for the fund. The billion dollar fund loses 60% and has a huge drawdown. Subsequently Asness reins in the risk exposure of the fund and makes it a sustainable venture during the troublesome times. Rest is history. Today AQR is a huge success story with assets close to $40 Billion. In this book, Asness dispels a lot of myths surrounding quants such as

• Quants are data miners
• Quants use blackboxes
• LTCM's blowup shows the limit of Quantitative investing
• Quants are driving with rear-view mirror

Learning's:

• Being in industry, managing money does not mean, you don't publish stuff. Keep publishing articles / opinions / models regularly.
• Never be afraid to call a bluff a bluff.

Stephen Kealhofer

This is the story of a quant and an entrepreneur. Like other stories mentioned in this book, there are random events that shape this quant's story. Stephen Kealhofer's story starts off with a decision to move to Berkley as a faculty where he starts working on `default probability' models. The second significant event that happens in his life is a consulting assignment that involved developing a statistical rating model that Oldrich Vasicek had developed. This project helped him in getting in a good understanding of the practical difficulties of implementing models.The third significant event happens when he is consulted for analyzing Junk bond cases. This assignment resulted in creating a good database with variables that could be used to estimate the empirical default probabilities. The fourth significant event was meeting Mac McQuown who became the co-founder of Stephen's startup , KMV corporation. The other co-founder was the legendary Vasicek himself.

There is sometimes a myth that quants are these nerdy people who work with formulas and not good business people. Vasicek is a brilliant counter case for such a notion. Vasicek's model is something that any quant learns in his 101 course. The fact that the team was instrumental in building a company like KMV that ultimately got sold off to Moody's speaks volumes about the success quants can have in entrepreneurial ventures. Nowadays with most PhDs directly going in to quantitative money management, we might see many more quentrepreneurs . I loved this story because it actually talks about the hardships a quant startup goes through in explaining the work they do to , to established institutions and adding practical value to the business.

The fact that the trio built a company based on a model is something that any quant can take inspiration from and remind himself from time to time, that ,”One has to integrate whatever quantish stuff that he/she does with the business problem”. Pie-in-the-sky work is good but one should also focus on doing quant that is relevant to the business.

Learning's:

• Always keep in mind that model /quant work has to deliver business improvement / business value. One cannot divorce the modeling aspects of the problem from the nature of data available , nor from the business context the model would be used
• Even if you are not completely certain about it, take a position and start exploring the position. It is similar to "having a map is better than no map" situation where having a map will motivate people to explore.
• Finance is a beautiful field. It touches everything, so it is a license to explore the world
• There is more data in finance than any field I can think of. One of the many great things about markets is that they generate large amounts of high-quality data about the actions of people.
• Finance is a beautiful field. It touches everything, so it is a license to explore the world
• The path from data analysis to the implementation of business ideas is incredibly fast. In biotechnology, it is measured in decades; in finance we do it in months or even weeks.
• If you can deduce something useful, you get paid.

Julian Shaw

I found the story of Julian Shaw as one of the best quant stories in the book.

After completing a PhD from University of Toronto, Julian Shaw loses interest in pure mathematics. He takes up job at Gordon capital as he needed a better job than teaching math or computer science in his university. He has a very unique experience at Gordon capital which was populated by market makers, option traders, basically risk takers. Nobody was interested in quant stuff like risk management. Julian Shaw applies his quant skills and brings to the attention of the management of a trader using wrong vol estimates to price and subsequently trade. His work is not so well received in the beginning. However when the trader loses his money, then people start taking notice of him. But Julian Shaw sadly remarks , `Risk management's role should come before the trade goes haywire and not after'. In any case, Gordon Capital blows up and he moves CBIC, another firm where nobody wanted to listen to quant saying the positions carry a huge risk. So, Shaw leaves CBIC very quickly and through a random head-hunter call, lands up at Barclays. He then writes about a few war stories at Barclay that make an interesting read.

Learning's:

• Finance is more than just pricing models and arbitrage, more than picking up dimes in front of steamrollers and sweeping up golden crumbs. Finance is concerned with the way people organize production and distribution, which is a prerequisite for human welfare.
• The hardest part of quantitative analysis is framing the problem in the first place.Many quants aren't good at this, partly because they don't think it's their job. They want the PDE or whatever to be served up to them on a plate. Solving PDEs is a useful skill, but there is a lot of good software to do that. There is no good software for identifying options embedded in deals defined by verbose legal documents
• Most of JP Morgan quants have ditched complex multivariate stuff to simple historical simulation to capture VaR. This makes it easy to communicate to the trader. However there is an entire debate about whether VaR is good absolute measure of risk at all. Consensus is that it is merely a relative measure
• A crude but transparent risk system is more effective in practice than a sophisticated but opaque system!
• The quantitative firepower applied to problems in finance is inversely proportional to the amount of money at stake.
• Many quants from the physical sciences are too lazy or arrogant to learn some econometrics
• Unlearn two attitudes to become a good quant.
  • The first attitude is that specialization is good. Bad quants pretend they are still physicists or mathematicians or whatever; they can't be bothered learning new tricks from other disciplines, and they never learn much finance. 'If all you've got is a hammer everything looks like a nail.'
  • The second attitude to unlearn is the assumption that the failure of people to understand what you are saying proves how smart you are. In academia, one only cares what the other specialists in one's own field think. By contrast, in a financial institution nothing you do counts for anything unless you can convince the (usually) intelligent but nonmathematical people in charge to do something different from what they would have done otherwise. Despite Poincare's famous maxim that one doesn't really understand a mathematical theorem until one can explain it to the first person one meets on the street, most mathematicians can't even explain their theorems to other mathematicians! And they are proud of it!
• Quantitative finance is a craft and a trade. It is barely engineering, and it is certainly not a science. Good quantitative finance can be summed up as the art of leaving things out, plus the art of selecting the right tools.
• The test of a model is its ability to hedge a real portfolio in the markets
• One can't be an expert at everything but one does need to understand the essence of a wide range of mathematical and statistical techniques. It is rare that one needs to invent completely new techniques; usually you can find a problem with the same mathematical form, often in an apparently unrelated discipline. The art of the quant is to find appropriate tools and bolt them together to create an effective solution to the problem at hand.
• If you want to be more than a technician, you will have to learn some finance; finance is not a corollary (trivial or otherwise) of any mathematical science.
• Interview Tip : think up one money-making idea and be prepared to defend it. This will generate a lot more interest at your interview than the Malliavin calculus!
• Go through Peter Carr's FAQ's in Option Pricing Theory to see where you stand as far as understanding options theory is concerned.
• if you want to make your mark, find a really big financial problem and create a quantitative framework for dealing with it. You will need some imagination.

Steve Allen

After graduating from Columbia and NYU Courant, Steve Allen joins Chase Manhattan bank to work in their operations research department.Till then he had never worked with computers and so he taught himself languages needed for the job.The first year at Chase was frustrating for his team as there was a distinct lack of management interest in their quantitative skills. Despite the obvious discontentment in the environment, Steve Allen stuck to his job and started utilizing the time effectively. He learnt to code, take up special classes in the evenings to learn bond mathematics , interact with traders to suggest tweaks in their existing formulas, etc. Basically he kept his mind active.

Soon, things started changing at Chase when a new management comes in that is more interested in quantitative techniques.Steve then gets to use MonteCarlo simulations etc not for their finance department but to improve their operations. After spending quite a number of years in Operation research, he moves on to building an analytic and modeling support for the firm's traders and this he does it for 10 years. He self-learns differential equations, option theory and a lot of math that he never had a chance to learn. These 10 years proved to be extremely useful in Steve's career as he developed modeling + reporting skills that became valuable to Chase traders. These 10 years of effort(it reminds me of Malcom Gladwell's observation of the time to become an outlier) helped him in launching a successful risk management career.

Steve Allen's attributes his success to the environment as he says that it was environment that changed where quantitative techniques became more prominent in the area of trading and risk management. After a successful 35 year stint in the industry, Steve Allen became the program director for MFE at NYU courant. Does he think the field has become matured and there is no opportunity to be creative ? . He quips

If you want to have a good career, you had better find a way to be creative; it's unlikely that your personality will be charming enough to induce an employer to pay you well for routine performance. But I add that creativity takes many forms- it consists not just of finding some new mathematical solution but also of discovering new ways to communicate results and build consensus.

Learning's:

• Keep learning . Steve Allen's attitude can be inferred from this remark `I enjoyed an advantage in having to struggle to come up the curve mathematically. It put me in a good position to figure out how to educate others who were finding the new concepts difficult.'
• Always have a vague sense of outcome so that you don't become too theoretical, to the point that you miss the fact that you are modeling in finance-a social science.
• Crunching numbers is a good thing and it is better to show results to traders than talk about some arcane mathematical concept that they would be least likely to be interested in.

Mark Kritzman

Mark Kritzman graduates with a degree in economics and joins investment advisory department that managed asset allocation of pension fund clients. Here he comes across mean variance optimization technique that appeals to him as a method for asset allocation. He then gets an MBA from NYU to sharpen his quant skills. Post this,he moves on to the investment department of AT&T. This was a great place for Mark as he could interact with top notch people in the research team of AT&T. He moves to Banker's trust and then eventually starts his own firm.As of the book's publication, his firm Windham Capital Management , managed $30B of assets. He cites three main things that helped him develop quant skills.

1. First is AT&T research team where his one-one conversations / discussions with Bill Sharpe, Harry Markowitz, Bob Merton, Steve Ross, Jack Treynor, and Fischer Black helped him immensely in developing financial intuition.
2. Starting up a new firm gave him a ton of learnings as he had develop many applications himself
3. Contributing editor for Financial Analyst Journal role helped him get better at communicating difficult concepts in easy terms , devoid of jargon and symbolism.

Mark gives a list of problems that he solved in his quant career. The readings gives an idea of the kind of problems that one need to tackle in the industry to make a mark.

Learning's:

• Mathematical proficiency will not be sufficient to guarantee a successful career as a quant, especially as these skills become more commoditized. The successful quant should combine mathematical proficiency with an appreciation for economic and financial theory, and he or she must know which questions are really important

 

Bruce I. Jacobs and Kenneth N. Levy

This is a unique story of 2 quants who are managing billion dollar funds. These funds have close to 83 accounts totaling $9B as of 2010. If you read this story it does not sound like as you are reading the story of businessmen. If you ingore the fact that they are managing money, the activities the two quants mention in the book could as well be of 2 social scientists in a research lab.

Bruce gets a PhD from Wharton and ends up as a faculty at Wharton. He meets Ken while Ken is doing his doctoral education at Wharton. During 1970s , almost everyone in academia believed in `Efficient market hypothesis' and so Bruce ends up choosing PhD topic on the same. Bruce gets a little let down by the ivory tower thinking at academia and joins industry. He joins Prudential where he meets Ken again and this random event changes both their lives forever. Neither of them believed in Efficient market hypothesis and soon they started Jacobs Levy Equity Management in 1986. At one point in time before the crash of 2008, they were managing $20B. That's quite an achievement. From 0 to $20B in 24 years with focus on quant research is amazing. Their investment approach was based on market complexity. Their focus on Kaizen approach to quant can be inferred from their remark

Once modeled, return-predictor relationships are likely to change over time. The world is constantly evolving, and old inefficiencies can disappear, giving way to new ones. Merely tilting a portfolio toward historical anomalies does not produce consistent performance. It takes ongoing research on new inefficiencies, new sources of data, and new statistical techniques to keep an investment approach in synch with evolving opportunities.

While most of the then investment managers were using historical data, these quants believed that history was merely one realization from many that could have happened. So, they build a simulator that takes in to account possible alternate histories, alternate correlations etc and start managing their fund. They call this process `disentangling'. Well you can call it i guess, sophisticated bootstrapping, in todays world. First three years of the firm, they earned hardly anything.They did research , wrote papers and got them published. So, this is a kind of startup where founders wrote papers instead of thinking about money, sales, marketing etc. Why did they do it ? Why couldn`t they do it in academia itself? I have no answers but I guess the fact that you are in a startup makes one that much more focused on what they are doing things,than let`s say a rather relaxed university setting.

Basically they spent their first three years doing multi-variate analysis. Its actually very praise worthy that they started off doing focused multivariate analysis before even thinking of the usual stuff in a startup. Wow. these guys rock...I mean , you come across some people, who just write some ill researched trading strategy/portfolio management strategy and then start a firm, and then morph in to sales people. They come with fancy brochures and lot of ENGLISH. So, for all such people, this story should be a telling reminder that `Doing homework matters in Quant' . You just can't start a firm in a garage , build a fancy site and start pitching. Might work for other areas but definitely not for a quant shop.

In this case, the quants got their initial clients based on their published research articled on portfolio disentangling. It was difficult to convince the normal investors to put in money and so they found few pension managers willing to take that risk. Today their average account size runs in to 100 million dollars. They did a lot of research and tried them out in the market. I guess thats a big advantage of being in a smaller organization where things are nimble. They were among the first pension funds that shorted assets and soon they did a ton of quant stuff on long-short strategies and incorporated the same in to their investment strategies. With $20b in AUM, they also took time out to write three books that are popular amongst investment practitioner community. After reading this story, I was amazed what these two quants have done.

Learning's:

• Spend time in understanding concepts / techniques clearly
• Always simulate and backtest. Historical data is merely one realization
• It is possible to do extensive research even when you are managing money. So, this notion that sometimes we carry as traders being sharp , quick and quants being slow is not that universally applicable. These two quants show that managing money and doing research can happily coexist.

 

Tanya Styblo Beder

After graduating from Yale, Tanya Syblo Beber takes up a job in the M&A department at First Boston. She tries returning to Yale for a PhD but that never materializes. Instead she gets involved at a swap trading desk . After a few years at the desk, she starts a risk management consulting start up and runs it for about 13 years. Somehow this story sounds like an detailed CV rather than giving any pointers/cues for aspiring quants.

Allan Malz

Allan Malz story can be summarized in one phrase,` Being at the time place at the right time'. He was at the Fed during the Golden Age of Supervision, at RiskMetrics during and after the technology bubble, and at a hedge fund during what may prove the heyday of hedge funds. So, as one would guess, he attributes his quantdom to the way he responded to random events than anything else.

Peter Muller

Peter Muller is a star quant on Wall Street, who striked it big with his team, `Process Driven Trading' at Morgan Stanley. After graduating with a math degree from Princeton, he heads to California and ends up at BARRA, a startup that was doing innovative modeling stuff headed by Barr Rosenburg , a Berkley Professor. He meets Richard Grinold at BARRA and gets the financial intuition needed for any math nerd to make sense of the markets. Peter Muller wants to do a PhD , while at BARRA. However after attending a few classes at Berkley decides that industry provided many more interesting problems and challenges than academia. Once BARRA became huge, the start up culture was lost and Peter Muller developed Poker skills. He gets an idea of starting a fund based on BARRA's models, but applied to trading. Luckily he finds himself at Morgan Stanley and gets the authority to start a prop trading desk. And they rest is history. Peter Muller's PDT is one of the most successful trading desks in the world and nobody knows how they operate to this day. In this book, though, Peter promises to write a book someday titled,`How I became a trader ?'

Andrew J. Sterge

Andrew J. Sterge graduates from Princeton with a Phd in mathematics and heads out for his first job at CoreStates Financial Corp in Philadelphia, where he learns the first and probably the most important lesson for trading,"Cut your losses". He then joins Cooper Neff, an options trading firm where he interacts with Richard Cooper and Roy Neff, whom he calls the most important people in shaping him as a quant. Over a period of time Cooper Neff morphs in to a HFT firm and this is the place where Andrew finds the work challenging , fun and thus ends up contributing massively to the P\&L of the book. Cooper Neff gets acquired by BNP and Andrew spends another successful career in quant trading at BNP. Currently Andrew works at AQR as VP. One of his statements in the book, captures his focus and drive in becoming a successful quant trader

A big part of becoming a quant was the hunger I had to improve my life,
both literally and figuratively

This quant story is interspersed with a ton of lessons and pointers to aspiring quants and traders. Here are a sample

• Quant is not a destination but a process
• You have got to be a voracious reader of market microstructure , trading strategies , everything that is related to markets. This will give you an immense edge in trading.
• Read `The Microstructure of Securities Markets' book
• Start working and start playing with tick data. You have got to store, clean , manage, view, analyze, visualize tick data. These skills are essential to become a good hft trader.Also, It is a prerequisite for building market microstructure models.
• You cannot make yourself a successful quant with out implementation. The greatest research in the world does no good if it cannot be implemented
• Effective implementation requires a lot of courage on the quant's part.A quant must take responsibility for his work and live the P&L day to day. Handing a model off to a trading desk to then go work on another project is a subtle way a quant tries to gain a free option: Take all the credit if the model works, blame it on traders if it does not.Working every day with traders, making their pain and the firm's pain your own, and putting yourself at risk for possible failure, is your only hope if you want to be really great in this business.
• You cannot just take your backtests to a bank and ask them to give you the money. Implementation takes a Herculean effort from many people.
• Becoming a quant is most of the times a team effort
• Prices are determined by agents acting in their singular self-interest. The only way anyone knows a fair, equilibrium price has been established is for prices to overreact in both directions. I have set out to profit by making this process more efficient. In the two areas I really know anything about, options pricing and market microstructure, I read virtually every book and article published on those subjects and then find things to exploit that are not written about. Lastly, no model or mathematical insight can make money on its own. One needs a team that collectively understands every aspect of running a trading business. Becoming a quant is not an individual sport.

 

John F Marshall

This is the story of a quant who is deeply influenced by his childhood incident of visiting commodity futures trading floor. So, he does his bachelors at Fordham and then works as a commodity trader for 8 years. Subsequently, he gets a PhD and lands up in St Johns University. The highlight of Marshall's career is founding IAFE ( International Association of Financial Engineers) . They say that one wrong doing can erase all the good things that one does. In this case, even though this story is presented in this book, John Marshall was accused of insider information scam by Securities and Exchange Commission. He was accused of passing inside information about a multibillion-dollar corporate takeover to a professor at Pace University. The Pace professor, Alan L. Tucker, made more than $1 million trading on the tips in 2007, according to the S.E.C. The Justice Department convicted John Marshall and put him behind bars. Such a horrendous ending to an illustrious quant career.

---

Finally the authors of this nice collection of quant war stories:

Richard R. Lindsey

Richard R. Lindsey is president and CEO of the Callcott Group, LLC, where he is responsible for directing research activities and advisory services. He is the Chairman of the International Association of Financial Engineers. Dr. Lindsey served as the Director of Market Regulation for the U.S. Securities and Exchange Commission (SEC) and as the Chief Economist of the SEC. He was a finance professor at the Yale School of Management before joining the SEC.He has a BS in Chemical Engineering from Illinois Institute of Technology, an MS in Chemical Engineering from Berkeley, an MBA from the University of Dallas, and a PhD in Finance from the University of California, Berkeley.

Barry Schachter

Barry Schachter is Director of Quantitative Resources at Moore Capital Management, where he is responsible for risk management, financial engineering and trade analysis. He is also a Fellow of the Program in Mathematics in Finance at the Courant Institute of New York University.Dr. Schachter received an MA and PhD in Economics from Cornell University, and a BS in Economics from Bentley College.

---

Here is the summary in pdf format - Download

 Takeaway:

This book gives a nice collection of quant stories , people who have transitioned from academia to Wall Street and have made a strong case for applying quantitative skills to finance, be it managing money/ risk/ transaction costs.

Calculus Gallery : MindMap

I was going over some old folders when I stumbled on to this mind map of the book “Calculus Gallery”.  
Indeed, a picture is worth a thousand blah blah blahs.

 

Models Behaving Badly : Summary

Emanuel Derman’s book, “Models.Behaving.Badly”, gives a physicist and quant’s perspective of models Vs theories, their nature, what to expect of them, how to differentiate between them and how to cope with their inadequacies. Derman starts off by citing a few incidents from his childhood in Africa, where political models, social movement models failed badly. He then talks about the need to understand the crucial difference between theories and models, thus providing the necessary motivation for a reader to go over the book. The book is not as much as describing the precise faulty nature of all the financial models, which would be quite a stretch that it would not fit in a single book. The book is more about the kind of basic things that a financial modeler must always keep in mind and remain humble in his pursuit, always remembering that his model will always say “what something is like?”. It will never be able to answer “what something is”. Let me summarize the main chapters of this book.

Metaphors, Models and Theories

In this chapter, Derman makes the distinction between “theory” and “model”. He starts off by quoting Arthur Schopenhauer’s metaphor about sleep.

Sleep is the interest we have to pay on the capital which is called in at the death; and the higher the rate of interest and more regularly it is paid, the further the date of redemption is postponed.

In essence, this metaphor is saying that Life is temporary nonblackness. At birth you receive a loan, consciousness and light borrowed from the void, leaving a hole in the emptiness. The hole will grow bigger each day. Nightly, by yielding temporarily to the darkness of sleep, you restore some of the emptiness and keep the hole from growing limitlessly.

What is the relevance of metaphors in a book that aims to talk about models? Well, the connection is this: A language is nothing but a tower of metaphors, each “higher” one resting on a “lower” one and all of them resting on non-metaphorical words and concepts. Metaphors by default say that X is something like Y. This is similar to a Model that tells us “what something is like”. Derman then cites Dirac, who came up with a similar metaphor in physics where he pictured positron, as a brief fluctuation in the vacuum. However what grounds Dirac’s work is the Dirac’s equation. This fundamental equation when combined with the metaphor successfully predicted the existence of a particle no one had seen before. Metaphor by itself seldom qualifies as a theory.

Why do we need Models at all? Because the world is filled with quasi-regularities that hint at deeper causes. We need models to explain what we see and to predict what will occur. So, the important thing to note is that Models are a kind of proxy to the deeper causes. Whatever be the model, i.e. a Model T from Ford, a fashion Models, an artists’ Models, a weather Model, an economic Models, Black-Scholes Model; they are all a proxy to the real world which is too complex for us to understand. A model thus is a metaphor of limited applicability, not the thing itself. A model is a caricature that overemphasizes some features at the expense of others. The world is impossible to grasp in it’s entirely. We focus on only a small part of its vast confusion and here is where models come in, They reduce the number of dimensions and allow us to make a little extrapolation in that proxy world.

What is a theory?
Weather model’s equations are a model, but Dirac equation is a theory. Similarly you build an econometric model for interest rate prediction, the equations are a model, but the Newton’s equation is a theory. What’s the difference? Derman goes on to give a nice explanation to explain this difference.

Models are analogies; they always describe one thing relative to something else. Models need a defense or an explanation. Theories, in contrast are the real thing. They need confirmation than explanation. A theory describes essence. A successful theory becomes a fact. So, basically what he saying is “Dirac equation IS the electron”, “Maxwell’s’ equations ARE electricity and magnetism”. A theory becomes virtually indistinguishable from the object itself. This is not the case with Models. By default, there is always a gap between models and real thing. A Theory is deep, A Model is shallow. A Theory doesn’t simplify. It observes the world and tries to describe the principles by which the world operates. A theory can be right or wrong but it is characterized by its intent: the discovery of essence. You can layer metaphors on the top of the equations of a theory but the equation is the essence.

The chapter ends with Derman narrating his experience with the doctors. About 25 years ago, Derman went through a retina surgery and since then a peculiar problem haunts him, Monocular Diplopia (seeing double in one eye). This problem keeps recurring at random times. In 2008 he gets an acute problem in his eye and visits n number of doctors for a remedy. None of them seem to get a handle on the problem which appears like a problem relating to retina. Finally a technician cracks the problem by looking at the problem by a simple examination of the symptoms and not bringing in too many assumptions about the problem. Derman then says that this expert problem persists in many of us, who do not step back and question the assumptions from time to time. If you ask an active fund manager who has beaten the market for x number of consecutive years, he starts attributing his success to skill rather than luck/ extraneous factors. Similarly if you go and ask a passive fund manager, he might scorn at arbitrageurs, who breathe day-in day-out “the inefficient market hypothesis”. I remember something from Twyla Tharp’s book, “The creative habit”, that goes something like this: one should always consider oneself to be inexperienced in whatever they pursue. Putting X number of years, managing X number of people, executing X number of ideas, doing X number of surgeries etc should never make one feel that he/she is an expert. Because once you think you are expert, you will definitely develop some amount of fear, be it financial/psychological/ social / intellectual/ etc… however Inexperience erases fear.. One must constantly question the assumptions in a model so that one does not risk of becoming an expert in one specific area / specific type of modeling. This also means that if you are P type quant(buy side), it might make sense to develop a Q type quant model(sell side) and vice-versa, the reason being the kind of modeling that happens on the two sides are different and you never know which model might becomes useful in a particular time frame.

The Absolute

Derman talks about the nature of theories by illustrating Baruch Spinoza’s analysis of human emotions. Spinoza theory is similar to Euclid’s geometry. Euclid starts off with a few axioms and develops entire structure of geometry. Spinoza does the same with respect to human emotions. The following diagram summarizes Spinoza’s logical structure behind the theory:

This shows that Spinoza’s theory basically has three primitives, pain, pleasure and desire. There are derivative emotions like pity, cruelty etc.

In one of the blog entries, Derman gives a beautiful summary of the Spinoza theory:

That thing is called free which exists from the necessity of its nature alone, and is determined to act by itself alone. But a thing is called necessary, or rather compelled, which is determined by another to exist and to produce an effect in a certain and determinate nature.

Underlyers <==> free. Derivatives <==> compelled. Derivatives suffer passions, Underlyers have actions. Try to be an underlyer, not a derivative

What’s the relevance to the context of the book? Well, as one can see, Spinoza’s theory is not saying “something is like something”. It basically states things and shows the way world IS, or in the case the emotions ARE. Also there is also something that one can learn from Spinoza, the way to extend our inadequate knowledge. Spinoza was of the view that some of the ways to extend our inadequate knowledge was a) via particulars, b) via generalities and c) via intuition. The author gives a set of examples to show that most of breakthrough theories in science occurred via intuition that various scientists had about their inventions. Once intuition was firmly in place, ONLY then the mathematical framework was used to show it to the world.

The Sublime

Derman gives a whirlwind tour of electromagnetism and the importance of Maxwell’s intuition in development of the entire theory. Along the way Derman drives home the point that Maxwell’s equations IS electromagnetism. The theory becomes indistinguishable from the object itself. Derman also mentions about “renormalization” in physics and “recalibration” in quant’s world and says both are completely different though they seem to be connoting the same meaning. In Physics the normal and abnormal are governed by the same laws, whereas in markets the normal is normal only while people behave conventionally. In crisis the behavior of people changes and normal model fails. While Quantum electrodynamics is a genuine theory of reality, financial models are only mediocre metaphors for a part of it.

The Inadequate

This chapter is the core of the book where Derman relegates almost all the financial models to imperfect models and says financial modeling is not the physics of the markets. Like there are theorems in mathematics, laws in physics, one tends to use phrases such as “fundamental theorem of finance” etc, which actually makes no sense. Derman raises a critical question, “How can a field whose focus is the management of money and assets possess a theorem? and physics a field which deals with real life lack a fundamental theorem “.

The basic thing that every financial modeler tries to have a grip on is “value” of a security. Unlike physics where fundamental particle’s value / charge is absolute, there is nothing absolute about the value of a financial security. Value is determined by people and people change their minds. So, it does appear that whatever value that equity-research people, technical analysts, quants come up with, it is all a big fraud.

Derman rips apart the EMM / CAPM model and raises the critical question: Is EMM a theory or a model and concludes that EMM is not a theory, it is not even a good model, it is an ineffectual model. No financial theory can dictate what return an investor should expect in exchange for taking risk that too depends on appetite and varies with time. CAPM is a useful way of thinking about a model world that is quite often far from the world we live in. Derman , on the other hand, does not criticize Black-Scholes model and says that it is the closest to robustness that any model has been in finance.Why? the replication argument says that the risk premium for a stock and risk-free bond should be same as the option, an argument which is robust even though one can debate about the computation of risk premium.

The chapter concludes with a reference to the movie Bedazzled where the protagonist fails to woo the waitress in all the seven scenarios he seeks a wish for. Devil outwits in all the seven scenarios. Derman concludes saying

The difficulty of the hopeful would-be lover is the same difficult we face when specifying the future scenarios in the financial models; as does the devil, markets eventually outwit us. The devil is indeed in the details. Even if the markets are not strictly random, their vagaries are too rich to capture in a few short sentences or equations.

Breaking the cycle

In the final chapter of the book, Derman comes to the rescue of models and says that they are useful in finance because

• Models facilitate interpolation, whatever be its rudimentary form
• Models transform intuition in dollar value( example – implied vol of the option)
• Models are used to rank securities by value

And the right way to use models are by following a few rules like

• Avoid Axiomatization
• Good Models are vulgar in sophisticated way
• Sweep Dirt under the Rug, but Let Users Know about it
• Use imagination
• Think of Models as Gedankenexperiments
• Beware of Idolatry

The book ends with Financial Modeler’s Manifesto, an ethical declaration for scientists applying their skills to finance.

The Modeler’s Hippocratic Oath

• I will remember that I didn't make the world, and it doesn't satisfy my equations.
• Though I will use models boldly to estimate value, I will not be overly impressed by mathematics.
• I will never sacrifice reality for elegance without explaining why I have done so.
• Nor will I give the people who use my model false comfort about its accuracy. Instead, I will make explicit its assumptions and oversights.
• I understand that my work may have enormous effects on society and the economy, many of them beyond my comprehension.

Takeaway :

This book is a must read for financial modelers as it shows that , whatever model one comes up, it is just a metaphor. If one keeps this in mind while developing models, it is likely that at least the end result will be a vulgar but useable & practical model instead of a mathematically elegant but a totally useless model.

Markov Chains : Summary

This book by J.R.Norris is a classic reference for Markov Chains. It is unlikely that any paper on Markov chains in the recent times does not mention this book somewhere in the paper. I will try to attempt to summarize the main chapters of the book in this post.

The book starts off by saying that Markov process are random processes that don’t retain memory. When the state-space is restricted to finite or countably many, these processes are called Markov Chains. The intro gives a great clarity for any reader in listing the kind of chains that would be dealt in the book. The following gives a basic flavor of Markov chains that are dealt in the introductory chapters:

Fig 1	Fig 2	Fig 3

Fig 1 is that of a finite Markov chain with three states 1,2,3. Since the movement of the random variable is restricted to discrete states, the chain is termed as discrete chain. In Fig 2, the random variable moves from 0 to 1 after waiting for a time T(exponential density). In Fig 3, the random variable moves from 0 to 1 and then 1 to 2 and so on, but the time that the variable has to wait to jump from one state to another is a poisson process with rate lambda. The latter two chains correspond to continuous Markov chain.

A very useful diagram which summarizes a lot of terminology is the following Markov chain.

The features of this Markov chain are the following :

• {0},{1,2,3},{4,5,6} are communicating states
• {1,2,3} and {4,5,6} are closed states. These closed states are recurrent states
• {0} is transient state
• {4,5,6} is periodic chain
• {1,2,3} is aperiodic chain

All these terms become intuitively clear in the context of the above Markov chain. Clear definitions of these terms are presented in subsequent chapters. A few questions are posed for the above Markov chain so as to motivate the reader to think about ways to solve various kinds of problems that arise in this context of a Discrete Markov chains.

Chapter 1: Discrete-Time Markov Chains

This chapter forms one of the core chapters of the book and the important theorems on the following are stated and proved:

• Hitting times
• Strong Markov Property
• Characterizing recurrence and transience
• Invariant Distributions
• Positive recurrence
• Convergence to equilibrium
• Reversibility
• Long run averages

Firstly necessary terms are defined such as state-space, initial distribution, transition matrix, stochastic matrix. Using these objects, Markov chain is defined. The symbolic representation of the Markov chain essentially captures the memory-less property of the Markov chain. The chapter then introduces the method to calculate the probability of remaining in a particular state after n transitions. One of the obvious but dumb method that one can think of , is to keep multiplying the transition matrix n times and then use the initial position and this powered matrix to calculate the probability of remaining in the same state. There is a better method and this sections explains it by Linear algebra where powers of the matrix are easily calculated using diagonalization method. Basically one finds the Eigen values of the transition matrix, writes the power of matrix in terms of Eigen values and then calculates the probability of remaining in the same state after n transitions. This method is computationally efficient in finding the probability of remaining in the same state after n transitions. Once the Eigen vectors are found, any element in the transition matrix can be found by the following equation:

The chapter introduces the “class structure”, way to identify different states and categorize them. Two states are said to be “communicating” when there is positive probability to reach one from another. If a set of states are in such a way that each communicates with the other, then such a set of states are called “closed state”. A closed state is one from which there is no escape. “communicates” is actually an equivalence relation and set theory tells us that we can categorize the sets based on the equivalence relation. If there is only one single class in the chain then such a chain is called “irreducible”. If there is only a single state in an equivalence relation, such a state is called “absorbing state”. This means that if a chain enters this state, it remains there forever.

Hitting times and absorption probabilities are introduced subsequently. The first time I came across hitting times was in Marek Capinski’s book and subsequently in Shreve’s book. I could not appreciate those concepts at that time as much as I should have. Hitting times were defined and various distributions were computed, some in closed form, some using numerical analysis. I did not have the faintest clue on its application in real world, except in American options case. Years later when I was developing a pairs model, things became clear. Modeling the hitting times for the spread and estimating the parameters of the model made me realize the importance of the practical application of hitting times. This book has given me a lens to view the hitting times , i.e via Markov chain. The key takeaway from this section is that the vector of hitting time probabilities (mean hitting times) are found by solving a set of linear equations and this solution is the minimal non-negative solution. The fact that the solution is a minimal non-negative equation plays an important role in determining the solution to the system of equations involving hitting time probabilities(mean hitting times). This is showed using gambler’s ruin example and a simple birth-death chain.

Strong Markov Property is introduced subsequently. To summarize in plain English, the intention behind using “strong” is as follows: Markov property is memory-less conditional on the chain taking a particular value, at a time interval m. To expand this property to different situations, one of the first generalizations that one can think of is ,”Is the memory-less property applicable to random times, instead of a fixed time,as given in the definition of the Markov chain?”. The answer to this question is yes, but in the context of specific time variables , called, stopping times. “Stopping time “ variables are those variables whose value is only dependent on the history of the path and not based on the future of the chain. In this context, first passage time + first hitting time are defined and are used to prove the “Strong Markov Property” theorem. The theorem states that Markov property is preserved at stopping times. Ok, so what if Markov property holds good ? Well, this property gives us the flexibility to compute the entire probability generating function for the hitting times. If the chain is in state(i), the probability of hitting 0 , let’s say, can be computed by a recurrence relation and then using the condition that the set of linear equations are minimal non-negative solutions. However if one has to compute the entire set of probabilities at once, then the generating function approach works like a charm. Strong Markov property is used to come up with closed forms for the probability generating functions for gambler’s ruin and other examples. The reader can at once see the importance of the knowing generating function, as it is basically the signature of the random variable. You can calculate hitting probabilities starting from any state, you can compute the mean hitting time by simply finding the derivative of the generating function. So, the main takeaway from this section is that , “Strong Markov Property” helps in computing more general mathematical objects like generating functions which provide much more information about the hitting time probabilities.

A State in the Markov chain state space can be transient or recurrent based on the whether the probability of hitting the specific state as number of steps decreases to 0 or tends to 1. The section on transient and recurrence behavior is very important as it provides definitions for these terms, links these terms to class structure. Some of the main theorems mentioned in this section are

• Every recurrent state is closed
• Every finite closed set is recurrent
• If C is a communicating class, either all states are recurrent or all states are transient

First passage time decomposition problem given as an exercise problem is very useful to get another perspective towards characterizing a recurrent state based on probability of return in the nth step. The chapter then moves on to using the following conditions for state classification:

The above conditions are applied to random walk in 1D, 2D and 3D space so that a reader can get an idea to use the same for other situations.

The chapter then shifts to explaining invariant distributions. Invariant distributions are those distributions specific to a transition matrix that have the property of reaching a stationary value. Meaning, if you start with some random distribution of initial states, after taking infinite steps, the Markov chain starts moving across states in such a way that the probability distribution of values it takes, mirrors the invariant distribution. Or in other words, the probability of moving from statei to statej becomes constant as the number of steps in the Markov chain increases. The calculation of invariant distribution becomes easier if one chooses to use linear algebra methods. If one computes the eigen vectors for the transpose of the transition matrix and pick the vector that corresponds to eigen value 1, then the vector is nothing but the invariant distribution of the Markov chain. The chapter then introduces the expected time spent between recurrent visits to a state. This expected time is very useful in classifying the state space based on the value. If the value is finite , then the state can be termed as “positive recurrent state” and if the value is infinite , then the state can be categorized as “null recurrent state”. Thus states can be classified in transient states, positive recurrent states and null recurrent states. Irreducible chain is a chain where each state is positive recurrent state. Computation of invariant measure also leads to easy calculation of expected return times.

Another related concept discussed is the periodicity. In an irreducible chain, either every state is periodic or every state is aperiodic. Basically a state is aperiodic if one can revisit the same state for all sufficiently large number of steps. Well it is easy to definite periodic state. A state is periodic if the chain revisits the same state in a set pattern. The relevance of periodicity is that , the invariant distribution exists for a irreducible and aperiodic chain. An extremely important aspect relevant to invariant distributions is discussed, i.e, time reversibility. One of the sufficient conditions for the existence of invariant measure is “detailed balance” condition. This condition is defined and applied to a few examples. The chapter ends with proving ergodic theorem, the pivotal achievement of A.A. Markov

In real world , no one hands us the transition matrix. One ought to estimate it in some manner. Given a Markov chain realization and a set of states, it is important to estimate the transition matrix. The chapter shows an approach that is typically used in most of the situations, i.e MLE method. With MLE method, one writes the likelihood function and use the Lagrangian method to compute the transition probabilities. The problem with this approach is that the transition probabilities are not consistent estimates for transient states. Hence this approach is modified so that the transition matrix estimates are consistent.

Chapter 2 : Continuous Time Markov Chains - I

Continuous Markov chain is more involved and hence the author has decided to split the concepts in to two chapters, first being written to equip the readers with the machinery to understand continuous time processes and another chapter using this machinery to discuss continuous Markov chains. This chapter discusses the machinery needed to understand Continuous time processes.

The first thing the chapter touches upon is the infinitesimal generator or the Q matrix. This generator is defined and various properties are explored. Once this is done, the crucial link between transition matrix and Q matrix is provided using the following theorem:

 
This connection between P and Q matrix gives the flexibility of creating a Markov process at fine grid points. A few examples are provided to illustrate the computation of transition matrix given the Q matrix. The chapter then moves on to giving the first introduction to continuous-time random processes. A very important result from measure theory says that Right continuous processes can be determined from its finite-dimensional distributions. Such right continuous processes are chosen so that the probability can be summarized with the help of jump times and holding times. The most important thing to notice is the summation of a stochastic process using jump times and holding times. If you carefully look at the basic stochastic processes, what one assumes about holding times and jump times is the basis for the random process realization. For example in a poisson process ,the holding times are exponentially iids, i.e the process holding time before a jump is independent of the holding time after the jump. The chapter then introduces exponential distribution and shows the connection between exponential distribution and memory-less property. An important theorem stated in the context of this section is : Sum of independent exponential random variables is either certain to be finite or certain to be infinite based on the harmonic mean of the parameters of the exponential random variables. Another term introduced in this section is the “first explosion time”, that is defined as the supremum of all jump times. A process satisfying the requirement that if t > first explosion time, then it takes on the value infinity, is called “minimal” process. The minimal does not refer to the state of the process but to the interval of time over which the process is active.

The section moves on to defining poisson processes based on holding times and jump times. A simple way to construct a Poisson process is to simulate a sequence of exponential random variables with poisson rate lambda, and define the jump chain such that it jumps by 1 unit after every holding time. Three equivalent conditions are stated to identify any poisson process and the proof involves forward equations. Subsequently a few properties of Poisson chains are explored. A counting process is characterized by the distribution of increments. The increments might be independent OR they can be stationary increments where it is only dependent on the length of the interval. So the first question one must ask when applying a counting process to a problem is , “Does the context have independent increments or stationary increments ?”

The section then introduces Birth processes, which can be thought of a generalization of poisson process where the holding times are distributed with an exponential distribution but with different rates. Like in the case of Poisson process, the section proceeds in building the Q matrix, formulating the forward equation for computing transition probabilities from the Q matrix and finally defining Birth process in three equivalent ways.

The most interesting part of this chapter is the one on Jumping times and holding times where continuous Markov chains are formulated using the joint distribution of holding times and jump chain. It goes on define a Markov chain as follows :

It then goes on give three constructions to Markov chain. The one I liked was the one with a good analogy , i.e

Imagine a state-space I as a labyrinth of chambers and passages, each passage shut off by a single door which opens briefly from time to time to allow you go through in one direction only. Suppose the door giving access to chamber j from chamber I opens at the jump times of a Poisson process of rate q(i_j) and you take every change to move that you can, then you will perform a Markov chain with Q matrix-Q

The above analogy then is used in taking a set of Poisson processes to construct a Markov chain. I found this kind of analogy very appealing as such things are always easy to understand and recall in various situations. Actually this whole construction of Markov processes using holding times and jump times itself is very interesting and makes tremendous sense in getting a general idea of the way random processes work. Sections on explosion times , forward and backward equations , Non minimal chains are to be read selectively as the difficult levels shoots up exponentially.
In author’s words, “There is an irreducible level of difficulty here.”

Chapter 3 : Continuous Time Markov Chains - II

With the necessary mathematical tools and framework covered in the previous chapter, the author introduces the continuous time Markov chain concepts in the same order as they were done for the discrete case. Basic terms are introduced like generator matrix, the initial distribution, transition matrix and transition probabilities. Class structure for the states is discussed where in the states are categorized based on their communication status. In this context, the system of equations needed to solve the hitting times and expected hitting times are introduced. Depending on the Q matrix, the system of equations help one determine the minimal solution for hitting time probabilities and expected hitting times of various states. Subsequently recurrent and transient states are defined in the context of continuous time processes and conditions for verifying the recurrence or transience of a state are given. They are basically in the integral form whereas they are in the summation form in Chapter 1 for the discrete Markov chains. Invariant distributions and ergodic law are discussed.

The basic funda that this chapter and the previous chapter for the discrete case teaches is that, one must analyze a Markov chain in the following manner, by posing questions to the problem at hand

• What is the transition matrix ?
• What are the states of the process ?
• Is there an underlying Q matrix for the process ?
• What is the transition matrix for the jump process, if it is a continuous Markov chain ?
• What are the types of states ?
• How can one identify or verify whether a state is recurrent or transient ?
• What are the first passage time probabilities and expected hitting times for various states ?
• Does the Markov chain converge to an equilibrium state ?
• Is the Markov chain irreducible?
• Is the Markov chain periodic or aperiodic ?
• Does time reversal hold good ? This is crucial for MCMC applications where detailed balance is one of the conditions for chain convergence(though it is only a sufficient condition and not a necessary condition)

The first 3 chapters comprise ~ 60% of the content of the book. I found chapter 4 to be very dense and overwhelming , as the author tries to extend the Markov chains and cram concepts relating to Martingales, Potential theory, Electrical networks and Brownian Motion, all in just 40 pages. The last chapter gives a flavor of applications of Markov chains by giving sample models in biology,queuing theory, resource management, Markov decision processes and MCMC.

Takeaway :

The book gives an intuitive yet rigorous introduction to discrete and continuous Markov chains. The decomposition of a Markov chain in terms of holding times and jump chain to explain various concepts of a continuous Markov process is the highlight of this book.

PageRank

I am hooked on to “Markov Chains” these days and they seem to fascinate me as the applications are in almost every field that I look at. I happened to go over Page Rank algo. From a Markov chain’s perspective, the algo can be summarized  in 2 steps

Step 1 : Represent a random surfer’s movement as a Markov chain

Here N is the total number of pages indexed by Google, Q is a transition matrix( irreducible, a periodic) that captures the transition probability of moving from one page to another , p is the page rank of the pages on the internet and alpha is adjustment factor to take in to consideration the inherent importance of a page.

Step 2 : Solve the Markov chain equation of Step 1 to compute the page rank. This is solved using iterative methods from Linear algebra (SVD)

This algo needs to be tweaked day in day out as the transition probability matrix keeps changing every second. As soon as any webpage (i) puts out an external link to any of the page (j), the probability corresponding to the origin and destination page Q_ij in the transition matrix changes.

Combine these 2 steps with more than a decade of computational learning about each element in the transition matrix , and you get a multi-billion dollar company called “Google”

Steve Kroft investigates HFT

Doing Bayesian Data Analysis : Summary

Firstly, something about the puppies on the cover pages. The happy puppies are named Prior, Likelihood, and Posterior. Notice that the Posterior puppy has half-up ears, a compromise between the perky ears of the Prior puppy and the floppy ears of the Likelihood puppy. The puppy on the back cover is named Evidence. MCMC methods make it unnecessary to explicitly compute the evidence, so that puppy gets sleepy with nothing much to do. These puppy images basically summarize the essence of Bayes’ and MCMC methods.

I was tempted to go over the book after reading the preface of the book where the author writes candidly about, “What to expect from the book?”.He uses poetic verses, humor to introduce the topic. He promises the usage of simple examples to explain the techniques of Bayesian analysis. The book is organized in to three parts. The first part contains basic ideas on probability, models, Bayesian reasoning and R programming. So, I guess this part could be speed read. The second part is the juicy part of the book where simple dichotomous data is used to explain hierarchical models, MCMC, sampling methods, Gibbs sampler and BUGS. The third part of the book covers various applications of Bayesian methods to real life data. So, this is more like a potpourri of applications and a reader can pick and choose whichever application appears exciting / relevant to one’s work. The highlight of this book is it enables you to DO Bayesian analysis, and not just KNOW about Bayes’. The book also gives an analogue for each of the tests that one learns in NHST( Null Hypothesis Significance testing). Historically Bayesians have always scorned at tests based on p-values. The inclusion of the tests in the book shows the author’s willingness to discuss issues threadbare and highlight the flaws in using frequentist tests for real life data.

Something not related to this post – I wonder how many Statistics courses in Indian universities teach Bayes to students. Historically Bayes became popular in Bschools . It was only after it was absorbed by BSchools, that it was then was adopted in other disciplines. Considering this sequence of events, I really doubt whether Bschools in India ever think of highlighting atleast a few case studies based on Bayes. As far as my experience goes, Bschools scare the students with boring statistical techniques which are outdated. Andrew Gelman wrote a fantastic book titled, “A bag of tricks? ”. I will blog about it someday. The book has fantastic content that can be used to structure any statistics based course at BSc/MBA level. But how many faculty even bother to do such things ? What matters is that a few faculty personnel who have the courage to change the curriculum and teach what is relevant in statistics, than merely following the traditional frequentist ideas. If you take a random sample of students from any Bschool in India  and ask them whether they remember anything from statistics courses, I bet they would say, “Yeah it was something about pvalues , null hypothesis and something hypothesis testing”. Sadly, this reflects the state of our education system as it has failed miserably to inculcate statistical thinking amongst students. Anyways enough of my gripe, Let me get back to the intent of the post.

As I mentioned earlier, the Part I of the book can be quickly read and worked on. There is one thing worth mentioning about the first part of the book. The way in which Bayes’ is introduced is very intuitive and by far the easiest to visualize, out of all the intros I have read till date. Well, one comes across Bayes’ in some form or the other be it through Monty-Hall problem/ conditional probability problems etc. This is the first time I am coming across where Bayes’ is introduced from a Contingency table perspective. If you look at a contingency table and assume that rows represent various data realizations and columns represent parameter realizations, then one can formulate the Bayes’ theorem quite easily. Conditioning on the data is equivalent to restricting the attention to one row and Bayes probabilities are nothing but reevaluated probabilities in that row, based on the relative proportions of the probabilities appearing in the row. One new term that I got to learn from this chapter is “evidence” and the way it is used in relation to Bayes. The denominator appearing in Bayes is termed as evidence. The “evidence”, is the probability of the data according to the model, determined by summing across all possible parameter values weighted by the strength of belief in those parameter values. In other books, “evidence” is the called “prior predictive”. Another important aspect mentioned is Data order invariance, meaning the likelihood is independent and identically distributed.The likelihood function has no dependence on time ordering and thus is time invariant.

Part II of the book is the core of the book where all the fundamentals are applied to Inferring a Binomial Proportion. Most of algorithms are applied to a simple case of dichotomous data so that the reader gets an intuitive understanding as well as working knowledge of these algorithms.

Inferring Binomial Proportion Via Exact Mathematical Analysis

By taking beta as a prior distribution for binomial likelihood, one gets the posterior as beta distribution. Based on one’s belief one can choose the values of a & b to reflect the bias in the coin. Highly skewed priors can be represented with values of a and b less than 1, for uniform priors, one can take a=b=1, for skewed on one side priors, one can take the prior as a=100,b=1 or a=1, b=100 and for a fair coin, one can take a=b=some high value. So, specifying beta prior is a way to translate the beliefs in to quantitative measure.

The three goals of inference are 1) estimating the parameter of binomial proportion, 2) predicting the data , 3) model comparison. For the first goal, a credible interval is computed based on the posterior distribution. Predicting the data can be done using the expectation rule on posterior distribution. The third goal is tricky. Only a few guidelines are given, one being the computation of Bayes’ factor.

If there are two competing models, meaning two competing priors for the data, then one can use Bayesian inference to evaluate the two models. One needs to calculate the probability of evidence for both the models i.e calculate Bayes factor P(D/M1) / P(D/M2). If this factor is extremely small / big, one can get an idea that Model 1/ Model 2 is better. Let’s say the ratio is very close to 0. Based on this evaluation, one cannot come to conclusion that Model M1 is better. The model comparison process has merely told us the models’ relative believabilities, not their absolute believabilities. The winning model might merely be a less bad model than the horrible losing model.

Steps to check winning model robustness (Posterior predictive check )

1. Simulate one value for the parameter from the posterior distribution
2. Use that parameter to simulate data values
3. Calculate the proportion of wins
4. Repeat these steps million times and check whether the probability of evidence is big enough

It is possible that Best model of the competing models might be a less bad model than the horrible losing model. Basically this chapter gives the first flavor of using Bayes’ with using a known closed form conjugate prior for computing the posterior probability model.

Inferring Binomial Proportion through Grid approximation:

The chapter then talks about a method that frees the modeler from choosing only closed form priors. The prior need not be a closed form distribution such as beta but might as well be tri-modal/ discrete mass function. In all probability, the real life prior would mostly be a discrete mass function for binomial proportion estimation. Prior distributions for binomial parameter estimation thus will have some discrete values with some specific probability values. One can think of triangular, quadratic, parabolic, whatever discrete prior that you can think of. The beauty of the grid method is that you can evaluate the probability at each of the grid value and then multiply that probability by the likelihood function for that point on the grid. This gives the posterior probability for the same point on the grid. The grid method has another advantage, i.e the calculation of HDI( Highest density Interval) that is a discrete approximation. Estimation + Prediction + Model Evaluation are applied to dichotomous data to show the application of grid based method. The grid method thus is an amazing way to incorporate subjective beliefs in to the prior and compute the HDI for the binomial proportion.

Inferring Binomial Proportion Via Metropolis Algorithm:

Nicholas Metropolis published the algorithm in 1953

The methods introduced in the previous chapters involve specifying the prior that are in closed form, or priors that can be specified in a discrete form on a grid. However if the parameters explode, the number of grid points that one needs to evaluate grows exponentially. If we set up a grid on each parameter that has 1,000 values, then the six dimensional parameter space has 1,000^6 = 1,000,000,000,000,000,000 combinations of parameter values, which is too many for any computer to evaluate.

One can use Metropolis Algorithm or invoke the necessary functions in BUGS to sample values from the posterior distribution. The condition that, “ P(theta) and P(evidence/theta) can be computed at every theta “ is enough to generate sample values from the posterior distribution. The metropolis algorithm is introduced via “Politician visit example”, a simple but powerful example of showing the internals of Metropolis algorithm. Even though Metropolis is almost never used to infer binomial proportion, the example builds a solid intuition in to working of Metropolis.

The main components of Metropolis algorithm applied to the simple example are

• Proposal distribution
• Target distribution ( Typically the product of likelihood and prior )
• Burn rate ( what % of the initial random walk should be abandoned ?)

One can also form a transition matrix which gives an intuition on,” Why the random walks converge to the target distribution? “, “ Why does the repeated multiplication of transition matrix converge to a stable matrix? ”. One thing to keep in mind about Metropolis algorithm is that prior and likelihood need not be normalized probability distributions, all that matters is the ratio of target probabilities of proposed and current probabilities. The book says it better, “The Metropolis algorithm only needs the relative posterior probabilities in the target distribution, not the absolute posterior probabilities, so we could use an unnormalized prior and/or unnormalized posterior when generating sample values of θ”

One must however keep in mind that, Proposal distributions can take many different forms, but the goal should be to use a proposal distribution that efficiently explores the regions of the parameter space where probability has most of its mass. MCMC methods have revolutionized Bayes’ methods and Metropolis algorithm is an example of one. Computation of evidence is the toughest part of Bayesian analysis. Hence MCMC methods can be used to solve this specific kind of problem. Thus “politician example”, mentioned in the book is a good introduction to Markov Chain Monte Carlo methods.

Basic Intro to BRugs

For the metropolis to work, the following conditions become crucial

• The proposal distribution needs to be tuned to prior distribution
• Initial samples during the burn-in-period needs to be excluded
• Sampling chain needs to be run long enough

These issues are taken care of by using BUGS package. Now to use BUGS, one needs a wrapper so that R can communicate with BUGS. There are different BUGS versions for windows, linux and other open source softwares. OpenBUGS is used in this book for specifying Bayesian models and generating MCMC. The wrapper that is used to communicate R with OpenBUGS is BRugs package. I am using a 64 bit machine and it was particularly painful to know that BRugs is available only for 32 bit machines. So, the code I wrote had to be configured to talk to 32 bit installation of R so that BRugs could be invoked. BTW, it requires a 32 bit JRE if you are working with eclipse.

The syntax for OpenBUGS is somewhat similar to R , so learning curve is not so much. Infact all one needs to know atleast for preliminary applications is the way to specify, likelihood, prior and the data realization. The chapter does a fantastic job of showing the way to use OpenBUGS from R. modelData(), modelCompile(),modelGenInits(),modelUpdate() are the main functions in BRugs to put data in to model, to compile the model, to initialize the chain and creating a MCMC chain. All these function details are already coded in BUGS can be leveraged using BRugs wrapper.BUGS can also be used for prediction and model comparison.

The highlight of this chapter is the application of Metropolis to single parameter estimation. Typically Metropolis is used only for multi parameter estimation and hence is usually introduced in any book after significant material is covered. By applying Metropolis to a simple example where the proposal distribution takes only 2 values, a lot of things get intuitively clear for the reader.

Also the extensive R code provided for Metropolis algorithm, computing HDI, invoking BUGS using BRugs is extremely useful to get a feel of the workings. The code is extremely well documented and the fact that they are part of the chapter itself makes the chapter a self-contained one.

Inferring Binomial Proportion Via Gibbs Sampling Algorithm:

Stuart Geman and Donald Geman were enthused on Bayes’ application to Pattern recognition after attending a seminar. They both went on to invent a technique called “Gibbs Sampling Method”

Stuart Geman Donald Geman

In any real life modeling problem one needs to deal with multiple parameters and one needs a methods for doing Bayesian analysis. BUGS( Bayes using Gibbs sampler) provides powerful software to carry out these analysis.

What is Gibbs Sampling ? You consider the parameters to be estimated , let’s say theta_1, theta_2,…theta_n. Select a theta_i from the list and generate a random value for the parameter from the conditional distribution of theta_i given other thetas. This procedure is repeated in a cyclical manner for all the thetas until you get to the target distribution. In Metropolis, the proposed jump affects only one parameter at a time, and the proposed jump is sometimes rejected, unlike Gibbs sampling where the proposed jump is never rejected. Gibbs Sampling is extremely efficient algorithm when it can be done, but the sad part is that it cannot be done in all the cases.

The thing about multiple parameter is that to look at the probability distribution you need a 3d plot, or a projection on a 2d surface. So, the chapter starts off with giving some fundas about basic plots using contour and persp functions in R package. One needs to know “outer” function in R to plot these 3d plots. The chapter starts off with deriving posterior for a two parameter case using formal analysis. The prior, likelihood and posterior are displayed using persp and countour plot. Grid method is used when the prior cannot be summarized by a nifty function. Let’s say you have prior function that looks like ripples and you want to estimate the posterior. One can easily form a grid, evaluate the prior at each point, evaluate the likelihood at each point and multiply both to get the posterior distribution.

So, if grid methods or closed form prior methods do not work ( in the case of multiple parameter) , one can use Metropolis algo where you choose a prior, select a burnout period, select a likelihood function and use BUGS/ R code to generate the posterior distribution. So, if there are already three methods , what the advantage of Gibbs sampling ? Answer : One can ignore the effort that goes in to tuning the prior distribution.

The procedure for Gibbs sampling is a type of random walk through parameter space,like the Metropolis algorithm. The walk starts at some arbitrary point, and at each point in the walk, the next step depends only on the current position, and on no previous positions.Therefore, Gibbs sampling is another example of a Markov chain Monte Carlo process.What is different about Gibbs sampling, relative to the Metropolis algorithm, is how each step is taken. At each point in the walk, one of the component parameters is selected. The component parameter can be selected at random, but typically the parameters are cycled through, in order: θ1, θ2, θ3, . . . , θ1, θ2, θ3, . . .. (The reason that parameters are cycled rather than selected randomly is that for complex models with many dozens or hundreds of parameters, it would take too many steps to visit every parameter by random chance alone, even though they would be visited about equally often in the long run.) Gibbs sampling can be thought of as just a special case of the Metropolis algorithm, in which the proposal distribution depends on the location in parameter space and the component parameter selected. At any point, a component parameter is selected, and then the proposal distribution for that parameter’s next value is the conditional posterior probability of that parameter. Because the proposal distribution exactly mirrors the posterior probability for that parameter, the proposed move is always accepted.

The place where Gibbs sampling is extremely useful is when it is difficult to estimate the joint distribution but it is easy to estimate the marginal distribution of each parameter. Advantage big advantage of Gibbs sampling is that there are no rejected simulations unlike the Metropolis algorithm. Thus the basic advantage of Gibbs sampling over the Metropolis algorithm, is that there is no need to tune a proposal distribution and no inefficiency of rejected proposals. But there is one other disadvantage of Gibbs sampling. Because it only changes one parameter value at a time, its progress can be stalled by highly correlated parameters.

A visual to illustrate what’s wrong with Metropolis incase one doesn’t tune the proposed distribution properly. Incase you choose the proposed distribution with low standard deviation, the path just gets stagnated at a local point (fig. on left) . If you choose the proposed distribution with high probability, the most of the jumps are ignored(fig. in the center). The key is to use the correct the proposed distribution so that the chain generated is long enough and wanders enough to get suitable values from the posterior distribution(fig.on the right)

The above visual makes a strong case to trust MCMC in BUGS instead of Metropolis algorithm where the modeler might not be sure about the proposal distribution.

Bernoulli Likelihood with Hierarchical Prior

Dennis V Lindley Adrian F. Smith

Lindley and his student Adrian F Smith were the first scientists who showed Bayesians the way to develop hierarchical models. The hierarchical models fell flat in the face as the models were too specialized and stylized for many scientific applications. It would be another 20 years before students began their preliminary understanding of Bayes’ by looking in to hierarchical models. The main reason Hierarchical models became workable was “the availability of computing power”.

This chapter is all about Hierarchical models and applying various techniques for parameter inference. The chapter starts off with an example where the binomial proportion parameter of a coin depends on another parameter(hyperparameter). This hyperparameter is a beta distribution and the dependency between hyperparameter and parameter is through a constant K. Looking at the figure on the left mu is the hyperparameter, theta is the parameter and K is the constant that decides the dependency between mu and theta. For large values of K, there is a strong dependency as the resulting beta distribution is very narrow , whereas for small values of K, there is a weak dependency as the resulting beta is flat. One thing to notice is that there is no need for any hierarchical modeling if K takes a very high value or mu takes only one value. In both these situations the uncertainty of theta is captured in only one level. The first approach explored is the grid approach. Basically you divide the parameter space in to fine grids, formulate priors and joint priors, multiply by joint likelihood and you obtain a join posterior.

This is further extended to a series of coins and this where one sees that plain vanilla grid approach fails spectacularly. For a 2 coin experiment, it is still manageable but once we go on to 3 coin model, the grid points explodes to 6.5 million(on a 50 point grid for each param). It explores to 300 million for a 4 coin model. Hence this approach even though appealing and simple in one way becomes inefficient as the parameter space widens even a bit. MCMC comes to the rescue again. BUGS is then used to estimate parameters for more than 2 coins. The approach followed is , write BUGS code , wrap in a string, use BRugs package to interact with BUGS, simulate the MCMC chain , get the results from BUGS and analyze the result. BUGS gives an enormous flexibility. One can even include K as a parameter instead of fixing it. The chapter then introduces modeling a bigger parameter space.. It ends with a case study where Hierarchical models are applied to a real life situation.

The problem with examples mentioned are BRUGS is that it works with OpenBUGS that is available for a 32 bit machine. My machine is 64 bit and I had to do some acrobatics to make the examples work. I used RStudio which has a 32 bit R version and 32 bit JRE and then tried running the whole stuff. Even though I could run the code, I could never understand stuff as I was struggling to code. That’s when I stumbled on R2WinBUGS which had a wrapper to WinBUGS. I am relieved that I can now run R code to interact with WinBUGS with out having to worry about 32bit/62 bit constraint. Once I figured out the way to code almost everything in R and use R2WInBUGS to run MCMC sampling, working on Hierarchical models was a charm. While experimenting various software and packages, here are a few things I learnt :

• BRUGS works with OpenBUGS. All the functions in BRUGS replicate the interface functions in WINBUGS software. BRUGS works for 32 bit machine and not 64 bit machine
• OpenBUGS is published under GPL. It runs on Linux too. Provides a flexible API so that BRUGS can talk to OpenBUGS
• "“coda” package is used to analyze WinBUGS output.
• JAGS – Just another Gibbs Sampler : Alternative to the existing versions in WinBUGS/ OpenBUGS. It is used to run with coda and R
• R2WinBUGS – Interface written by Gelman to interact with WinBUGS. The main functions of R2WinBUGS are bugs() , bugs.data.inits(), bugs.script(), bugs.run(), bugs.sims()
• It’s better to code the model in WinBUGS , check the basic syntax of the model and then code the whole thing in R

Thinning is another aspect that is discussed in the chapter. Since posterior distribution samples are dependent, it is important to reduce the autocorrelation amongst the samples. This is used by specifying the thinning criteria where the samples are selected after some lag.

Hierarchical Modeling and Model Comparison

This chapter talks about model comparison, meaning if you specify two or more competing priors, on what basis does one choose the model ?

For comparing two models, an elementary approach is used to give an intro. Let’s say one is not certain about the binomial proportion parameter and chooses to have a discrete prior with two peaks at 0.25 and 0.75. One can use the code the model in WinBUGS in such a way that posterior samples are generated from these two priors at once. So, one simulation gives out the conditional probability values of both the models. These posterior probability values can be then used to judge the competing models. The chapter then goes on to use pseudo priors and shows a real life example where Bayes’ can be used to evaluate competing models/priors.

 

Null Hypothesis Significance Testing

Ronald Aylmer Fisher

It was Fisher who introduced p values, which became the basis for hypothesis testing for many years. Now how do we tackle this issue in this new world where there is no paucity of data, amazing visualization tools and computational power. What has Bayes’ got to offer in this area ?

The chapter is extremely interesting for any reader who wants to compare the frequentist methods to Bayesian approaches. The chapter starts with ripping apart the basic problem with NHST. From a sample of 8 heads out of 23 flips, the author uses NHST to check whether the coin is biased. In one case, he says the experimenter had a fixed N in mind which leads to rejection of alternate hypothesis, while in the second case the experimenter was tossing the coin until 8 heads appeared, in which case NHST leads to rejecting the null hypothesis. Using this simple example the author makes a point that the inference is based on the intention of the experimenter which the realized data will never be able to tell. This dependence of the analysis on the experimenter’s intentions conflicts with the opposite assumption that the experimenter’s intentions have no effect on the observed data. So, NHST in that way looks dicey for application purposes. Instead of tossing coins, if we toss flat headed nails and assume that tails means nail falls on the ground and heads is the alternate case, then NHST gives the same result even though our prior about flat headed nails is that the parameter is strongly biased towards tails. NHST gives no way of incorporating prior beliefs in to the modeling process. So, in a lot of cases it really becomes a tool which gives nonsense results.

The same kind of reasoning holds good for confidence intervals. Based on the covert intention of the experimenter, the confidence intervals could be entirely different for the same data. On the other hand, Bayesian Highest Density Interval is very clear to understand. It has direct interpretation of the believabilities of theta. It has no dependence on the intention of the experimenter and it is responsive to analyst’s prior beliefs. The chapter ends with giving a few advantages of thinking about sampling distribution.

Bayesian Approached to Testing a Point(“Null”) Hypothesis:

The way to test the null hypothesis is to check whether the null point falls within the credible interval. One important point mentioned in this context is that one must not be blinded by visual similarity between marginal distributions of two parameters and infer that they are same. It might so happen that they might be positively correlated in the joint behavior and the credible interval for the difference in the parameters might not contain 0. Instead of inferring that the two parameters are different, visual similarity might blind us to infer that they are the same. I came across another term in the chapter for the first time till date, Region of Practical Equivalence(ROPE). Instead of checking whether null value lies in the credible interval, it is better to check whether the an interval around null value , i.e whether ROPE comprises the credible interval or not?. By talking about ROPE instead of a single point, we are basically cutting down the false alarm rate. To summarize, a parameter value is declared to be accepted for practical purposes, if that value’s ROPE completely contains the 95% HDI of the posterior of the parameter.

Part III of the book that talks about model building, more specifically GLM

The Generalized Linear Model

The entire structure of modeling that is usually found in statistics 101 courses is based on Generalized Linear Model structure. In such a structure, you typically find predictor and predicted variable linked by a function. Depending on the type of predictors and the functions, GLM model goes by a different name. If the predictors and predicted variable are metric scale variable, then GLM usually goes by the name, “Regression” / “Multiple Regression”. If the predictor is nominal then it is recoded as appropriate factors and then fed in to the usual regression equation. There are cases when predicted variable is connected to the predictors using a link function. Typically this takes the form of sigmoid(logit), cumulative normal etc. Sigmoid is used when the predicted variable takes values between 0 and 1. The various illustrations to show the effect of gain + threshold + steepness in a sigmoid function are very helpful to any reader to get an idea of various GLM models possible.

The following is the usual form of GLM

The mean of the predicted variable is a function (f) of predictors(x1, x2,..) where f is termed as the link function. The predicted variable is in turn modeled as a pdf with the above mean and a precision parameter. Various forms of GLM models are an offshoot of the above structure. Typically f is Bernoulli / sigmoid/ constant / cumulative normal function. Various chapters in the part III of the book are organized based on the form f takes and the type of predictors + predicted.Chapter 15 is Bayes’ analogue of t-test. Chapter 16 is the Bayes’ analogue of Simple linear regression. Chapter 17 is the Bayes analogue of Multiple Regression. Chapter 18 is the Bayes analogue of One-way Anova. Chapter 19 is the Bayes’ analogue of two way ANOVA. Chapter 20 deals with logistic regression.

I will summarize the last part of the book (~200 odd pages) in another post at a later date. The first two parts of the book basically provide a thorough working knowledge of the various concepts in Bayesian Modeling. In fact a pause after marathon chapters of part I and part II of the book might be a better idea as one might need some time to reflect and link the concepts to whatever stats ideas that one already has.

Takeaway

The strength of this book is its simplicity. The book is driven by ONE estimation problem, i.e, inferring a binomial proportion. Using this as a “spine”, the author shows a vast array of concepts / techniques / algorithms relevant to Bayes’. In doing so, the author equips the reader with a working knowledge of Bayesian models. The following quatrain from Prof. McClelland (Stanford) on the cover of the book tells it all :

John Kruschke has written a book on Statistics
Its better than others for reasons stylistic
It also is better because it is Bayesian
To find out why, buy it – its truly amazin!

The theory that would not die : Summary

The book by sharon bertsch mcgrayne, is about Bayes’ theorem stripped off the math associated with it. In today’s world, statistics even at a rudimentary level of analysis (not referring to research but preliminary analysis) comprises forming a prior and improving it based on the data one gets to see. In one sense modern statistics takes for granted that one starts off with a set of beliefs and improves the beliefs based on the data. When this sort of technique or thinking was first introduced, it was considered equivalent to pseudo-science or may be voodoo science. During 1700s when Bayes’ theorem came to everybody’s notice, Science was considered extremely objective, rational and all the words that go with it. On the other hand, Bayes’ was talking about beliefs and improving the beliefs based on data. So, how did the world come to accept this perspective of thinking? In today’s world, there is not a single domain that is untouched by Bayesian Statistics. In finance and technology specifically, Google Search engine algos + Gmail spam filtering , Net flix recommendation service in e-tailing space , Amazon book recommendations, Black-Litterman model in finance, Arbitrage models based on Bayesian Econometrics etc. are some of the innumerable areas where Bayes’ philosophy is applied. Carol Alexander in her book on Risk Management says that, world needs Bayesian Risk Managers and remarks that , “Sadly most of risk management that is done is frequentist in nature” .

You pick any book on Bayes and the first thing that you end up reading is about prior and posterior distributions. There is no history about Bayes that is mentioned in many books. It is this void that the book aims to fill and it does so with a fantastic narrative about the people who rallied for and against a method that took 200 years to get vindicated. Let me summarize the five parts of the book. This is probably the lengthiest post I have ever written for a non-fiction book, the reason being , I would be referring to this summary from time to time as I hope to apply Bayes’ at my work place.

 

Part I – Enlightenment and Anti-Bayesian Reaction

Causes in Air

The book starts off with describing conditions around which Thomas Bayes wrote down the inverse probability problem. Meaning deducing the cause from the effects, deducing the probabilities given the data, improving prior beliefs based on data. The author speculates that there could be have multiple personalities that would have motivated Bayes to think on the inverse probability problem like the David Hume’s philosophical essay / deMoivre book on chances / Earl of Stanhope / Issac Newton’s concern that he did not explain the cause of gravity etc. Instead of publishing or sending it to Royal Society, he let it lie amidst his mathematical papers. Shortly after his death, his relatives ask Richard Price to look in to the various works that Bayes had done. Price subsequently got interested in the inverse probability work and polished it , added various references , and made it publication ready . He subsequently sent it off to Royal Institute for publication.

Thomas Bayes (1701-1776) Richard Price (1723-1791)

The Bayes’ theory is different from the frequentist theory in the sense that, you start with a prior belief about an event, collect data and then improve the prior probability. It is different from the frequentist view as frequentists typically do the following :

a) Hypothesise a probability distribution - a random variable of study is hypothesized to have a certain probability distribution. Meaning, there is no experiment that is conducted but all the possible realized values of the random variable are known. This step is typically called Pre-Statistics( David Williams Terminology from the book “Against the Odds” )

b) One uses actual data to crystallize the Pre-Statistic and subsequently reports confidence intervals.

This is in contrast with Bayes where a prior is formed based on one’s beliefs and data is used to update the prior beliefs. So, in that sense, all the p-values etc that one usually ends up reading in college texts are useless in Bayesian world.

The Man who did Everything

Pierre-Simon Laplace (1749 – 1827)

Baye’s formula and Price reformulation of Baye’s work would have been in vain , had not it been for one genius, Pierre Simon Laplace, the Issac Newton of France. The book details the life of Laplace where he independently develops Bayes’ philosophy and then on stumbling upon the original work tries to apply IT to everything that he could possibly think of. Ironically, Baye’s used his methodology to prove the existence of God while Laplace used it to prove God’s non-existence(in a way ). In a strange turn of events, at the age of 61 Laplace became a frequentist statistician as data collection mechanism improved and mathematics to deal with rightly measured data was easier in the case of frequentist approach. Thus a person who was responsible for giving mathematical life to Bayes’ theory turned in to a frequentist for the last 16 years of his life. All said and done, Laplace single handedly created a gazillion concepts, theorems, tricks in statistics that influenced the mathematical developments in France. He is credited with Central Limit theorem, generating functions, etc , terms that are casually tossed around in today’s statisticians.

Many Doubts, Few Defenders

Laplace launched a craze for statistics by publishing some ratios and numbers in the French society like number of dead letters in postal system, number of thefts, number of suicides, proportion of men to women etc and declaring that most of them were almost constant. Such numbers increased French Government’s appetite to consume more numbers and soon there were plethora of men and women who started collecting numbers, calling them statistics. Well, no one cared to attribute the effects to a particular cause; no one cared whether one can use probability to qualify lack of knowledge. The pantheon of data collectors lead quickly to an amazing amount of data and subsequently the concept that probability was based on frequency of occurrence took precedence over any other definition of probability. In the modern parlance, the long term frequency count became synonymous with probability. Also in the case of large data, the Bayesian and frequentist stats match and hence there was all the more reason to push Bayesian stats in to oblivion that was anyway based on subjective beliefs. Objective frequency of events was far more plausible than any sort of math that was based on belief systems. By 1850, with in two generations of his death, Laplace was remembered largely for astronomy. Not a single copy of his treatise on probability was available anywhere in Parisian bookstores.

1870s- 1880s-1890s were dead years for Bayes’ philosophy. This was the third death for Bayes’ principle. First was when Thomas Bayes did not share with anyone and it was idle amongst his research papers. The second death for the principle was, subsequent to Price publication of Bayes’ in scientific journals and the third death happened by 1850s as theoreticians rallied against it.

Precisely during these years, 1870s – 1910s , Bayes’ theory was silently getting used in real life applications and with great success. It was getting used by French army and Russian artillery officers to fire their weapons. There were many uncertain factors in firing artillery, like enemy’s precise location, air density, wind directions etc. Joseph Louis Bertrand a mathematician in French army put Bayes’ to use and published a textbook on the artillery firing procedures that was used by French and Russian army for the next 60 years till the Second World War. Another area of application was Telecommunications. An engineer in Bell Labs created a cost effective way of dealing with uncertainty in call handling based on Bayes’ principles. The US insurance industry was another place where Bayes’ was effectively used. A series of laws were passed between 1911-1920 obligating employers to provide insurance covers to employees. With hardly any data available, pricing the insurance premium became a huge problem. Issac Rubinow provided some relief in this situation by manually classifying records from Europe and thus helping to tide over the crisis for 2-3 years. In the mean time, he created an actuarial society which started using Bayesian philosophy to create Credibility score, a simple statistic that could be understood, calculated and communicated easily amongst people. This is like the implied volatility in Black Scholes formula. Irrespective of whether any one understands Black Scholes replication argument or not, one can easily talk / trade / form opinions based on the implied volatility of an option. Issac Robinow helped create one such statistic for the insurance industry that was in vogue for atleast 50 years.

Despite the above achievements, Bayes’ was nowhere in prominence. The trio that was responsible for near death-knell of Bayes’ principle were Ronald Fisher, Egon Pearson and Jerzy Neyman

Ronald Aylmer Fisher Egon Pearson Jerzy Neyman

The fight between Fisher and Karl Pearson is a well known story in statistical world. Fisher accused Bayes’ theory saying that it was utterly useless. He was a flamboyant personality and a vociferous in his opinions. He single handedly created a ton of statistical concepts like randomization, degrees of freedom etc. The most important contribution of Fisher was that he made stats available to scientist and researchers who did not have the time / did not possess skills in statistics. His manual became a convenient way to conduct a scientific experiment. This was in marked contrast to Bayes’ principle where the scientist has to deal with priors and subjective beliefs. During the same time when Fisher was developing frequentist methods, Egon Pearson and Jerzy Neyman introduced hypothesis testing that helped a ton of people working in the labs to reject alternate or null hypothesis using a framework where the basic communication of a test result was through p values. 1920s- 1930s was the golden age for frequency based statistics. Considering the enormous influence of the above personalities, Bayes’ was nowhere to be seen.

However far from the enormous visibility of frequentist statisticians, there was another trio who were silently advocating and using Bayes’ philosophy. Emile Borel , Frank Ramsey and Bruno De Finetti.

Emile Borel Frank Ramsey Bruno De Finetti

Emile Borel was applying Bayes’ probability to insurance, biology, agriculture, physics problems. Frank Ramsey was applying the concepts to economics using utility functions. Bruno De Finetti was firmly of the opinion that subjective beliefs can be quantified at the race track. This trio kept Bayes’ alive in a few far removed circles of English statistical societies.

Harold Jeffrey

The larger credit however goes to the geo-physicist Harold Jeffrey’s who single handedly kept Bayes’ alive during the anti-Bayesian onslaught of 1930s and 1940s. His personality was quiet and gentlemanly and thus he could coexist with FisherJ . Instead of trying to distance away from Fisherian stats, Jeffrey was of the opinion that some principles like Maximum Likelihood function from Fisher’s armory were equally applicable to Bayesian Stats. However he was completely against p-values and argued against anyone using them. Statistically, lines were drawn. Jeffreys and Fisher, two otherwise cordial Cambridge professors embarked on a two-year debate in the Royal Society proceedings. Sadly the debate ended inconclusively and frequentism totally eclipsed Bayes’. By 1930s Jeffrey’s was truly a voice in the wilderness. So, this becomes the fourth death of Bayes’ theory.

 

Part II - Second World War Era

Bayes’ goes to War

The book goes on describe the work of Alan Turing who used Bayesian methods to locate the German U boats, breaking enigma codes in the Second World War.

Alan Turing

His work at Bletchley park along with other cryptographers validated Bayesian theory. Though Turing and others did not use the word Bayesian, almost all of their work was Bayesian in Spirit. Once the Second World War came to an end, the group was ordered to destroy all the tools built, manuscripts written, manuals published etc. Some of the important documents became classified info and none of the Bayesian stuff could actually be talked in public and hence Bayesian theory remained in oblivion despite its immense use in World War II.

Dead and Buried Again

Making the second world war work as classified information, Bayes’ was again dead. Till mid 1960s there was not a single article on Bayesian Stats that was readily available to scientists for their work. Probability was applied only to long sequence of repeatable events and hence frequentist in nature. Bayes theory’ was ignored by almost everyone by mid 1960s and a statistician during this period meant a frequentist who studies asymptotics and talked in p values, confidence intervals, randomization, hypothesis testing etc… Prior and Posterior distribution were terms that were no longer considered useful. Bayes’ theory was dead for the fifth time!

Part III - The Glorious Revival

Arthur Bailey

Arthur Bailey, an insurance actuary was stunned to see the insurance premiums were actually using Bayes’ theorem, something considered as a heresy in the schools where he learnt stuff. He was hell bent on proving the whole concept flawed and want to hoist the flag of frequentist stats on insurance premium calculations. After struggling for a year, he realized that Bayes’ was the right way to go. From then on, he massively advocated Bayes’ principles in insurance industry. He was vocal about it , published stuff and let everyone know that Bayes’ was infact a wonderful tool to price insurance premiums. Arthur Bailey’s son Robert Bailey also helped spread Bayesian stats by using it to rate a host of things. In time, the insurance industry accumulated enormous amount of data that Bayes’ rule , like the slide rule , became obsolete.

From Tool to Theology

Bayes’ stood poised for another of its periodic rebirths as three mathematicians Jack Good, Leonard Jimme Savage and Dennis V Lindley tackled the job of turning Bayes’ rule in to a respectable form of mathematics and a logical coherent methodology.

Jack Good Jimmie Savage Dennis V Lindley

Jack Good being Turing’s wartime assistant knew the power of Bayes’ and hence started publishing and making Bayes’ theory known to a variety of people in Academia. However his work was still classified info. Hampered by governmental secrecy and his inability to explain his work, Good remained an independent voice in the Bayesian community. Savage on the other hand was instrumental in spreading Bayesian stats and making a legitimate mathematical framework for analyzing small data events. He also wrote books with precise mathematical notion and symbols thus formalizing Bayes’ theory. However the books did not become famous or were not widely adopted as computing machinery to implement ideas were not available. Dennis Lindley on the other hand pulled off something remarkable. In Britain he started forming small group of Bayesian circles and started pushing for Bayesian appointments in stats department. This feat in itself is something for which Lindley needs to be given enormous credit as he was taking on the mighty Fisher, in his own home turf, Britain.

Thanks to Lindley in Britain and Savage in US, Bayesian theory came of age in 1960s. The philosophical rationale of using Bayesian methods had been largely settled. It was becoming the only mathematics of uncertainty with an explicit, powerful and secure foundation in logic. “How to apply it? “, though remained a controversial question.

Jerome Cornfield, Lung Cancer and Heart Attacks

Jerome Cornfield was the next iconic figure who used Bayes’ to a real life problem. He successfully showed the linkage between smoking and lung cancer, thus introducing Bayes’ to epidemiology. He was probably one of the first guys to take Fisher and win arguments against Fisher. Fisher was unilaterally against Bayes’ and hence had written an arguments against Cornfield’s work. Cornfield with the help of his fellow statisticians proved all the arguments of Fisher baseless thus resuscitating Bayes’. Cornfields rose to head the American Statistician association and this in turn gave Bayes’ a stamp of legitimacy , infact a stamp of superiority over frequentist statistics. Or atleast it was thought that way.

There’s always a first time

frequentist stats, by its very definition cannot assign probabilities to events that have never happened. “What is the probability of an accidental Hydrogen bomb collision?” , This was the question on Madansky’s mind, a PhD student under Savage. As a final resort, he had to adopt Bayes theory to answer the question. The chapter shows that Madansky computed posterior probabilities of such an event and published his findings. His findings were taken very seriously and many cautious measures were undertaken. The author is of the view that Bayes’ thus averted many cataclysmic disasters.

46656 Varieties

There was an explosion in Bayesian stats around 1960s and Jack Good estimated that there 46,656 different varieties of definitions of Bayes’ that were prevalent. One can see that Statisticians were grappling with Bayes’ stats as it was not as straightforward as frequentist world. Stein’s paradox created further more confusion. Stein was an anti-bayesian and had published a paradox which looks like pro-bayes’ formula. Stein’s shrinkage estimator smelled like a Bayes formula but the creator did not credit Bayes for it. Thus there were quite a few problems in computing using Bayes’ framework. Most importantly was actually integrating a complex density form. This was 1960s and computing power eluded statisticians. Most of the researchers had to come up with tricks, nifty solutions to tide over laborious calculations. Conjugacy was one such concept that was introduced to make things tractable. Conjugacy is a property where prior and posterior share the same family of distribution thus making estimation and inference a little easier. 1960s and 1970s were the times when academic interest in Bayesian Statistics was in full swing. Periodicals, Journals, Societies started forming to work on, espouse, and test various Bayesian concepts. The extraordinary fact about the glorious Bayesian revival of the 1950s and 1960s is how few people in any field publicly applied Bayesian theory to real-world problems. As a result, much of the speculation about Bayes’ rule was moot. Until they could prove in public that their method was superior, Bayesians were stymied.

Part IV – To Prove its Worth

Business Decisions

Even though there were a ton of Bayesians around in 1960s, there were no real life examples to which Bayes’ had been used. Even for simple problems, computer simulation was a must. Hence devoid of computing power and practical applications, Bayes’ was still considered a heresy. There were a few who were gutsy enough to spend their lives in changing this situation. This chapter talks about two such individuals

Osher Schlaifer Howard Raiffa

These two Harvard professor set on a journey to use Bayes’ to Business Statistics. Osher Schlaifer was a faculty in the accounting and business department. He was randomly assigned to teach statistics course. Knowing nothing about it Schlaifer crammed away the frequentist stats and subsequently wondered about its utility in the real life. Slowly he realized that in business one always deals with a prior and develops better probabilities based on the data one gets to see in the real world. This logically bought him to Bayes’ world. The math was demanding and Schlaifer immersed in math to understand every bit of it. He also came to know about a young prof at Columbia, Howard Raiffa. He pitched to Harvard to recruit Raiffa and subsequently brought him over to Harvard. For about 7 years, both of them created a lot of practical applications to Bayesian methods. The professors realized that there was no mathematics toolbox for Bayesians to work and hence went on developing a lot of concepts which could make Bayesian computations easy. They also published books on applications of Bayesian statistics to management, detailed notes on Markov chains etc. They also tried inculcating Bayesian stuff in to curriculum. Despite these efforts, Bayes could not really permeate through academia for various reasons that are mentioned in this chapter. It is also mentioned that some students burnt the lecture notes in front of professor’s office to give vent to their frustration.

Who Wrote the Federalist?

Fred Frederick Mosteller

What is the Federalist Puzzle ? Between 1787 and 1788 , three founding fathers of the United States, Alexander Hamilton, John Jay and James Madison, anonymously wrote 85 newspaper articles to persuade New York State voters to ratify the American Constitution. Historians could attribute most of the essays but no one agreed whether Madison or Hamilton had written 12 others. Fredrick Mosteller at Harvard was excited by this classification problem and chose to immerse in the problem for 10 years. He roped in David Wallace from Chicago University in this massive research exercise. To this day, the Federalist is quoted as THE CASE STUDY that one can refer to, for the technical armory and depth of Bayesian statistics. Even though the puzzle exists to this day, it is the work that went behind it that showed the world that Bayesian stats was powerful in analyzing real life hard problems. One of the conclusions from the work was the prior did not matter. It’s the learning from the data that mattered. Hence it served as a good reminder to all the people who criticized Bayes’ philosophy because of its reliance of subjective priors. As an aside, the chapter brings out interesting elements of Fredrick Mosteller’s life and there are a lot of inspiring elements in the way he worked. The life of Mosteller is a must read for every statistician.

The Cold Warrior

Tukey

This chapter talks about another missed opportunity for Bayes’ to become popular. The section profiles Tukey, sometimes referred to as Picasso of statistics. He seemed to have extensively used Bayesian stats in his military work, his election prediction work etc. However he chose to keep his work confidential, partly because he was obliged to, and partly out of his own choice. The author gives enough pointers to make the reader infer that Tukey was an out and out Bayesian

Three Mile Island

Despite its utility in the real world, 200 years later, people were still avoiding the word Bayes’. Even though everyone used the method in some form or the other, no one openly declared it. This changed after the civilian nuclear power plant collapse, a possibility that was very remote according to frequentist world, but Bayesians predicted it .This failure recognized that having subjective beliefs and working out posterior probability is not a heresy.

The Navy Searches

This is one of the longest chapters in the book and it talks about the ways in which Navy put to use Bayesian methods to locate lost objects like Hydrogen Missiles, Submarines etc. In the beginning even though Bayes’ was used, no one was ready to publicize the same. Bayes’ was still a taboo word. Slowly over a period of time when Bayes’ was used more effectively to locate things lying on the ocean floor, Bayes’ started to get enormous recognition in navy circles. Subsequently Bayes’ was being used to track moving objects, which also proved to be very successful. For the first time Monte Carlo methods were being extensively used to calculate posterior probabilities. This was at least 20 years before it excited academia. Also cute tricks like conjugacy were being quickly incorporated to calculate summaries of posterior probabilities.

Part V – Victory

Eureka

There were five near-fatal deaths to Bayes theory. Bayes had shelved it, Price published it but was ignored, Laplace discovered his own version but later favored frequency theory, frequentists virtually banned it and the military kept it secret. By 1980s data was getting generated at an enormous rate in different domains and hence statisticians and frequentists were faced the “curse of dimensionality” problem. Fischerian and Pearson methods applicable to data with a few variables were felt inadequate with the explosive growth of factors for the data. How to separate the signal from the noise? , became a vexing problem. Naturally the analyzed data sets in the academia were the ones with fewer variables. Contrastingly, others such as physical and biological scientists analyzed massive amounts of data about plate tectonics, pulsars, evolutionary biology, pollution, the environment, economics, health, education, and social science.Thus Bayes’ was stuck again because of its complexity.

In such a situation, Lindley and his student Adrian F Smith showed Bayesians the way to develop hierarchical models.

Adrian F. Smith

The hierarchical models fell flat in the face as the models were too specialized and stylized for many scientific applications. (It would be another 20 years before students began their preliminary understanding of Bayes’ by looking in to hierarchical models). Meanwhile, Adrian Raftery studied coal dust incident rates using Bayesian stats and was thrilled to publicize one of the Bayes’ strengths i.e evaluating competing models/hypothesis. Frequency-based statistics works well when one hypothesis is a special case of the other and both assumed gradual behavior. But when hypotheses are competing and neither is a special case of the other, frequentism is not as helpful, especially with data involving abrupt changes—like the formation of a militant union.

During the same period , 1985-1990 , image processing and analysis had become critically important for the military, industrial automation, and medical diagnosis. Blurry, distorted, imperfect images were coming from military aircraft, infrared sensors, ultrasound machines, photon emission tomography, magnetic resonance imaging (MRI) machines, electron micrographs, and astronomical telescopes. All these images needed signal processing, noise removal, and deblurring to make them recognizable. All were inverse problems ripe for Bayesian analysis. The first known attempt to use Bayes’ to process and restore images involved nuclear weapons testing at Los Alamos National Laboratory. Bobby R. Hunt suggested Bayes’ to the laboratory and used it in 1973 and 1974. The work was classified, but during this period he and Harry C. Andrews wrote a book, “Digital Image Restoration”, about the basic methodology; Thus there was an immense interest in image pattern recognition during these times.

Stuart Geman and Donald Geman were enthused on Bayes’ application to Pattern recognition after attending a seminar. They both went on to invent a technique called “Gibbs Sampling Method”

Stuart Geman Donald Geman

These were the beginning signs to the development of computational techniques in Bayes’. It was Smith who teamed up with Alan Gelfand and turned on the heat towards developing computational techniques. Ok , now a bit about Alan Gelfand.

Alan Gelfand

Gelfand started working on EM (Expectation Maximization) algo. Well, the first time I came across EM algo was in Casella’s Statistical Inference book. It was very well explained. However there was one missing part in such books that can only be obtained by reading around the subject, “the historical info”. This chapter mentions that tidbit about EM which will make learning EM more interesting. It says

EM algorithm, an iterative system secretly developed by the National Security Agency during the Second World War or the early Cold War. Arthur Dempster and his student Nan Laird at Harvard discovered EM independently a generation later and published it for civilian use in 1977. Like the Gibbs sampler, the EM algorithm worked iteratively to turn a small data sample into estimates likely to be true for an entire population.

Gelfand and Smith saw the connection between Gibbs Sampler, Markov chains and Bayes’ methodology. They recognized that Bayes formulations, especially the integrations involved in Bayes’ could be successfully solved using a mix of Markov chains and Simulation techniques. When Smith spoke at a workshop in Quebec in June 1989, he showed that Markov chain Monte Carlo could be applied to almost any statistical problem. It was a revelation. Bayesians went into “shock induced by the sheer breadth of the method.” By replacing integration with Markov chains, they could finally, after 250 years, calculate realistic priors and likelihood functions and do the difficult calculations needed to get posterior probabilities.

While these developments were happening in statistics, an outsider might feel a little surprised at the slowness of the application of montecarlo methods to statistics as they were being used by Physicists from as early as 1930s. Fermi , a Nobel prize winning physicist was using Markov chains to study nuclear physics. He could not publish his stuff as it was classified info. However in 1949, Maria Goeppert, a physicist and a future Nobel winning scientist gave a public talk on Markov chains + simulations and its application to real world problems.

Nicholas Metropolis

That same year Nicholas Metropolis, who had named the algorithm Monte Carlo for Ulam’s gambling uncle, described the method in general terms for statisticians in the prestigious Journal of the American Statistical Association. But he did not detail the algorithm’s modern form until 1953, when his article appeared in the Journal of Chemical Physics, which is generally found only in physics and chemistry libraries. Bayesians ignored the paper. Today, computers routinely use the Hastings–Metropolis algorithm to work on problems involving more than 500,000 hypotheses and thousands of parallel inference problems. Hastings was 20 years ahead of his time. Had he published his paper when powerful computers were widely available, his career would have been very different. As he recalled, “A lot of statisticians were not oriented toward computing. They take these theoretical courses, crank out theoretical papers, and some of them want an exact answer.” The Hastings–Metropolis algorithm provides estimates, not precise numbers. Hastings dropped out of research and settled at the University of Victoria in British Columbia in 1971. He learned about the importance of his work after his retirement in 1992.

Gelfand and Smith published their synthesis just as cheap, high-speed desktop computers finally became powerful enough to house large software packages that could explore relationships between different variables. Bayes’ was beginning to look like a theory in want of a computer. The computations that had irritated Laplace in the 1780s and that frequentists avoided with their variable-scarce data sets seemed to be the problem—not the theory itself.

The papers published by Gelfand and Smith were considered as landmark in the field of Statistics. They showed that Markov chains simulations applied to Bayes could basically solve any frequentist problem and more importantly, many other problems. This method was baptized as Markov chain Monte Carlo, or MCMC for short. The combination of Bayes and MCMC has been called “arguably the most powerful mechanism ever created for processing data and knowledge.”

After this MCMC birth in 1990s, statisticians could study data sets in genomics or climatology and make models far bigger than physicists could ever have imagined when they first developed Monte Carlo methods. For the first time, Bayesians did not have to oversimplify “toy” assumptions. Over the next decade, the most heavily cited paper in the mathematical sciences was a study of practical Bayesian applications in genetics, sports, ecology, sociology, and psychology. The number of publications using MCMC increased exponentially.

Almost instantaneously MCMC and Gibbs sampling changed statisticians’ entire method of attacking problems. In the words of Thomas Kuhn, it was a paradigm shift. MCMC solved real problems, used computer algorithms instead of theorems, and led statisticians and scientists into a world where “exact” meant “simulated” and repetitive computer operations replaced mathematical equations. It was a quantum leap in statistics.

Appreciation of the people behind techniques is important in any field. The takeaway from this chapter is that MCMC’s birth credit goes to

Adrian F. Smith + Alan Gelfand

Bayes’ and MCMC found its application in genetics and a host of other domains. MCMC took off and Bayes was finally vindicated. One aspect that was still troubling people at large was the availability of software to work the computations. MCMC , Gibbs Sampler, Metropolis-Hastings all were amazingly good concepts that needed some general software that could be used for the same. The story gets interesting with the contribution from David Spiegelhalter

David Spiegelhalter

Smith’s student, David Spiegelhalter, was working in Cambridge at the Medical Research Council’s biostatistics unit. He had a rather different point of view about using Bayes’ for computer simulations. Statisticians had never considered producing software for others to be part of their jobs. But Spiegelhalter, influenced by computer science and artificial intelligence, decided it was part of his. In 1989 he started developing a generic software program for anyone who wanted to use graphical models for simulations. Spiegelhalter unveiled his free, off-the-shelf BUGS program (short for Bayesian Statistics Using Gibbs Sampling) in 1991.

Ecologists, sociologists, and geologists quickly adopted BUGS and its variants, WinBUGS for Microsoft users, LinBUGS for Linux, and OpenBUGS. Computer science, machine learning, and artificial intelligence also joyfully swallowed up BUGS. Since then it has been applied to disease mapping, pharmacometrics, ecology, health economics, genetics, archaeology, psychometrics, coastal engineering, educational performance, behavioral studies, econometrics, automated music transcription, sports modeling, fisheries stock assessment, and actuarial science.

A few more examples of Bayes formal adoption mentioned are:

• Federal Drug Administration (FDA) allows the manufacturers of medical devices to use Bayes’ in their final applications for FDA approval.
• Drug companies use WinBUGS extensively when submitting their pharmaceuticals for reimbursement by the English National Health Service.
• The Wildlife Protection Act was amended to accept Bayesian analyses alerting conservationists early to the need for more data.
• Today many fisheries journals demand Bayesian analyses.
• Forensic Sciences Services in Britain

 

Rosetta Stones

The last chapter is a recount of various applications that Bayes’ has been used successfully. This chapter alone will motivate anyone to keep a Bayesian mindset while solving real life problems using statistics.

Bayes has broadened to the point where it overlaps computer science, machine learning, and artificial intelligence. It is empowered by techniques developed both by Bayesian enthusiasts during their decades in exile and by agnostics from the recent computer revolution. It allows its users to assess uncertainties when hundreds or thousands of theoretical models are considered; combine imperfect evidence from multiple sources and make compromises between models and data; deal with computationally intensive data analysis and machine learning; and, as if by magic, find patterns or systematic structures deeply hidden within a welter of observations. It has spread far beyond the confines of mathematics and statistics into high finance, astronomy, physics, genetics, imaging and robotics, the military and antiterrorism, Internet communication and commerce, speech recognition, and machine translation. It has even become a guide to new theories about learning and a metaphor for the workings of the human brain.

Some of the interesting points mentioned in this chapter are:

• In this ecumenical atmosphere, two longtime opponents—Bayes’ rule and Fisher’s likelihood approach—ended their cold war and, in a grand synthesis, supported a revolution in modeling. Many of the newer practical applications of statistical methods are the results of this truce.
• Bradley Efron, the man behind bootstrapping, admitted that he had always been a Bayesian.
• Mathematical game theorists John C. Harsanyi and John Nash shared a Bayesian Nobel in 1994.
• Amos Tversky, 2002 Nobel Prize winner thought through Bayesian methods, though he reported the findings in frequentist terms
• Crash courses in Bayesian concepts are being offered in Economics depts. at all Ivy League schools
• Reniassance uses Bayesian approaches heavily for portfolio management and technical trading. Portfolio manager , Robert L Mercer states that ,” “RenTec gets a trillion bytes of data a day, from newspapers, AP wire, all the trades, quotes, weather reports, energy reports, government reports, all with the goal of trying to figure out what’s going to be the price of something or other at every point in the future. We want to know in three seconds, three days, three weeks, three months.The information we have today is a garbled version of what the price is going to be next week. People don’t really grasp how noisy the market is. It’s very hard to find information, but it is there, and in some cases it’s been there for a long, long time. It’s very close to science’s needle-in-a-haystack problem.”
• Bayes’ has found a comfortable niche in high-energy astrophysics, x-ray astronomy, gamma ray astronomy, cosmic ray astronomy, neutrino astrophysics, and image analysis.
• Biologists who study genetic variation are limited to tiny snippets of information reflect that Bayes is the manna from the heavens for such problems
• Sebastian Thrun of Stanford built a driverless car named Stanley. The Defense Advanced Research Projects Agency (DARPA) staged a contest with a 2 million prize for the best driverless car; the military wants to employ robots instead of manned vehicles in combat. In a watershed for robotics, Stanley won the competition in 2005 by crossing 132 miles of Nevada desert in seven hours.
• On the Internet Bayes has worked its way into the very fiber of modern life. It helps to filter out spam; sell songs, books, and films; search for web sites; translate foreign languages; and recognize spoken words.
• A 1-million contest sponsored by Netflix.com illustrates the prominent role of Bayesian concepts in modern e-commerce and learning theory.
• Google also uses Bayesian techniques to classify spam and pornography and to find related words, phrases, and documents.
• The blue ribbons Google won in 2005 in a machine language contest sponsored by the National Institute of Standards and Technology showed that progress was coming, not from better algorithms, but from more training data. Computers don’t “understand” anything, but they do recognize patterns. By 2009 Google was providing online translations in dozens of languages, including English, Albanian, Arabic, Bulgarian, Catalan, Chinese, Croatian, Czech, Danish, Dutch, Estonian, Filipino, Finnish, and French.

What’s the future of Bayes ? In author’s words

Given Bayes’ contentious past and prolific contributions, what will the future look like? The approach has already proved its worth by advancing science and technology from high finance to e-commerce, from sociology to machine learning, and from astronomy to neurophysiology. It is the fundamental expression for how we think and view our world. Its mathematical simplicity and elegance continue to capture the imagination of its users.

The overall message from the last chapter is that Bayes’ is just starting and it will have a tremendous influence in the times to come.

 

Takeaway:

Persi Diaconis , a Bayesian at Stanford says , "Twenty-five years ago, we used to sit around and wonder, 'When will our time come?' . Now we can say: 'Our time is now.' "

Bayes’ is used in many problem areas and this book provides a fantastic historical narrative of the birth-death process that Bayes’ went through before it was finally vindicated. The author’s sketch of various statisticians makes the book an extremely interesting read.

Probability Theory and its Applications ( Volume I ) - Feller

A classic is a book that has never finished saying what it has to say –  Italo Calvino.

These words definitely apply to Feller’s books. Both the volumes by Feller on probability can be considered as classics. The first book deal with the discrete variables while second is far advanced as it deals with measure theory and continuous variables. Markov processes are one of the main sources for Martingales and I had to go back to Feller to work on Markov Processes and managed to go over the entire book instead of only looking up stuff on Markov Processes. Let me attempt to various probability topics that are covered in Volume I. This post is going to serve mainly as my reference to various ideas and thoughts that the book brings out. This is definitely one of the longest posts that I have written till date. It is a ~5500 word summary and hence this post will definitely have a list of some of the powerful ideas in probability.

The author starts off with mentioning three aspects of any theory, a) formal logical content, b) intuitive background, c) the applications. From what I could make out, I think he urges the reader to work on all the three areas for a good understanding of the theory. Formal logical content comprises the axioms, lemmas and theorems based on which the entire probability theory is built. The intuitive background, I guess refers to a constant re-evaluation of our beliefs. Applications, the third and I think the most important part for a guy like me whose sole purpose in slogging through this stuff is to build useful models.

So, in one sense this book needs to be read in such a way that one must check the progress in all the three directions at the end of every chapter by asking these questions to oneself

1. What axiomatic theory has been developed in the chapter?
2. What intuitive notions that the theory supports or refutes?
3. Where can I apply this theory?

Unless you keep asking these questions at regular intervals, it is likely that you will have a limited understanding of the theory. A trivia from the introduction - “Sample space“ – term was coined by Von Mises.

Chapter 1: Sample Spaces

The chapter starts off with a basic description of sample spaces. As the book is all about discrete sample spaces, the number of events in the probability space is considered to be denumerable. The chapter provides umpteen number of examples of sample spaces and provides the necessary understanding to distinguish outcomes to events in a probability space. A fantastic point mentioned in this chapter is about “how probability and experience go hand in hand in selecting the models?” If there are r balls to be places in n slots in such a way that there are r₁, r₂, r₃,….., r_n balls in each of the slots then the probability of occurrence of this event is n! /( Π r_i! * rⁿ) . This is what is taught in elementary courses in probability. However who says this model is correct? Well there are models for which one cannot assign the above probability. In the case of Bose-Einstein Statistics experience leads to an assignment of 1/ ^n+r-1c_r probability whereas Fermi-Dirac computes the probability as 1/^n+r-1c_r. It is impossible to select or justify the probability model by a priori reasoning. Thus there is an intricate interplay of theory and experience while assigning probabilities. There is always this argument you get to hear the finance models are so different from physics models and one must be cautious about it. Well, here is a argument which says physics and finance models do have something in common. Experience and Theory should go hand in hand while assigning probabilities in finance, much like assignment of probabilities in Bose-Einstein/Fermi-Dirac/Maxwell-Boltzman worlds.

Chapter 2: Elements of Combinatorial Analysis

This chapter deals with all the necessary tools to think about combinatorial problems. Tons of examples are given to make the reader understand sampling without replacement, sampling with replacement. The highlight of this chapter is it shows the way to crack occupancy problems. Based on your notions about the probability spaces, a partition of r balls in n slots can take various forms. Hyper geometric distribution is introduced and a nifty linkage is provided between the usage of the distribution to Maximum Likelihood estimate. A glimpse in to “waiting times” is provided using simple balls/urns example. This intuition / simple examples are needed to understand sophisticated concepts such as hitting times in martingales and ultimately develop a model for American option. Yes everything is connected in one way. If you want to evaluate an American option, hitting times become important. To understand hitting times via Martingales, you might have to understand hitting times in simple coin toss examples, which in turn means that you need to understand stuff using simple ball/urn models. It is often seen that students are interested in fancy models and no one is interested in spending time in understanding a few basics. Fancy models look good only in “talks” and not in “action”. Anyways coming back to the chapter, it concludes with a bunch of equalities involving binomial coefficients , stirlings approximation etc. This chapter is a reference chapter of sorts and one can come back to the content at frequent times during the book.

Chapter 3: Fluctuation in Coin Tossing and Random Walks

This chapter is a brilliant and an eye opening one; It can be read independently of the entire book. Many myths are shattered by looking at the world of coin tosses. It explores the concepts of random walks using simple coin tossing experiments. Sophisticated concepts can be extrapolated once random walks are seen as realization of infinite coin tosses. The chapter starts off with “Refection Principle” which finds its applications almost everywhere throughout the chapter. A few examples are given at the beginning of the chapter to provide motivation to any reader. Ballot Problem, Galton’s rank order test, Kolmogorov-Smirnov tests become analytically tractable by viewing it from coin toss perspective. The following questions are explored in this chapter:

• What is the probability that no return to the origin occurs up to and including epoch 2n ?
• What is the probability that the first return to the origin happens at epoch 2n ?
• What is the probability that a random walk always stays to one side until epoch 2n ?
• Probability that the last visit to the origin occurs at epoch 2k considering that the random walk is at epoch 2n now?
• How does the above probability relate to arc sine distribution?
• What is the probability that the random walk spends k % of the time of the total time ?
• Surprising connection between Sojourn times and Last visit times
• What is the probability that the first passage time through r occurs at epoch n?
• What is the probability that the rth return to the origin occurs at epoch n ?
• Connection between first passage time and return time
• What is the probability that the maximum value of the random walk = r in its journey till epoch = 2n

Each of the above questions is solved in a detailed way so that user understands the logic + intuition + practical application of the theory behind these questions.

This chapter is a little overwhelming and needs a re-read atleast a few times to appreciate the results. The applications of concepts from this chapter are wide and far reaching. For example, the sojourn times and last visit to origin’s distribution – ArcSine law can be used in deciding the holding period in a pair trading model. Assuming the spread reverts to origin x number of times in a year, one can fit an arc sine distribution to decide the holding period of the pair.

Chapter 4: Combination of Events

If you consider a set of events A1, A2, …AN, How does one calculate the probability of the event that at least one of the events happen? How does one calculate the probability of the event that exactly k out of N events happen? Once the number of events grows beyond 2, one needs a systematic way to solve these problems. This chapter introduces an approach to calculate the probability that at least one of event happens in a set of events. This approach is then applied to “Matching Problem”, “Occupancy Problem”. Occupancy problem is described in detail and a connection is made to the fact that probabilities reach Poisson distribution asymptotically. This chapter is essential to compute the probability of events such as

• Probability that atleast one of events happens from the event set (A1, A2, …AN)?
• Probability that exactly k events happen from the event set (A1, A2, …AN)?
• Probability that atleast k events happen from the event set (A1, A2, …AN)?

Even though closed form solutions are given for these kind of problems, I wonder whether one really applies these closed forms. For example, if you had 1000 slots and 5000 balls and you distribute these balls randomly in to 1000 slots, Let’s say you wanted to find the probability that exactly 3 boxes are empty ; Just put this command in a loop that goes over N times 

• ( 1000 - length( unique( c ( sample( 1:1000, 5000, T ) ) ) ) == 2 )
• Count the number of TRUE values for the condition in the loop, (count / N) gives the probability.

You don’t need to know any of the stuff mentioned in this chapter. However the reason you probably NEED to know the closed form probability is that it builds the intuition behind such stuff. Simulation gives you an estimate but it will not help you build a probabilistic mindset I guess.

Chapter 5: Conditional Probability and Stochastic Independence

Conditional probability is introduced for discrete variables. The real power of Conditional probability and Conditional expectation is usually seen in the continuous case. Dealing with discrete is easy and appeals to our intuitive notions. The highlight of the chapter is the description of urn models and its usage in the formulating conditional probability models. Polya’s urn scheme is discussed so as to model contagions. Independence is also explored where conditions are given in order for a group of variables to be independent. Product spaces are merely introduced as a thorough description would need measure theory. There are several starred sections in this chapter which can be skipped during the first read.

Chapter 6: The Binomial and the Poisson Distributions

The most popular distributions in the probability theory are introduced in this chapter, namely binomial and Poisson. As is well known that binomial distribution B(r;n,p) increases and then decreases as r increases. Nifty tail approximations are provided in the book that are useful for quick back of envelope calculations. Weak law of large numbers is introduced where convergence in probability is discussed. An easy derivation of weak law of large numbers is shown applying tail approximations of binomial distribution. Subsequently Poisson as a limiting distribution for binomial is introduced. A dozen examples or so are provided to see the relevance of Poisson process. The chapter ends with a brief description on multinomial distribution

Chapter 7: The Normal approximation to the Binomial distribution

For very many cases, we usually deal with large values of n and hence it makes sense to approximate the distribution with a normal or a Poisson distribution. Both versions of binomial distributions, symmetric & asymmetric are shown asymptotically to converge to normal distribution. However the approximation sucks as we move away from the mean of the binomial distribution, a subtle point often not paid attention to. Demoivre-Laplace theorem is then stated and proved which gives a convenient way to formulate probabilities for events that restrict the random variable realizations. One thing to be noticed is that binomial approximation to Poisson is better when lambda is small whereas it does not matter whether you approximate with Poisson or Normal if lambda is large and n is large.

Chapter 8: Unlimited Sequences of Bernoulli Trials

This chapter deals with Borel Cantelli Lemmas that are tremendously useful in formulating probabilities on an infinite probability space. One of the lemmas is subsequently used to prove strong law of large numbers, i.e the cases where the law does not hold good, form a negligible set. Law of iterated logarithm is also introduced in this chapter which I have skipped and would revisit at a later date. Author clearly suggests to skip certain sections of the book so that the reader does lose sight of the forest for too many trees.

Chapter 9: Random Variables; Expectation

Basic definition of random variable, density function, distribution function, expectation of a random variable is given. The chapter can be quickly covered as most of the concepts any reader would have come across in some elementary course. The author makes a few interesting points like

The reduction of probability theory to random variables is a short-cut to the use of analysis and simplifies the theory in many ways. However, it also has the drawback of obscuring the probability background. The notion of random variable easily remains vague as "something that takes on different values with different probabilities." But random variables are ordinary functions, and this notion is by no means peculiar to probability theory.

BASICALLY measure theory is a MUST to get clarity in your understanding.

Negative binomial distribution and its connection to exponential distribution is shown. Examples on waiting times that figure out in Negative binomial distributions can be very crucial in understanding stuff about Martingales. I had never come across Kolmogorov inequality till date and was realized that it is a scaled version of Chebyshev’s inequality.

One thing I consciously keep in mind while reading is that – “Is this content/chapter/theorem/lemma changing the way I think about stuff? Sometimes I forget this principle and I end up in a state of “Awareness”, instead of “Understanding”. Let me give an elementary example. If you were asked to compute the mean and variance of a hypergeometric distribution, then you can as well write its probability mass function and then religiously compute the mean and variance. However that is not the elegant way to do things once you see the covariance formula. Covariance formula gives you the power to break up a big problem in to series of small problems. Applying to this hyper geometric example, you can actually look at the distribution as sum of iids taking 1 or 0 based on the selection of defective ball. Once you zero on to the individual block, you can calculate mean and variance at an individual level, covariance between these individual elements and then just sum up the expectation and variance to get the metrics at a aggregate level. So, this is an example where the existence covariance formula changes the way you think /approach / solve problems. In this book, the author delights at so many places that I bet even a well trained probabilist will have aha moments from this book

Chapter 10: Law of Large numbers

Law of Large numbers and Central Limit theorem are stated at the very beginning of the chapter. Subsequently, the book makes an important point that there is a need to formulate an analogous form for variables which do not have finite expectation. It is a mistake to dismiss variables which do not have finite expectation from our study as they frequently occur in many stochastic processes. The Proof of Law of Large numbers is given by using “method of truncation”, a technique which is commonly used to prove limit theorems.

The chapter talks about “Petersburg game”, the puzzle which stumps any beginner who needs to deal with a situation where there is a need to formulate long term probabilities but the random variables have no finite expectation. Petersburg game is one such example where the random variable has infinite expectation but one can still one form some sort of bounds in order to compute the cost of entering in to the game.

Some nice examples are given to show the wide applicability of Central limit theorem. So, one should not have the notion that central limit theorem is a stricter condition and applies to a subset of the sequences for which weak law holds good. Sufficient conditions for Weak law and Central limit theorem are mentioned clearly and derived. In this context, Lindeberg theorem is mentioned as the sufficient condition for CLT to hold good. For Law of Large numbers to hold good the variables need to be uniformly bounded. The chapter shows that Strong law of large numbers deals with almost sure convergence whereas Weak law of large numbers deals with convergence in measure. It is put in words brilliantly by the author as follows:

“Weak law does not imply the average remains small as you increase the sample size.The value continues to fluctuate between finite and infinite limits. However one can conclude that large values occur at infrequent intervals.”

Strong law on the other hand talks about the entire tail of the sequence of random variables and hence is a stricter condition, meaning Convergence almost sure implies Convergence in measure

Chapter 11: Integral-Valued Variables. Generating Functions

Generating function is a very useful tool for solving a multitude of problems in the discrete variable space. Events for which probability computations appear very complex become tractable with the usage of generating function. What is a generating function in the first place? If you are given a set of real numbers, in this context a set of discrete probabilities, you can create a summary function for all the numbers in the form of a generating function. The name is apt as the function appears like generating all the probability values of a discrete variable. One of the powerful applications of generating function is to compute convolutions. If you have a convolution, i.e sum of certain number of random variables, the probability that the sum of random variables behave in a specific way is analytically intensive from first principles but becomes solvable using generating function. For example, if you toss n coins, what is the probability that no 3 heads appear together in all the trials? Attempt this problem from first principles and then attempt the same using generating function, you will clearly see the power of generating functions. In chapter III of the book, various interesting events such as first passage times, equilibrium times, return times to origin are derived using nifty tricks and observations that involves reformulating the problem so that the problem changes to a known form. However the same problems are solved using generating functions in this chapter and the advantage that one gets from using this tool is that you get to see not only the probabilities but also the various moments.

For example, the probability that in a simple random walk, the random walk always stays equal to or below 0 and at epoch n , reaches 1 can be solved using generating function. The resulting generating function gives much more information of the entire process and helps one get to a ton of results at once. Bivariate generating functions are also touched upon where a brief introduction is given to compound Poisson distribution. The applications of compound Poisson distribution is immense in field of quant finance. Think about it, the bid and ask processes are generally modelled using Poisson distribution and there is a need to understand the generating function of the combined bid and ask process. I have never built a model till date on bid and ask processes but certainly hope to do so in my working life. The chapter ends with a discussion on “Continuity theorem”, which says generating functions convergence is necessary and sufficient condition for a distribution to converge to the limiting distributions. For example when binomial generating function converges to Poisson generating function, then it means that in the limiting case, binomial converges to Poisson. One way to visualize generating function is that it is the DNA of discrete variable. You can study all the properties of the creature using this basic DNA. You can extend the analogy to characteristic functions for more generic random variables.

Chapter 12: Compound Distributions, Branching Processes

One often deals with a sum of random variables in real life applied math problems. The previous chapter dealt with the power of using generating functions to simplify things; a generating function of a convolution can easily be written as product of generating functions of the involved variables. Most often we come across convolutions where the number of independent variables involved in the convolution is a Poisson variable and hence the resulting distribution is called a compound Poisson distribution. A few examples are given relating to compound Poisson distribution so that a reader has a clear idea of the place where such distributions arise. The chapter then moves on to discussing branching processes.

I was little skeptical to go over this stuff mainly because my naive brain said that these processes would not be used as such in math finance. However a quick perusal of math fin literature showed that there was a serious paper on pricing barrier options using branching process. Instead of using standard GBM for the price path evolution, the authors have used a branching process to evaluate a barrier option. Motivated by seeing such an application, I began understanding various aspects of branching process. Frankly till this date, I had always though people use GBM for prices primarily and never thought there could be something else to model the price evolution. I hope someday in the future I will check the validity of using a branching process for price evolution. In theory, the problem that branching process deals is “Given an ancestor which spawns children with a certain probability distribution, what is the probability of certain event after n generations”? The math is little tricky here as , one does not compute a generating function per se but one needs to come up with a recurrence relation which is then used to find out the probability and expectation of certain events. The chapter ends with a discussion of a detailed example of total progeny in a branching process. This chapter makes one realize the immense power of generating functions in probability models.

Chapter 13: Recurrent Events, Renewal Theory

This chapter serves as a superb introduction to Renewal theory which is crucial to OR Models. From a Quant finance perspective, I came across an order book model where Renewal processes where used. There is also a usage of Renewal processes in high frequency trading. So, this chapter has important implications for those looking to develop quant fin models on high frequency data.

The chapter introduces about 9 examples of recurrent events.

1. Return to equilibrium in a sequence of Bernoulli trials and event is “Accumulated number of successes and failures are equal”
2. Return to equilibrium through negative values
3. Accumulated number of successes equals K times the accumulated number of failures
4. Partial sums exceed all the preceding sums
5. Success runs in Bernoulli trials
6. Continuation – Repeated patterns
7. Geiger counters
8. Simple Queuing process where the event that “server is free “constitutes a recurrent pattern.
9. Servicing of machines

In all the above examples, the inter arrival times are iid. They need not be exponential as in the case of Poisson distribution. This is what differentiates Renewal theory from the usual Poisson processes. If the inter-arrival is geometric distribution then the recurrent events/ renewal process is Bernoulli.

Some basic terminology of event types is introduced such as persistent event, transient event, and periodicity of the event. The crucial link between inter-arrival distribution and the waiting time is summarized by generating function, which is then used to arrive at waiting distribution under some of the above recurrent events mentioned. Elementary Renewal theorem is derived; Central limit version for Renewal process is derived. This chapter took me the longest to understand and I have left about 3 sections to revisit at a later date. It is too overwhelming for me on the first read.

Chapter 14: Random Walks and Ruin Problems

This chapter gives a firsthand introduction to stochastic processes. Coin tossing examples are extremely useful to get an intuitive sense of stochastic processes. The chapter begins with the classic ruin problem where difference equations are used to answer the following questions

• What is the probability that a gambler gets ruined?
• What is the probability of a ruin if the casino has infinite amount of money?
• What is the expected duration of gambler’s ruin?
• What is the expected duration of gambler’s ruin if casino has infinite capital?

The chapter is fairly advanced for the first time reader. Generating function approach is used to compute duration and first passage times. The highlight of this chapter is where the author makes the connection between coin tosses and diffusion processes. By imposing some conditions on the size of the simple random walk and time duration of the random walk, one gets a good intuition about general stochastic processes. By providing two approaches, one by explicit probability density computations and second by differential equation approach, the author shows the 2 basic approaches that are used to formulate various stochastic processes.

Chapter 15: Markov Chains

Markov chains are extremely important in developing analytical techniques for solving classical probability problems. Before encountering Markov chains, I had always thought that the only way to approach problems like the following, was to set up recurrence relations and solving them.

• In a simple random walk, what is the probability that the random walk is between a and b?
• What if the absorbing barrier at a is made in to a reflecting barrier?
• What if the absorbing barrier at b is made in to a reflecting barrier?
• What is the mean first passage time of a particular coordinate in the simple random walk?
• What is the mean recurrence time of a particular coordinate in a simple random walk?

This was slightly posing a resistance in my mind as I wanted to computationally solve such problems. I was oblivious to Markov chains which were developed almost 100 years ago and that were used to solve precisely the problems such as above, using matrices. As I spend more time doing math, I am realizing that any problem especially which involves lot of repeated calculations, one should use matrices in some way or the other.

Coming back to the chapter, it starts off by giving idea of a Markov chain using examples like random walk, urn models. It makes it clear that Markov chain by definition generalizes the outcomes to be dependent on the previous outcome, thus it is defined in terms of conditional probabilities. Since one is dealing with a number of possible states, one needs a matrix to represent these conditional probability movements. This kind of matrix is called transition probability matrix. A dozen examples are given with their transition matrices so that a reader gets an idea of the whole stuff. At this stage I was left wondering the reason for not thinking/using Markov chains in my work. I had vaguely heard of Monte Carlo using Markov chain but had never ventured in to understanding it. Last night I was hearing a introductory lecture on Markov Chain and one of the Stanford professors says that “Where do I use MCMC methods is like asking an undergrad, where do you use quadratic equation?” I felt ashamed of the fact that I had never worked on MCMC till date. Have made a resolution that I will learn this technique and see where all its usage makes a tremendous sense in math finance.

The chapter introduces Chapman-Kolmogorov equations which talk about the transition probabilities from state i to state j after n trials. Subsequently concepts such as Closures and Closed Sets are introduced. The terms Closed Sets and Closures might seem abstract but they are extremely useful in breaking up the transition matrix in to stochastic independent matrices which can then be analyzed. This logically leads to the definition of irreducible chain where every state can be reached from every other state. One must be careful to note that an irreducible chain need not be a regular chain , but every regular chain is an irreducible chain.

After the first 4 sections, the chapter then moves in to classifying states. The terms that one must be clear while classification are

• Persistent - means that the unconditional probability that the path moves from state j to state j is 1.
• Transient - means that the unconditional probability that the path moves from state j to state j is <1.
• Periodic - States are visited periodically
• Aperiodic - There is no sense of periodicity in the way states are visited.
• Null - a persistent state where mean recurrence time is infinite.
• Not Null - a persistent state where mean recurrence time is finite.

The above definitions are useful in classifying states. So, one can classify the Markov chain in to the nature of states. Typically one is interested in “aperiodic-persistent -Not Null “states. These are called Ergodic states.

The chapter subsequently talks about invariant distributions, a key concept that will be used in Markov Chain Monte Carlo. In an ergodic markov chain , if one looks at the probability of reaching a specific state from any of the initial starting states, it converges to a fixed number. This means that after n iterations, you will end up with a transition matrix that is a fixed row matrix. This means that it does not matter what initial distribution you start from. You end up with a constant probability in a specific state. Now one can flip the question – What is the condition that the fixed weight vector that you end up is the same as the initial distribution? The answer is not easy, given any transition matrix. However there are certain types of transition matrices for which one can work out. A number of examples that you come across have transition matrices that are band matrices with values only on the upper diagonal and lower diagonal. For such type of matrices, the book gives a condition for the presence of an invariant distribution. This condition is then applied to a variety of situations, post which, one can formulate an opinion about the stability of the transition matrix. The examples where the invariant distribution is checked are

• Reflecting barriers
• Ehrenfest model for diffusion
• Bernoulli- Laplace model for diffusion
• Recurrent events

Once you read this section, you wonder how easy computations become once you formulate problems using Markov chain. Choosing the states of the Markov chain is not always obvious. Look at this card shuffle example where choosing states in a smart way reduces the computational complexity of the problem.

After reading this chapter, you will understand the difference between Markov chain and stochastic process. In a Markov Chain, all that is needed to understand the conditional probability for a state n is the previous state. In a stochastic process, it is not just the previous state but the entire history of the process will play a role in the prediction of future state. Markov property is related to conditional probability whereas Martingale is related to Conditional expectation. So, there is a lot of difference between the two mathematical objects. A Markov process need not be a martingale, though Markov processes are a good source for martingales. Similarly not every martingale is a Markov process.

Chapter 16: Algebraic Treatment of Markov Chains

I skipped this chapter and instead preferred Matrix approach presented in “Finite Markov Chains”.

Chapter 17: Simplest Time Dependent Stochastic Process

This chapter uses the concepts of conditional probability to set recurrence relations which in turn could be looked as a PDE. You get to see the construction of simple time dependent stochastic processes like Poisson, Birth process, Birth-Death Process etc. The last chapter gives a flavour of the stochastic process from a discrete world view.

Takeaway:

The author’s enthusiasm for the subject is infectious, as evident from the way the book is written. The book has outstanding breadth and depth. Any seasoned probabalist would still find something new in this book, even on an nth reading. Every year there are professors/ practitioners/ instructors/ modelers referring to / debating on /agreeing with /pondering over various aspects mentioned in this book. In that sense, the content of the book is timeless.

The Housekeeper and the Professor : Summary

The story is about an old professor and a special bond that develops between the professor and his housekeeper. The professor has a peculiar problem that he cannot remember anything beyond 80 minutes. His memory loss caused by a certain accident in his middle age leads to a strange life that he leads. Since he cannot remember anything beyond 80 minutes, he is forced to write short notes and pin it up on his suit so that he can glance at them everyday and remember stuff. His sister-in-law generously takes care of him and provides him with basic amenities like food , shelter and a study room. The professor despite his old age continues doing math. To take care of the cooking,cleaning and other household activities, his sister-in-law appoints a housekeeper.

Since the professor has no memory beyond the last 80 minutes, the housekeeper has to introduce herself everyday to the professor to gain entry in to the house. The professor has a peculiar way of letting her in to the house. He would ask a few questions whose answers are numbers like her shoe-size, her date of birth and allows her to enter the house. The housekeeper brings along her son to the work, at Professor’s request . The Professor soon develops a liking toward the kid and slowly starts taking time to teach him some basic math. He fondly calls him “root” , because of his rather flat head and resembles a square root sign.

Math becomes the focus of most of the conversations in the house. The housekeeper is sucked in to the infectious enthusiasm that the professor displays. Even though she is supposed to merely take care of household chores, she tries to strike conversation with the professor whenever possible and in the process learns about a whole lot of math stuff like perfect numbers, amicable numbers, prime numbers, fascinating square root sign, 0 (queen of numbers), triangular numbers, Euler’s equation, the way all the primes can be divided exactly in to two categories etc. Professor’s liking towards the kid makes him spend more time with him teaching math in such a way that it brings an element of delight and surprise even in some mundane math concepts.

The book ends with Professor’s death and the Housekeeper’s son becoming a math faculty at a local college. Well, as the story has a bit of melodrama in it, it is no wonder that this book was made in to Japanese film titled “The Professor and His Beloved Equation”.

Via Wikipedia :

The Professor's Beloved Equation is a Japanese film released January 21, 2006 and directed by Takashi Koizumi. It is based on the novel The Housekeeper and the Professor.

In contrast to the original work, which is told from the perspective of the narrator, the film is shown from the perspective of a 29 year old root as he recounts his memories of the professor to a group of new pupils. Though there are a few differences between the film and the original work (for example, the movie touches on the relationship between the professor and the widow while the book does not give much detail), the film is generally faithful to the original.

Finite Markov Chains : Summary

This book is an awesome resource for understanding finite Markov chains. The book is written in Pre-Latex era and hence one has to struggle to follow the notation. Is the Struggle worth it? IT IS, if you are looking at developing a Matrix perspective towards “Discrete Stochastic Process”. IT IS NOT, if you are looking at quick and dirty formulae. The first version of the book appeared in 1960 and second version in 1976. I wasn’t even born when these books came out –:) . However like many things in life, things that age have their own charm. The book serves as a precursor to understanding Markov chain Monte Carlo method which is an essential tool for any quant.

Chapter 1: Pre-requisites:
Most of the stuff can be quick read in this chapter. What I found interesting was the mention of set theory concepts such as equivalence relation, weak ordering relation, minimal elements etc. One must patiently go over these stuff as they find immense application in classifying Markov chains. An attempt is made to describe a simple stochastic process and readers might find this example appealing before venturing in to complicated stochastic processes. I understood Cesaro-Summability and Euler Summability clearly in this context , even though I had quick read them in “Understanding Analysis”- Abbott.

Chapter 2: Basic Concepts of Markov Chains

The chapter starts off by defining a Markov process which essentially is a process where essentially previous outcome is all that is needed to predict the probability of future outcome. Markov chain is a finite Markov process where the transition probability from step i to step j does not depend on the trail number. One of the equivalent ways to state a Markov chain is that , given the present, the past and future are completely independent of each other. To deviate in to philosophy here a bit, I think we should lead our lives also like a Markov process. Whatever be the past, given the present, we must work in the present, be in the NOW so that future becomes independent of the past. Ok, enough of this philosophy crap J , Let me get back to the contents of the chapter.

What’s the difference between Markov Process and Markov Chain ?

Well, Markov chain is a type of Markov process. Apart from that, one of the biggest differences arises from the fact that a Reverse Markov process is also Markov process but a reverse Markov chain need not be a Markov chain. The transition probability matrix of a reversed Markov chain may well depend on the trail number and hence does not qualify to be a Markov chain. This nifty difference is sometimes not highlighted clearly most of the times in other books.

The author gives a set of examples representing Markov chains to get an idea of various finite Markov chains one can come across. One of the reasons I got interested in Markov chains is that they are an excellent computational tool for classic probability problems. At the same time, they serve as an ideal platform to understand stochastic processes. I used to struggle to work with problems involving absorbing barriers, reflecting barriers in a simple random walk. Setting up a recurrence relation and solving using PDE approach or some tricky method never gave me a tool to understand the stuff. Markov chains on the other hand actually give a fantastic way to compute these using matrices. I love when any problem is formulated using matrices. It makes everything so pleasant for a problem solver.

Classification of states in a Markov Chain:

The author uses set theory concepts such as partial ordering, equivalence classes induced by partial ordering, minimal elements of the partial ordering of equivalence classes etc to classify the states of a Markov Chain. Well, I was aware that “Relation” can be used to define equivalence classes that partition a set. But beyond that, my understanding of “Partial Ordering”, “Minimal Elements” etc was shallow. Hence I took a detour for a few hours and went through “Naive Set Theory” – Paul Halmos. I managed just enough to understand stuff about Markov Chain.

You start off with a relation – iRj, you can reach state i from state j, meaning it is a type of relation and you can then extend this to another relation ( iRj and jRi ) meaning you can reach i from j and j from i . So, you start with a weak ordering relation, and extend it form equivalence classes. When I first came across these concepts, I found some resistance in understanding these ideas. Why should I care if you start with a weak relation and you can extend that weak relation so that you can form equivalence classes?

Well, all these concepts make tremendous sense when you look at a Markov Chain. Firstly,the weak ordering relation can be extended to”communication” relation to first classify the states in to equivalence classes. Subsequently, you can order these states and the minimal elements of these ordered states form ergodic states. Cutting the fancy stuff around the word ,”minimal”, all it means is that if you take any element x of a set U, if iRx holds then xRi holds too. All those elements i form an ergodic set. One must understand the reason for this ordering and the rationale behind ordering. Once you order stuff , you have the transition matrix as follows

This pattern emerges once you order the states accordingly. The first thing that strikes you about the above matrix is that you can higher powers of this matrix retains the individual transition matrices on the diagonal and thus one can individually analyze these matrices without worrying about the entire chain.

The chapter then goes in to giving labels to various kinds of Finite Markov Chains. There are two broad categories of Markov Chain. Firstly the chains which do not have transition states. Secondly, the states have transition states.

Chains without Transition States are also called chains with single ergodic set (ergodic chain). They can be further divided in to:

• Regular Markov chains symbolize the transition matrix where each state can be reached from any other state. Thus all the elements of the transition matrix will eventually become positive.
• If the chain has a period d then such a chain is called cyclic Markov chain.

Chains with transition states can be further divided in to

• Absorbing chain where the ergodic states are unit sets
• All ergodic sets are regular. This means if you take an ergodic set, then you can reach any state from any state in that ergodic set
• All ergodic sets are cyclic. This means that the states in the ergodic state are cyclical
• Both cyclical and regular ergodic states

As can be seen from the above illustration, almost all the categories can be expressed using simple random walk. Given various states, what are the kinds of questions that one would be interested in?

Regular Markov Chain Questions

• If a chain starts in Si, what is the probability after n steps that it will be in Sj?
• Can we predict the average number of steps that the process will be in Sj? Does it depend on where the process starts?
• We may wish to consider the process as it goes from Si to Sj. What is the mean and variance of the number of states passed? What is the probability that process passes through Sk?
• Study a subset of states and observe the process only when it is in these states

Transient States Questions

• Probability of entering a given ergodic set , starting from Si
• Mean and Variance of the number of times that the process is in Si, before entering an ergodic set, and how this number depends on the starting position ?
• Mean and variance of the number of steps needed before entering an ergodic set starting at Si?
• The mean number of states passed before entering an ergodic set , starting at Si

The book is sequenced in a way that the above questions are answered systematically. Absorbing Chains, Regular Markov Chains and Ergodic Chains are covered as specific chapters.

Chapter 3: Absorbing Markov Chains

The book looks at Absorbing Markov chain by segregating transient states from Persistent states. It then analyzes Transient State matrix and derives basic formulae in terms of matrix operations. The highlight of this book is “Fundamental Matrix Approach”. For any Markov chain, the book tries to zero on to a specific matrix which is fundamental to all the calculations relating to the Markov chain

Fundamental Matrix for Absorbing Markov Chains is derived: . The reason it is called Fundamental is because it is used in formulating solutions for most of the interesting questions about Absorbing Markov Chains

Solutions in Matrix form are furnished for the following:

• Total # of times that it is in various states
• Probability of absorption
• Total time before it gets absorbed
• Variance of total time before it gets absorbed.

From the examples give, all of them have high variance for the mean estimates. Is this a general case ? I mean are all the estimates of Markov chain characterized by high variance? I don’t know. Will find out someday.

Chapter 4: Regular Markov Chains

Regular Markov Chains are explored in this chapter using Matrices. The limiting properties of Regular Markov chain are explored where the chain settles down in to a constant row matrix after n iterations. This limiting markov chain is then used to state “Law of Large Numbers” . Most of us would have heard of “Law of Large Numbers” for independent trials where the statements become weak law or strong law based on whether the convergence is almost sure or convergence is in probability. This law from a Markov chain is radically different as it removes , “iid” clause from the law of large numbers and thus massively expanding its scope. This form of law was worked out by A.A.Markov in 1907. In the 100 odd years that have passed since then, Markov chains are now practically used in tons of applications.

• The book’s USP is Fundamental Matrix and hence one sees the Fundamental Matrix derived for these Regular Markov chains as well, which takes the form . This matrix is then used to compute
• Mean of first passage times for various states
• Variance of first passage times for various states
• Correlation for the above events

The chapter then talks about Central Limit theorems for Markov chains. It merely states the theorem and defers proving the same. CLT for Markov chains connects the (average number of visits to a particular state, its limiting value) WITH Standard Normal Distribution.

The preface in the book mentions one of the reasons for the second edition. In the above formulae, Fixed weight vector was used to obtain the Fundamental Matrix. However there is an alternative method where any constant row vector can be used to obtain Z. The appendix of the book mentions the paper where pseudo-inverses are used. 

Chapter 5: Ergodic Markov Chains

What if there is cyclicality in chains with transient states ? This chapter delves in to the math behind such chains. Condition for a markov chain to be considered as reversible is also mentioned. A Markov chain being reversible or not, has a great impact from a simulation perspective.The book then talks about further extensions to the above mentioned chains. Basically it involves stuff where a transient chain is made in to an persistent chain forcefully to compute some interesting stuff and vice versa.

In the concluding chapter, the book shows various application of Markov chains like

• Random walks
• Ehrenfest Model
• Application to Genetics
• Learning Theory
• Mobility Theory
• Open Leontif Model

By no means these examples should make you think that Markov chain is used as Toy examples. The research and amount of stuff that has been done on Markov chains for the last 100 years is so massive that it has found applications in a wide variety of fields from sports betting to

Take away:

Persi Diaconis (the iconoclastic Stanford Professor) remarks “To someone working in my part of the world, asking about applications of Markov chain Monte Carlo (MCMC) is a little like asking about applications of the quadratic formula. The results are really used in every aspect of scientific inquiry.”

Indeed, Markov Chain Monte Carlo methods have revolutionized the field of statistics. My takeaway from the book is not so much so about simulation as it is about understanding Martingale Objects. While formulating a Martingale, If you are able to visualize vaguely the discreet Markov Chain in the background, I bet your understanding will be much better.

Andrei Andreevich Markov(1856 –1922 )

It is profoundly important to read around the area that you are working on; more so in mathematics. Theorems that you see in the texts are usually a result of ardous efforts / long drawn fights between mathematicians / result of being in extreme hysteria(Cantor for example)/ family duels(Bernoulli)/ Open air competitions(Solution to cubic & quartic polynomial ).

It is important for any person building stochastic models to have a thorough understanding of Markov chains as they typically lead to random walks and Brownian motion concepts .Typically one comes across some form of limit theorem in elementary courses on probability or statistics. In a crude form, one has an intuitive understanding that “You take a large collection of numbers and you take an average, it converges to some number.” It is tucked away in most books under some title which has the words,” law of large numbers” in it. However you miss the entire action if you miss the historical development to this concept and more importantly, the application of this law to dependent variables. Almost all the forms of weak law that one usually comes across has “independent and identically distributed” statement in it. This is where Markov’s work becomes important. Almost 100 years back he generalized the weak law to dependent variables. Sometimes historical developments such as these are not highlighted in math books and one needs to resort to reading around the material to get an idea of the immense contributions of the mathematicians.

This brief on the life of Markov is elegantly written. The takeaways from this note are :

• Markov’s animosity towards his colleague Pavel Alekseevich Nekrasov was a key reason for the development of Markov Chains. He desperately wanted to prove Nekrasov wrong
• Markov was Chebyshev’s student , the person behind the famous Chebyshev’s inequality
• Markov emphasized problem-solving to understand various aspects of mathematics
• Prelude to Markov’s work on extension of weak law
  • 1738 – Jacob Bernoulli proved it for independent binary random variables
  • 1837 – Poisson extended to variables where probability of success and failure depended on the trial number
  • 1867, Pafnuty Chebyshev’s paper, “On Mean Values”, generalized the weak law of large numbers to any sequence of independent random variables with bounded second moments
  • Markov generalized this law for the case where the variances do not exis
  • 1909 Markov extended the weak law to dependent variables.
  • Markov paid extraordinary attention to details and looked down upon statistics. He always thought mathematics is at a far higher pedestal than statistics. Though over the years, his correspondence with a statistician Chuprov changed his mindset.

The note concludes saying

Markov proved that the independence of random variables was not a necessary condition for the validity of the weak law of large numbers and the central limit theorem. He introduced a new sequence of dependent variable, called a chain, as well as a few basic concepts of chains such as transition probabilities, irreducibility and stationarity. His ideas were taken up and developed further by scientists around the world and now the theory of Markov Chains is one of the most powerful theories for analyzing various phenomena of the world.

Once you read this note I am certain that you will start looking at Markov chains with awe and admiration.  The very essence of simulating random variables has undergone profound changes with the application of Markov chains.

Measure, Integral and Probability : Summary

I have found this book very challenging to go over a few years ago. This was one subject that I found it very difficult to understand. The main reason being I was never exposed to any real analysis course back then. Needless to say, my understanding was shallow. The offshoot of this limited understanding has come to plague me now when my task is to develop a model that is completely based on general measures. The model that I am trying to customize is heavily based on general measures. The model’s creator has given a few guidelines and that’s about it. The guidelines point to heavy usage of martingale theory. I realized that my understanding of general measures and martingales was pathetic and I decided to go over this book, being well aware of the fact that the book would be very challenging.

Reading this book after 3.5 years, I realized that this book is amazingly useful for a persistent reader. However unlike the last time, I was prepared with the prerequisites needed to go over this book. This book has a tall order of pre-requisites something the title fails to convey. A reader must have good knowledge about Analysis on Real Line, Finite Dimensional Vector Spaces, Metric Spaces and at least 10,000 ft view of Functional Analysis. Summarizing a math book is very tricky and usually no summary can do justice to the contents of the book. My intent of writing this summary is to highlight an important aspect of the book, i.e, the way probability theory and measure theory concepts are explained in parallel. The intent behind theorems is made crystal clear by providing the relevant applications in probability theory and math finance. As you go over Lebesgue theory, you will be able to connect the various probability concepts that are related to Lebesgue theory. In that way, you will not find the book dry at all. Let me try to summarize the main chapters of the book from this point of view. 

Chapter 1 : Motivation and Preliminaries

As the title of the chapter suggests, it contains some necessary real analysis concepts to follow the content of the book. It starts off with asking a simple question “What is the probability of choosing a random number between (0,1)?”. For a reader who is exposed to classic probability stuff where he/she deals with finite outcomes, the way to answer such a question poses a challenge. How to compute probability when there are infinite outcomes? Such questions can be only answered with the help of a mathematical framework. The chapter introduces some set theory notation and topological concepts. It then moves on providing arguments for an alternate integral rather than Riemann integral. The classic Dirichlet example is used to show the reader that there are integrals which are not Riemann integrable. Infact there are tons of issues with Riemann integration. A reader would be well advised to read other books before reading this concise Riemann bashing in the book. The authors state that the focus of the book is to show the essential role of Lebesgue measure in the description of probabilistic phenomena based on infinite sample spaces.

Chapter 2 : Measure

Probability is basically a type of measure on a probability space. In order to understand probability spaces, one needs to have a thorough knowledge of sigma fields and lebesgue measure. Probability measure is a countably additive measure on the sigma algebra of the outcome space. This chapter does a superb job of making the reader understand where all the pieces fit like outer measure, lebesgue measure, Lebesgue measurable field, Borel sigma algebra etc. The chapter starts off with defining null sets as they are key to understanding measure of sets like rationals,finite sets, cantor sets. All these sets have lebesgue measure 0. Outer measure is defined and its properties are discussed. The typical problem with outer measure is explained, i.e measure is countably subadditive. Subsequently, Lebesgue measure is introduced precisely to solve this issue. By selecting a subset of the power set of R(Lebesgue measurable sets), countably additivity is achieved. Topological properties of Lebesgue measurable sets are discussed so that one can use appropriate definitions and concepts from topology to prove and derive new theorems. Borel Sets and Borel Sigma algebras are then introduced so that one can conveniently talk about family of Lebesgue measurable sets which have the necessary properties. It is also shown that the Lebesgue sigma algebra has more elements than Borel Sigma algebra, though for probability applications, one can conveniently ignore the differences and work with Borel Sigma algebra.

Chapter 3 : Measurable Functions

Random variables , a 101 term in probability theory, is actually a misnomer. It is not a random variable but a function. To understand the function and properties of the function, this chapter talks about measurable functions. The beauty of these functions is that limiting operations on a sequence of measurable functions preserve measurability. One often comes across “Sigma field generated by X” in most of the theorems. This chapter makes the term precise by giving a definition for the same. Intuitively the sigma field generated by X is coarser than the sigma field of the measurable space. Once you understand that a probability distributions is nothing but a set function on a coarser sigma algebra you can organize your thoughts the following way:

• You have Omega which is the set of all out comes
• You define a measure on a sigma algebra generated by Intervals ( Borel Sigma Algebra)
• The measure is defined in such a way that the measure is countable additive on Borel Sigma Algebra
• This measure defined in such a manner is Lebesgue measure
• Each subset of Sigma algebra is an event
• You define random variable on Sample space
• So, obviously the sigma algebra of this random variable is coarse
• The probability measure on this coarser sigma algebra can be summarized with the help of distribution function / discrete measures / absolutely continuous measures / mix of discrete and absolutely continuous measures.

Chapter 4 :  Lebesgue Integral

“What has probability distribution got to do with integration”? , is a beginner’s question as it opens up the whole Lebesgue integral theory. An integral is basically an area under the curve of a function, at least that’s the intuitive notion. Now one can find measures on probability space such that integral with respect to a measurable function f, over the measurable space is 1. Such measures are called absolutely continuous measures. From a computational angle, one always writes an integral for continuous variable for calculating moments, probabilities etc. But behind the integral lies the entire theory of Lebesgue measurable functions. A non negative Lebesgue measurable function serves as the density function for an absolutely continuous variable. For a very loooooong time I thought there were only discrete / continuous/ mix of discrete and continuous variables. However after going over Cantor set and its mysterious properties, I realized that it is very much possible to construct measures which do not belong to { Discrete, Absolutely continuous, mix of Discrete and Absolutely Continuous measures}. They go by the name singular measures. Anyways, this chapter does not discuss such measures. The relevant background to understanding concepts like density function, distribution function, expectation and characteristic function of a random variable is provided in this chapter. They are

• Definition of Lebesgue integral via Simple functions
• Properties of Lebesgue integral
• Convergence Theorems like Monotone Convergence theorem and Dominated Convergence theorem
• Relation between Riemann Integral and Lebesgue integral .

Chapter 5 : Spaces of Integrable Functions

Moments for Random variables are usually introduced in a computational way. If it is discrete variable or a continuous variable, then there are usually formulae that are introduced in any undergraduate course. However to marry with the concept of “X is a measurable function”, one needs to know functional analysis. Any concept relating to Moment calculations or Characteristic function computations is related deeply to functional analysis. This chapter introduces the concepts of metric space, vector space and inner product spaces. The concept of Lebesgue measurable function is expanded to spaces where each individual function is a point. Vector spaces with Lebesgue measurable functions are introduced with the norm defined. Subsequently Hilbert Spaces are introduced where each point is a Lebesgue measurable function and the functions have their L² norm finite. Hilbert Space is important as one can define an inner product space and can make use of orthogonality aspects of a vector elements. The inner product induced norm gives more flexibility in working with orthogonal variables and Fourier functions. Even though Fourier series are not talked about in the book, Hilbert Spaces are extremely useful in relation to Fourier series. The other interesting aspect of L^p spaces is that they are complete, meaning every Cauchy sequence of functions converges to a point in the space.

One of the highlights of this chapter is the construction of Conditional Expectation where Hilbert Spaces are used to give a preliminary introduction. Conditional expectation is a very interesting concept and opens up a completely different way to look at random variables. Conditional expectation deals with understanding a random variable under a sub sigma-algebra. For a discrete variable E(X/Y) calculation is easy. For a continuous variable, it is easy if the conditional density is given. This is the way it is presented in undergrad books where all the discussion about sub sigma algebra is avoided. However if Y is a general random variable, then Expectation of X given Y has no formula. It needs to be implicitly calculated. Existence of such a variable is obtained from a deep theorem in probability Radon-Nikodym theorem. This theorem is covered in a separate chapter of the book, a chapter which I found to be the most difficult to follow.

Chapter 6 : Product Measure

The natural transition from a single dimensional probability space to multidimensional probability space is shown in this chapter. For simplicity sake, if there are two sigma fields, one must work on product sigma field to make sense of random variables defined on both spaces. Lets say X is defined on Sigma algebra F1 and Y is defined on Sigma Algebra F2, then a variable like Joint distribution would be defined on the product sigma algebra. For this new space, obviously one needs a measure. The notion of length in a one dimensional space is extended to a set of intervals on a plane to define the measure. The chapter gives a very good construction to the product measure by introducing projections. It culminates in Fubini Theorem which gives the condition for swapping integrals for a multiple integral case. All these fundas are extremely useful in describing Joint Distributions, Convolutions, Conditional density and Characteristic functions. There is a long proof to show that Characteristic functions determine distributions for random variables.

Chapter 7 : Radon Nikodym Theorem

I think this is the toughest of all chapter as there are far too many concepts that are introduced. At times I felt overwhelming. It starts off by introducing a property of measures called “absolutely continous”. Measure m1 is said to be absolutely continous with respect to measure m2 if they agree on Null sets. So, why is it relevant to explore this property ? The reason behind this question is “Radon Nikodym theorem”. The relation between the measure m1 and m2 where m1 is absolutely continous with respect to m2 is given by Radon Nikodym derivative. If I were to describe naively, it would be like this : Lets say you have a space Omega1 equipped with m as measure. Now if one were to look at another measure m1 which is absolutely continous with m, then all the computations with respect to m1 can automatically be written as an equivalent problem with respect to measure m. (Option pricing math thrives on the existence of Radon Nikodym derivative). The section ends with Lebesgue decomposition theorem which states that a sigma finite measure m2 can be expressed as a combination of two measures , one being absolutely continous with m1 and other being singular / perpendicular to m1. This smells like the case of a vector in finite dimensional space which can be decomposed as a vector in a projected space and vector perpendicular to the projected case. In this case, instead of vectors, we are dealing with measures.

The chapter then moves on Lebesgue-Stieltjes measure. Well, frankly I did not understand this section and had to go over a book on Lebesgue – Stieltjes to make sense of this section. The effort of going over a separate book and then coming back to this section proved useful in understanding this section. It took me sometime to understand this section and I think I kind of got the crux of it, thought I intend to read it a few more times later. The crux of Lebesgue Stieltjes measure is this : If you want to weight the interval over which a function is integrated in a different way, lets say g(x), then one needs Lebesgue Stieljes integral and this integral induces a sigma finite measure called Distribution measure, which is a function. Now given this distribution function F, the key questions to answer are:

• Does this induce a measure ?
• Does this induce a density function ?

Both are very important questions. It is shown methodically that F does induce a measure m_F

However there are additional restrictions for F in order to induce a density. The condition is that F should be absolutely continuous. Only when F is absolutely continous , one can talk about density of such a Distribution function. What’s the connection between this density and the lebesgue measure ? It’s the Radon Nikodym derivative which again comes to rescue and clearly fits in the linkage. There are other measure decompositions that are discussed like Hahn-Jordan decomposition. An elegant description of these decompositions can be found at A Mind for Madness. Connecting these concepts to probability applications, the chapter explores the properties of Conditional Expectation. It then discusses Martingales, which are the most important mathematical objects as far as math-fin is concerned. Typically a stats student spends his time looking at random variables, distributions, limit theorems like Weak Law, Strong Law, Central Limit Theorems etc. However this exposure is not enough for understanding random processes. Like one tries to understand iids, one must spend time in understanding Martingale processes. One slowly begins to realize that Martingales have their own set of rules, set of limiting theorems, set of inequalities etc. So even though this book covers martingales in a few pages, one must not mistake that that is all there is to it. This chapter requires multiple readings as it has too many concepts to be digested at one go. I am certain to revisit this chapter over the course of my working life.

Chapter 8 : Limit Laws

This is the most useful chapter of the book from stats perspective. To begin with, the chapter discusses various modes of convergence for random variables. Uniform, pointwise, almost everywhere, Lp norm and convergence in probability. One needs to have a clear picture of the relationships between these modes of convergence. The chapter then introduces weak law of large numbers and strong law of large numbers where the former talks about convergence in probability and the latter talks about almost sure convergence.

Convergence in distribution is a very different animal as compared to other modes of convergence. That’s the reason it is called weak convergence. Irrespective of the individual distribution of random variables, the cumulative distribution function can converge to a specific probability distribution and hence the name, convergence in distribution. Central Limit Theorem is one of the theorems introduced in various elementary statistics course / business statistics courses in MBA etc. One usually comes across the statement and wonders why it is true. Why should let’s say a specific form of sum of random variables converge to standard normal distribution? The question might seem appropriate but to understand the rationale behind it requires a good understanding of limit laws. In that sense this chapter is very unique. However the theorems themselves are very long winding. I have gone through them but I will certainly go over them again on some long rainy day.

 Takeaway:

Authors build up measure theory ground up and provide motivation for the reader to understand the concepts by shows applications in math finance area. In every chapter, whatever concepts are introduced, an immediate application in math-fin area is provided, thus making the seemingly dry measure theory, an interesting read.

The Lebesgue-Stieltjes Integral : Summary

Firstly, something on the pronunciation –:).Lebesgue Stieltjes is pronounced as Le-BECK Steel-ye. The former being a French mathematician and the latter being a Dutch mathematician and the integral being named after their outstanding contribution to the field of analysis. I came across Stieltjes integral for the first time in Marek Capinski’s book on Probability. It was introduced in relation to measure decomposition theorems. The treatment in Marek Capinski’s book is very concise and hence I really did not understand the significance of Lebesgue Stieltjes integral. Also I came across this reference to this integral while I was studying Ito’s integral a few years back. Back then, I had no clue about Lebesgue Stieltjes integral and had never bothered to check its limitations in describing Brownian Motion. All I cared that it was somehow useless for describing Brownian motion. My limited understanding became a handicap in understanding  measure decompositions. So, finally I had to get out of limbo and slog through to understand the integral. I picked up this book which looked like an accessible introduction to the integral, which in the hindsight appears the perfect choice. Let me try to summarize the contents of the book.

The first three chapters of the book cover the prerequisites needed to understand the Lebesgue-Stieltjes integral. Basic terms like supremum, infimum, Cardinality, Topology of R are covered in the Chapter 1. Chapter 2 talks about monotone sequences, monotone functions and explores their properties. It subsequently introduces the concept of bounded variation and absolute continuity. Absolute continuous functions are a subset of continuous functions. A few theorems are stated relating to functions which have bounded variation. Chapter 3 gives a basic introduction to Riemann integral and cites the Dirichlet function as an example where Riemann integral breaks down. Not only is the function not Riemann integrable, it reveals a bigger problem with Riemann integral. If we consider a sequence of functions that are Riemann integrable, then we might not be certain that the limiting function is Riemann integrable.

Chapter 4 is the meat of the book. The approach taken by this book is the step function approach. Instead of taking measure theory approach, the book takes a step function approach. As is found in most books which avoid measure theory, the step function approach is an easier way to understanding Lebesgue Stieltjes and Lebesgue integral. The following term are introduced :

Subsequently Lebesgue-Stieltjes integral is defined as follows. Let me try to put in simple words( which is always a challenge than writing an equation). One starts off with sequence of step functions, applies certain criteria like finite measure and then creates a sequence of these functions called alpha summable. The key idea is this :

If you have a function and you want to integrate the function over Interval I with respect to alpha measure, You create a set of all possible alpha summable functions and in each case the alpha summable function is always greater than the function that we are interested in integrating. So, instead of integrating the complicated function , we are integrating all possible alphas summable functions over the same interval. Obviously the latter is easier to do as they are all internally a combination of step functions. Once you find the integral of all these alpha summable functions, you take the minimum of those values, or to use the right word, infimum of all those values, what you get is the Lebesgue-Stieltjes integral with respect to alpha measure. (That was mouthful!) . To see it with math symbols( which is so elegant) it is as follows :

The chapter ends with a discussion on the differences between Riemann and Lebesgue integral. Basically the thing to be understood is that Lebesgue integral of a function is computed by a set of approximating functions which are much more generic than the step functions used in the Riemann sense. This coupled with the fact that the measure itself is generic makes Lebesgue integral applicable to a mind boggling set of functions. However as the author rightly points, Lebesgue integral’s true power is visible in Convergence theorems which help in computing integrals of very complicated functions over complicated sets –:)( For example Dirichlet function). There is also a nice example of a function which is Riemann integrable and not Lebesgue integrable. One key requirement for any function to be Lebesgue integrable is that the integral must be absolutely convergent.

Chapter 5 deals with the properties of Lebesgue-Stieltjes integral. Integrability of f⁺, f^-, |f| are explored. The section on null sets and null functions is very tedious. For someone who is exposed to measure theory where sets with measure 0 and null sets are explored at the very beginning, the treatment in this book looks very circuitous. All the proofs in this section of the chapter can be massively simplified by using set theory concepts and using measure theory. So, even though step functions can be used to interpret lebesgue integrals easily, there is a flip side to it. Things like null sets becomes very challenging to understand. The chapter then states the important convergence theorems like Monotone Convergence Theorem, Fatou’s Lemma, Dominated Convergence Theorem, Beppo-Levi’s theorem. All of these are merely stated and no proof is given. The reader should appreciate that these theorems are the main reason that Lebesgue theory became massively popular. Dominated Convergence theorem is a very broad sufficient condition ( Note: It is not a necessary condition). So, these theorems can be used to approximate complicated integrals by sequence of functions and then integral and limit can be swapped to compute the value of the integral. I found the last section of this chapter to be very interesting. It talks about extending theory in two directions 1) by allowing integration over sets than intervals 2) allowing the alpha measure to be a function of bounded variation. The second direction is about splitting a alpha measure function with bounded variation in to two monotonic functions. This discussion is closely related to measure decomposition. A related topic is Jordan decomposition. I came across a nice way of describing measure decomposition in a blog “A Mind for Madness”.Its worth a read

Chapter 6 is useful from a computational point of view. A laundry list of theorems is stated that are useful for evaluating Lebesgue-Stieltjes integral. The chapter also explores change of variable and integration by parts in L-S world.A few examples are cited where to evaluate an integral, it is better to differentiate the entire equation and then apply integration on the differential. Most of them are computational tricks rather than any conceptual principles. Chapter 7 extends the Lebesgue Stieltjes integral to multidimensional case. While dealing with double integral , the order of integration does matter, meaning it is possible that if you integrate first with respect to x and then with respect to y, you get a totally different result than if you had integrated first with respect to y and then x. The condition under which the order of integration does not matter is when the function involved in the double integral sign is absolutely convergent with respect to x and y. Fubini’s theorem is just this. It specifies conditions under which the order of integration does not matter. In terms of the usual measure theory perspective , Fubini’s theorem is nothing but a condition on the integrabilty of projection  function on the various measures involved. If these projections are measurable functions, they Fubini’s theorem says that order doesn’t matter.

Chapter 8 offers a crash course in functional analysis. Beyond a certain point, one would like some structure in various Lebesgue measurable integrals. The chapter gives some basic definitions of vector spaces, normed vector spaces, norm, linear dependence, function spaces, Cauchy sequences etc. It then shows that the space of continuous functions cannot be equipped with norm based on Riemann integral as it creates a lot of problems. Dirichlet function is one where the sequence of functions are Riemann integrable but the limiting function escapes from this space where norm is defined based on Riemann Integral. Hence there is a case for a better norm and that norm turns out to be based on Lebesgue integral. There is a small wrinkle with using Lebesgue integral as one of the definitions of norm is violated. If you take a function which is 0 almost everywhere, the norm turns out to be 0 but the function as such is not 0. Spaces such as these have a specific name , “semi normed vector spaces”. It can be shown that semi normed vector spaces can be partitioned in to equivalence classes based on almost everywhere property and subsequently , this space is a nice mathematical space meaning, it is a complete space. Every Cauchy sequence of functions based on L1 norm converges to a function in the same space. Similarly L^P spaces are also complete normed vector spaces. Any space which is a complete normed vector space is a Banach space and hence all L^P spaces are Banach spaces.

Amongst all L^P spaces , the space relating to p = 2 offers an unique opportunity to define inner product space and thus enabling one to marry the concepts of orthogonality/projection etc with Lebesgue measurable functions. This space is referred to as Hilbert Space, in recognition to the remarkable contribution of David Hilbert, the German mathematician who developed a broad range of fundamental ideas in many areas, including invariant theory and the axiomatization of geometry. Hilbert Spaces are pivotal to functional analysis and are discussed in Chapter 9. It talks about application of properties of Hilbert Spaces to Fourier Series and PDEs. Obviously you get only a 1000 ft view of this stuff and you have to refer other texts if the applied math interests you in a specific area. From a math fin perspective though, viewing Fourier series from Hilbert space is vital as many option pricing problems are solved using Fourier Series applications.

Chapter 10 is a cautionary note from the authors that all is not rosy with Lebesgue Stieltjes integral as it is valid only for absolutely convergent integrals. There is a whole host of conditionally convergent integrals which Lebesgue cannot handle. As a cue to an interested reader, the authors show developments post Lebesgue like Denjoy-Perron integrals, Henstock-Kurzweil integrals , thus ending with a opinion that perfect integration method is still an elusive dream.

I personally think that to integrate, you must be a fox rather than a hedgehog. Depending on the context, one must use a specific method and get done with the problem. An all encompassing integration method is like a hedgehog , and to me it appears that such a hedgehog has become an extinct species and chances of appearing is a remote possibility.

Takeaway:

This book provides an easy access to Lebesgue-Stieltjes via step function approach. One does not need to know measure theory to understand the book; however exposure to measure makes it an easy read. The highlight of the book is that it has a lot of examples that show the motivation behind Lebesgue-Stieltjes integral.

Probability Through Problems

This book has a nice collection of problems related to Modern Probability. Unlike the classical problems which are related to discrete variables, the problems in the book are related to variables whose measure is a combination of discrete , absolute continuous and singular measures.

My motivation in going through this book was Chapter 10 which is on Conditional Expectation. Martingales are very important mathematical objects , as far as math-fin stuff is concerned. They appear everywhere, be it option pricing/ hedging/ stat arb etc.They also play an important part in stochastic portfolio theory. Martingales are Conditional Expectation variables.

Conditional expectation is a very tricky concept to understand mainly because there is no ready formula to compute Conditional Expectation. You can only guess the form based on a few constraints. E(X/Y) is easy to compute if Y is an event or if Y is a discrete variable. However it becomes a non trivial problem if Y is a general random variable. Existence of such a variable is guaranteed by Radon Nikodym derivative.  Computation though is from indirect means.

If you look at the definition of Conditional Expectation , it goes something like this :

Let X and Y be any random variables. The conditional expectation  E[ X / Y ]  of X given Y is a random variable such that

 

Each of the above statements need to be understood carefully. The first statement says that Sigma algebra of this variable is always a subset of Sigma algebra generated by Y. Second is a condition on projection operator, ( projection of X on the sigma algebra generated by Y).

Now one way to understand these issues is to actually pick up a few random variables and calculate Sigma algebra and see to it the above two conditions do actually satisfy. Another way is to look up books like these where exercises are tailor made so that one can understand these aspects. In that aspect, the problems in Chapter 10 are priceless as they give clues to compute implicitly the conditional expectation of general random variables.

  Takeaway:

Conditional Expectation and the relevance of Radon-Nikodym derivative is shown via a superb set of problems. The fundas relating to  Conditioning a variable on a sub sigma algebra become crystal clear after working through these problems.

Probability Essentials : Summary

I was going through this book after a gap of 3 years, reason being, I had conveniently forgotten some important stuff relating to martingale theory.  Now that my work demanded a thorough application of this theory, I had to go over it again.  In order to refresh my memory, I thought I should go over this book by Jacod & Protter where I had read about Martingales for the first time.

However,after some thought,I went over the book from scratch.Why ? A book is like a good old friend you meet, who always tells you something that you can connect . So, instead of merely reading up martingale theory, I re-read the entire book. After 2 years of being away from this book, the re-read was worth the effort. This book cannot be the first book for someone looking to understand probability. It is too precise. However for some one who is already exposed to modern probability concepts, this book would appear awesome because such a person would appreciate precision than redundant ranting about stuff. 

Ok, the purpose of this post is to summarize the chapters in plain English. Writing about math without equations sometimes skirts the danger of appearing ugly. Anyways let me give it a try.

The book starts off with defining the triple (State space, Events and Probability). State space is basically all the outcomes of an experiment. Event is a property that can observed after the experiment is done (a subset of state space) and Probability is a mapping from the family of all events to a number between 0 and 1.  The three main ingredients of probability theory are clearly defined. Subsequently, the book introduces random variable and cautions the reader not to confuse it with a variable in the analytical sense. The random variable is in fact a function of the outcome of the experiment and hence the probability associated with X are termed as law of the variable X to distinguish it from the original probability measure on the entire state space.

Two axioms are given in Chapter 2 from which almost the entire theory of probability flows. These axioms are 1) probability of state space is 1, and second axiom relates to the concept of countable additivity which is different from finite additivity.  These axioms are the foundations of the entire probability theory. Basic difference between the two types of additivity are given with the help of few examples. In the subsequent chapter (Chapter 3) , a basic definition of Conditional probability is given and the linkage between conditional probability and independence of events is explained using Partition equation and Bayes’ theorem.

Chapter 4 gives the initial flavour of the method to construct probabilities. By focusing on the state spaces which are countable, authors tie the frequentist intuition that we all have AND the definition of probability measure on a countable space. Well , if it is a countable space, we all know that probabilities of an event A is nothing but the proportion of number of times the event A can occur in the entire state space. The same intuition is shown using the two axioms of probability stated earlier in the book. For a finite or countable space, one usually constructs a probability measure by defining probability for the atoms in the finite space. Once you define probability for atoms of the sample space, you can easily compute probabilities of the events in the sigma algebra, which itself is finite. So, finite case is a trivial case where all the intuitive knowledge about classical probability comes true.
Chapter 5 of the book is about formalizing the definition of a random variable on a countable space.

Chapter 6 moves on to constructing a probability measure on a measurable space where there is no longer the restriction that state space is countable. Now this throws up a very large state space and hence a convenient smaller collection of sets (sigma-algebra) is used for defining the measure. I did not understand this aspect for quite some time since the first time I read this book years ago. However after getting used to these terms and seeing them in various theorems, I understand this stuff better. I will attempt to verbalize my understanding. If you want entire subsets of R, you have to sacrifice countable additivity feature as it breaks down, if you are considering all subsets of R. However if you restrict your universe to almost all subsets of R, meaning measurable sets (Lebesgue measurable space) , then countable additivity hold good for such sets and you can gladly compute all the events in the sigma algebra of the measurable sets. That’s the key trade off which is not usually mentioned properly in most of the books / maybe it is mentioned and I never understood it in the first attempt. Now how does one go about constructing a measure for countable sets ? Extension theorem is the tool/ technique. I think one must spend (whatever time it takes) to understand Extension theorem properly as this serves as a foundation for probability theory.

One usually ends up defining a measure on a semi-algebra and then extends it to the sigma algebra after imposing some conditions on the sets. In this book, though the author starts off with an algebra and then extends it to a sigma algebra. This chapter is very hard to understand as the author leaves the derivation of the key idea , the existence of a measure , and asks the reader to refer other books. So, what’s the point in knowing that this measure somehow exists and you end up reading uniqueness of this measure ? Ideally one should read this construction from a better book rather than trying to understand the terse statements from this chapter. Take away from this chapter : Skip this chapter and read the existence and uniqueness from a better book –:)

Chapter 7 is a special case of Chapter 6 where the state space is R. One comes across the distribution function induced by the probability P on the space( R, B). The distribution function F characterizes the probability. Basic properties of distribution function are given and a laundry list of the most popular continuous distributions is provided.

In a general case where the random variable maps the events on to a space, the task is to construct a random variable in such a way that for every set in the range of the function, there is a pre-image defined in the sigma algebra of the domain space. Hence the concept of measurable function becomes important.

Chapter 8 talks about the generic case where measurable spaces ( Ω, ƒ , Ρ) , (R,Β) are defined and the mapping between measurable spaces now becomes a measurable function. Thus a word like random variable , technically speaking is a measurable function which maps two measurable spaces. Why should one take an effort to understand this ? Well , because measures on  Ω are difficult to construct mathematically whereas measures on (R,B) can be constructed and worked on. This is the key idea is thinking about distribution of X.
The concepts related to measurable functions are gradually built in this chapter. After giving a basic definition of measurable function, it starts off with an important theorem that can be used to check whether a function is a measurable function or not. The basic condition for a measurable function is that inverse image of every Borel set in Borel Sigma Algebra on R should be present in ƒ , the sigma algebra of the domain space. However to check every Borel set in R is painful and hence the theorem states that if you check for any class of function which generates the Borel Sigma algebra, then it is good enough. Thus if you can check for a class of interval like (-inf, a] then it is good enough for the entire Borel Sigma algebra. The good thing about measurable functions is that a lot of operations involving measurable functions retain the measurability, like sup, inf, lim sup, lim inf, closed under addition, multiplication, minimax operations. More over if a random variable converges pointwise, the function it converges to is also measurable. So, in a sense, the gamut of measurable functions is very large and it is really tough to produce a non measurable function. Infact it look a lot of time since Lebesgue introduced these functions in1901 for someone to come up with non-measurable functions. The key idea though of this chapter , is , one can define a law for Random variable X and thus can create valid probability triple ( R,B,Px) so that one can forget about the original domain space and happily work with this space as it is analytically more attractive.

Chapter 9 talks about the role of integration with respect to the probability measure. Why is integration figuring in  probability ? Well, if it is countable state space then expectation of the random variable is in terms of the summation of the events and their respective probabilities. But if it is countably infinite set, then the summation is replaced with integral sign.

Another nifty way to explain the integration connection with probability measure is that , expectation is defined as follows: If you take a collection of simple random variables so that they are less than the random variable that is studied, take the Expectation of this collection and find supremum , you get the expectation of random variable. With out writing the equation and instead explaining in words, the above description sucks. In any case, the point to be understood is this :Any Riemann integral is obtained by Supremum of collection of simple random variables and in the case of bounded functions, Riemann integral and Lebesgue integral converge. That’s the reason for the connection between Integral and Expectation.

This chapter starts off with defining simple random variables and describes various properties. Using Simple random variables, expectation of general random variables are computed. Key theorem such as Monotone Convergence theorem and Dominated Convergence theorem are described. Towards the end of the chapter, Inequalities like Cauchy Schwartz , Chebyshev’s are introduced. I did not really understand the reason for introducing them arbitrarily in this chapter. So, in that sense this part of the chapter is really tangential.

Chapter 10 is about independence of two variables. Well the idea is pretty straightforward – If the joint distribution function splits in to product of marginals then the two variables are independent. However the chapter is something that I have skipped / speed read always. It was a little different this time as I could understand the various arguments made. The chapter starts off with the notion of independence of random variables and ties it to the fact that sub sigma algebras generated by those random variables are independent. This is the correct view to hold , rather than what is usually taught in analytically focused courses on probability. Atleast I remember the definition in this way : P(A^B) = P(A)P(B). This is true but fails to give the right picture. Only when you think in terms of sub sigma algebra’s things become clear and you can extend this definition in to equivalent forms such as : If X and Y are independent, f(X) and g(Y) are independent too for every pair(f,g) of measurable functions. Similarly independence also means E[ f(X) g(Y) ] = E[ f(X) ] E[ g(Y) ]. Product sigma algebras are explored as they become crucial for defining joint distributions and marginal distributions. The chapter ends with Borel-Cantelli theorem. I found the proof of this theorem simpler in Rosenthal’s book . It is nifty simple and clear. Protter’s proof is somewhat round about in nature. Borel Cantelli theorem is striking as it says if {An} sequence of events are independent then P(lim Sup An) is either 0 or 1.It is not ½ or ¼ etc. For a simple application , here is an example – In an infinite coin toss event space, let Hn be the event that nth coin toss is Heads, the theorem says that P(Hn infinitely often ) = 1 , meaning there is a probability 1 that infinite sequence of coin tosses will contain infinitely many heads. With out the knowledge of these theorems and terms, if one were to asked the same question, one can only answer based on intuition and sometimes it can lead to wrong answers!

After a very abstract and conceptually difficult chapter, Sanity is restored for a reader like me, in Chapter 11 :) where things can be understood/ can be related to the real life applications!. For certain measures, we can find density function so that probability and area under curve can be connected. Certain Probability measure determine density up to a set of Lebesgue measure zero. One must note the subtle difference between almost everywhere and almost sure. The former is used for functions while the latter is used for convergence in probability context. The chapter then talks about “law of unconscious statistician”, where expectation of a function of random variable is computed. Most of the practical applications of probability involve an appropriate function of random variables. For example, a payoff of a plain vanilla option is a function of random variable S denoting the price of the underlying security. One needs a method to construct density of a transformed random variable.  For a specific transformation of a variable, one can investigate the monotonicity and differentiability of the function to split the domain of the function (so that it is bijective in its intervals) and then apply a few theorems mentioned in this chapter to arrive at the density.  One example which is always quoted in this context is that of chi square distribution, i.e.  Transforming a standard normal to a chi square variable). Chapter 12 is the extension of the previous chapter to n dimensional space.  The key idea in this chapter is the computation of the density of transformed multivariate random variable. There are at least three different methods illustrated using examples but the easiest one is by using Jacobi’s Transformational formula.

One of the uses of transformations like Fourier and Laplace is to formulate the solution of a problem in the transformed space and map it back it to the original space. In the context of probability measure, Fourier transform of the measure has a name,”characteristic function”. These Characteristic functions are dealt in Chapter 13 and Chapter 14 . Typically these are extremely useful in computing higher order moments / testing the independence of random variables etc. A laundry list of characteristic functions for common random variables is stated. Also uniqueness of the Fourier Transform of the probability measure is proved. This means that if two measures have the same characteristic function / Fourier transforms then the two measures are identical. This is useful thing to keep in mind.

In stats, most of what is done involves linear transformation of random variables. Thus sum of independent random variables as an idea needs to be studied as there are tons of applications in real life. Take for example as simple as a sample average. It involves the sum of the random variables and one need tools to compute the probabilities and densities of such sums. Chapter 15 talks about the convolution product of the probability measures of the individual random variables and provides a methodology to compute the distribution measure of the sum of random variables. Usage of Characteristic function is made in all the examples to easily compute the distribution of sum of iids.  Chapter 16 is a very important one as it deals with Gaussian variables in multi dimensional space. It is necessary to first analytically identify whether a set of variables is indeed from a multivariate normal. It is the form of characteristic function that plays an important role. For any combination of variables to be called multivariate normal, a simple litmus test is that any linear combination of the variables involved should be a normal distribution.  As an example, a linear regression model is taken and the distribution of its estimates are computed. The authors avoid using matrix algebra for deriving the distributions and thus make the computations very ink-intensive :). The chapter ends with mentioning 6 important properties of multivariate normal distribution which make a multivariate normal distribution analytically attractive. One casual remark we often hear “ Normal distribution is everywhere in the nature “ .  If one thinks about it, Normal distributions do not really exist in nature. It arises via a limiting procedure (Central Limit Theorem) and thus is an approximation of reality and often it is an excellent approximation. The irony is that normal distribution is a great approximation to the True distribution of most of the natural phenomena (which itself is not precisely known!!!).

Whenever we talk about limiting procedures, approximations, we need tools to compute and think about. Most of the classical stats is developed using asymptotics, where limiting behaviour of random variables are invoked to justify hypothesis tests and inferences of parameters in a model. Hence the study of convergence of random variables becomes important, which is dealt in Chapter 17.  One usually comes across point wise convergence in calculus courses but such point wise convergence is too harsh / precise to be applicable to the probabilistic world. The chapter discusses 3 other types of convergence, which are, almost sure convergence, convergence in pth mean, convergence in probability. Here is a nice visual to summarize the relationship between various modes of convergence is

Chapter 18 introduces the most important type of convergence , in the context of Statistics, the weak convergence or convergence in distribution. Most of the stuff you come across in stats use convergence in distribution to make statements. With this type of convergence you can make statements relating to distribution of Xn and X without worrying about whether there is a relation between Xn and X. There is no mention about Xn and X, meaning they can exist in different sigma algebra, can have different laws etc. It doesn’t matter and the weak form can be applied away to glory. This is the strong point :) of the weak form of convergence. Firstly, how does one check whether Xn converges in distribution to X ? lim E[ f(Xn) ] should be equal to E[ f(x) ]. This condition must be checked for all f continuous and bounded functions. There is also a mention of a theorem which reduces the test cases. Instead of testing all the continuous functions, one can instead test bounded Lipschitz continuous functions. Slutsky’s theorem is derived which is a very useful theorem in statistics. It talks about convergence of a random variable based on the distance metric between two random variables.

Chapter 19 makes the relationship between weak convergence and characteristic functions.  This relationship forms the key to limit theorems. When we say that, irrespective of the underlying distribution, the centered mean of the variables divided by the deviation converges to standard normal, the proof depends on this critical relationship between weak convergence and characteristic functions. Thus the three chapters 17, 18, 19 prepare the ground for launching in to developing limit theorems.

Chapter 20 talks about the strong law of large numbers : If there are n independent and identically distributed variables, then the average of the sum of the variables for large n converges ( almost surely & converges in L2 ) to the population mean . Weak law is the same as above but the convergence is in probability sense. The proof for these laws is elegantly shown using various modes of convergence discussed in the previous chapters.  Finally an example of strong law is shown in the Monte carlo world where integration of a complex function can be computed using a simulation of uniforms.

Chapter 21 is all about, the most widely used theorem in stats, the Central Limit Theorem, which essentially says that, irrespective of the underlying distribution of random variables, a particular transformation of “sum of random variables “converges in distribution to standard normal. The proof of the theorem uses the relationship between weak form of convergence and characteristic function. The chapter also provides CLT in multidimensional case. There is also some stuff where you get to know the rate of convergence of strong law vis-a-vis CLT.

Chapter 22 might sound rather abstract. What’s the point in understanding that there Hilbert Spaces, What’s the connection anyway between Hilbert Spaces and Probability. Such questions are only answered in Chapter 23. So, a reader needs to understand these concepts and have a vague notion that they will be somewhere used in the book. Frankly when I had read this chapter for the first time, I was swamped by the sheer terminology like – complete spaces, inner product spaces, normed vector space, metric space, orthogonal operator etc. For any reader who is in a similar situation, my suggestion would be put this book aside for some time and read up on metric spaces , vector spaces and inner product spaces thoroughly. Understand their relevance, historical significance to general mathematics. Once you are at least familiar with some basic stuff about functional analysis, in the sense that, you must be able to cogently explain, all the following questions:

• What are metric spaces?
• How is a metric defined?
• Can the same metric space have two different metrics?
• What do you mean by metric space being complete?
• What is vector space? What is normed vector space?
• Can a metric always induce a norm?
• Can a norm always induce a metric?
• What is inner product space?
• Is inner product space subset of vector space? Is it a subset of metric space?
• Can inner product induce a norm on the vector space?
• Can inner product induce a metric?
• What is complete normed vector space?
• What is complete inner product space?
• How to check whether a space is complete, be it metric/ normed vector / inner product space?

Unless you convince yourself that you know the answers to the above questions, it is better to keep this book aside and work through metric spaces. Once you are comfortable with the above questions, this chapter can be read easily.

Chapter 23 is one of THE MOST important chapters of the book, from a math fin perspective. In almost all cases, be it option pricing / hedging / econometrics based forecasting, one always deals with conditional expectation model. Regression, which is considered as workhorse of statisticians is a conditional expectation model E(Y/X). Undergrad intro courses in probability usually introduce conditional probability and leave it at that. Or may be they scratch the surface of conditional probability models by spelling out a formula for E(X/B) where B is some event, E(X/Y) where Y is a discrete random variable. In all such cases, the formula based approach hides the complexities behind computing conditional expectation. For a case where E(X/Y) where both X and Y are random variables, how does one go about computing E(X/Y)? You need exposure towards Hilbert Spaces to understand Conditional Expectation. This is where all the slog one goes through in understanding sigma algebras, Borel functions, etc pay off. There are two things that one realized when computing E(X/Y). Well three things actually. First is that E(X/Y) is itself a random variable. Secondly, the sigma algebra of the inverse images of this random variable is a subset of sigma algebra of the inverse images of Y. One must not take this statement at face value. Just cook up some example and check it out for yourself. A simple example of a dice thrown twice and computing E(X/Y) where Y is the first throw and X being the sum on the two dice will convince you that it is indeed that Sigma algebra of E(X/Y) is a subset of Sigma algebra of Y. Third aspect to be kept in mind is that on any borel set belonging to Sigma algebra of Y, the expectations of E(X/Y) matches with E(X). Again this is abstract and makes sense once you work with an example and see for yourself that this is indeed the case. So, basically there are two properties which are damn important while thinking about Conditional probabilities.

Conditions (a) and (b) impose conflicting restrictions on E(X\Y). On the one hand, E(X\Y) needs to have a rich enough structure to satisfy (b). On the other hand, it cannot be too rich or the sigma-field would be too large to satisfy (a). Meeting the two conditions simultaneously calls for a compromise.

So, the conditional expectation is calculated implicitly in such a way that the above two conditions are satisfied. I did not understand this aspect of conditional probability for a very looooooong time. However one you understand that E(X/Y) can be computed implicitly, you begin to appreciate Radon Nikodym theorem. So, the takeaway from this chapter is that you will start to appreciate that E(X/Y) should be looked at from E(X/ ) perspective. Thus you no longer care of Y in the sense of what values it takes, but all you are interested is in Sigma algebra of Y. This is the key to understanding Conditional Expectation.

Ok, I did not mention here the relevance of Hilbert Spaces. Here is the connection: If one looks at complete inner product spaces, one can use the orthogonality concept, E(X/Y) becomes the best estimate of X given information of Y. This is essentially projecting X in the sub algebra of Y. For projection to make sense, the concept of inner product is used and the first construction of Conditional Expectation is done on Hilbert Spaces. However L2 spaces are only a subset of L1 spaces which most of us would be interested. The extension of Conditional expectation from L2 spaces to L1 spaces is done using the standard procedure of 1) showing that it works for indicator functions 2) it works for simple functions 3) it works for non negative random variables 4) it works for general random variables. Another key aspect to understand about conditional expectation is that it is only unique in “almost sure “sense. Meaning there could be more than one conditional expectation variables that meet the criterion, where the variables only differ on 0 measure sets.

Chapter 24 deals with the properties of a sequence of random variables (Xn) instead of Sequence of iids, which is usually the norm. A specific type of sequence of random variables that is relevant to math fin area is “Martingale”. A Martingale is a sequence of random variables with the following properties

• Each element of the sequence is in L1
• Xn is Fn measurable
• The most important being E[ Xn/ Fn ] = E[ Xm ]

Several properties of Martingales are very appealing from fin modeling perspective. Martingales have constant Expectation and hence attacking a problem like option valuation from a martingale perspective always makes one hopeful of ending up with a martingale.

The other class of variables that are discussed in the chapter are Stopping times. Bounded Stopping times form Martingales. These are extremely useful in American option pricing. Doob’s Optional Sampling theorem is also discussed in this chapter.

Chapter 25 explains super martingales and sub martingale, that form a class of useful mathematical objects in financial modeling. Most importantly it talks about decomposing a super martingale or a sub martingale in to martingale and an increasing/decreasing process. Chapter 26 and  Chapter 27 explore Martingale Inequalities and Martingale Convergence Theorem. Chapter 28 is about Radon-Nikodym theorem. This theorem is used in a ton of places in math-fin area. However this chapter uses Martingales to prove the theorem. Ideally it would have been better if the theorem was proved using measure theory concepts. So, in that sense the organization of the last section of the book was little challenging for me. The book introduces martingales and then introduces measure change. As stated earlier, there is no neat closed formula for E(X/Y) where X and Y are both random variables. Radon- Nikodym derivative provides a neat way to show the existence of such a variable. One can always show that such a variable exists for Hilbert Spaces but for L1 spaces, one has to prove it using indicator functions, simple functions, non negative random variables and general random variables.

Takeaway:

I think this book is too concise for some one looking to understand concepts.  Existence theorems are conveniently ignored for some important mathematical objects. However this book is an awesome reference to most of the theorems of modern probability.

Modes of Convergence

Stumbled upon a nice visual summarizing modes of convergence amongst random variables.

Inside the Black Box : Summary

The book is divided in to three parts. The first part of the book gives a basic primer to the Quant world which includes some description about the benefits of quant trading and intro to the structure of a basic quantitative trading system. The second part of the book deals with the key elements of the black box and the third part of the book is relevant to investors / managers who would want to evaluate various quant trading strategies.

Part I - The Quant Universe

The first part of the book introduces the reason for considering quantitative trading as a strategy, by describing the basic difference between quantitative trading and discretionary trading. The author starts off with a fact that Algorithmic / Computer driven trading is a reality, whether one likes it or not. 60% of the trades in US from the buy side are computer driven and about 45% of the trading volume in Europe are system driven. Given that quant trading is a market reality, what is it that one can learn from a quant’s approach to markets. The book cites three main reasons for understanding quant trading

1. Deep thought : Since quant trading strategies are executed using a system, it becomes very important to pen down the exact strategy , signal generation , signal checking conditions, stop-loss rules etc . The rules have to be precise, at least in the probabilistic sense. Thus unlike a discretionary trader, who most often than not, cannot verbalize or pin down his trading strategy , a quant trader can exactly tell the strategy in a series of steps(almost). One of the other skills a quant brings to the table is “Data Visualization”. Well, as is well known that 80% of our brain is allocated to visual processing. So, by providing visuals to the various trends about parameters / P&L / simulated scenarios, one can look at an investment strategy from multiple angles and reduce Type I error (Trade when there is no signal) and Type II error( Not trade where there is signal).This reduction of Type I & Type II error itself can add value to an investment strategy.

2. Measurement and Mismeasurement of Risk : This is a very debatable aspect of the use of quant methods to measure risk. Taleb has rallied against anyone who uses math to define risk. However there are a lot of situations where it is possible to tame risk. I strongly believe that some map is better than no map. At least it gives some sense of direction to the portfolio manager who can then use a mix of Bayesian and Fischerian stats to get an idea of risk. Well, whatever be math used, Black swinish events are anyways beyond the scope of quant’s work as they come under the category unknown-unknowns. So any risk metric for that matter should always be taken with a pound of salt!.

3. Disciplined Implementation: Quant trading tries to cut out emotion, fear , greed, manual mistakes out of the execution process and thus brings in a discipline in to a trading process / investment strategy.

The above three reasons should make any investor, trader , portfolio manager to be interested in the quant world.The book gives an interesting definition of quant strategy. It goes like this:

There is a full spectrum between fully discretionary strategies to fully automated strategies. The key determination that puts quants on one side of spectrum and everyone else on the other side is : Whether daily decisions about the selection and sizing of portfolio positions are made systematically or discretionarily. If both the questions of “what positions to own?” and “how much of each to own?” are answered systematically, that’s a quant strategy. If either of the two questions are answered by a human, that’s not a quant strategy

It then goes to describe a schema for understanding quant trading black box

The above flow chart is merely a schema . Obviously there are many quant strategies where only a few of these elements are chosen (ex: transaction costs in to the alpha model itself). There are strategies where the flow could be recursive. However the above schema helps one to have a discrete map of various components of a quant system. Alpha model is designed to predict the future of those instruments that the quant wants to consider trading , in order to generate returns. Risk models are designed to help limit the amount of exposure the quant has , to those factors that are unlikely to generate returns but could drive losses. The Transaction cost model is used to help determine the cost of whatever trades are needed to migrate from the current portfolio to whatever new portfolio is desirable to the portfolio construction model.The alpha, risk and transaction cost models then feed in to a portfolio construction model, which balances the tradeoffs presented by the pursuit of profits, the limiting of risk, and the costs associated with both, thereby determining the best portfolio to hold. Based on the portfolio construction model, the new trades are then sent through the execution model. The whole system’s life line is Data + Research. Without these two elements the black box is a deadbox!.

Part II – Inside the Black Box

This part of the book explains each of the blocks of the above schema. A chapter is dedicated to each of the components of the schema.

Alpha Models
The output from Alpha model is either a return forecast or direction forecast.The book starts off by explaining the core difference between the vast numbers of the alpha models. Either they belong to theory driven type or empirical type. In the former one, a quant starts off with a theoretical relationship and vets the data to calibrate the parameters of the model. The advantage with this is that the model can be easily communicated to people. However just because you can communicate the theory behind a model does not mean that the model will make money. There is another school of thought, i.e empirical type where you allow the data to speak for itself and you build/ trade accordingly. Personally , the latter type is far more appealing to me as you don’t have to carry theoretical baggage while building the model. Yes, there is a risk of data mining. So , the approach depends on the time horizon of the strategy. If you are dealing high freq data , I guess the best thing is to work on empirical model building. Most of the people whom I have seen building models in the high freq give a damn to theories. They crunch the data and trade on the pattern. Their belief I guess is ,”At such a frequency, Who has valid theories ?” In a way their opinion is right. Micro Market Structure studies is still at a nascent stage and researchers / academicians have not made a great amount of literature public. Most often than not, if a professor cracks an algo at a high frequency level, he is likely to trade it in a bank/hedge fund. Classic case that I know of is Dr.Robert Almgren from NYU who has written fantastic stuff on execution algos at high frequency scale and has started his own firm, Quantitative Brokers to capitalize on the algos. So , in a way all these theory laden quant models are suited for may be medium term to long term investment strategies. At a high frequency scale, I think empirical models are the flavour at the moment.

Anyways coming back to this book, the author expands on the Alpha block in the following manner:

The theory driven alpha models are explored from two perspectives, price based models and fundamental analysis based models. From whatever I have seen or read till date, quants primarily using price /volume/ etc to churn out models. Fundamental Analysis based quant models , I think are actually fraud models. My professor used to say that you must build a model that makes money, and once all alpha is gone, you can bring in some fundamental attributes and give a spin to the model so that the model is publication ready in some journal. Strange things happen when you mix academia and hedge funds! .I have started to believe that this fundamental attributes based quant model is bogus. For example, I have seen a few factor models which are based on part statistics, part fundamental analysis. They make fantastic back testing results and sadly perform pathetic in production. Most of them are often flawed as there is not enough data to test their statistical significance. For quants who actually take the pains to test such factor models using random matrix theory or equivalent theory , I think they trade away the signal asap rather than making in to a sales pitch to buy side.

The chapter then delves in the implementation aspects of any such alpha model. These details include Time Horizon, Bet structure, Instrument type, Run Frequency of the trading model. One inevitable conclusion that a reader draws from this book is that, there are only a few alpha seeking strategies but the implementation attributes are so diverse that it can potentially give rise a ton of trading strategies.

Risk Models
The book states at the very beginning that risk management function from a quant perspective is not about reducing risk , but it is primarily about selecting sizing the risk exposure. Post that , the quant can decide whether it makes sense to go ahead with the strategy. For sizing the risk exposure, one can simulate and statistically formulate risk exposure bands or apply heuristics to size the exposure. The other aspect to be dealt with is leverage. The author makes a passing remark about Kelly’s criterion and its use for optimal sizing of exposure.

The author makes the same type of distinction in risk models , i.e theory driven risk model and empirical risk model. Stat arb world seems to like empirical risk model as they bring out the risk factors from the data. However the downside is that there could be risk factors which have characteristics that cannot be hedged away in the real world.May be there are no instruments in the market you are working , that can be used to hedge risk factors. If you are working in emerging factors where things are still developing, you might as well take cognizance of the fact that your position is unhedged and hence you don’t have a choice but to reduce risk by tweaking the size your exposure. That’s the best you can do. If you do not have control on risk exposure type, at least you can control the size of risk exposure. So, a quant has to strike a balance between theory laden risk modelling approach and empirical approach. In any case, he/she can embed the risk model in the alpha model itself or can use it as an external component. It all depends on the strategy I guess.

Transaction Cost Models
The three key elements of transaction cost models are Commissions & Fees, Slippage Costs and Market impact costs , with increasing order of difficulty in building a model. Commission& Fees is the easiest to incorporate as they are mostly fixed hurdle costs for a trade. Slippage is difficult to model as it depends on the strategy being adopted. Slippage cuts in to Trend following strategies whereas it aids mean reverting strategies. The most difficult one to model is the Market impact and the book mentions the four common models used for Market impact, i.e Flat, linear, piece-wise linear and quadratic. The takeaway from this note is that transaction cost model’s purpose is to simply advice the portfolio construction model how much it might cost to transact. Its job is not to minimize the cost of trading.A nice analogy given about the three components described is as follows: The alpha model plays the role of the starry eyed optimist, and the risk model plays the role of the nervous worrier, and transaction cost models act as frugal accountants.

 

Portfolio Construction Model

Portfolio construction model acts as an arbitrator between Alpha, Risk and Transaction Cost Models. Given that alpha model is an eternal optimist , Risk Model is an eternal pessimist and Cost Model being the guy who reminds of the trading costs, the portfolio construction model balances the output from these models and tries to construct a portfolio based on some objective function. There are basically two types of Portfolio construction models. First are the Rule based construction models like equal weights, equal vols, decision tree methods etc. These are heuristic by definition and hence will appear as adhoc than quantish models. However it is still a debatable issue among finance literature whether equal weight model beats all the fancy optimizers out there. Second type of portfolio construction models are optimization based. There is an objective function, there are constraints on the size of holding and type of holdings and you basically optimize the function. Here the book mentions a laundry list of techniques like plain vanilla unconstrained optimization, constrained optimization, Black Litterman model, Grinold and Kahn’s factor portfolio approach, Michaud’s resampling approach(which is far more appealing to me from stats perspective) and Data mining approach. Given the arbitrator’s role played by the construction model, this is one area which can come close to being termed as “Black Box” as there are tons of variations that a quant can choose based on statistical tests and market conditions. The author mentions an interesting observation that quants who build Rule based construction models typically take intrinsic alpha approach(meaning they rely on individual security forecasts), while quants who build Optimization based portfolios take a relative value alpha approach.

Execution Model
This is one of the toughest and exciting area for any quant. Probably that is one of the reasons for sparse academic literature and trading strategy documentation. Recently I came across a flyer about a high frequency trading shop that is going to be conducted in Singapore / Mumbai in April 2011 that costs a couple of thousand dollars!!. Are the strategies so secretive that a two day workshop costs ~ $3000? I guess this execution world is more like a social video game. The guy who has a better strategy in a video game wins. This chapter talks about various technology options for executing a trade and talks about DMA, high frequency trading platform, that are very much a reality in developed markets. These are useful in markets like US where getting alpha from medium term to long term strategies is difficult. So, I guess Execution Model is the new Alpha Model in all such markets.

Data & Research

The concluding sections talk about data and research components of the black box. Data is the starting point for quant’s work and the book merely scratches the surface about data by giving an overview of data procurement, data treatment and data storage issues. The section on research talks about sources of idea generation for a quant strategy and research issues( more from a back testing perspective)

Part III – A practical guide for investors in Quantitative Strategies

The book talks about a couple of inherent risks in any quant strategy that an investor should be aware of, they being , Model Risk, Model Mis-specification Risk , Regime change risk, Exogenous shock risk , Contagion or common investor risk. Most of these terms are pretty self explanatory. The author narrates Aug 07 quant crisis to highlight the crowding phenomenon of quant strategies.

The author gives his opinion on some of criticisms of quant trading that one gets to hear such as

• Trading is an art and not a science. Quant trading is of no use.
• No”, says the author, though the argument is little weak as he focuses on all the successful quant firms. Taleb’s “silent evidence” makes the argument weak.
• Quants cause more market volatility by underestimating risk
• “No “ , says the author with a few numbers based arguments
• Quants cannot handle unusual events
• “Valid criticism” says the author.
• Quants are all the same
• “No “, says the author by giving two arguments. First the components of black box described has so many levels of combining that quant has a very large degree of freedom. Second reason being numbers based. He cites his own firm where he gives an estimate of 30% of quant trades in opposite directions. He also shows correlation between quant long short funds to be very close to 0, vis-à-vis a relative high hedge funds return correlation
• Only a few large Quants can thrive in the long run
• “No”, says the author citing about half a dozen reasons. Some of them are compelling and make the case that a boutique shop is as appealing as a large quant fund for an investor
•  Quants are guilty of data mining
• “Not a fair claim “, says as it is often use interchangeably with “curve fitting” which obviously is useless.

The last section of the book talks about evaluating quants and quant strategies. It talks about the ways to interview quants, what sort of questions to ask quants , how to understand what quants are doing and finally the way to incorporate quant traders in to your overall portfolio strategy. I found the last chapter of the book particularly interesting as it mainly flows from the author’s experience in hiring and managing quants.

Takeaway:

The schema described in the book is very appealing and can serve as a good framework for all the quant strategies that one comes across. So, in that sense, the book does indeed demystifies black box trading by showing various components of the black box and the interdependencies. 

Jim Simons @ MIT

 

Creativity, Technology and Culture of openness – Key to Renaissance story

Lebesgue Measure & Integration - Frank Burk : Summary

Lebesgue Integration is usually introduced in either one of the two ways , in most of the books. Either using measure theory OR  skipping measure theory altogether and using approximating functions like step functions, monotone functions etc. The second approach is usually taken so that one can actually understand all the concepts of Lebesgue integral with out going through measure theory. However that approach would make it difficult for a reader to connect Lebesgue Integral and concepts relating to stochastic processes. This is one of rare books which combines both the approaches. It introduces measure theory as well as approximations in the book and uses them in various proofs, wherever the introduction makes the proof easier to follow. Let me attempt to summarize this book.

Chapter 1 : Historical Highlights

The first chapter gives a historical perspective of “Integration”. Right from 408 B.C.E till 1904 , there were lots of brilliant people who contributed to the understanding of the process of integration. The main personalities mentioned are

• Exodus (408 B.C.E)
• Hippocrates(430 B.C.E)
• Archimedes(287- 212 B.C.E),
• Pierre Fermat (1601 – 1665)
• Leibnitz (1646 – 1716)
• Cauchy(1789-1857)
• Bernhard Riemann(1826-1866),
• Emile Borel(1871-1956)
• Camille Jordan(1838-1922)
• Giuseppe Peano(158-1932)
• Henri Lebesgue(1875-1941)
• William Young(1863-1942).

Exodus and Archimedes pioneered the technique called Exhaustion. Fermat, Newton and Leibnitz were masters in providing anti-derivatives for specific functions. But it was Cauchy who laid out a radically different view of analysis, i.e using limits. He described everything from the view of limits. Karl Weierstrass provided the algebraic language needed to express the concepts like limits, continuity. It was followed up by Reimann and Darboux who generalized the work of Cauchy and extended the concepts to integrals for bounded functions. However there were a lot of problems with Riemann Calculus as well as FTC (Fundamental theorem of Calculus) using Riemann Integral. Most of the pathological examples perplexed mathematicians and at the same time raised serious doubts about Riemann Calculus. Peano-Jordan used the concept of inner content and outer content to find integrals. The biggest limitation with Jordan measure was that it was building measure using finite partitions. They seemed to be a ray of hope but their definition missed an important aspect of measurability, i.e content of rationals in [0,1] + content of irrationals in [0,1] > 1 which flew against the usual requirement that measure of disjoint sets needs to be equal to measure of the union of disjoint sets. Finally Lebesgue used the concept of countable covers and introduced outer measure and Lebesgue measure to create a breakthrough in mathematics – Lebesgue Integration. All these developments are summarized in the book with the help of the following visual.

Chapter 2 : Preliminaries

This chapter mentions all the concepts needed to understand the three core chapters of the book, Lebesgue Measure, Lebesgue measurable function and Lebesgue Integral.

It starts off by introducing basic operations on sets like union, intersection, complements etc. Then it introduces monotone sequence of sets and defines limit superior of a sequence of sets (lim sup) , limit inferior of a sequence of sets ( lim inf). Well, if one is reading this book with absolutely no exposure to set theory, one might wonder the importance of limiting operations of sets. I mean, in any analysis text , one usually comes across lim inf and lim sup for sequences. Lim inf and Lim sup are related to the limit of sequence. However the lim inf and lim sup for a sequence of sets become extremely important in the context of probability. If you have events A1, A2, A3,...An then lim sup (An) means An infinitely often , and lim inf(An) means An almost always.

Functions are then introduced. This is followed up by explaining concepts of cardinality. Terms such as finite set, infinite set, countable, uncountable are explained. For a first time reader of Lebesgue theory, it is difficult to understand the importance of cardinality concepts to measure theory. For all such readers, they would gain immense understanding by going over the historical development of measure theory. Many mathematicians tried to wrestle with the concept of measure considering only finite intersections and finite unions and thus limiting the collection of sets for which measure and integral could be defined. It was Lebesgue/Borel who were the first mathematicians to combine the concepts of cardinality with nowhere dense concepts( Baire’s contribution).Books such as these are good reads after you have gone through the struggles that various mathematicians went through in defining mathematical objects.With out historical background, these books are difficult to follow. But if you have some historical background , Books such as these are very illuminating. Anyway, coming back to the summary, the countability and uncountability are concepts which are key to understanding Lebesgue measure. This is followed up with some concepts relating to the construction of Real line. Nothing too difficult to follow . Just some basic  stuff like least upper bound, greatest lower bound, supremum, infimum definitions are mentioned. Personally I felt Abbot’s book “Understanding Analysis”, does a fantastic job of introducing the Real Line. If you have worked through Abbott, you can quick read this entire chapter.

The highlight of this chapter is the concept relating to sequence of real numbers.lim sup and lim inf of sequences are introduced with pictures. I am always on the lookout for books that explain things using images, for our minds are tuned to visual processing. 80% of our mind is dedicated to visual processing and hence images, more so in math, can make you remember stuff for a LOONG time. Cauchy sequences are then introduced in the book. Well, Cauchy sequences are the life blood to everything in analysis, from as simple as convergence of a series, to understanding metric spaces. Nowadays I tend to reflect on my sheer ignorance of these concepts for a very long time in my life. I had crammed up stuff, learnt to crack a few exams without any good understanding of “Real Analysis”. My first face-off with Real Analysis came out of sheer necessity. I had to teach Calculus to undergraduates during my masters, to take care of my daily expenses. You can’t teach Calculus without a thorough understanding of Analysis. If someone had asked me, whether a sequence can fill up all the numbers between (0,1) back then, in all probability I would have said yes. While in my first semester of my masters, I taught the calculus course to a few students and it was a disaster to say the least. I knew all the formulae, methods, tricks, ways to solve problems relating to limits, differentiation, integration etc. I taught them to crack exams . But my fundamentals were extremely shaky. It was the first time I painfully realized the importance of SOUND fundamentals in Real Analysis. Slowly over the course of time, I improved my teaching skills and brought in the discussion of basic principles in to the class to appreciate the beauty behind all the formulae. Ok..I am deviating from the intent of the post.

Coming back to the summary of this book, the chapter subsequently gives a quick recap of some topological definitions / terms / theorems such as Open sets, Closed Sets, Compact Sets, Limit points, Open Cover, Finite Sub cover, Heine-Borel theorem, Bolzano – Weierstrass theorem. Obviously this chapter provides a good recap ONLY. This is NO GOOD for a beginner. If you want to know thoroughly the topological terms and concepts, you must pick up a book with  enough coverage and problems in it. Math can only be learnt from doing. You cannot read math / listen to math .You understand ONLY when you DO math and probably TEACH math. Books by Abbott / Rudin / Victor Byrant would be the best way to start off on understanding the principles. I found Rudin very tough to go through and chose Abbott’s book instead. For topology, I found Victor Byrant’s book on Metric spaces to be a nice learning resource. I remember the first time when I  came across these terms and really felt clueless. If I want to integrate, why should I know about compactness? But slowly I realized that there was no shortcut to understanding Lebesgue integral or for that matter anything in calculus without actually slogging through Real Analysis and understanding the theorems behind it.

The chapter then talks about Continuous functions and Differentiable functions in a breeze. As I start spending more time on math, I have started to realize that you cannot work on one book at a time. You have got to read at least 2-3 books simultaneously. For example , a proof of theorem might be using Nested Interval property in one book while it might be using Bolzano – Weierstrass theorem to prove the same in another book. A third book might contain the motivation behind the formulation of a theorem. Only when you see things from at least two or three perspectives, you get a decent idea of math principles.

The chapter ends with the discussion of a sequence of functions and uniform convergence of a sequence of functions. Is the limit of derivative same as derivative of the limit? Is the limit of the Sum the same as Sum of limit? Is the limit of Integral same as Integral of limit? These are some of the crucial questions which lead mathematicians to make real analysis more precise. Bressoud’s books Radical Introduction of Real Analysis and Radical Introduction to Lebesgue theory start off with Fourier Series example that perplexed mathematicians for over a century. Fourier series is an example where you can approximate a constant with infinite trigonometric series. You differentiate each term of the series and you get some non sense result. Nobody had a clue the reason for such anomalous behaviour when it was first introduced. Perplexing behaviour of Fourier Series was one of the biggest motivations for mathematicians to bring out the rigor in defining terms like differentiation and integration.

Overall this chapter makes tremendous read for someone who is already familiar with the concepts of real analysis and historical developments of real analysis. My favourite in this genre is “The Calculus Gallery”. I have read it about 3-4 times. Every time I read, I find something that makes me wonder at the immense achievements of the people behind Calculus and Lebesgue Integration.

Chapter 3 : Lebesgue Measure

Chapter 3 introduces Lebesgue measure in a systematic manner. Instead of diving right in to the definition as most books on measure theory do, the approach taken here is very interesting. It lists down a set of 8 desirable attributes of any measure for a subset of R. It then shows the conditions that Lebesgue outer measure satisfies. Out of the laundry list of desirable attributes, there are two attributes which outer measure fails to possess. One is that you cannot have all the subsets of R. Second is that the outer measure does not satisfy countable additivity for a collection of disjoint sets. Outer measure actually carries countable subadditivity property. Hence Lebesgue introduced a new measure which satisfies all the desirable attributes except the attribute that it is applicable to all subsets of R. Such sets for which countable additivity holds good are called Lebesgue measurable sets. There are some sets in R which are not Lebesgue measurable, whose construction is very difficult. In this context, Caratheodory’s condition comes in handy, who came up with a simple condition to check the measurability of the set. One can easily see that null set and R is Lebesgue measurable set. At the same time 2^R , all the subsets of R are not all measurable.

The book then logically introduces sigma algebra, a collection of sets which satisfy certain properties such as countable unions, countable intersections, complements and limits are all present in the collection. One “not to be missed” point is that “Once you are inside a sigma algebra, it is hard to get outside”. All intervals are Lebesgue measurable. However it is desirable to have much more than simple intervals. In any case collection of open intervals is not a sigma algebra. This is where Borel sigma algebra comes in which is nothing but the smallest sigma algebra of all the sigma fields generated by the intervals. Borel Sigma Algebra happens to be a subset of Lebesgue measurable sets. One of the highlights of this book is good visuals. The following visual summarized the structure of all the discussed concepts in this chapter.

The chapter ends with discussing the topological structure of a measurable set. The discussion helps in understanding that an open set can enclose a measurable set and a closed set can almost exhaust a measurable set. Meaning, Lebesgue measurable sets are “almost open”, “almost closed”

Chapter 4 : Lebesgue Measurable Function

A measurable function is one whose preimages are measurable sets. Functions in the Lebesgue world  are not “measured” but integrated. Besides the definition, various forms of functions are explored in this chapter to check their measurability. With the wide range of applicable functions, the inevitable conclusion is that Lebesgue by defining measurable functions via Measurable sets had cast his net very very wide. The beauty of measurable functions is related to sequence of functions. If one takes a sequence of functions which are measurable, the function to which the sequence converges is also measurable. Basically it means that we cannot escape the world of measurable functions even by taking point wise limits. This is not true about bounded, Riemann-integrable functions, functions in Baire class 1. In those situations, the family of functions was too restrictive to contain all of its pointwise limits. Measurable functions, by contrast, are strikingly inclusive.

The highlight of this chapter is the careful construction of simple functions to approximate a measurable function. The detailed description of the algo for approximation , is by far the best description that I have found amongst all the books on Lebesgue. Here’s a visual to demonstrate the procedure. For example a function like y = x^2  and y = 1/x are approximated using a series of monotonically increasing

The chapter ends with discussing almost uniform convergence by proving Egoroff theorem. This theorem states that if {fk} is a sequence of measurable functions converging almost everywhere to f, then on a subset of that space where the sequence converges, the convergence is uniform and hence the name almost uniform convergence. I feel this part could have been improved by taking the Bressoud-II approach where the author discusses, convergence in measure, Riesz’s theorem etc. At least by discussing all aspects of convergence like pointwise, almost everywhere, almost uniform convergence, convergence in measure, it is more likely that one gets an nice overall idea. In that sense, this final part of the chapter is a bit let down as it randomly introduces almost uniform convergence concept and ends it abruptly.

Chapter 5 : Lebesgue Integral

The chapter starts off with a basic introduction to Riemann Integral. In most of the real analysis books you find the introduction to Riemann using partitions that eventually concludes with an elegant formulation using Darboux integrals. This book however takes a different approach, the step function approach. The definition of lower Riemann Integral, Upper Riemann Integral, the properties of Riemann Integral like homogeneity, additivity, monotonicity, additivity on the domain and mean value are all derived using step functions. Basically it’s an old wine in new bottle approach but somehow the proofs are much easier to follow. The proofs using step function approach are easier to follow than using let’s say the sup/inf of lower/upper sums that one usually comes across. Even the FTC(Fundamental theorem of Calculus) , the anti-derivative part and the evaluation part are both derived using the step function approach. One basic takeaway from this introduction is that you can formulate Riemann Integrability condition purely based on step functions and that is an intuitively easy way to understand the condition.

The chapter then talks about Lebesgue integral for Bounded functions on sets of finite measure. Homogenity, Additivity, Monotonicity, Additivity on Domain hold good for Simple functions. One of the best proofs in the book is for the theorem, ” Let f be a bounded function on the interval [a,b] If f is Riemann integrable on [a,b] then f is Lebesgue integrable on [a,b]. ” Since step functions are a subset of simple functions, it is proved using the fact that you can sandwich a Lebesgue integrability condition with in Riemann Integrability condition. Subsequently, Homogenity, Additivity, Monotonicity, Additivity on Domain properties are explored for Lebesgue integrals.

How does one decide whether a function is Lebesgue integrable or not ? For functions whose domain is of finite measure, it is easy. If you can sandwich the function between two simple functions such that the difference between their integrals can be made as small as one wants, then the function is Lebesgue integrable. Another obvious way to decide is whether the function one is trying to integrate , is measurable or not. Can there be a Lebesgue integrable function which is not measurable ? No, says the proof of a theorem from this book.

Books such as these should not be missed for a simple reason. You get both intuition and rigorous explanation of results. It is a standard thing that a Lebesgue measurable function can be approximated using Monotone Sequence of simple functions. I always used to wonder, the reason why one should  not , in a dumb fashion generate sequence of simple functions and basically use it for integration purpose. However the book makes the reader realize that it is not always a nice way to do that way. Some of the examples in the book show that it is technically extremely cumbersome to work with sequence of simple functions to approximate the integral. Instead the book says that it is elegant to approximate the lebesgue integral with a sequence of monotone measurable functions. Again examples come before the theory so that reader is well motivated to see the relevance of the theory. Fatou’s lemma is usually used in proving Monotone Convergence theorem. But this book takes a different approach where Monotone Convergence Theorem is used to prove Fatou’s lemma.

Finally the chapter extends it to integration to all measurable functions and not just nonnegative functions. One must be very clear with the difference between the two statements, “Lebesgue integral of f is blahblah“ and “ f is Lebesgue integrable on E and equals blah blah blah”. The finiteness for the integral is crucial to call a function Lebesgue integrable on a set E. So in one sense f is Lebesgue integrable on E only if |f| is integrable. This is very different from Riemann case where there is a chance the negative part of function might cancel some part of positive summands and make the Riemann integral converge. Not in the case of Lebesgue. This means that there would some unbounded indefinite integrals which are Riemann Integrable but not Lebesgue integrable on a measurable set. The chapter ends with a discussion on Lebesgue Dominated Convergence theorem which gives a very broad sufficient (note : it is not a necessary) condition for interchanging limits and integral sign for a sequence of functions. One of the highlights of the book is the detailed derivation of cantor set using ternary expansion, and the construction of devil’s staircase function. 

Takeaway:

The book is very focused in treatment. Instead of covering a laundry list of topics related to Lebesgue theory , the book focuses on three core concepts i.e Lebesgue Measure, Lebesgue Measurable function and Lebesgue integral and explains them very clearly. The author uses visuals to explain concepts, thus making the content very interesting. The highlight of this book is the conversational tone that the author adopts in explaining stuff, thus enabling the reader connect seemingly disparate theorems/concepts/problems from the book.

Computing power isn’t good enough

Via Paul Erdos:

We have all these powerful computers
but they are not good enough to answer this question,

“Find the minimum number of guests that must be invited so that
at least 5 will know each other OR at least 5 will not know each other ? ”

 

Cauchy-Schwarz Inequality

Via Proof with out Words:

Math is not Linear

The Cauchy – Schwarz Master Class : Summary

You see inequalities in any discipline. In math-fin area specifically, most of the times, the inequalities are derived from a basic set of inequalities such as Cauchy’s, AM-GM, Jensen’s,Holder's, Minkowski’s Inequalities. One typically comes across inequalities in some math course where one is asked to prove a specific inequality. Typically one solves them just like one learns the grammar and syntax of a language. Sadly ,the principles behind them are conveniently forgotten as one does not actually use then in some practical context. So, the GAP between the time one is working on basic inequalities in a course work and the time where one needs to apply them to solve a practical problem, sometimes runs in to years/ decades. Sadly , all one can do is to go back and refer some books on inequalities that most often than not , appear consisting of  pages with a laundry list of inequalities. You start to wonder, “ Are there any principles behind solving inequalities?”, “Are there any common strategies to work with inequalities ?” , “Is there a connection between a specific strategy / inequality to problems in various scientific disciplines ?”. The book provides these answers in a delightful way. Math books written in conversational style are few and this is one of them.

The word , “Master Class”, in title of the book attracted me to this book, as I had come across this term and the context in “Shop class as Soul craft”.The author at the very beginning of this book says :

In the fine arts, a master class is a small class where students and coaches work together to support a high level of technical and creative excellence.This book tries to capture the spirit of a master class while providing coaching for readers who want to refine their skills as solvers of problems, especially those problems dealing with mathematical inequalities.

The book starts off with the famous Cauchy’s Inequality. The beautiful thing about inequalities is that it will give you a chance to view them from different lens. You can wear a linear algebra lens OR inner product vector space lens OR a simple algebraic lens OR  functional analysis lens etc. I mean whatever your area of work, you would have come across some variant of Cauchy inequality. When I first saw the inequality, I drew parallels to two processes which have finite variance and the inequality as the link between covariance of such processes and the individual variance. So, in one way, by studying inequalities you get to view stuff from various perspectives. You never know which perspective would help you to solve a problem in your area of work. Coming to the chapter on Cauchy’s inequality, the author proves it by induction. Then the author talks about a very important principle that one must keep in mind.

Mathematical progress depends on the existence of a continuous stream of new problems, yet the processes that generate such problems may seem mysterious. To be sure, there is genuine mystery in any deeply original problem, but most new problems evolve quite simply from well established principles. One of the most productive of these principles calls on us to expand our understanding of a quantitative result by first focusing on its qualitative inferences.

The above statement appears VAGUE until you see the connection between Cauchy inequality and

and

The latter statement is an inference from Cauchy’s inequality but when applied systematically gives rise to to an additive inequality

The chapter then introduces the concept of inner product space to look at the same inequality. It shows that the inequality is nothing but an expression in inequality for the cosine of angle  between two vectors in an inner product vector space. 

Moving from the discrete version of the inequality to continuous form took about 6 years and it appeared in a memoir written by Victor Yacovlevich Bunyakovsky. There was no proof given to the continuous form of inequality

The continuous version of the inequality was proved brilliantly by  Hermann Amandus Schwarz (1843–1921) while working on the theory of minimal surfaces. He also came out with inner product version of the inequality. One brilliant point of this chapter is the derivation of Cramer Rao bound for the MLE problem using Cauchy’s inequality. Any guy who uses stats in his work will appreciate the derivation of this bound from a simple looking Cauchy’s inequality. This introductory chapter introduces 1-Trick and Splitting-Trick that are often used in the context of proving Cauchy’s variants.

My biggest takeaway from this chapter has nothing to do with inequalities but it is about learning a method to crank out inner product spaces. I used to always wonder whenever I came across an inner product definition , about its source .”How do people come up with the inner product definition which just satisfies all the properties of inner product ?”. From this chapter, I have learnt that the source is any positive definite matrix. If you take any positive definite matrix A, then for any two vectors x and y in the vector space, you can define inner product as Y transpose times A times X and that will get you an inner product definition. 

---

<  The AM-GM Inequality  >

The next type of inequalities the book focuses on are Arithmetic Mean – Geometric Mean inequality.

This is one of the most popular inequalities. It is learnt in some form or the other either in high school/ college level/ undergrad education. The proof is usually shown by mathematical induction. However the book goes on to prove using a technique “ Leap-Forward Fall-Back technique”, a technique which works in lots of cases , where the usage of mathematical induction  might be tedious.

Self generalizing quality of the above inequality  is used to explain Generalized AM-GM inequality

 

One of the challenging questions before proving any inequality is , “What elementary inequalities should be used ?”. Just because something looks like a AM-GM inequality does not mean you can use raw version of AM-GM inequality and proceed. An example of this is shown using Carleman’s inequality where the usual AM-GM fails to go anywhere. The example illustrates the principle of maximal effectiveness whereby we conspire to use our tools under precisely those circumstances when they are at their best. The chapter ends with stating the three principles from George Polya which are extremely relevant for solving inequalities

• Can you solve your problem in a special case?
• Can you relate your problem to a similar one where the answer is already known?
• Can you compute anything at all that is related to what you would really like to compute?

---

<   Lagrange’s Identity and Minkowski’s Conjecture  >

The author then sheds light on Lagrange’s Identity and Minkowski’s conjecture. The connection between Cauchy’s inequality and Lagrange’s Identity is shown. The identity focuses on the defect in Cauchy’s inequality.

The chapter then talks about the problem of writing a non negative polynomial as a sum of squares and derives interesting stuff. It is possible for a 1d case but is not possible for any 2d case.Minkowski’s Conjecture is discussed which basically states that any non negative polynomial in more than one variable cannot be written as the sum of squares of arbitrary polynomials. This conjecture was later proved by Hilbert

---

 <  On Geometry and Sums of Squares  >

I loved this chapter as it was dealing with projection operators , householder reflectors and their connection with Cauchy-Schwartz Inequality.  By illustrating a simple example of how our intuition fails sometimes when we move to higher dimensional world, the author reinforces the point that we need to have mathematical objects and properties well defined so that we can operate correctly in the slippery world of n dimensions.  The chapter uses projection operator to prove Cauchy-Schwartz. It also derives a tighter bound for the product of two linear forms using projection and reflection operator. For a person well versed with linear algebra stuff, this chapter will be an absolute charm!. The takeaway from using these operators is that plain Euclidean geometry helps one to deepen the understanding of inequalities. The chapter ends with deriving Cauchy-Schwartz using a different geometric model, “Space-time geometry of Einstein and Minkowski.”. I found this part difficult to understand, despite clear exposition.

The highlight of this chapter is the connection between Gram-Schmidt and Inequalities. It turns out that one can use Gram-Schmidt to derive Cauchy-Schwartz inequality and a bunch of other inequalities like Bessel, Products of Linear Forms etc.  If you use linear algebra at work, you are going to love this chapter.

---

 <  Consequences of Order  >

Chebyshev’s Order Inequality and Chebyshev’s popular inequality relating to tail probabilities are covered in this chapter. I have skipped the Rearrangement inequality .. Will refer to it whenever I need it. As such, my naive mind could not relate it to any problem in the math-fin context .

---

 <  Convexity – The Third Pillar  >

The chapter starts off by saying that

There are three great pillars of the theory of inequalities: positivity, monotonicity, and convexity. The notions of positivity and monotonicity are so intrinsic to the subject that they serve us steadily without ever calling attention to themselves, but convexity is different. Convexity expresses a second order effect.

What is Jensen’s Inequality ?

Jensen’s inequality is something which any math-fin student comes across in option valuation fundas, This chapter talks about Jensen’s inequality and a ton of inequalities which are variants of it. The basic approach is to crack a convex function , whose properties help you prove the desired inequality. So, you got to play around and check for various convex functions. However it is not all that difficult as it sounds. Basic functions like log, exponential , trigonometric most often than not, get you home.

---

 <  Integral Intermezzo  >

Inequalities with integrand signs are explored. There are two themes or approaches which are explained using specific inequalities. The first one is to dissect the continuous form of integrand in to various intervals and prove the necessary inequality. The second approach is more involved and unique. It goes by the name “ Transform-Schwartz-Invert”, which basically means that any inequality needs to transformed( may be integration by parts), apply Cauchy Schwartz and then integrate by parts again to prove an inequality. The highlight of this chapter is proving the continuous form of Jensen’s inequality and showing the linkage between Jensen’s inequality and AM-GM inequality.

The continuous form of Jensen’s inequality shows up in a lot of areas in probability, where expectation of a random variable / moments of random variable are expressed in integral form. In all those places, Jensen’s continuous inequality is priceless.  This chapter also shows an amazing connection between the fact that correlation and Centered version of Schwarz’s Inequality.

---

 <  The Ladder of Power Means  >

The upper bound in Cauchy’s inequality can be generalized and this is precisely that is done in the chapter.

Generalized Power means are introduced and Power mean curve is explored . The curve shown below can be an effective tool for proving quite a number of inequalities, starting from the simple HM<=GM<=AM to intricate inequalities.

By having an understanding of generalized power means, you can identify power mean inequality lurking in a problem and exploit the properties.

---

 <  Holder’s Inequality  >

From a math fin point of view, this chapter is probably the most important of all , as it talks about Holder’s and Minkowski’s inequality. Both these inequalities are very useful in dealing Lebesgue spaces. Holder’s inequality states that:

In the norm format, it is easier to recognize. Whenever Holder’s inequality is used, there is inevitable talk of Minskowski’s inequality. It arises mainly to prove that p-norm used in the Holder’s inequality makes sense. The triangular inequality that is need to justify p-norm is translated to Minkowski’s inequality.

The beauty of this book is that it shows connections between various inequalities. Triangle implies Cauchy, Minkowski implies Holders, Schwartz inner product version implies Cauchy, etc. After sometimes you start to wonder that , may be , you can solve a problem from any set of inequalities and it  an ART to choose the right inequality and the right equality (sometimes) for the given context. No wonder the book is subtitled, “ The art of mathematical inequalities”.

---

The last part of the book covers Hilbert’s Inequality, Hardy’s Inequality , Symmetric Sums and Schur Convexity. I found the book as one of those books that is overwhelming in the first read. Not at all in the negative connotation. Your mind is bombarded with so many wonderful ways of looking at inequalities that you have to PAUSE and actually take stock of the ways to look at different inequalities. For example an inequality like,

can actually be solved by 1) Cauchy’s, 2) Combination of Power mean and Chebyshev’s Order Inequality , 3) Combination of Jensen’s and Holder’s Inequality 4) etc …Basically , this book will change the way you think about inequalities. You no longer stare at an inequality wondering what the hell it is supposed to imply , but you get in to pattern oriented thinking. You start making connections between inequalities and real life stuff that you come across , like a centered version of Schwarz’s inequality has a direct connection with the concept of correlation, Chebyshev’s Inequality with tail probabilities, Holder’s Inequality with norms in Lebesgue measurable space etc. 

I am hoping to use this as a reference to inequalities as and when required. But more than a reference, I  would definitely be going over this book a couple of more times in my working life as it equips you to connect seemingly unrelated stuff.  Also the inequality tricks mentioned in the book are priceless.

  Takeaway :

Inequality, from a very practical point of view. gives you a handle on the bounds of  a problem. Most of the problems in the math fin area are assumed to be cracked if you are able to form effective bounds, be it option pricing / hedge ratio / No arb bounds on implied vols,etc.

This book will give you a working knowledge of inequalities by providing a thorough explanation of 4 core principles, i.e Cauchy-Schwartz Inequality , AM-GM Inequality , Jensen’s Inequality and Holder’s inequality. Once you go think through these 4 principles and understand the tricks behind extending them, you will start noticing their variants in umpteen number of situations.

Numerical Linear Algebra : Summary

  Prof.Trefethen  David Bau

Prof Lloyd N.Trefethen and his student, David Bau have neatly organized all aspects of numerical linear algebra in to a set of 40 lectures. Each lecture revolves around one specific idea. I will try to summarize the key points of these lectures.

Every person who has solved any real life math fin problem knows that the classic numerical algebra is dead. Iterative methods are almost always used for finite difference methods, solving pde’s, optimization. Books such as these , which explain things clearly and  give the intuition + math behind iterative methods should be considered as a treasure. To appreciate the iterative methods, it is important to know the classic algos. In that sense 31 lectures out of 40 lectures in the book revolve around the classic way of solving stuff. If you have the patience to slog through the 31 lectures, then you will definitely see the iterative methods in a different perspective altogether.

Lecture 1 & 2 : Matrix-Vector Multiplication , Orthogonal Vectors and Matrices

The first two lectures starts off with defining matrix multiplication, Null Space, Rank, Inner Product, Outer product , Unitary Matrices etc. Just enough concepts to get going instead of swamping the reader with Gaussian elimination /pivoting etc which is the way books on Linear Algebra typically begin.

Lecture 3: Norms

Norms assume an important role in numerical linear algebra as they serve as a measure of size and distance in a vector space. One generally comes across Vector Norms in lots of places but Matrix Norms are little special as one can define them based on the norms induced by the vector subspace OR norms independent of the vector subspace, which are called General Matrix Norms. The only norm that I had known before reading this book was inner product induced norms. Not many books discuss norms at a detailed level as this book does, and more so , right at the beginning of the book. Bounds for the norm of product of two matrices are derived in this note and are very helpful in deciding the backward stability of the algos.

Lecture 4: The Singular Value Decomposition

This note introduces the basic notation of SVD. SVD which was used relatively sparsely by scientists and engineers a few decades ago, has become one of the pivotal algos in Linear algebra. SVD is motivated by a nice geometric fact - “ SVD is the image of the unit sphere under any m*n matrix is a hyper ellipse”. By using SVD you get to play a Surgeon’s role , meaning you get to see all the internals of the matrix – the four subspaces of the matrix , Row space, Column Space, Null Space, Left Null Space. There are two versions of SVD, the Reduced SVD and the Full SVD. This note discusses both these versions and the differences between them. The other fascinating aspect of SVD is that every matrix has an SVD representation. This is akin to “ Every Square matrix having a Schur Decomposition”

Lecture 5: More on the SVD

Considering that SVD is used in tons of applications, it is not surprising that there is an extra chapter on SVD. This starts off by saying that SVD helps in choosing a smart basis in such a way that the new basis reduces Ax = b to a diagonal matrix relationship.

There are three differences between SVD and EVD( Eigen value decomposition)

• SVD gives out orthogonal basis whereas EVD need not always(except for Normal operators)
• SVD works with 2 basis whereas EVD works with one
• SVD exists for any matrix whereas EVD works for square matrices only

The other appealing properties of SVD are

• With SVD , you can have two different basis for the matrix of transformation.
• With respect to the two orthogonal basis, the matrix of the transformation is a diagonal matrix
• Inverse of a matrix can easily be found by SVD
• One can do an SVD on the matrix and get the maximum singular value to be the norm of the matrix where norm is induced by a norm 2 vector space

In fact most of the important theorems in linear algebra can be easily derived using SVD.

Lecture 6: Projectors

It can safely be said that Projection operator is possibly THE MOST important operator of linear algebra. Most of the statistics based problems need a projection operator. Therefore this note becomes important as all the properties of Projectors are summarized. Some of them are

• Range( I -  P ) = null( P ) where I is identity operator
• Null( I – P ) = Range( P )
• Projector operator is idempotent
• If Range( P ) = S1 and Range( P )  = S2, then P is the projector onto S1 along S2.
• An Orthogonal Projector is one that projects on to a subspace S1 along S2 , where S1 and S2 are orthogonal.

Lecture 7: QR Factorization

This lecture introduces QR factorization because it connects almost all the algos in numerical linear algebra. Sadly this is never taught at the beginning of the linear algebra courses . Existence and Uniqueness of QR factorization is proved and its usage in solving Ax = b types problem is shown. When you step back from the world of matrices and then think about QR factorization in general, it strikes that you can use this in any application to make it computationally efficient. If you want to project a function in the vector space of polynomials, you can very well do that by starting with any basis and using QR to represent the problem in orthogonal basis.

Lecture 8: Gram-Schmidt Orthogonalization

Gram-Schmidt Orthogonalization is a method of factorization that can be termed as “triangular orthogonalization”, meaning a set of triangular matrices are applied on the matrix to produce an orthogonal matrix. Classic Gram-Schmidt is numerically unstable and hence this lecture introduces modified Gram-Schmidt which is nifty trick on the original algo. Unless you go over the two algorithms very carefully, you might not notice the difference between classical and modified algo. The operation count for Gram Schmidt is about ~ 2mn^2 for a m by n matrix. This note introduces a geometrical way of computing the operation count , an idea which is very interesting.

Lecture 9: MATLAB

Three examples are provided to motivate the reader to use Matlab for visualizing matrix operations. Well , You can use any stats /math based software. The authors main intention is that linear algebra stuff is understood only when you play with matrices.

First example deals with orthogonalization of Vandermonde Matrix which gives rise to Legendre polynomials. Why are Legendre polynomials used ? Well if you can represent a function as a linear combination of Legendre polynomials, you have the advantage that components are orthogonal. This makes a lot of computations easier.

Second example is a wonderful way to illustrate machine epsilon using QR decomposition and Gram Schmidt method. It is a superb example that shows the difference between between classical Gram Schmidt algo and Modified Gram Schmidt algo. The visual that is presented with this example is something that any reader will never forget.

The last example shows the instability of different algos when a 2*2 matrix has a rank close to 1. This basically hints at the problem of ill-conditioning. Another interesting exercise mentioned in this chapter is the use of SVD for image compression. Take an image and you can use SVD to find just enough rank 1 matrices to represent the sparse data. It can be best understood if you actually create an image and apply svd to compress the data.

Lecture 10: Householder Triangularization

This note introduces Household reflector method as an improvement over QR decomposition. QR decomposition using triangularization can be improved using Householder Orthogonal triangularization If there is m*n matrix, the ops count for improved gramschmidt is 2m n^2 whereas for Householder triangularization is 2m n^2 – (2/3) n^3 .Almost all the sparse matrices use Household triangularization for decreasing the ops count

Lecture 11: Least Squares Problems

This lecture introduces the three standard methods to solve Ax = b.

• Linear equations – flip side : numerically unstable
• QR decomposition to tide over numerical issues – flip side : bad results with rank deficient matrices
• SVD works well with rank deficient matrices.flip side – yet to come across !

Lecture 12: Conditioning and Condition Numbers

This note introduces the concepts of condition number. Conditioning pertains to the perturbation behaviour of a mathematical problem. Stability pertains to the perturbation behaviour of an algorithm used to solve that problem on the computer.One can work with Absolute condition number / relative condition number. Both absolute and relative condition numbers have their uses, but the latter are more important in numerical analysis. This is ultimately because the floating point arithmetic used by computers introduces relative errors rather than absolute ones;

The note then gives examples of ill-conditioned problems. Polynomial root-finding is an example of ill-conditioned problem and hence finding eigen values from the characteristic equation needs to be avoided.

The condition for Matrix-Vector multiplication is then derived . The note ends with a very important theorem that talks about the condition number for Ax=b. The essence of this theorem is that one can at least give bounds to the condition number of the problem. The bound which is the norm of ( A )times norm of (A inv) has a special name , “Condition Number of the matrix”. This is relevant to the matrix and is not to be confused with the condition number of a problem.

Lecture 13: Floating Point Arithmetic

If you have never thought about machine representation of numbers , then this note tells you all. Floating point arithmetic basically deals with the way in which computer stores numbers. Any computer programmer/ algo developer / modeller must know about this floating point arithmetic. There are very subtle issues that need to be understood. In any case, this note only deals with machine epsilon. If you are comfortable with Big O notation,IEEE standards for number representation, you can safely skip this note.

Lecture 14: Stability

This note introduces the concepts of accuracy, stability and backward stability. A stable algorithm is one which gives nearly the right answer to nearly right question. A backward stable algorithm is one that gives the right answer to nearly right question. An important theorem mentioned in this lecture is that

For problems f and algorithms f’ defined on finite-dimensional spaces X and Y, the properties of accuracy, stability, and backward stability all hold or fail to hold independently of the choice of norms in X and Y.

The above theorem allows you to use any norm for checking the stability and accuracy aspects.

Lecture 15: More on Stability

This note talks about stability and condition number of the matrix. It shows that solving eigen values using characteristic equation is a bad idea as the polynomial resulting from the characteristic equation is usually ill-conditioned, meaning whatever method you use to extract the roots of the polynomial, they are going to be extremely sensitive to minor perturbations in the polynomial coefficients.

Given a problem, it is obvious that conditionality is going to affect the accuracy of the solution.Hence if one has to choose an algo or evaluate an algo, it is backward stability that matters. The condition number of A is so global a property as to be more or less invisible at the level of the individual floating point operations involved in solving Ax = b.

The basic takeaway of this note is that algo needs to be evaluated from backward stability perspective and the solution needs to be evaluated based on conditionality and backward stability perspective.

Lecture 16: Stability of Householder Triangularization

This note introduces the concept of stability using an example of an ill-conditioned matrix. If you generate a random triangular matrix, the column spaces of the matrix are going to be exceedingly ill-conditioned as a function of the entries of the matrix. This means that whatever algo you use for QR decomposition, the individual Q and R are going to show large absolute and relative errors. However the astonishing thing is that Householder gives the product of QR in such a way that QR differs from the original matrix by a very small value which is of the order (machine epsilon). This example in the note makes you realize that algo needs to be judged from backward stability . WHY? Well, the problem could be ill conditioned and hence blaming the algo for errors is not the right approach.

To reiterate, the most important aspect in linear algebra is backward stability, meaning, giving a right answer to an approximately right question. Householder Triangularization fits this requirement and hence qualifies as a backward stable algorithm. The QR thus obtained from Housholder Triangularization would be the right factorization for a perturbed A instead of A. It is stated in the note that Householder triangularization is backward stable for all matrices.

QR factorization is not an end in itself but is a means to solve the MEGA equation of linear algebra Ax = b. If the Householder factorization QR is backward stable, is it enough to make it a satisfactory piece of larger algorithm? Thankfully the answer is YES and hence the algo for calculating x in Ax = b using Householder triangularization is ALSO backward stable. Basically the point that this note makes is that , if you can solve x using an algo for an approximate A, i.e A + delta(A) where delta(A) depends on machine epsilon, then the algo is good enough to be used in various applications.

This note also mentions about SVD where one can apply SVD on an ill conditioned matrix and get a lesser forward error as compared to House Holder factorization. Though SVD does not reduce the forward error to 0 as the other component effecting the result is the conditionality of the matrix. A extremely important thing to remember, i.e conditionality and algo both effect the results. Algo can be evaluated based on backward stability.

Lecture 17: Stability of Back Substitution

This note systematically deals with all the aspects of a back substitution algorithm in proving that it is a backward stable algorithm. For a simple back substitution algo for Rx = b, it is shown that a small perturbation in R gives an exact answer for x, i.e (R+ delta(R)) x’ = b where x’ denotes the floating point representation of x.

The above bounds are derived for the R matrix. Basically we are seeing a component wise bounds rather than a weaker norm based bounds in the above proof. In the early decades of numerical analysis after the Second World War, most error estimates were obtained in the norm-wise form, whereas in more recent years there has been a shift toward component-wise analysis, since such results are sharper and algorithms that satisfy component-wise bounds are less sensitive to scaling of variables.

Lecture 18: Conditioning of Least Squares Problems

This note talks about the effect of perturbation of A and b on x and y. The following matrix summarizes the results in terms of three dimensionless parameters κ , θ , η. Kappa represents the conditioning number, theta gives an idea of the closeness of fit, and eta represents how much the projection falls short of condition number.

It is imperative to calculate these 4 numbers as soon as you see as Ax =b least squares problem before using an algo. The numbers in the matrix will give an intuitive idea about the nature of problem.

Lecture 19: Stability of Least Squares Algorithms

This note checks various algos solving Ax = b, such as Householder Triangularization, Cholesky, Modified Gram Schmidt, SVD for stability and accuracy issues. The results from various algos gives the reader an idea of relative strengths and limitations of the decomposition algorithms. The input matrix is deliberately chosen as a rank deficient Vandermonde matrix to show the performance of various algos. After going through this note, you will always tend to use SVD for any factorization for rank deficient matrices, as it is likely to be a superior over other algos. The highlight of this chapter is that it will make the reader realize that , Whenever one comes across error estimate, one needs to always gauge the individual contribution of ill-conditioning AND contribution of algo-performance. There is also a nice reasoning given for the instability of cholesky decomposition algo used to solve Ax = b.

Lecture 20: Gaussian Elimination

This note starts off by stating the various factorization in words

• Gram-Schmidt : A = QR by Triangular Orthogonalization
• Householder : A = QR by Orthogonal Triangularization
• Gaussian Elimination : A = LU by Triangular Triangularization

The Gaussian elimination is one of the basic factorizations used for solving a system of equations. Basically it involves solving Ax = b by factorizing A as LU and then using forward and backward substitutions. The problem with plain vanilla LU is that it is not backward stable. Operation count is about (2m^3)/3 flops for a m by n matrix.

Lecture 21: Pivoting

This note introduces complete pivoting / partial pivoting to improve the performance of Gaussian elimination. Basically this involves factorizing PA = LU or PAQ = LU , where P and Q are row and column permutation matrices

Lecture 22: Stability of Gaussian Elimination

This note goes in to the details of the reasons behind the instability of Gaussian elimination. The note says “We shall not attempt to give a full explanation of why the matrices for which Gaussian elimination is unstable are so rare. This would not be possible, as the matter is not yet fully understood. But we shall present an outline of an explanation.” The note concludes with a positive tone saying that Gaussian elimination with partial pivoting algo is highly unstable for certain matrices of class A. For instability to occur, however, the column spaces of A must be skewed in a very special fashion, one that is exponentially rare in at least one class of random matrices. Decades of computational experience suggest that matrices whose column spaces are skewed in this fashion arise very rarely in applications. Basically you can still rely on the partial pivoting algo for most of real world applications.

Lecture 23 :Cholesky Factorization

This note talks about a matrix decomposition applied to Hermitian positive definite matrices. The algo is a variant of Gaussian elimination which exploits the symmetry present in the matrix. The operation count is (m^3 ) / 3 flops. All of the subtleties of the stability analysis of Gaussian elimination vanish for Cholesky factorization. This algorithm is always stable. Intuitively, the reason is that the factors of R can never grow large. The stability of Cholesky factorization is achieved without the need for any pivoting. Intuitively, one may observe that this is related to the fact that most of the weight of a hermitian positive definite matrix is on the diagonal.

Lecture 24: Eigenvalue Problems

The note starts off by saying that eigen value problems are particularly interesting as the algos for solving them are powerful, yet not obvious. Basic definitions of eigen value and eigen vectors are provided at the beginning of the note.Eigenvalue and Eigen vectors are useful for two reasons, one algorithmic, the other physical. Algorithmically, eigen value analysis can simplify solutions of certain problems by reducing a coupled system to a collection of scalar problems. Physically , eigen value analysis can give insight in to the behaviour of evolving systems governed by linear equations.

Usage of EVD produces the following form X need not be orthogonal for a general eigen value decomposition. However it so happens that one can choose X in such a way that they are orthogonal in which case, the diagonalization is termed as Unitary Diagonalization. Only Normal matrices are unitarily diagonalizable. This means that eigen vector decomposition and svd coincide only for Normal matrices( transformations for which T*T = TT*)

The characteristic polynomial is then defined and is used to define algebraic multiplicity.The concept of algebraic multiplicity and geometric multiplicity is introduced so as to classify matrices as defective matrices. A defective matrix is one where algebraic multiplicity of one or more eigen values is greater than the respective geometric multiplicity. What are these multiplicities? Algebraic multiplicity of an eigen value is its multiplicity as a root of the characteristic equation. Geometric multiplicity of a eigen value lambda is equal to the dimension of (A-lambda* I) ^n for a n by n matrix.  The note concludes by introducing Schur Factorization, which is applicable to any square matrix.

The major takeaway from this note is as follows :

Lecture 25: Overview of Eigenvalue Algorithms

The next five lectures talk about various aspects of eigen value algorithms. I was very sceptical about going over these lectures as it was going in to a depth which was probably not required for my work. I mean eigen(A) gives all the results that you need. Why should I care about the internal workings about EVD algos ? Harbouring such feelings, I decided to speed read and see whether there is any thing that I could get from the dense lectures about eigen value decomposition.

The overview note was brilliant to say the least. It makes the brilliant connection between a polynomial equation and an EVD problem and puts forth a beautiful argument that since there is no formula that exists for expressing the roots of an arbitrary polynomial, given its coefficients, there is no closed form solution/no finite number of steps that can be programmed to find the eigen values. This means that eigen value solver must be iterative.

The goal of eigen vector solver is to produce sequences of numbers that converge rapidly towards eigen values. In this respect eigen value computations are more representative of scientific computing than solutions of linear equations. There are two phases for any eigen solver. Phase1 is to reduce the input matrix in to an upper Hessenberg matrix and in the second phase, an iteration is applied to generate a formally infinite sequence of Hessenberg matrices that converge to Triangular form. Once Triangular matrix is formed, Similar matrices argument is used to show that eigen values of the initial matrix and the triangular matrix are the same.

Lecture 26: Reduction to Hessenberg or Tridiagonal Form

This note shows , why is it a bad idea to use householder type matrices for reducing the input matrix to a upper Hessenberg matrix. Subsequently it goes in to developing the algo that actually reduces the input matrix in to upper triangular Hessenberg matrix. The next 4 lectures goes in to great depths to explain the inner workings of an EVD algo. The last lecture in this note talks about the implementation of SVD Algo.

The last part of the book deals with iterative methods which are extremely useful in solving real world problems. In the recent times, they have overshadowed the classic methods of linear algebra. In one sense, if you are going to use computers to solve something, most often than not, you will have to resort to iterative methods. I will try to post the main points of the last part of the book, “Iterative methods” , some other day.

Gene Golub (1932 – 2007 )

Gene Golub’s Obituary written by Professor Lloyd N. Trefethen( Oxford) :

A century ago, matrices and the techniques for their manipulation — linear algebra — were a backwater of mathematics. Today, they are the foundation not just of the mathematical field of numerical analysis,but also of computational science and engineering, and have become indispensable for anyone who wants to get numerical results from a computer. The pre-eminent figure in matrix computations over the past 50 years, Gene Golub, died on 16 November,2007.

Golub was born in Chicago on 29 February 1932, to Jewish parents from Latvia and the Ukraine. His childhood was not affluent, but he was a good student. After two years at a junior college, he transferred to the University of Illinois at Urbana-Champaign, achieving his doctorate there in 1959. At the time, Illinois, with the first of its ‘ILLIAC’ supercomputers, was a great centre of computing, and Golub showed his affection for his Alma Mater by endowing a chair there 50 years later. Rumour has it that the funds for the gift came from Google stock acquired in exchange for some advice on linear algebra. Google’s PageRank search technology starts from a matrix computation — an eigenvalue problem with dimensions in the billions. Hardly surprising, Golub would have said: everything is linear algebra. He came to believe that in his twenties, as he realized that new methods of orthogonal matrix factorization introduced by Wallace Givens and Alston Householder offered the right mathematical recipe for solving all kinds of problems. In particular, Golub focused on the idea known as singular value decomposition, SVD, which systematically isolates the dominant components of a linear process. Together with William Kahan and Christian Reinsch, he invented the now standard SVD algorithms, and showed scientists, engineers and statisticians how these algorithms could be used in areas such as the least squares method to find the best fit to a curve; in optimization problems and control theory; and for the determination of crucial matrix parameters such as their norms, ranks and condition numbers. In later years he drove a car with the licence plate ‘PROF SVD’.

Golub found his way to Stanford University in 1962, eventually becoming the senior professor in its formidable computer science department. In 45 productive years there, he advanced matrix computations in areas as diverse as geodesy, data mining and quantum chromodynamics. The dimension of what was considered a ‘big’ matrix grew from 100 to 1,000,000 in the same period, and Golub was among the first to develop the iterative algorithms that make problems involving such huge matrices tractable. As the new methods came in, older ideas such as gaussian elimination (essentially,the way one is taught to solve a system of simultaneous equations in school, by eliminating the variables one by one) became a smaller part of a new and greater enterprise. Along with the new algorithms came a new world of software for solving mathematical problems, such as EISPACK, LAPACK and MATLAB.

Golub’s book Matrix Computations, co-authored with Charles Van Loan of Cornell University, became a bestseller and the\ definitive textbook of the field. Honours flowed in, including membership of the US National Academies. As a servant of the wider scientific community, Golub did as much as anybody to make the Society for Industrial and Applied Mathematics (SIAM) the organization it is today. He served it in various capacities, among them as president (1985–87). He also founded and edited two of the society’s journals, the SIAM Journal on Scientific and Statistical Computing and SIAM Journal on Matrix Analysis and Applications. It was his proposal that led to the quadrennial International Congresses on Industrial and Applied Mathematics. But this impressive list of achievements misses the truly extraordinary aspect of this complex man: the scale of his devotion to people.

Golub was a bachelor for most of his life, and his colleagues were his family No family ever had a more loving, attentive or exasperating father. As he liked to say, “Every numerical analyst has a second home at Stanford”. Countless colleagues enjoyed a glass of wine at his home there, and hundreds of them stayed over for a night or even a month at his invitation. How did he remember all our birthdays and reading tastes and children’s names? Golub could not spend a day without other people. He would eat dinner with them, talk matrices with them, organize conferences with them, write papers and books with them, argue academic politics with them — an endless dance of interactions, plans and projects. Anywhere in the world, a numerical analyst knows who is meant by ‘Gene’. About 250 of them were his co-authors. They knew that it would fall to them to do most of the writing; but Golub saw the connections, knew the literature, and made the paper happen. He seemed almost to have invented e mail. As early as 1981, his office computer was set up to beep the moment a message arrived. His personal address list evolved into the worldwide database of numerical analysts, and his notes to friends became the Numerical Analysis Digest. This newsletter, one of the first e-bulletins, is now sent to some 8,000 recipients weekly. He could not sit still. As he left us in Oxford last September after an extended sabbatical visit, having spent much of the preceding months talking with the graduate students in the common room — to which he had donated $1,000 for a biscuit fund — he mentioned that he had three trips to China planned for the upcoming year.

Gene Golub was restless and never entirely happy. He was a demanding friend; behind his back, we all had Gene stories to tell. It was a huge back: Gene was big, dominating any room he was in, and grew more impressive and imposing with the years. Graduate students around the world admired and loved him, and he bought them all dinner when he got the chance. His unexpected death, in Stanford in between speaking at a conference in Hong Kong and flying to Zurich for his eleventh honorary degree, has left the world of numerical analysis orphaned and reverberating.

In Code : Summary

 

Sarah Flannery became famous at a young age of 16 when her algorithm for cryptography was speculated to be a far better alternative to the widely adopted RSA algorithm. She presented an algorithm at the Young Scientist Competition with no fan fare and she won the competition. This book would not have been written but for one reason , the competition result got picked up by “London Times “  and an article appeared on the front page with a nerdy picture and a catchy title , ”Sarah Flannery, 16 , who baffled the judges with her grasp of cryptography”. Subsequently “Reuters” published the story , which put Sarah, her family, her life till then, under public eyes. She was inundated with calls from journalists, TV shows, firms offering her employment , VCs wanting to give seed capital , universities asking her to give a talk to their students etc.

This book is an attempt by Sarah to shed light in to her mathematical journey and the various factors that helped her to create the algorithm, to a far wider audience. The book has been co-authored by her father David Flannery.

Sarah Flannery hails from a village of Blarney,County Cork, Ireland where she attended a local girls school, a very ordinary school by the usual standards. Her father was a math lecturer at Cork Institute of technology. What brought her to the world of math ?  Sarah credits her father for introducing her to the world of math in a unique way, “using puzzles”. David Flannery believed that math needs to enjoyed for one to be creative. One way to enjoy math is to solve puzzles which bring out mathematical concepts. So, he cultivated this puzzle culture at home.   

At a blackboard in the kitchen, the father & daughter would discuss math puzzles and like a good coach, Sarah’s father merely provided directions and subtle cues and almost never gave the entire solution at once. This culture of solving puzzles and engaging one’s mind over puzzles was the main reason for Sarah to develop a liking towards math. It made math more tangible and interesting . Also , Sarah’s father never allowed to let go an opportunity to extend a puzzle once it was solved. He used to extend the solved puzzle to create another puzzle , a little difficult one , and scribble it on the blackboard. What he was doing through this culture at home was basically trying to inculcate the axiomatic method of mathematics where you build up theories over a nice structure of axioms,  theorems, lemmas. For Sarah, learning through Puzzle was one of the fundamental ways to understand math.

In the book she says

Puzzles, like humour , have an universal appeal and know no boundaries – cultural , educational or otherwise. People of all ages and levels of education are attracted to the puzzle as they are to the joke. In a sense, there is an affinity between the two in that a vital ingredient of both is the element of surprise. No problem is worthy of the name “puzzle” if its solution is obvious, just as the joke whose punch line is easily anticipated is soon forgotten. The true puzzle should be accessible to all, its solution should require no specialist knowledge other than, at times, the rudiments of arithmetic and algebra. It is perhaps, the unconscious feeling that we all start out equal that gives puzzles their charm

Transition Year

This book talks about a specific aspect of Irish educational system that I found very interesting . After the end of high school, the students in Ireland can opt for a one year Transition Year Programme before moving on to 2 year college education. The purpose of transition year is described as follows at an Irish school site.

The overall mission of the Transition Year Programme is to promote the personal, social, educational and vocational development of students and to prepare them for working life. The course is designed to cater for the needs and capacities of students within a framework of broad general education which would have a substantial academic base. The course also includes a wide range of practical applications, activity-based learning, team and group work and work experience.

The Transition Year Programme acts as a "bridge" from the highly structured environment of the Junior Cycle and to the much more independent, responsible and mature attitude towards work, study, school and interpersonal relationships of the Leaving Certificate Programme.

Almost every parent in India is anxious at the time his/her kid moves from school to college. From a highly structured and regulated environment, the kid moves to college environment where the learning typically is self-regulated/ semi-structured. Most of the kids cannot handle this sudden burst of freedom and mostly fail to use it constructively. This transition year concept sounds very appealing to me and it is definitely an idea that can be explored in the context of Indian education system. Imagine a scenario where the kid after 10th class has one year time to explore his/her interests  / take time out to read up stuff from varied fields / take up mini community projects / explore some programming skills / experiment with stuff etc with no pressure of performance..It would be immensely beneficial to parents too as they can get an idea of what their kids truly enjoy.. They can then guide the kids in that direction.A one year break at the right time in a person’s life might do wonders and at least increases the chance of finding interest areas. However I see resistance to this idea in Indian educational system where everybody is in a hurry to graduate out of some place or the other:).,I hope at least a few parents encourage their kids to take a year off and explore stuff.

It comes as no surprise that Sarah found her calling during the Transition year where she developed a liking towards number theory and Mathematica package. Sarah spent the entire transition year learning about prime numbers, their distribution, their properties etc. By the end of the transition year , she had pretty much decided that she would explore cryptography field besides going through college education.

Sarah then mentions a few essential math stuff needed to understand her improved algo. The details mentioned does not need any pre-requisite knowledge for understanding. She goes over the following stuff :

1. How were enciphering and deciphering systems created in the olden times ?

• The basic math behind enciphering  and deciphering text depends on the modulus function. It starts off from the Caesor system which can  be summarized as
  “ C = ( P + s ) mod 26, P = ( C - s ) mod 26 “. C represents enciphering and P represents deciphering system for the 26 alphabets.The above system is essentially a single key system,meaning the only thing that is essential to crack the system is key s.

• The above system can be refined as follows :
  “ C = ( m1*P  ) mod 26 , P = ( m2*C ) mod 26 “.This is a two key system where instead of additive shift,  there is a multiplicative shift in m. Even for such a simple system one needs to know the multiplicative inverse of m1*mod 26. Appendix provides the Euclid’s algorithm for generating the multiplicative inverse of m1*mod 26

• The above system again can be refined as follows :
  “ C = ( m1*P + s ) mod 26 , P = ( m2*C + s ) mod 26”. This is a three key system where there is additive shift, and a multiplicative shift in m.

• The above system again can be refined as follows:
  ” C = ( m1*P + s ) mod 676, P = ( m2*C + s ) mod 676”. Here the key space is improved by considering digrams

• The above system again can be refined as follows:
  ” C = ( m1*P + s ) mod 17576 , P = ( m2*C + s ) mod 17576 ”.Here the key space is improved by considering trigrams At a broader level, there is a one-to-one function mapping C and P and hence the system components can be  summarized as keys,key space and an invertible function.

2. What sort of Arithmetic is used in Cryptography ?

3. Why are one-way functions & trap-door functions important ?

4. What is Public Key Cryptography and What is the concept behind RSA algorithm ?

With this background provided in the book, Sarah resumes her story.Sarah working as a apprentice in Baltimore technologies meets Dr.William White who then shows a paper by his colleague Dr. Michael Purser. Sarah picks up a lot of stuff from the paper and then tries to come up with an alternative algo to RSA , an algo which is 30 times faster than RSA by exploiting the non-commutative property of matrices. Basically RSA uses exponential calculations whereas Sarah’s also uses multiplication operations.

The last part of the book shows the various phases of preparation that Sarah goes through before winning the Young Scientist award.  She decides not to patent the algo and  opens it for Peer review. Very soon she finds that there are cracks in the algo and all the publicity she got was unwarranted. She realizes that media will jump on to anything saucy and actually don’t care about the veracity of the news item.  Meanwhile, cracks in her algorithm make her return to sanity and get back to life where she can do further research in math. Her decision of not patenting algo actually was pivotal as it helped her see chinks in her math and thus provided the much needed breathing space to continue research in cryptography.

Takeaway :

This book is a great story of a youngster who uses her time to learn and implement an algorithm , to challenge the prevalent RSA algo , which was originally designed by 3 MIT guys. A school kid having the guts to challenge the RSA algo is definitely an inspiring read. It goes on to show that , if you have to have the right attitude towards math ,  you can churn out kick-ass stuff, irrespective of your age.