Showing posts from June, 2015

Automatically Finding Recurrence Relations from Integer Sequences

In a lot of the recreational math and computer science problems I solve, I try to derive a recurrence relation that describes the situation. These recurrence relations pop up pretty often in counting problems (how many ways can you tile a 2xn grid with 2x1 tiles?) In some cases, I am unable to derive a recurrence relation directly from the problem statement, but still suspect that there exists some recurrence relation. In these cases, I end up solving the problem usin g brute force methods for small input sizes and analyzing/extrapolating the pattern. However, when the relation is obscure, it becomes hard to find. In order to make this process easier in the future, I created a program that can automatically find recurrence relations for arbitrary integer sequences. To use it, simply type in the first few terms of a sequence you are interested in, and it will try to find a recurrence relation for that sequence. There are some constraints on the allowable inputs/outputs which I di

Beat the Streak: Day Two

With the mid way point of the MLB season fast approaching, it is starting to become apparent that I need to finish my program if I want to have any shot at compiling a respectable streak this season. In this blog post, I will talk about one formula that I am relying heavily on in my tool. This formula is based on Bill James' Log5 formula but is modified for non-binary output. In general, the Log5 formula is used to approximate the probability that team A will defeat defeat team B given each of their individual winning percentages. It can be modified to handle batter vs. pitcher matchups as well. There is no mathematically rigorous derivation of the formula, so using it in my tool is a little bit iffy to say the least. However, I think using it will yield a better approximation to batter vs. pitcher matchups than not using it. In it's simplest form, the approximate batting average of batter B against pitcher P is given by: $$ AVG_{B v P} = \frac{\frac{AVG_B \cdot AVG_P}{AVG

Non-Numeric Matrices 2

In my last blog post , I showed how matrices and matrix multiplication in particular can make sense for more than just numbers. In fact, I used a boolean matrix construct to find the connected components of a graph. In this blog post I will extend that idea to two more types of matrices: "Distance" matrices to find the shortest distances between any two nodes Path matrices to find the (shortest) list of actions that lead between any two states The first type of matrix that I will talk about is what I call a 'Distance' matrix. This is not to be confused with how distance matrices are usually defined in mathematics and computer science (pairwise distance between points). Instead, my definition is more closely related to an adjacency matrix, where connected nodes have non-zero entries (given by the weight, or distance between the nodes), and unconnected nodes have a distance of 'X' to denote that there is no edge between the nodes. Using this newly de

Non-Numeric Matrices

Matrices are a fundamental part of linear algebra, and we typically think of a matrix as a 2 dimensional array of numbers. In this post, I will show that matrices can be used in other ways too, and I will show that these new types of matrices can be used to solve real problems. Adjacency Matrix If you are already familiar with Adjacency matrices, I recommend you skip ahead to the next section; otherwise, read on! Matrices are especially important in graph theory, as they can be used to model the structure of a graph. A graph is a set of vertices and edges, and the edges indicate how the vertices are connected. Graphs can be used to model a number of real world things: the internet, social networks, road systems, etc. One common representation of a graph is an adjacency matrix: For a matrix \( A = [a_{ij}] \), \( a_{ij} = 1 \) if node i is connected to node j and \( a_{ij} = 0 \) otherwise (Note I implicitly implied there is some ordering on the nodes). One interesting prop

Beat the Streak: Day One

In 2001, released the Beat the Streak challenge : A challenge to fans to essentially beat the all time best hitting streak established by Joe DiMaggio in 1941. In that season, Joe DiMaggio had a 56 game hitting streak. The longest hitting streak by any MLB player since that is 45 games. When the challenge was first introduced, fans were asked to pick a (possibly different) player every day who they expect to get a hit. If that player earned a hit, then their streak would increase by 1. Otherwise, it would go back to 0. The first fan to reach a streak of 57 would win the grand prize. Since it's introduction in 2001, the grand prize has grown from $100,000 to $5,600,000, and a number of new features have been added to improve the odds for the fans. Yet, no one has even broken the 50 game streak barrier, let alone win the grand prize. I have been a casual beat the streak player for a few seasons, but I never really took it too seriously. Last season, I decided to use my back