`RcppDynProg`

is a new `Rcpp`

based `R`

package that implements simple, but powerful, table-based dynamic programming. This package can be used to optimally solve the minimum cost partition into intervals problem (described below) and is useful in building piecewise estimates of functions (shown in this note).

# Tag: Dynamic Programming

## A dynamic programming solution to A/B test design

Our last article on A/B testing described the scope of the realistic circumstances of A/B testing in practice and gave links to different standard solutions. In this article we will be take an idealized specific situation allowing us to show a particularly beautiful solution to one very special type of A/B test.

For this article we are assigning two different advertising message to our potential customers. The first message, called “A”, we have been using a long time, and we have a very good estimate at what rate it generates sales (we are going to assume all sales are for exactly $1, so all we are trying to estimate rates or probabilities). We have a new proposed advertising message, called “B”, and we wish to know does B convert traffic to sales at a higher rate than A?

We are assuming:

- We know exact rate of A events.
- We know exactly how long we are going to be in this business (how many potential customers we will ever attempt to message, or the total number of events we will ever process).
- The goal is to maximize expected revenue over the lifetime of the project.

As we wrote in our previous article: in practice you usually do not know the answers to the above questions. There is always uncertainty in the value of the A-group, you never know how long you are going to run the business (in terms of events or in terms of time, and you would also want to time-discount any far future revenue), and often you value things other than revenue (valuing knowing if B is greater than A, or even maximizing risk adjusted returns instead of gross returns). This represents severe idealization of the A/B testing problem, one that will let us solve the problem exactly using fairly simple R code. The solution comes from the theory of binomial option pricing (which is in turn related to Pascal’s triangle).

Yang Hui (ca. 1238–1298) (Pascal’s) triangle, as depicted by the Chinese using rod numerals.

For this “statistics as it should be” (in partnership with Revolution Analytics) article let us work the problem (using R) pretending things are this simple. Continue reading A dynamic programming solution to A/B test design

## Unspeakable bets: take small steps

I was watching my cousins play Unspeakable Words over Christmas break and got interested in the end game. The game starts out as a spell a word from cards and then bet some points game, but in the end (when you are down to one marker) it becomes a pure betting game. In this article we analyze an idealized form of the pure betting end game. Continue reading Unspeakable bets: take small steps

## Lanchester’s Law: why small advantages swell in StarCraft

StarCraft and StarCraft II are very popular real time strategy games. The core of these games is the mining of resources, and conversion of those resources into specialized military units. Idealized fighting and predator/prey relations have long been analyzed in terms of differential equations. We use the differential equation formalism (in particular Lanchester’s equations of 1916) to discuss expected game outcomes and how, in principle, one can derive a StarCraft strategy that complements search, simulation or more classic artificial intelligence techniques.

Continue reading Lanchester’s Law: why small advantages swell in StarCraft

## The Local to Global Principle

We describe the “the local to global principle.” It is a principle used to break algorithmic problem solving into two distinct phases (local criticism followed by global solution) and is an aid both in the design and in the application of algorithms. Instead of giving a formal definition of the principle we quickly define it and discuss a few examples and methods. We have produced both a stand-alone PDF (more legible) and a HTML/blog form (more skimable).

Continue reading The Local to Global Principle

## Betting Best-Of Series

Betting Best of Series is a new expository paper describing the mathematics involved in betting on something like the United States’ Major League Baseball World Series. It isn’t so much about baseball as about demonstrating some of the really great ideas from mathematical finance in a simplified setting. This sort analysis is the “secret sauce” in a lot of financial models and I trying to share the thrilling feeling of working with these techniques in an elementary essay (with diagrams). Continue reading Betting Best-Of Series

## Paper on stock trading

author: John Mount

I have finally written up and released a paper in PDF: Automatic Generation and Testing of Trades describing a lot of the statistics and optimization methods used when I was technical trading on a Banc of America Securities proprietary program trading desk. It was a very exciting time.