RK's Musings

Statistical Pragmatism

Via  The Big Picture :

The note summarizes that one does not need to have a split personality to apply Bayesian or Frequentist thinking to stats. Separating Real World with Theoretical World from the perspective of data shows that both the schools of thought kind of have the same assumptions.

========================================================

Frequentist OR Bayesian Inference

========================================================

Frequentist AND Bayesian Inference

Statistical Pragmatism
Bayesian and Frequentist approach

Univariate Distribution Relationships

There are a ton of relationships between various distributions. One typically understands them, remembers them based on the kind of stats work that one does. If one does a lot of Bayesian stuff, one tends to remember the conjugate priors and related distributions. If you are doing survival modeling, you tend to focus on specific distributions like weibull etc. If you are in to OR work, Erlang, gamma, beta distribution parameters are at your finger tips. Irrespective of the type of analysis that one does, it is always good to have a decent overview of various random variables and the connections between them. The connections that one must understand should typically encompass :

• If I am given a random variable from a distribution F1, How do I generate a random variable with distribution F2 ?
• Does a distribution F1, tend to another distribution in the limiting case involving one of the parameters ?
• If you take a convolution of random variables belonging to a specific family of distribution, does the resulting variable belong to the same family ?
• What if you scale a random variable, Does the distribution change ? What if you invert ?
• What if you take a min or max of sample data from a distribution ,Does the resulting statistic belong to the same distribution family ?
• Is the conditional density of a random variable same as unconditional density of the random variable ?
• Does a linear combination of random variables from a family result in a variable that belongs to the same family ?
• Does the CDF allow you to do inverse transformation ( for simulation purpose)

Answering the above questions for the various distributions and more importantly remembering them is a challenging task,at least to me. Recently I stumbled on to a fantastic visual from The American Statistician that summarizes the relationships between 76 univariate distributions that includes 57 continuous probability distributions and 19 discrete probability distributions. Tremendous effort seems to have gone behind making this visual. By merely looking at various segments of the visual, you will get to learn and remember the deep connections between the various probability distributions.  If you work out the relations using pen and paper, then you will tend to appreciate them more.

Psychologist & Netflix prize

Thanks to Ravi, came to know about an old wired article on Netflix prize, where Gavin Potter used fundas from Behavioral economics to crack the problem

A deeper part of Potter's strategy is based on the work of Amos Tversky and Nobel Prize winner Daniel Kahneman, pioneers of the science now called behavioral economics. This new field incorporates into traditional economics those features of human life that are lost when you think of a person as a rational machine, or as a list of numbers representing cinematic taste.

One such phenomenon is the anchoring effect, a problem endemic to any numerical rating scheme. If a customer watches three movies in a row that merit four stars — say, the Star Wars trilogy — and then sees one that's a bit better — say, Blade Runner — they'll likely give the last movie five stars. But if they started the week with one-star stinkers like the Star Wars prequels, Blade Runner might get only a 4 or even a 3. Anchoring suggests that rating systems need to take account of inertia — a user who has recently given a lot of above-average ratings is likely to continue to do so. Potter finds precisely this phenomenon in the Netflix data; and by being aware of it, he's able to account for its biasing effects and thus more accurately pin down users' true tastes.

Couldn't a pure statistician have also observed the inertia in the ratings? Of course. But there are infinitely many biases, patterns, and anomalies to fish for. And in almost every case, the number-cruncher wouldn't turn up anything. A psychologist, however, can suggest to the statisticians where to point their high-powered mathematical instruments. "It cuts out dead ends," Potter says.

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

Lady Tasting Tea

The connection between The Lady Tasting Tea and Statistics :

P-value Fallacy

Via BayesianBiologist  : An excellent explanation of the fallacy that most people have about, P-value

What we really want is the probability of hypotheses given our data (written as P(H | D) ), which we can obtain by applying Bayes rule.

What we get from a p-value is the probability of observing something as extreme or more than our data, under the null hypothesis ( written as P(x>=D | Ho) ).  Isn’t that awkward? No wonder it is so commonly misrepresented.

The theory that would not die

 

This is a talk by Sharon Bertsch McGrayne , the author of a fantastic book titled, “The theory that would not die”. 

My book summary is here . The video lecture @ CMU is worth watching and might motivate someone read the book.

 

Robust Portfolio Optimization & Management : Summary

I tend to read books from the Fabozzi factory , not to get mathematical rigor in a subject but to get an intuitive understanding of the stuff. Overtime, this approach has helped me managed my expectations from Fabozzi books. Having never worked on Black-Litterman model till date, I wanted to get some intuition behind the model. With that mindset, I went through the book. The book is divided into four parts. Part I covers classical portfolio theory and its modern extensions. Part II introduces traditional and modern frameworks for robust estimation of returns. Part III provides readers with the necessary background for handling the optimization part of portfolio management. Part IV focuses on applications of the robust estimation and optimization methods described in the previous parts, and outlines recent trends and new directions in robust portfolio management and in the investment management industry in general. The structure of the book is pretty logical. Starting off with the basic principles of modern portfolio management, one moves on to understanding estimation process, and then understanding the optimization process and finally exploring new directions.

 

PART I - Portfolio Allocation : Classic Theory and Extensions

Mean Variance Analysis and Modern Portfolio Theory

Investment process as seen from Modern Portfolio management

Mean variance framework refers to a specific problem formulation wherein one tries to minimize risk for a specific level of return OR maximize return for a specific level of risk. The objective function usually is set as a quadratic programming problem where the constraints are formulated for asset weights. These constraints typically specify the target risk and the bounds on asset weights. If there is no target return constraint specified, the resulting portfolio is called the global minimum variance portfolio. Obviously there is a limit to the diversification benefits that an investor can seek. Just by adding limitless number of assets, the portfolio risk does not vanish. Instead it approaches a constant

Minimizing variance for a target mean is just one type of formulating fund manager’s problem. There can be other variants, depending on the fund manager’s context and fund objective. Some of the alternative formulations are explored in this chapter such as expected return maximization formulation, Risk aversion formulation, etc.

The efficient set of portfolios available to investors who employ mean-variance analysis in the absence of risk-free asset is inferior to that available when there is a risk-free asset. When one includes a risk-free asset, the asset allocation is reduced to a line, called “Capital Market Line”. The portfolios on this line are nothing but some combination of risk-free asset and minimum variance portfolios. The point at which the line hits the frontier is called “tangency portfolio”, also called the market portfolio. Hence all the portfolios on the CML line represent combination of borrowing or lending at the risk-free rate and investing in the market portfolio. This property is called the “separation”.
Utility functions are then introduced to measure the investor’s preferences for a portfolio with a certain risk and return characteristics.

If we choose the quadratic utility function, then the utility function maximization coincides with mean variance framework.

Advances in the theory of Portfolio Risk measures

If investor’s decision making process is dependent beyond the first moments, one needs to modify or work with an alternative framework than the mean variance framework. There are two types of risk measures explored in this chapter, Dispersion measures & Downside measures. Dispersion measures are measures of uncertainty. In contrast to downside measures, dispersion measures consider both positive and negative deviations from the mean, and treat those deviations as equally risky. Some common portfolio dispersion approaches are mean standard deviation, mean-variance, mean-absolute deviation, and mean-absolute moment. Some common portfolio downside measures are Roy’s safety-first, semi variance, lower partial moment, Value-at-Risk, and Conditional Value-at-Risk. In all these methods, some variant of utility maximization procedure is employed.

Portfolio Selection in Practice

There are usually constraints imposed on the mean variance framework. This chapter gives a basic classification of the constraints, which are

• Linear and Quadratic constraints
• Long-Only constraints
• Turnover constraints
• Holding constraints
• Risk factor constraints
• Benchmark Exposure and Tracking error constraints
• General Linear and Quadratic constraints
• Combinatorial and Integer constraints
• Minimum-Holding and Transaction size constraints
• Cardinality constraints
• Round lot constraints

Portfolio optimization problems with minimum holding constraints, cardinality constraints or round lot constraints are so-called NP-complete. For the practical solution of these problems heuristics and approximation techniques are used.

In practice, few portfolio managers go to the extent of including constraints of this type in their optimization framework. Instead, a standard mean-variance optimization problem is solved and then, in a “post-optimization” step, generated portfolio weights or trades are pruned to satisfy the constraints. This simplification leads to small, but often negligible, differences compared to a full optimization using the threshold constraints. The chapter then gives a flavor of incorporating transaction costs in asset allocation models. A simple and straightforward approach is to assume a separable transaction cost function that is dependent only on the weights of the assets in the portfolio. An alternate approach is to assume a piece-wise linear dependence between the assets and trade size. As such the models might appear complex, but this area is well explored in the finance literature. Piece-wise linear approximations for transactions cost are solver friendly. There is an enormous breadth of material that is covered in this book and it sometimes is overwhelming. For example the case of multi-account optimization does sound very complex to understand in the first reading.

PART II – Robust Parameter Estimation.

Classical Asset Pricing

This chapter gives a crash course on simple random walks, arithmetic random walks, geometric random walks, trend stationary processes, covariance stationary processes, etc. that one sees in the finance literature.

Forecasting Expected Risk and Return

The basic problem with mean variance framework is that one uses historical data estimates of mean return and covariance to use it in the asset allocation decisions for the future. There is a forecast that is built in to plain vanilla mean variance framework. Ideally an estimate should have the following characteristics

· It provides a forward-looking forecast with some predictive power, not just backward looking historical summary of past performance

• The estimate can be produced at a reasonable cost
• The technique does not amplify errors already present in the inputs used in the process of intuition
• The forecast should be intuitive, i.e, portfolio manager or the analyst should be able to explain and justify them in a comprehensible manner.

It is typically observed that sample mean and sample covariance have a low forecasting power. It is obvious as the asset returns are typically the realization of a stochastic process and in fact could a complete random walk as some believe it to be and vehemently argue for the same.

The chapter goes on to introduce basic dividend discount models, which I think are basically pointless and dumbest way to do formulate estimates. Using sample mean and covariance is also fraught with danger. Sample mean is a good predictor only for distributions that are not heavy-tailed. However most of the financial time series are heavy tailed and non-stationary and hence the resulting estimator has a large estimation error. In my own little exercise that I have done using some assets in the Indian markets, I found that

• Equally weight portfolios offer a comparable advantage to using asset allocation using sample mean and sample covariance
• Uncertainty of mean completely plays a spoil sport in efficient asset allocation. It is sometimes ok to have an estimation error in covariance, but estimation error in mean kills the performance of asset allocation
• Mean variance portfolios are not diversified properly. In fact one can calculate zephyr drift score for the portfolios and one can easily see that there is a considerable variance in the portfolio composition.

What are the possible remedies that one can use?

For expected returns, one can use a factor model / Black-Litterman model / Shrinkage estimators. Remedies can easily be talked about, but the implementation is difficult. Black-Litterman needs views about assets, views about the error estimates of the views. So, you take these subjective views and then try to build a model based on Bayesian statistics. In the real world for a small boutique shop offering asset allocation solutions, who provides these views? How to put weights on these opinions? I really wonder the reason behind this immense popularity of Black-Litterman model. Can it really outperform a naïve portfolio? My current frame of mind suggests it might not beat a naïve 1/N portfolio.

For Covariance matrix, there are remedies too, but the effectiveness is context specific and sometimes completely questionable. Sample covariance matrix is essentially a non-parametric estimator. One can put a structure for the covariance matrix and then estimate it. Jagannathan and Ma suggest using portfolios of covariance matrix estimators. Shrinkage estimator is another way to work on it. The crucial thing to ponder upon is ,” If the estimator is a better estimate , does it actually give a higher out-of sample Sharpe ratio ? “.The chapter then talks about Heteroskedasticity and Autocorrelation consistent covariance matrix estimation. It talks about the treatment for covariance matrix under varying lengths, increasing the sampling frequency etc. Overall this gives the reader a broad sense of estimators that can be used for covariance matrix. Chow’s method is mentioned where the covariance matrix is built using the two covariance matrices ,one in quieter period and another in noisy period. Well, how to combine these matrices could be as simple as relying on intuition , or complex way by considering a markov chain. Another remedy suggested is in using a different volatility metric , i.e one of the downside measures such as semi-variance etc. .

Random matrices are introduced to show the importance of dimensionality reduction. It can be shown in cases where the asset universe is large, there are a few eigen values which dominate the rest. Hence random matrix theory makes a case for using factor based model like APT. Again factor models can themselves be of multiple varieties. They can be statistical factor models, macroeconomic factor models, fundamental factor models etc. Selecting the “optimal number of factors” is a dicey thing. The selection criteria should be in such a way that it reduces estimation error and bias. Too less factors decreases estimation error but increases bias. Too many factors increase estimator error but decrease bias. So, I guess the ideal number of factors and type of factors to choose is more an art than science. One of the strong reasons for using a factor model is the obvious dimensional reduction for a large asset universe allocation problem.

The chapter also mentions various methods for estimating volatility such as modeling it based on the implied vols of the relevant options,use clustering techniques, use GARCH methods or use stochastic vol methods. One must remember though that most of these methods are relevant in the Q world (sell side) and not the P world( buy side).

Robust Estimation

Robust estimation is not just a fancy way of removing outliers and estimating parameters. It is a fundamentally different way of estimation. If one is serious about understanding it thoroughly, it is better to skip this chapter as the content merely does a lip service to the various concepts.

Robust Framework for Estimation: Shrinkage, Bayesian Approaches and Black-Litterman Model

Estimation of expected returns and covariance matrix is subjected to estimation error in practice. The portfolio weights change constantly and resulting in the considerable portfolio turnover and sub-optimal realization of portfolio returns. What can be done to remedy such a situation?

There can be two areas where one can improve things. On the estimation side, one can employ estimates that are less sensitive to outliers, estimators such as shrinkage estimators, Bayesian estimators. On the modeling side, one can constrain portfolio weights, use portfolio resampling, or apply robust or stochastic optimization techniques to specify scenarios or ranges of values for parameters estimated from data, thus incorporating uncertainty in to the optimization process itself.

The chapter starts off by talking about the practical problems encountered in Mean-Variance optimization. Some of them mentioned are

• Sensitivity to estimation error
• Effects of uncertainty in the inputs in the optimization process
• Large data requirements necessary for accurately estimating the inputs for the portfolio optimization framework

There is a reference to a wonderful paper, “Computing Efficient Frontiers using Estimated Parameters”, by Mark Broadie. The paper had so many points clearly mentioned, that I feel like listing down them here. Some of them are intuitively obvious, some of them I understood over a period of time working with the data and some of them are nice learning’s for any MPT model builder.

• There is a trade-off between Stationarity of parameter values Vs. length of data that needs to be taken, to get good estimates. If you take too long a dataset, you run the risk of non-stationarity of the returns. If you take too short a dataset, then you run the risk of estimation error
• One nice way of thinking about these things is to use 3 mental models
  • True efficient frontier – based on true unobserved return and covariance matrix
  • Estimated Efficient frontier – based on estimated return and covariance matrix
  • Actual frontier – based on the portfolios on estimated efficient frontier and using the actual returns of the assets
• One can draw these frontiers to get an idea of one basic problem with Markowitz theory – error maximization property. The assets which have large positive error for returns, large negative errors for standard deviation and large negative errors for correlation tend to get higher asset weights than they truly deserve
• If you assume a true return and covariance matrix for a set of assets, draw the three frontiers, it is easy to observe that , minimum variance portfolios can be estimated more accurately than maximum return portfolios.
• To distinguish between two assets having a distribution of (m1,sd1) and (m2,sd2) requires a LOT of data and hence identifying the maximum return portfolio is difficult. However distinguishing securities with different standard deviations is easier than distinguishing with different mean returns
• Estimate of mean returns have a far more effect on frontier performance as compared to estimate of cov. If possible, effort should first be focused on improving the historical estimates of mean returns.
• To get better estimates of actual portfolio performance, the portfolio means and standard deviations reported by the estimated frontier should be adjusted to account for the bias caused by error maximization effect
• The greatest reduction of errors in mean-variance analysis can be obtained by improving historical estimates of mean returns of securities. The errors in estimates of mean returns using historical data are so large that these parameter estimates should always be used with caution.
• One recommendation for practitioners is to use historical data to estimate standard deviations and correlations but use a model to estimate mean returns
• A point on the estimated frontier will, on average have a larger mean and a smaller standard deviation than the corresponding point on the actual frontier.
• Due to error maximization property of mean-variance analysis, points on the estimated frontier are optimistically biased predictors of actual portfolio performance.

This paper made me realize that I should be strongly emphasizing / analyzing the actual frontier Vs. estimated frontier, instead of merely relying on quasi stability of frontiers across time. I was always under the impression that all that matter is frontier stability. Also from an investor’s standpoint, I think this is what he needs to ask any asset allocation fund manager – “Show me the estimated frontier vs. actual frontier for the scheme across the years”. This is a far more illuminating than any numbers that are usually tossed around.

Using a few assets I looked at Estimated and True Frontier in two separate years, one in bull market and one in bear market. In the first illustration, the realized frontier is at least ok, but in the second case, the realized frontier shows pathetic results. It is not at all surprising that the frontier works well for minimum variance portfolios but falls flat for maximum return portfolio. This means “return forecast” is key to getting good performance for high risk profile investors.

Also, one can empirically check that errors in expected return are about 10 times more important than errors in covariance matrix, and errors in variance are twice more important than errors in covariance.

Shrinkage Estimators

One way to reduce the estimation error in the mean and covariance inputs is to follow either shrink the mean ( Jorion’s method) / shrink the cov( Ledoit and Wolf) method. I have tried the latter but till date have not experimented with shrinking both the mean and covariance at once. Can one do it ? I don’t know. Shrinking covariance towards a constant correlation matrix is what I have tried before. Estimator with no structure + Estimator with lot of structure + shrinkage intensity – These three components are essential for shrinkage of estimated mean. Ledoit and Wolf method shrinks the covariance matrix and compare the performance with sample covariance matrix, statistical factor model based on principal components, and a factor model. They find that shrinkage estimator outperforms other estimators for a global minimum variance portfolio.

Bayesian Approach via Black Litterman Model

Since expected returns are so much more important in the realized frontier performance, it might be better to use some model instead of sample mean as an input to the mean-variance framework. Black-Litterman model is one such popular model that combines views with prior distribution and gives the portfolio allocation for various risk profiles. If one has to explain Black-Litterman in words, it can be done this way – You want to strike a middle ground between market portfolio and “views”. You have an equation for market portfolio and you have an equation for views. You combine these equations and form a Generalized Linear Model, estimate the asset returns. These returns turn out to be a linear combination of market portfolio returns and expected return implied by investor’s views. One key thing to be understood is that you don’t have to views on all the assets in the considered asset universe. Even if you have views on few assets, that will change the expected return for all the assets.

However I am kind of skeptical about this method as I write. “Who in the world can give me views about the assets in the coming year?” If I poll a dozen people, there will more than dozen views with confidence intervals for their views. I have never developed a model with views till date. But as things change around me, it looks like I might have to incorporate views in to asset allocation strategies.

Part III of the book is a list about optimization techniques and appears more like a math book than a finance book .For an optimization-newbie, this chapter is not the right place to start. For an optimization-expert, the chapter will be too easy to go over. This chapter then is targeted towards a person who already knows quite a bit about optimization procedures and wants to know different viewpoints. Like most of the Fabozzi books that try to attempt at mathematical rigor and fail majestically, this part of the book throws not surprise. Part IV of the book talks about application of robust estimation and optimization methods.

Takeaway :

Like many Fabozzi series books, the good thing about this book is that it has an extensive list of references to papers/ thoughts/opinions expressed by academia & practitioners about portfolio management. If the intention is to know what others have said/done in the area of portfolio management, then the book is worth going over.

Introduction to Probability Simulation and Gibbs Sampling with R : Summary

Gibbs Sampling is an important method in the context of Bayesian estimation. There are other books on R that focus on Bayesian Simulation (Jim Albert), Monte Carlo simulation (Robert and Casella) that are very good and little advanced. So, where does this book fit in? If one has never done any kind of simulation in R, this book is the ideal reference. For someone who is already aware of the basic simulation stuff, there are 3 chapters in the book that talk about Markov Chain, Bayesian Estimation and Gibbs Sampler that are worth going over. I will try to summarize the main points of the book.

The authors suggest going over Appendix to R newbie. In the appendix, the book talks about basic installation procedure, vectorization present in R, basic syntax for loops, basic graphs using base package and the sample function. In all likelihood a person reading this book might already be very familiar with the basic syntax and operations in R. So, appendix is more a formality in this book. The book contains 10 chapters. The first 7 chapters of the book can be used as a supplementary material for any frequentist based course and the last three chapters for Bayesian Course.

Chapter 1: Introductory Examples: Simulation, Estimation, and Graphics:

The entire chapter is about sample function that is used to generate bootstrap samples to answer some probability questions like birthday matching problem, Envelope mismatch problem etc. By going over this section, a reader will understand all the arguments of the function “sample” in R. The chapter then talks about coverage probabilities for confidence interval, which is nothing but the proportion of time that the interval contains the true value of interest. Using a simple binomial case, the coverage probabilities are shown for various population parameter values. A first timer would find this topic illuminating and will start developing a skeptical eye towards confidence intervals based on frequentist methods. For a simple binomial proportion case, once the true parameter moves away from 0.5, the coverage probabilities drop a lot. There is a mention about Agresti-Coull confidence intervals that addresses coverage probability problem. The best thing about this chapter is the last exercise where Beta distribution is used to model binomial proportion and Bayes is used to form credible intervals for the parameter. Frankly a person exposed to Bayesian Stats will just ignore all these fancy methods like Agresti-Coull method etc and go ahead with prior+ likelihood + posterior modeling of the situation.

Chapter 2: Generating Probabilities:

This chapter starts off by talking about the ways to generate random numbers. Firstly, the random numbers that are generated by computer are pseudo random numbers as there is nothing that is perfectly random. The word “random” is more appropriately applied to the process by which a number is produced than the number itself. The section briefly traces the history of pseudo random numbers starting from Linear Congruential generator, RANDU, Mersenne twister. A few conditions are mentioned for any generator to be useful in real life, i.e. 1) large modulus and full period, 2) histogram of scaled values should look uniform, 3) pair wise independence of the values. R has Mersenne twister algo behind runif() command and its power is really amazing. Its behavior has been tested up to 623 consecutive dimensions and has a period of 4.32 followed by 60001 zeroes. These distinct values from runif() are mapped in to roughly 4.3 billion numbers that can be expressed within the precision of R. That’s the power you have when you use generators from R. The section then moves to generating random variables from uniform random variates. The quantile transformation method is used to simulate values from distributions such as beta, binomial, chi-square, exponential, standard normal, normal, Poisson, Rayleigh etc. Knowing functional forms of the density for these distributions are useful in general, as they help one immediately recognize them when they appear in various contexts. For example if you see f(x) = constant * x ^(constant- 1) , you can immediately decipher that the distribution can be a beta in some form. I mean, these are little things but are very useful. Let’s say you see a function whose cumulative density function is sqrt(x) , you should immediately of relate this to beta(1/2,1) distribution. These little linkages will help one decide the components of model better. This chapter will enable a reader to simulate values from the popular distributions, either using uniforms / standard normal variates.

Chapter 3: Monte Carlo Integration and Limit Theorems

The chapter starts off with solving an integral problem with Riemann integration method, Monte Carlo Integration, Accept-Reject Method and Random sampling method. It then explores law of large numbers and explains convergence in probability using visuals. You can’t use Law of Large numbers for Cauchy; a fact that is showed using integrals and drilled in to every student in an elementary course on statistics. But a simple visual shows it instantly. The section then talks about limiting behavior of Markov process and shows that the convergence of Markov process to be very slow. Convergence in distribution is explained using Central Limit theorem, the crucial difference between LLN and CLT being that former doesn’t given any indication about the uncertainty of the estimate while the latter gives an idea about the error possibility. The section ends with showing connections between Riemann integral and Monte Carlo simulation. It then shows the importance of Monte Carlo Simulation in higher dimensional parameter problems where Riemann integral using grid based approach turns out to be computationally inefficient.

Chapter 4: Sampling from Applied Probability Models

This chapter goes in to sampling from known distributions to estimate probabilities of situations where closed form solutions are painful/ sometimes intractable. It starts off with looking at Poisson process, exponential holding times of the process and tries to apply sampling procedures to solve simple problems from Queuing theory. Based on the assumptions of inter arrival times of customer and distribution of servicing time of various servers, many kinds of estimates can be obtained by approximating values from sampling distribution. Another application explored is order statistics. Most of the distribution related questions about Order statistics can be solved using painful integration procedures and it is a classic area where simulation gives you quick answers. Another advantage of simulation is that you can quickly check your intuition. Most of the intro stat books tell you that sample mean and sample variance are independent variables for a normal distribution. For other distributions like exponential, it doesn’t hold well. To test this, one can easily simulate some random samples from whatever non-normal distribution you want to check, look at the joint distribution of sample variance and sample mean visually. Visuals do a good job of showing the independence of these variables, though merely relying on some correlation metric could be dicey(as correlation is merely a measure of linear dependence). The chapter ends with an introduction to Bootstrapping method. I vividly remember the days when I first got introduced to bootstrapping. I was so kicked about this concept as it relieved me of memorizing painful formulae (2 sample mean comparison tests equal / unequal sample sizes). It’s a shame that I actually memorized these things way back during my MBA days and never could understand the real practical applications. Thankfully Bootstrapping got my interest back in to stats. The section provides a few exercises that illustrate the difference between non-parametric bootstrapping method vis-à-vis parametric bootstrapping methods.

A cool thing one can learn from this chapter is the projection of n dim space in to sufficient statistic space. Let’s say you simulate 5 Random variables from Beta (0.3, 0.3) distribution and then you plot the sample mean vs. sample sd. The data fall inside the 5-dimensional unit hypercube, this has 32 vertices. A large proportion of data points will fall near the vertices, edges and faces of the hypercube. The horns in the below plots are images of these vertices under the transformation from the 5-dimensional data space to the 2-dimensional space of sufficient statistics. The horns correspond to the various vertices and actually each of horns correspond to choose(5,0) , choose(5,1), choose(5,2), choose(5,3), choose(5,4), choose(5,5) vertices of the hypercube. I guess such learning is valuable as one starts visualizing stuff in higher dimensional / multivariate cases.

Chapter 5: Screening Tests

This chapter gives an intro in to an estimation problem where traditional methods fail/ give absurd values. It subsequently introduces Bayes theorem, thus showing the importance of conditional probabilities in statistical inference problems. The relevance of these conditional distributions to sampling from target distributions is evident from the Gibbs Sampling method covered in the subsequent chapters.

Chapter 6: Markov Chains with Two States

Finally after 5 chapters, a reader gets to see Gibbs sampling procedure. The chapter starts off by introducing a Markov chain, a particular kind of stochastic process that allows for the possibility of a limited dependence amongst a set of random variables. Basic terminology is introduced like state space, transition matrix, homogeneity etc. The book is more a “DO” book where you are expected to understand stuff by coding up things. An example is shown where a sample R code is used to show the long run frequency of states in a simple 2 state Markov chain. acf plots are used as an exploratory tool to test out the rapidity of convergence of the Markov chain. Transition matrices are then introduced to show the ease of computation by looking at problems from a linear algebra perspective. The r step transition matrix boils down to multiplication of the transition matrix r times. Subsequently, the limiting behavior of the chain is shown. One crucial point that these examples bring out is that the rate of convergence of powers of transition matrix is not the same thing as the rate of convergence of the chain. The examples make it very clear that the transition matrix might converge very quickly but the chain might take a very long time to converge, and vice-versa. The last section of this chapter introduces Gibbs sampling where a set of conditional distributions are used to simulate the Markov chain. It is amply clear from the simple example mentioned in the chapter that it is difficult to simulate values from just one conditional distribution. The Gibbs sampling algo is meant to address this situation where the chain moves from one conditional distribution to another in a systematic manner so that the resulting Markov chain, after the initial burn out period, converges to the limiting distribution.

Chapter 7: Example of Markov Chains with Larger State Spaces

Personally, the main reason for going over this book was to understand the content in this chapter. I was looking for some simple examples to understand and internalize the core logic of Metropolis algo, Metropolis-Hastings algo and Gibbs Sampling algo and this chapter was perfect fit for my requirement. The chapter starts off with expanding on the state space of the markov chain, where K state, countably many and a continuum of states are considered. These types of state spaces are what we come across in real life situations. In the context of K state space markov chain, the chapter mentions 5 methods of computing the long run distribution. They are

1. Powers of the transition matrix
2. Simulation
3. Steady-state distribution
4. Explicit algebraic solution
5. Means of geometric distributions

Out of the above methods, the text uses the first two methods only. Powers of the transition matrix is obviously one of the straightforward but rather a lame way of doing stuff. Till what power do you multiply? What if the matrix converges very slowly? etc are some of the questions that one must have a clue before using this method. I guess this method is at best a diagnostic tool. The second method is based on simulation. You simulate a Kstate space markov chain and then examine the limiting behavior of the markov chain. The downside of this method is that we must be sure that it is an ergodic chain that we are simulating. The section also has an example where the long-run behavior for a non-ergodic chain is the absorption of the chain in to the absorbing states of the markov chain. The section briefly talks about countably infinite state spaces with a few examples of simple random walk with varying drifts. Finally, Continuous state spaces are covered where the transition density plays the role of transition matrix that was relevant for the discrete case. An important point illustrated from an example is that “A state space of finite length does not ensure useful long-run behavior”. The highlight of the chapter is using a simple bivariate normal variates to show the application of Metropolis Algorithm , its tweak for asymmetric jumps,i.e Metropolis-Hastings algorithm and the most important Gibbs Sampling algorithm. I think the example mentioned in the context of Gibbs sampling is probably easier to remember and internalize. Since the conditional distribution of a normal random variable given another normal random variable is again normal, one can easily apply Gibbs sampling for a bivariate normal case to see its effectiveness. Once the basic algo is internalized, one can then use it for complicated cases. The beauty of this book is that there are enough R based exercises that you get a pretty good idea of the concepts involved. Exercises for this chapter mainly helped me in understanding the following aspects

• What’s a doubly stochastic matrix? Can it be non-ergodic ?
• How to code a reflecting barrier in an efficient way?
• Assuming that there is a continuous state space Markov chain that is over a finite interval. One cannot conclude that it has a long run behavior. Using a markov chain based on beta distributions, there are 2 problems mentioned where one has a long run behavior and the other doesn’t.
• How to code Metropolis-Hastings algo efficiently ?
• How to simulate a finite markov chain efficiently?
• How to code a Gibbs sampler efficiently?

There are R codes given for each of these algos that make this chapter a very useful one.

Chapter 8: Introduction to Bayesian Estimation

The chapter talks about basic applications of Bayesian statistics. The crux of the Bayes stats is : Posterior probability is proportional to likelihood times prior probability. There are 4 examples mentioned that cover the most popular distributions:

• Beta Prior + Binomial likelihood = Beta Posterior
• Gamma Prior + Poisson likelihood = Gamma posterior
• Unknown mu - Normal prior + Normal likelihood = Normal Posterior
• Unknown sigma - Gamma for tolerance + Normal likelihood = Inverse Gamma for sigma.

Chapter 9: Using Gibbs Samplers to Compute Bayesian Posterior Distributions

In previous chapter, analytical form for posterior distribution was derived and used in the computation. However closed form solutions for posterior distributions are very difficult and more so in higher dimensional parameter space. This chapter delves in to the utility of Gibbs Sampler in computing posterior distributions. If you assume a normal prior and want to estimate mean , assuming you know the population standard deviation, then posterior distribution of mean turns out to be another normal distribution. If you assume a gamma prior for the precision and want to estimate standard deviation, assuming you know the population mean, then posterior distribution of standard deviations turns out to be inverse gamma distribution. What if you are unaware of mean and sd of the population ? This is where things become slightly complicated. Through a simple example of height differences, the chapter introduces this problem and solves it using Gibbs sampler algorithm.

Here is a hypothetical example, let’s say you are interested in knowing a variable X . You can take a random sample of 40 data points , call it xi. You are interested in knowing the mean and standard deviation of X and Y. Let’s say you observe the data as follows.( Actually I generated this data with the population mean of 40 and sd as 4, so that it will help me in comparing the effectiveness of the Gibb sampler)

Data (40 numbers) :

39 41 39 38 36 32 40 47 37 41 40 46 42 43 41 38 39 32 35 42 41 34 32 38 44 41 42 37 40 35 34 36 42 30 48 32 39 43 32 37

Lets say I assume a prior for mu as normal (30, 5) .. This is a vague prior looking at data I have assumed that the mean might be 30 and the sd for the same be 5.Lets say I assume a prior for sd^2 Inverse Gamma(5, 38) . How do I get these numbers ? Well, my vague prior for sigma is that it lies between 2 and 6 - 95% of the times, i.e sigma square lies between 4 and 36 – 95% of the times, i.e 1/ sigma square lies between 1/4 and 1/36 – 95% of the times.. I assume Gamma ( alpha, kappa) in such a way that this area under the prob distribution between 1/4 and 1/36 is 95%. A simple trial and error will give the values as 5 and 38 for the gamma distribution. This means that 1/sigma^square is gamma(5,38) and hence sigma.squared is Inverse Gamma(5, 38). Now I have my priors ready, I can use Gibbs sampling to get the posterior distribution of the random variable. Since marginals (mu | x,sigma.squared ) and (sigma.squared| x,mu) have closed forms , it is easy to actually code up the Gibbs sampler manually and see the results. I generated large # of sample paths, discarded the first 50% of the steps and obtained the posterior mean as 38.9 and posterior. sd as 4.19. As one can see the posterior mean and posterior sd come very close to the population mean and sd of 40 and 4 respectively with merely 40 data points. Once you increase the sample, the credible interval for the parameter is narrowed and more robust estimates are obtained.

Not always you manage to get closed form for partial conditionals, i.e. parameter1 given (data, parameter2,….parameter n) need not always lead to closed form. In fact most often than not, it won’t be a closed form. Here is where BUGS comes in to picture and makes our life easy. Anyways that is covered in the last chapter, so will summarize about BUGS at the relevant section of this post.

The chapter introduces another example where frequentist stats fall short in giving answers. In a two step manufacturing process, there is a need to understand whether there is variance at the batch level or whether there is variable at the individual unit level with in the batch. Using gibbs sampling, the book makes a strong case for using Bayes to get a clear understanding of the variability. This example is pretty involved and it took me 3-4 hours to understand it in its entirety. However the effort was well worth it as it gave me a better understanding of stuff. With Bayes, all you need is a good specification of priors + specification of likelihood— you don’t even have to code the partial conditionals…BUGS will do the job for you . The last chapter in this book is all about BUGS.

Chapter 10: Using Win BUGS for Bayesian Estimation

The last chapter in the book is like a wonderful dessert after a nice meal. If you want to do anything in Bayes world, you got to learn BUGS. Like any other language/ tool, there is the initial pregnancy period one needs to go through where things grow in you , you have nurture it and only then you can actually produce something real Well, my analogy might be stretched but it is something which I think is very apt. Some of the people I have met think that learning skill should be done very quickly. If they fail to get it in the first few days, they either assume that the whole thing is boring or think it is not worth it. If they do get a part of stuff correctly, they assume that they know everything about it. I had a lot of trouble teaching undergrads calculus as adjunct faculty. There were some kids who were willing to slog , but the majority were looking for instant solutions/ instant techniques to solve problems. Alas! They failed to recognize that “what comes easy never sticks”. I think I am going tangential here. Let me stick to the intent of this post, i.e summarizing the book.

This last chapter gives a very good introduction to BUGS. After going through this BUGS with the examples mentioned, one can fairly confident of testing out various models and meta-models. As such BUGS UI is not all that difficult. The syntax is very much R like and one can easily learn it. The content this chapter will make a reader curious to wrap Bugs functions with R/ Matlab/ whatever be the programming environment that he/she is comfortable. That’s when things start getting interesting. Let’s say you want to use a truncated normal prior, you cannot do it with plain vanilla BUGS. You have to look around and install a few plugins to specify truncated normal prior. Things like these can be learnt/ internalized as a consequence of this wonderful chapter. This chapter alone can be read from the book, by someone who is looking for BUGS 101 principles.

 

Takeaway:
This book is much more than an exposition of “Gibbs Sampling Method”. By systematically explaining the various algorithms that go with Bayesian estimation, it changes the way you look and formulate a statistical model in R. The tight linkage of all relevant concepts with excellent R code is the highlight of this book. Not many books manage this kind of balance between theory and practice.

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.

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”

MCMC

MCMC brilliantly explained by Iain Murray :

Markov Chain Monte Carlo

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!

Why cling ?

In most of the universities in India , statistics curriculum followed at undergraduate and graduate level, is completely outdated. The content taught, is relevant to times where there were:

• No computational capabilities - All computations had to be performed with paper and pencil.
• No graphing capabilities - Either  All graphs had to be generated with pencil, paper, and a ruler. (And complicated graphs—such as those requiring prior transformations or calculations using the
  data—were especially cumbersome.)
• Very small and very expensive data sets - Data sets were small (often not more than four to five points) and could be obtained only with great difficulty.

In other words, the situation is almost entirely the opposite of our situation today:

• Computational power that is essentially free.
• Interactive graphing and visualization capabilities on every desktop.
• Often huge amounts of data.

Then “Why do universities cling to outdated syllabi ? ” , is a question that leaves me puzzling.

Moneyball : Summary

This book by Michael Lewis delves in to the reasons behind the mysterious success of Oakland Athletics, one of the poorest teams in US baseball league . In a game where players are bought at unbelievable prices , where winning / losing is a matter of who’s got the bigger financial muscle, Oakland A’s go on to make a baseball history with rejected players and rookie players .

“Is their winning streak a result of random luck OR Is there a secret behind their winning streak ? “ , is a question that Michael Lewis tries to answer. Like a sleuth, the author investigates the system and the person behind the system , Oakland A’s manager Billy Beane.

The author traces of life of Billy Beane from his college days to the time when he becomes the manager of Oakland A’s. Billy is one of the most promising guys in his hey days and every one  believed that Billy was the superstar in the making. However Billy to everyone’s surprise doesn’t make it. He quits his job and takes up a desk job in the Oakland A’s team that is responsible to pick the talent and manage the team. Scouts, as they are called, are people who draft young and promising players in to the team. Billy in the course of time realizes that the methods followed by scouts are subjective, more gut feel based, touchy feely kind of criteria. Even some of the broad based metrics used to rate players appears vague to Billy. He sets on a mission to create metrics which truly reflect the value of the players. Billy relies on statistics, metrics to shortlist players and he does so in a manner that is similar to futures and options trader.

Much before Black-Scholes showed that the option can be replicated using a fractional unit of stock and bond, the option prices were way above the fair value. However once traders knew a rough picture of fair value, the difference was arbitraged away.  In the same way, the players belonging to the financially rich teams are overvalued in one way. Billy systematically chips away the broad metrics and tries to find ways to replicate these overvalued players with the help of new undervalued players, rookies who fit his metric criteria. So, if you think about the book from a finance perspective, Billy Bean is a classic arbitrage trader who shorts overvalued players and longs undervalued players. Infact the way in which Billy operates by selling and buying players is similar to any trading desk operation. He starts off the season with really average players and as the season proceeds, he starts evaluating the various team players available to trade , develops aggressive buy sell strategies ( of players) and creates a team which has statistically a higher chance to win. I found the book very engrossing as it is an splendid account of Billy Bean’s method of diligently creating a process that is system dependent rather than people dependent.

This book is being adapted in to a movie starring Brad Pitt as Billy Beane. It is slated to be released this September. If the movie manages to replicate at least 30-40% of the pace and content in this book, I bet the movie will be a run-away hit.

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.

Measuring the World : Summary

This book is more an historical account of two scientists (Alexander von Humboldt, Carl Friedrich Gauss) than a work of fiction.Daniel Kehlmann weaves interesting fiction around these two brilliant scientists exploring their lives, their view points, their personalities that seem to be completely opposite. Alexander von Humboldt believed that knowledge comes from exploring the world, while Gauss pretty much developed everything sitting in an observatory.

Alexander von Humboldt 1769- 1859	Carl Friedrich Gauss 1777- 1855

I will try to summarize the contrasting lives that the book that this book brings out.

Background

Humboldt came from a wealthy family and he used a part of the wealth to explore the world. In modern day parlance he never needed any VC funding. He funded his explorations all by himself. Gauss on the other hand always skirted with poverty in the process of living in the “Numbers” world. He takes up a surveying job to take care of his bread and butter. He remarries second time so that there is someone to take care of his children as he could not afford a nurse. The scientists thus have a contrasting financial background.

Belief

Humboldt’s vision was that of a unified science of earth, vegetation, animals, human beings , a science that integrated everything. He self taught every branch of science. This is really unbelievable stuff if you look at the range of contributions that Humboldt made. He self taught everything be it measurement types, instruments, instrument design, design of experiments, etc. Humboldt believed that “Whenever things were frightening, it was a good idea to measure them”. I am reminded of Robert Almgren from NYU who said a similar thing about intra-day volatility. If intra-day volatility is frightening, all the more reason to measure it.

Humboldt also knew that there is no easy way out for knowledge. An incident described in the book strikingly makes this point. Humboldt orders his servant to place two hot cupping glasses on his back so that it produces blisters on his back. He wanted to test some hypothesis about the flow of current. If a person can subject himself to such a torture to understand stuff, his motivation must have been completely different. Somewhere in the book he says,”A great deal of knowledge escapes man because he is afraid of the pain. The man who deliberately undergoes pain learns things that he didn’t. One wanted to know because one wanted to know.”

Gauss on the other hand had markedly different beliefs. For him learning was effortless. He could see things instantly and formed conjectures and theories very easily. A brief balloon ride made him realize that space was curved and parallel lines can meet based on the type of assumptions one made. For Gauss, everything was obvious. He could add up numbers from 1 to 100 with in no time. He could count primes like one counts numbers. He disparaged people who could not match his intellect which included his son too. His looked down upon people who could not think as fast as he could. He sometimes felt that “People wanted Peace. Most People wanted to eat and sleep and have other people be nice to them. What they didn’t want to do was think”. Needless to say with this kind of personality he was a loner and most of his work was result of singular brilliance. Contrast to this, Humboldt was a classic collaborator. His contributions grew by the kind of associations he formed with various scientists, philosophers, mathematicians etc.

Deliberate Practice

Humboldt spent his time practicing stuff before he could make his contribution. For about one year, he took daily measurements of the air pressure, he mapped the magnetic field, tested the air, the water, the earth and color of the sky. He practiced dismantling and reassembling every instrument until he could do it blind, standing on one leg, in rain, surrounded by a herd of fly-tormented cows. He believed that “A hill whose height remained unknown was an insult to his intelligence” and hence spent an enormous time measuring things. The measurements and the travel helped him become universalist. Direct experience through the senses of world, but measured experience made Humboldt a true quantitative researcher.

As for Gauss, he spent a lot of time silently watching the various planets, making measurements of various heavenly bodies. His deliberate practice involved sitting hours , observing and noting measurements diligently. So, this is one commonality of the two geniuses. Malcolm Gladwell’s theory of “10k hours to become a genius” seems to holding water in many cases.

Work

Humboldt begins working at mining academy. Unlike today’s mining world, a lot of new theories were put forth by mining experts. He would have learnt a lot of math/ earth science. Biology / geology were just being created around the time of Humboldt. This initial exposure to the mining world made him believe that “Whole world as a lab”. Gauss on the other hand, theorized effortlessly.

Family & Social Life

Gauss contemplated suicide incase his love was to be rejected. To his biggest surprise his love was accepted and he aborted the suicide attempt. Humboldt never married and remained a solitary individual throughout his life. Gauss had a mistress whom he loved more than his second wife. After the death of his first wife, he even considers marrying his mistress but finally doesn’t after being dissuaded by one of his friends. He remarries so that there could be someone to take care of his children as employing a nurse was expensive for him. He hated his children as none could match up his expectations. Gauss spent an enormous time seeing through his telescope in the observatory to take the measurement of the planets, heavenly bodies etc. He practically never had to move to work. His work was entirely sedentary. This is in marked contrast with Humboldt who formed instant connections with strangers who sometimes were part of his major explorations. Humboldt loved travel and hated home. He disliked his mother and never cried when mom died. Gauss on the other hand loved his mother more than anybody else in the world. For him mother came first and only then came others.

Work & Key Achievements

Gauss shot to prominence after he accurately predicted the precise date and time of the appearance of a planet. Subsequently he started studying and working in the field of astronomy.

Humboldt believed that data had to be presented well in order to get insights. He was the first person who was pivotal in making science more visual. During his explorations, he was actively charting stuff, creating new kind of maps( ISO Maps). He was first person who analyzed the world geographically and not historically ( new world vs old world kind of stuff). He was the first person to discover the Natural canal that connects Orinico and Amazon.

His work inspired Darwin who went on to create an outstanding piece of scientific literature – “Origin of Species”. Darwin described him as 'the greatest scientific traveler who ever lived'. Goethe declared that one learned more from an hour in Humboldt’s company than eight days of studying books and even Napoleon was reputed to be envious of his celebrity.

Humboldt spent 5 years in exploring the world and wrote profusely for the next 30 years. One wonders whether this prolific output is one of the main reasons for him becoming a household name by the turn of century. Most of his written text romanticizes his expedition and findings. The 30 odd volumes describing his measurements and adventures shows that he was totally passionate about his measurements, his explorations etc.

Takeaway

The book is a clever play on contrasting narrative. Humboldt firmly believed that to become the scientist, you have to travel. Gauss philosophy, on the other hand, can be understood by the following statement from the book:

Gauss observed the moment of the magnetic needle by the light of an oil lamp for hour after hour. No sound penetrated to him. Just as the balloon flight showed him what space was, at some point he would understand the restlessness in the heart of NATURE. One didn’t need to clamber up mountains or torment oneself in the jungle. Whosoever observed the needle was looking in to the interior of the world.

Despite these contrasting life styles and beliefs, both the scientists made ground breaking discoveries. This book delves in to their personalities and provides a fantastic narrative which makes it a worthwhile read.

R Graphics : Summary

 

To visualize data efficiently, one must make a transition from a state where you use point and click interfaces (a user’s view) to a state where you can code your own graphic( a developer’s view). At the outset, “User’s view” is very appealing as you can use a cutesy GUI to draw some graphs etc. However if you have discover something in the data, this “User’s view” is of no use and one needs to acquire developer skills to visualize graphics. The book is about a package “grid”, written by Prof.Paul Murrell. Well, one might think that base graphics is good enough. Why go in for grid ? Well, the power of grid lies in the fact that it gives complete control of various graphic elements, their position and their characteristics. Let’s say you have a scatterplot which is produced by base R. By using Grid package, you can rebuild the entire graphic piece by piece. This in itself is not the purpose of grid package, but it shows that any graphic that you have seen in base graphics/ lattice can be updated, created, modified at your heart’s content. This book gives a very detailed description of the grid package to create and explore various graphics.

At the outset, grid does not provide high level functions to create plots, meaning there is no specific function to create a histogram/ boxplot etc. The functions in the grid package provide the basis for creating high level graphics, ability to add sophisticated annotations to an existing graphic etc. So, the three big things that you can accomplish using grid are

• Create and control different graphical regions and coordinate systems.
• Control which graphical region and coordinate system graphical output goes into.
• Produce graphical output (lines, points, text, ...) including controlling its appearance (colour, line type, line width, ...).

If the reader is already aware of base / traditional graphics, he/she can jump to Chapter 5 to understand the grid package in depth. However the first chapters are very well written and deserve to be read.

Chapter 1: An Introduction to R graphics

R Graphics follows a “painter’s model” where a graphic is built using sequentially one component at a time. Most of the software apps that churn out graphics have a few commands to produce graphics. R gives a unique capability to add components bit by bit thus creating extremely rich graphics. Before I started using R, the only way I drew graphics was Excel, a few functions in SAS, Minitab. I learnt Ruby on Rails, mainly to build GUI quickly. I had painstakingly built a Ruby on Rails interface for a stat arb project during my research work, while one of the Phds in the group, built an awesome interface of the same using MATLAB. MATLAB’s interface building is extremely quick with the immense support of graphic libraries. I veered towards R and have been amazed at the graphic capabilities. One can safely say in the current context that, R beats Matlab in terms of sheer diverse nature of the graphs that R can churn out. The other day I was listening to Hadley Wickham’s talk at Google where he talked about the interactive nature of R which is yet to be explored by the R community. The open source nature makes it all the more powerful. Thanks to R graphics, the range of graphics that I am able to explore is definitely high. However there is still a ton of stuff that I need to explore. Ggobi is high on my priority list and someday I will have to take time to understand it.

I had never wanted to write summaries about R books but I changed my mind after reading some good summaries of a few R books on a blog. That’s when I decided to write summaries of R books that I have read / will be reading, the rationale being that the summaries might serve as a catalogue of various packages and programming hacks that are available in various books.

The first chapter of the book starts off with giving a flavour of graphs that are possible with R base package and other additional packages available such as maps , mapproj , CircStats , vcd , grid , party. Subsequently the book goes on to give a skeletal view of R graphic system.

 

The graphics engine consists of functions in the grDevices package and provides fundamental support for handling such things as colors and fonts, and graphics devices for producing output in different graphics formats.The graphics package mentioned in “Graphic Systems” refer to the base graphics package available in R. This is the default package that gets installed under a fresh R installation. There are additional packages that are add-ons for the graphics system / grid system. Lattice and ggplot2 build on grid systems and they have a ton of functionality that gives a tremendous flexibility for drawing graphics. Lattice also comes as a default package under the R installable. Infact the grid package started off with the intent of providing extensions to the lattice package(mentioned in one of the Paul Murrell’s talk)

These packages do take some time to understand/ get used to / apply in a project. Mastering base graphics package takes time. I had never ever used a painter’s model for building a graphic, so the learning curve was very steep for me. As of R2.13, there are about 87 objects in graphics which are

 

abline	contour.default	lines	plot.xy	text
arrows	coplot	lines.default	points	text.default
assocplot	curve	locator	points.default	title
axis	dotchart	matlines	polygon	xinch
Axis	erase.screen	matplot	polypath	xspline
axis.Date	filled.contour	matpoints	rasterImage	xyinch
axis.POSIXct	fourfoldplot	mosaicplot	rect	yinch
axTicks	frame	mtext	rug
barplot	grconvertX	pairs	screen
barplot.default	grconvertY	pairs.default	segments
box	grid	panel.smooth	smoothScatter
boxplot	hist	par	spineplot
boxplot.default	hist.default	persp	split.screen
boxplot.matrix	identify	pie	stars
bxp	image	piechart	stem
cdplot	image.default	plot	strheight
clip	layout	plot.default	stripchart
close.screen	layout.show	plot.design	strwidth
co.intervals	lcm	plot.new	sunflowerplot
contour	legend	plot.window	symbols

 

Combined with these 87 objects are various function arguments that go with it. So, it is quite a feat to remember most of the functions and arguments from the package. Thanks to excellent documentation for the various functions, the coder can refer to help as and when the situation demands. About the other packages, there are about 145 objects in lattice, 171 objects in grid, 554 objects in ggplot2. So, in total there are about 957 graphics related objects in the 4 packages, i.e graphics, lattice, grid and ggplot2. Well actually the functions matter not the objects, but the number of objects kind of gives an idea of the possibilities that one can explore. Working with the 87 objects in the base graphics was a steep learning curve for a newbie like me. Even though producing a simple scatterplot is shown as a starting example of using R graphics package, one has to work through, remember arguments, functions, etc and basically slog it out to draw a good visual. In the process one needs to remember the attributes for various arguments that can be used in a function. I have referred Chapter 2 and Chapter 3 umpteen number of times in my work.

Which graphic packages needs to be used? It obviously depends on the requirement. One needs to look at the broad functions of a package before deciding to learn and use it. Functions in the graphics systems and graphics packages can be broken down into three main types: high-level functions that produce complete plots; low-level functions that add further output to an existing plot; and functions for working interactively with graphical output. So, if one’s requirement is simple visual, the base graphics do superb job. However if you want to update the graphic, embellish the graphic and work on it bit by bit, lattice/ggplot2 are the packages to be used.

One of the powerful features of R graphics is the range output that one can push the graphic to, with the help of a few commands. The graphic devices that one can output an R graphic are Microsoft Windows window, Mac OS X Quartz window ,Adobe PostScript file, Adobe PDF file, LATEX PicTEX file ,XFIG file, GhostScript conversion to file ,PNG bitmap file ,JPEG bitmap file,Windows Metafile file , Windows BMP file ,GTK window (gtkDevice), Java Swing window (RJavaDevice) ,SVG file (RSvgDevice).The other fascinating aspect about R is the output from a Sweave file is a Latex file which can be easily made in to a publication ready document. Recently I stumbled on to beamer and I am fascinated by the range of output documents that beamer can produce.Beamer package has been used by statisticians for quite sometime. I am kind of ashamed of the fact that I had never used Beamer before. Need to work on it sometime soon. An additional and useful point made towards the end of the chapter is about “onefile” argument that can be used to produce output to a single file / multiple files.

Chapter 2 : Simple Usage of Traditional Graphics

The traditional graphics system provides a standard set of basic plot types. Plot() function produces scatterplots, barplot() produces barplot, hist() produces histograms , boxplot() produces boxplots, pie() produces pie charts, matplot() function is not a plot() method but a plot() with x and y as matrices, stripchart() for producing univariate scatterplot, curve() for drawing a mathematical function, stem() for stem-and-leaf plot. Basic arguments of the function that are used very often are col, lty, font, xlab, ylab, main, xlim, ylim, For a graph involving more than 2 variables, one can use contour(), filled.contour(), symbols(), image(), pairs(), stars(), mosaicplot(). For more than 2 variables there are packages like scatterplot3d, rgl , Rggobi that can be explored.

Chapter 3 : Customizing Traditional Graphics

I have referred to this chapter uncountably many times for drawing visuals from base graphics. If one restricts to using base graphics, then this chapter gives one all the nuts and bolts of using the functions and arguments in the base package. The chapter is divided in 5 sections.

The first section covers the traditional graphics model. In this context, the drawing region is divided in to three regions, outer margins, figure region, plot region. The figure region is used to draw the axes , labels, and the plot region is used to draw data points , symbols, lines etc. When you use a par(mfrow=..) or par(mfcol=..) , the inner region( region devoid of outermargins) is split in to specific rows and columns. Here is a master list of all setting for par( there are 113 of them)

xlog	cra2	font.sub	mfg3	omi4	xaxp3
ylog	crt	lab1	mfg4	pch	xaxs
adj	csi	lab2	mfrow1	pin1	xaxt
ann	cxy1	lab3	mfrow2	pin2	xpd
ask	cxy2	las	mgp1	plt1	yaxp1
bg	din1	lend	mgp2	plt2	yaxp2
bty	din2	lheight	mgp3	plt3	yaxp3
cex	err	ljoin	mkh	plt4	yaxs
cex.axis	family	lmitre	new	ps	yaxt
cex.lab	fg	lty	oma1	pty
cex.main	fig1	lwd	oma2	smo
cex.sub	fig2	mai1	oma3	srt
cin1	fig3	mai2	oma4	tck
cin2	fig4	mai3	omd1	tcl
col	fin1	mai4	omd2	usr1
col.axis	fin2	mex	omd3	usr2
col.lab	font	mfcol1	omd4	usr3
col.main	font.axis	mfcol2	omi1	usr4
col.sub	font.lab	mfg1	omi2	xaxp1
cra1	font.main	mfg2	omi3	xaxp2

Each one of the above 113 settings corresponds to some aspect of graph!. The chapter then goes on to explain the way to use colors in the visuals, color sets, lines, text, fonts, data symbols and the way they can be set for various visuals. The chapter then moves on describing layouts, one of the most important method of drawing and organizing content on an R graph. Even though par(mfrow) and par(mfc) can help you organize stuff on an R plot, the use of layout is extremely powerful as it expands the options that you have to organize stuff on an R plot

Chapter 4: Trellis Graphics: the Lattice Package

The output from a lattice function gives an object called “trellis”. Since this is a graphical object, the object can be directly updated like title, font etc. The author motivates the reader for using lattice by giving the following highlights of lattice

• The default appearance of lattice is much better than base graphics
• The lattice plot functions can be extended in several very powerful ways
• Powerful grid features are available for annotating, editing, and saving the graphics output

I think the biggest advantage of using lattice is the conditional plots. One of the things that one needs to notice while learning a new language is the terms introduced by the package. In the context of lattice, one of the most important terms that is used in Lattice package is shingle. A “shingle” is a data structure used in Trellis, and is a generalization of factors to ‘continuous’ variables. It consists of a numeric vector along with some possibly overlapping intervals. The intervals are the ‘levels’ of the shingle. One can explicitly generate the levels or used equal.count to cut a continuous variable in to various levels. The chapter then introduces trellis.par.set that is used to configure the settings such as font, col, lty, lwd , cex, col, font and pch. Another important aspect of lattice plots is arranging the plots on a panel. One can use layout argument, aspect argument and the index.cond argument to customize the layout of the graphic. One needs to play with the arguments to see the various ways to arrange the plots on the panel. The chapter ends with some basic explanation of panel functions and strip functions.

Chapter 5: Grid Graphics Model

This chapter introduces the grid graphics model in a gentle way. Instead of overwhelming the reader with too many details, the author handholds the first time user by explaining concepts gently. Grid Graphics Model has basically two types of functions. First type of functions are for drawing basic output(lines, rectangles, text) and second type of functions are used for specifying the location, colors and font. There is no predefined region for the graphical output in grid. However there is facility to define the regions(using viewport), which in my opinion is one of the most powerful features of grid graphics.

I had learnt ggplot2 before moving on to this book and hence I can relate to the author’s terminology of “Painters model”, meaning the graph needs to be built up one layer over the other. This type of graph building is very powerful as you can create a very complex graph using simple functions and then building one layer at a time.

The chapter starts off with giving a simple example of producing a scatter plot using grid package and provides some motivation to go over grid package. To produce simple scatterplot, a gamut of functions are used such as:

pushViewport, plotViewport, dataViewport, grid.points, grid.rect() grid.xaxis(), grid.yaxis(), grid.text(),grid.edit()upViewport(2), grid.rect(),downViewport()

For a first timer, learning all these functions might seem like a stretch to merely produce a scatterplot. Hence the author mentions two advantages of learning grid package, one complex plots can be produced by adding simple components one over the other, the second is the ability to edit other graphic packages like lattice and ggplot2. The two most popular graphics packages in R community are ggplot2 and lattice packages, both of which are built on grid graphics model. Hence an exposure to grid graphics will help you understand/edit/create functions from these packages. My personal experience is that, there is a learning curve to ggplot2 and one can ride this learning curve quickly if one has a good exposure of grid graphics model.

Most of the base stats options are set using par. Similarly grid uses gpar functions to set the options like fill,line type, etc. All primitives accept gpar, name and viewport as input. The options that can be used with gpar are

"fill,col,lty,lwd,cex,fontsize,lineheight,font,fontfamily,alpha,lineend, linejoin,linemitre,lex"

There are two types of graphical context here. First is explicit graphical context where one can set the above parameters to specific values and the specific grid object is displayed using explicit graphical parameters. Second type is the explicit graphical context is the default context and is invoked whenever a new graph is created.

One key feature of cex and alpha is that their effects are cumulative. Meaning if you push a grid with cex = 0.5, then you push another viewport with cex = 0.5 , then the cumulative effect is that it is multipled 0.25. Similarly if you set alpha and then push a layer with a specific color , a cumulative effect is shown on the grid. All the graphical primitive functions take vectorized input and hence a whole lot of complex graphics can be drawn using the grid.rect, grid.polygon etc.

Viewport is then introduced in the chapter when you basically get a drawing context, comprising geometric context + graphical context. A geometric context consists of a set of coordinate systems for locating and sizing output. Graphical context consists of explicit graphical parameter setting for controlling the appearance of the output.

One needs to understand certain terms in the context of grid package. Any graphic region is referred to as a “viewport”. A viewport is merely a description of the graphical region. It needs to be pushed in order to see it on a graphical device. A viewport needs to be created first and then pushed to create a geometric context upon which grid objects can be drawn. Basically you create a viewport, push the viewport and draw stuff on it. You can push any number of viewports and draw on the respective viewports. One needs to use functions like pushViewport, popViewport, upViewport, downViewport, seekViewport. pushViewport, popViewport are two functions used to push or pop the viewports. These must be distinguished from upViewport and downViewport which preserve the structure of viewports that are used in the session. The former operations do not remember the list of viewport history whereas up and down operations remember the viewport history. Grid maintains a tree of pushed viewports on each device. seekViewport might sound as a redundant option but the more you code, you realize that the seekViewport option is invaluable. You can push a viewport tree with parent and children viewport descriptions at one go and then you can use seekviewPort function repeatedly to operate on the specific viewport.

To create a viewport you need to pass the standard arguments of x coordinate, y coordinate, the width and height. One this viewport is created you can push it on to the grid.

Viewports can be smartly used to create graphics such as above using the clip attribute of pushViewport function. If you want to restrict the graphic to only the viewport you have pushed, then you have to select the clip attribute while pushing the viewport. By choosing the clip attribute as on/off/inherit, the graphical context region is altered.

Another alternative and easier way to create viewports is through layout option. Using layout option, one can push this layout viewport and then choose whichever layout that one wants to work with. An interesting feature of using layouts to structure viewports is the “null” option available to structure the graphics available.

Using the layout option, you can slice and dice the display panel. The range of options that grid package provides has motivated me to explore my own version of Billion-O-gram( from Visual Information ). The exercise was very useful in exploring various options of grid and layout functions. The chapter ends with discussion on customizing the output from lattice package.

A key takeaway from this chapter is the coordinate system that gives the user amazing number of options. First is the null option and one needs to remember that the meaning depends on the context

• unit(1, "null") inside a layout, specifies a relative width/height; outside a layout is zero.
• unit(1, "null") + unit(2, "null") inside a layout, specifies a relative width/height; outside a layout is zero.

The other units that are frequently used are "npc", "native", "inches", and "strwidth".

Chapter 6: The Grid Graphics Object Model

The chapter talks about grid objects, i.e the graphical output from grid functions. These objects are called grobs (grid objects) and gTrees( grid Trees). When you draw any grid object, the package creates a grob that you can access by a name. Once you get a handle on grob, you can update and change the content of the grob. getNames() gets you all the current grobs. The typical functions used to work on grobs are grid.get(), grid.edit(), grid.add(), grid.remove(), grid.set(). All these functions need a grob name to work with. The other type of storage mechanism is a gTree where a set of grobs are stored in a tree format. In all the above functions, one can also give the path to a grob contained in a gTree. One can use gPath to specify the element of a tree and then use grid.edit to change the respective grob. gTree can take in a viewport as an input too, in which case a viewport is pushed before gTree is pushed and then popped afterwards.

For each grid function that produces graphical output, there is a counterpart that produces a graphical object and no graphical output. The functions available are rectGrob(), textGrob(), arrowsGrob() etc.

One of the advantages of grid package is to capture the output of lattice or ggplot2 and modify the output based on your needs. For example a boxplot generated in lattice using bwplot, you can grab the tree list using grid.grab() function. You can use childNames to plot all the elements of a tree, for example in a bwplot from lattice package, the following are the grobs used :

plot_01.background

plot_01.xlab

plot_01.ticks.top.panel.1.1

plot_01.ticklabels.left.panel.1.1

plot_01.ticks.bottom.panel.1.1

plot_01.ticklabels.bottom.panel.1.1

plot_01.bwplot.box.polygon.panel.1.1

plot_01.bwplot.whisker.segments.panel.1.1

plot_01.bwplot.cap.segments.panel.1.1

plot_01.bwplot.dot.points.panel.1.1

plot_01.border.panel.1.1

You can access any grob and edit/delete the grob based on the requirement.

The last chapter of the book was fairly advanced for me. It talks about using the grid package to produce new graphic functions. Will come back to this chapter at a later date.

Takeaway :

The book gives in-depth knowledge on grid package, that forms the basis for packages like lattice and ggplot2. Once you understand the principles behind grid, you can easily modify/edit/annotate output from other packages. So in that sense this book gives the tools to tweak the regular output.

2009 KDD Cup entry – Model Description

Key Steps :

1. Did not use R for data import operation - Used SPSS to read the data
2. Feature Selection - Used R in this step
3. Data Cleaning - Treatment of Categorical variables was a problem

Software used : SAS + R

Techniques used :  Gradient Boosting machine(gbm package)

Rationale :

• Handling of missing values
• Robustness against extreme values
• Handling categorical and continous variables
• Models interaction between predictors
• Can model nonlinear dependencies

Fitting Time :  Couple of hours on a desktop

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.

Is Twitter Prediction Model Flawed ?

 

Yes , says this blog : Sour Grapes: Seven Reasons Why “That” Twitter Prediction Model is Cooked

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.

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.

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.

Image Compression & SVD

Image compression is a billion dollar industry. An optimal way to store and retrieve image data storage is the key. Though there are multiple algorithms that are usually used , one such algorithm that has found wide spread popularity is SVD( Singular Value Decomposition).

To explain SVD in simple words, let’s take an image

 

For illustration purpose, I have deliberately chosen two colors.  Now let’s say you want to store this data. One way is to store in a matrix. Lets say that the above image can be fit in a 15 by 40 matrix with each cell carrying either a white or a black colour. Now if you were to store the above data in a matrix , it will be a whole lot of 0’s to represent black color and sparse 1’s to represent white color. Most of the images that we come across are of the same pattern. If you represent them in a data matrix , it will turn out to be a sparse matrix, meaning a matrix with whole lot of 0’s as its elements. Now if you want to store the above data, you will be storing 15*40 = 600 numbers.  It might not sound a lot but if you pick up an image from the real world, the image might have 512 pixels in each row and 256 pixels in each column, thus having massive amount of data (2 power 17 entries). The example that I have chosen is for mere illustration purpose but the principle is applicable to any massive image data matrix too.

One needs an effective way of storing data than the naive m * n ( row times column) data points. SVD provides a technique to do so. Well, in simple words, SVD breaks the data matrix in to sets of rank 1 matrices . The image quality improves as you consider more and more rank 1 matrices. Each rank one matrix needs a storage of m+n data points , meaning in the above case , 15+ 40 = 55 data points.

So, the more rank 1 matrices you want to use, the better the clarity of the picture. The beauty of this method is that , for sparse matrices, a few rank1 matrices usually do a  good job of representing the image.

If I were to do SVD of the above matrix (15 rows*40 columns )and choose let’s say the first three rank 1 matrices, the image would look like this

 
Not good.Image looks very blurred.Let’s consider the first 6 rank 1 matrices ?

 
Looks better. What if we consider the first 8 rank 1 matrices ?

Looks much better. You can stop here OR based on the requirement, you can include a few more to get

 

At this stage, you have retrieved the image with total clarity and at the same time reduced the data storage for the image by a LOT. So, basically instead of storing 600 data points, depending upon the context, one can store far lesser data points and regenerate the image accordingly.

SVD has widespread applications in cryptography too. BTW, SVD is a crucial piece in Google’s page rank algorithm.

My particular interest in SVD stems from the fact that it is an incredibly useful tool in statistics. There are multiple areas where one can use SVD. But let me mention one of the most commonly known area, linear regression. If you have a linear model Xb = Y , the solution to b has a term (X*X) inverse. You cannot find X*X inverse by the usual methods as it is numerically very unstable. One uses SVD to get around these numerical issues and quickly gets to know the linear model coefficients.  Recently I came across an intra day arb model where SVD is heavily used.

An SVD trivia – Netflix $1 million dollar prize for improving their recommendation algo , had seen many participants using SVD to improve their algo results.

Optimize Travel Search

Via LANYRD

In this brief video, Jonathan Seidman and Ramesh Venkataramiah discuss the use of Hadoob, Hive for doing analytics on 500 GB /day data that gets generated via Orbitz.

A website like Orbitz generates millions of searches each day. Storing and processing the ever-growing volumes of data generated by all of those searches becomes prohibitive though traditional systems such as relational databases. This presentation details how Orbitz is using new tools such as Hadoop and Hive to meet these challenges. We’ll discuss how Hadoop and Hive are being used to analyze search data in order to optimize the products shown to users and detect trends in search keywords. This includes such tasks as using Hadoop to extract and transform data, and using Hive to perform statistical analysis on that data.

Can a similar setup be used to analyze high frequency trading data ? Looks like a possibility.

ColorBrewer

Visualization of data is one of the key components of analysis. The better the visual, the better the insight in to the data patterns. “Color” in a graphic is one of the key elements and in this aspect, Cartography provides valuable lessons.

Via Colorbrewer :
                   Different Schemes of colouring can be used based on the data requirements :

1. Sequential schemes are suited to ordered data that progress from low to high. Lightness steps dominate the look of these schemes, with light colors for low data values to dark colors for high data values.
2. Diverging schemes put equal emphasis on mid-range critical values and extremes at both ends of the data range. The critical class or break in the middle of the legend is emphasized with light colors and low and high extremes are emphasized with dark colors that have contrasting hues.
3. Qualitative schemes do not imply magnitude differences between legend classes, and hues are used to create the primary visual differences between classes. Qualitative schemes are best suited to representing nominal or categorical data.

 

Once you look closely at these principles, you will realize that these coloring principles can be put to use for any of the stats graph.

 

 

Dating a Statistician -:)

Via xkcd :

The Quants : Summary

The book starts off with the story of Ed Thorp, the father of stat arb. Priceton / Newport partners is a fund that is well known in the quant world that has a great track record of beating the market for decades and the quant behind it is Ed Thorp. If you want to read the entire story with bells and whistles about Ed Thorp,  Fortune’s formula is a better book. This book though quickly summarizes the success story of Thorpe-Shannon combination and goes on to tell a nice story of four quants who strike it big in the hedge fund world.  The author traces the lives of  Peter Muller(Morgan Stanley PDT) , Ken Griffin( Citadel), Cliff Asness (AQR) and Boaz Weinstein(Saba) from their childhood, to their trading careers, their eccentricities, their hiring decisions , their winning and losing trades.  Besides these four quants, there are host of people / funds mentioned in the book

Medallion’s fund performance is something that is revered by every one at Wall Street . 40% returns for three decades is god level performance in the quant fund space. Author traces the story of the fund from the inception to its performance over the years. Renaissance is always considered a mysterious place for many reasons. They hire scientists from fields like Voice Recognition space, Crypto analysis etc. Like google, they have 40 hours dedicated to research time that has no restrictions.  I have never heard of any quant fund that has this policy of “unstructured time” until I read this book.  In all likelihood all their breakthrough work might be a result of this “unstructured time” of all 90 odd Phds in the  company. One of my professors used to say that there are dedicated Phds at Medallion who focus just on “Data Missing Treatment analysis”. They write tons of algos to treat the missing data.Obviously very little is known about this fund and one can only read between the lines of the statements in the press that , as a fund, they believe that asset values follow CLOSE to random walk(not a complete random walk)  and it is their endeavour to get that little edge out of understanding it and subsequently using that understanding to spread it across multiple bets.  If ever Jim Simons retires and decides to write a book about his fund , I guess it will be a fascinating read! . Till then like a Hidden Markov Model, one can only form mental models of what they are up to :)

---

Chapter 10 of the book titled “August Factor”, is what I liked the most. It gives a hollywodesque spin to the Liquidity squeeze that happened in the week of Aug 6 2007. Khandani and Lo have written a superb analysis on the same. However author narrates it in a story format sans the numbers and the math. You forget for a moment that you are reading a book about finance and you are pulled in to a thriller ride, a ride , though , which cost the quant funds millions of dollars. Aaron Brown feels that quant community will remember Aug 07 more than the subprime crisis as the week showed that all models can go wrong. Every Quant fund on the street lost money because of massive deleveraging and Short Squeeze. 

---

A recount of the Lehmann’s fall, AIG’s bailout is given in the context of Andrew Lo’s Doomsday clock. Lo and Khandani wrote an insightful article analyzing the liquidity crisis in Aug 07 and  talked about the hedge fund industry and the doomsday clock. Here is in essence what they are saying :

In the aftermath of the Second World War, a group of socially minded physicists joined to form the Bulletin of Atomic Scientists to raise public awareness of the potential for nuclear holocaust. To illustrate their current assessment of the appropriate state of alarm, they published a “Doomsday Clock” indicating how close we are to “midnight”, i.e., nuclear annihilation. Originally set at 7 minutes to midnight in 1947, the clock has changed from time to time as we have moved closer to (2 minutes to midnight in 1953) or farther from (17 minutes to midnight in 1993) the brink of nuclear disaster. If we were to develop a Doomsday Clock for the hedge-fund industry’s impact on the global nancial system, calibrated to 5 minutes to midnight in August 1998, and 15 minutes to midnight in January 1999, then our current outlook for the state of systemic risk in the hedge-fund industry is about 11:51pm.

Despite the warning, Crisis happened!

---

The author cites Derman, Thorpe , Wilmott , Mandelbrot, Taleb to make a point that “ We are modeling humans and not machines” and hence takes a dig at the quasi-physics approach taken for quant modeling. Despite, the  warnings from Mandelbrot, Wilmott and others much before the crisis, the faulty models were rampant. Why ? There is no single answer for it.  The following manifesto was in circulation well before the crisis, but it did not stop quants from using faulty models!

The Modelers' 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.

---

The book talks about the performance of AQR(Cliff Asness) ,Citadel( Ken Griffin) and Saba(Boaz Weinstein) during the crisis and  hints at the black swan effect on any fund’s performance. Citadel has never  lost money except for 1995 in its two decades of existence and in 2008 , it was on the verge of collapse in just one year. AQR lost half its war chest ($20B) in 2008 betting on value centric models, treasuries, currencies, real estate etc. Saba which controlled $30 B was shut down post crisis. The damage is really mind-blowing stuff. By providing the gory details of the crisis , you can’t help but notice that the most dangerous word in QUANT’s career is “UNPRECEDENTED”. If there are regimes when historical data and patterns are not an indicator of the way things function, then basically a quant should be completely ignored.

So, who did well and survived the crisis. Renaissance for one was top notch in performance.Medallion’s fund gained 80% in 2008 ! It’s a jaw dropping number if you think of the panic and investors behaviour in the market. In Jim Simons words

Our approach is driven by my background as a mathematician. We manage funds whose trading is determined by mathematical formulas….We operate only in highly liquid publicly traded securities, meaning we don’t trade in credit default swaps or CDOs. Our trading models tend to be contrarian , buying  stocks recently out of favor and selling those recently in favor.

Renaissance was also free of the theoretical baggage of modern portfolio theory or EMH/CAPM. Rather the fund was run like a machine, a scientific experiment and the only thing that mattered was whether a strategy worked or not – whether it made money. In the end, THE TRUTH wasn’t whether the market was efficient or in equilibrium. THE TRUTH was very simple, and remorseless as he driving force of any Wall Street Banker, “ Did you make money or not ? Nothing else mattered

Fund floated by Black swan’s Taleb , Universa investments itself became a black swan as the AUM increased from $300M in Jan 07, to $6B by Mid 2009. High frequency trading outfits did exceptionally well. High frequency outfits made a lot of money like Tactical trading (arm of Citadel).

Somehow reading about the people who made/lost money makes me think that, one must rely on math and non-parametric assumption free statistics than finance theory laden models. When I hear the word factor models from any person pitching his model, the one thing that flashes in my mind is “ The ton of assumptions that factor models make” and I start wondering , Are they really valid ?, If you have back tested and it works for x years, will it work next year ? Who decides factors ? For a handful of assets, the covariance matrix might be stable but when you taking the entire market of securities which pass some market cap filter or liquidity filter, are the covariance matrices stable ? have you taken fat tails distributions in your model ?..The more I think of it, the more I realize that factor models are a CONVENIENT form of summarizing the market returns. But CONVENIENCE  need not equate to CASH FLOW.

---

The book ends with a note on dark pools, an off-regulatory limit exchange which almost every fund manager uses it in US. Quite contrary to the title of the book which hints to a casual onlooker that,  Quant is on a decline, the book ends with this statement

Just look : exotic leveraged vehicles, marketed to the masses worldwide, hedge funds gaming their returns, lightning fast computerized trading robots, predatory ninja algorithms hunting liquidity in dark pools…Here come the QUANTS !

---

Takeaway :

It gives a sneak peak in to the lives of Peter Muller(Morgan Stanley PDT) , Ken Griffin( Citadel), Cliff Asness (AQR) and Boaz Weinstein(Saba),  Ed Thorp( Princeton/ Newport Partners) , Jim Simons( Renaissance).

It leaves an indelible impression on the readers mind that , whether one believes or not, Quant is a reality in the market place and all exchanges are morphing in to giant supercomputers.  Here is a under-construction pic of the NYSE data centre at Mahwah, New Jersey.

 

NYSE Data Centre Mahwah, NJ

The Facility is as BIG as 7 FOOTBALL Fields

Whatever be the opinions floating around quant, HighFreq Trading , mediocristan / extremistan , fat tails, distribution free models……, one thing looks certain….We are going to see  money making machines AND massive blowups at a much smaller time scale. The next LTCM / Paulson & Co type fund would lose or make tons of money , may be in just 5 minutes!