## Posts

Showing posts from 2015

### A Neat Random Walk Problem

As many of the people that read this blog probably know, I enjoy inventing math problems, especially problems that are probabilistic in nature, and then working out the math to solve that problem. In this blog post, I will introduce one problem that I solved that I think is particularly elegant: You are randomly walking along the x-axis starting at $x=0$. When you are at $x = n$, you move to $x = n-1$ with probability $p = \frac{n}{n+1}$ and to $x = n+1$ with probability $p = \frac{1}{n+1}$. What is the expected number of steps until you return to $x = 0$ for the first time? This problem differs from standard random walk problems because the probability of moving left and right along the x-axis depends on your current location. In this problem, there is a force that is pulling you towards $x = 0$, and the further away you get, the more of an effect this force has on you. Show/Hide Solution So how do we go about solving this problem? When

### Modeling Baseball At Bats

This semester in my mathematics capstone course, students had the chance to develop mathematical models to describe real world research problems.  I took this as an opportunity to research and develop probabilistic models that can be used to predict the outcome distribution of a baseball at bat.  My hope was that I could apply my findings from this research project to my side project of Beat the Streak.  I learned a lot about mathematical modeling in this class, and explored a variety of techniques for making predictions about baseball at bats.  At the end of the class, we wrote a report that introduces the models we came up with, and compares the quality of the predictions they produce.  I have made this report available here .

### Evaluating the Sum of a Geometric Sequence

This is a short blog post that shows you an easy and intuitive way to derive the formula for the summation of an infinite geometric sequence. Let $0 \leq p < 1$, and let $a$ be some constant; then we wish to find the value of $x$ such that $$x = \sum_{k=0}^\infty a p^k$$ Writing out the first few terms of the summation, we get: $$x = a + a p + a p^2 + a p^3 + \dots$$ Rewriting the equation by factoring out a $p$ from every term except the first, we get: $$x = a + p (a + a p + a p^2 + \dots)$$ Notice that the expression in parenthesis is exactly how $x$ is defined. Replacing the expression with $x$ leaves us with: $$x = a + p x$$ Solving the equation for $x$ yields $$x = \frac{a}{1-p}$$ Just remember this simple derivation and you will never have to look up the formula for evaluating the sum of an infinite geometric sequence ever again!

### Beat the Streak: Day Three

In order to maximize your probability of beating the streak, you should (1) predict the probability that a batter will get a hit in a given game given the game parameters and (2) determine if it's worthwhile to risk your current streak in order to possibly improve it by 1 or 2 games. In this blog post, I outline my solution to (2). In previous blog posts, I've hinted at what I do to solve (1) and will continue that discussion in a later blog post. Motivation When your current streak is short, the optimal strategy is to pick the best player every day, regardless of how likely their probability of getting a hit is (to a certain extent). However, as your streak grows, you have an important decision to consider: is it better to pick the best player today and possibly lose your current streak, or skip picking a player and instead maintain your current streak. Naturally, this decision should be guided by the players probability of getting a hit, as well as the distribution of the

### 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

### Interpolation Search Explained

If you have taken an introductory computer science course, you've probably seen the binary search algorithm - an algorithm to efficiently find the index of an item in a sorted array, if it exists. You might not have heard of interpolation search, however. Interpolation search is an alternative to binary search that utilizes information about the underlying distribution of data to be searched. By using this additional information, interpolation search can be as fast as $O(log(log(n)))$, where $n$ is the size of the array. In this post I am going to talk about two implementations of interpolation search. First, I will discuss the algorithm as described on Wikepedia, then I will describe my own version of the algorithm that has a better worst case time complexity than the first and performs better in practice than the traditional binary search and interpolation search algorithms. The Basic Idea Interpolation search models how humans search a dictionary better than a binary search,

### An Efficient Communication Scheme

In this blog post, I'll be talking about an efficient communication scheme that can be leveraged in parallel programs for broadcast or reduce operations.  The idea is very simple, but I thought it was pretty cool when I learned it, so I thought I would pass along the information to you.  Let's abstract away the parallel programming aspect and analyze the following question: You have a message that you want to share with a large group of people, but you can only share the message with one person at a time. How should you distribute this message? Setting up the Problem To clear up some possible ambiguities, I want to emphasize that it takes one time step to share a message regardless of who you share it with, and anybody can share the message with anybody else (granted they've received it first).  I will identify each person in the group by a unique integer in ${0,1,...,n}$, and I will assign myself the id $0$. This is similar to how we might structure a distributed prog

### Generating Random Numbers from Arbitrary Distributions

Generating random numbers is an important aspect of programming, and just about every programming language offers some source of (pseudo) randomness, usually in the form of a uniform distribution. For example, java has a builtin function, <code class="java">Math.random()</code> that returns a random floating point number in the range $[0,1)$. In some instances, we would like to have random numbers coming from a different distribution, but most programming languages don't offer this functionality (except very specialized languages such as R). In the rest of this blog post, I am going to explain how you can use a uniformly distributed random number to generate a number from some other distribution. Special Case: The Normal Distribution If you would like to get numbers from a binomial distribution, or are willing to accept an approximation for the normal distribution in favor of simplicity, then you may want to use this technique. If you add together some num

### Triangles Containing the Origin

You may have found this site by searching for information regarding Project Euler Problem 184. This is not a solution to that problem. In fact, it really bothers me when I find people who post their solutions to these problems online, especially the higher level ones. In this blog post, I talk about a simple problem from probability that was motivated from this Project Euler problem, but the solution to this problem is not likely to help you solve that one. Pick three points uniformly at random along the circumference of a unit circle centered at the origin. What is the probability that the triangle connecting these three points contains the origin? Like I said, this problem is not as difficult as the problems that I usually write about, but I decided to write a blog post about it for two main reasons: I wanted to create the animation/simulation for this problem I eventually want to extend this problem to explore all convex polygons instead of just triangles (which is a more diff