Showing posts from October, 2014

A Challenge for my Readers!

In this blog post, I present a very interesting math problem that I came up with while pondering random walk problems. You are walking along the x axis and you start at $x=0$. At each time step you move to $x+1$ with probability $ \frac{1}{1+x} $ and to $ x-1 $ with probability $ \frac{x}{x+1} $.  What is the expected number of steps until you return to $ 0 $ for the first time? What makes this problem harder than a typical random walk problem is that the probability of moving to $x+1$ vs $x-1$ is not fixed -- it changes based on your position. That being said, the typical counting methods for solving problems of this type do not apply. There is a clever and fascinating solution that doesn't require too much advanced knowledge, but I will leave it to you to think about this problem.

Thinking Like a { Computer Scientist, Mathematician }

As a Computer Science and Mathematics double major, a lot of the things I learn in my math classes I can apply in my computer science classes (and vice versa). But there's also a lot of material that I learn in math that's way different than anything I'd ever do in computer science (and vice versa). I've also met a lot of different people in each subject. In this post, I will talk about a recent experience I had when I posed the same question to math students and computer science students. Mathematicians and Computer Scientists think differently, and in some cases they approach problems differently. I will also talk about why some Mathematicians should broaden their horizons and explore the world of computing. Each week I send out weekly challenge problems on behalf of ACM (and Math Club for that matter). I usually think up and solve these problems myself so the answers don't necessarily exist out on the internet. For last weeks ACM weekly challenge, the problem

A Fun Puzzle from Probability

Here is a problem that came up a few days ago and I'm still thinking about: There is an amoebae in a box. At each time step, it either multiplies in 2, multiplies in 3, stays the same, or dies - all with equal probability. What is the probability that eventually, all the amoebae die out? Show/Hide Solution Solution One can quickly see that the probability is at least $\frac{1}{4}$ because there is a $\frac{1}{4}$ chance of dying on the first time step. Similarly, you could die on the first time step ($\frac{1}{4}$), stay the same then die ($\frac{1}{4^2}$), etc. Thus, the probability of eventual extinction is at least $\sum_{n=1}^{\infty} \frac{1}{4^n}$. Unfortunately, this strategy leads to a dead end. Instead, I use a clever interpretation of the problem that leads to a very simple and elegant solution. My key insight came from seeing an infinite continued fraction problem, which uses a simple technique to define the value of the continued fraction in terms of itself. T