Taking the Long Way Home August 14th, 2009
Patrick Stein

I was pondering non-deterministic, shareware nagging. Suppose that every time you performed a particular function, I wanted to randomly decide whether to nag you this time or not. Suppose further that I’d prefer not to have to keep track of how long it’s been since I last nagged you, but I’d still like you to be nagged about once every n times. Naïvely, one would expect that if I just chose a random number uniformly from the range zero to one and nag if the number is less than \frac{1}{n}, this would do the trick. You would expect that if you rolled an n-sided die each time, that you’d roll a one about every n-th time.

Me, I’ve learned to never trust my naïve intuition when it comes to probability questions. Well, it turns out that the naïve answer is perfectly correct in this case. Here is the epic journey I took to get there though.

Here’s what I wanted. I wanted to know the probability p needed so the expected number of trials until the first success is some number n given that each trial is independent and is successful p proportion of the time. Suppose for a moment that I decided I am going to roll a six-sided die until I get a one. What is the expected number of times that I need to roll that die to get my first one? What I want here is the inverse problem. How many sides should my die be if I want it to take n tries (on average) to get my first one?

tree In the picture at the right, each circle represents a trial. Each square represents a success. What I am looking for is what value should I pick for p so that if you go left p proportion of the time and go right the other (1-p) proportion of the time, you will expect to hit n circles along your descent. You could, if very unlucky (or lucky in this case since I’m going to nag you) go forever to the right and never get to a rectangle. So, already, we’re expecting an infinite sum.

Indeed, the expected number of circles you cross in a random descent of this tree is E(p) = \sum_{k=1}^{\infty} k \cdot p \cdot (1 - p)^{k-1}. Massaging this a little, we can get it into a simpler form: E(p) = \frac{p}{1-p} \sum_{k=1}^{\infty} k \cdot (1 - p)^k.

That infinite series is pretty nasty looking though. So, we whip out a handy table of infinite series and see that:

\sum_{k=1}^{\infty} k^m q^k = \frac{1}{(1-q)^{m+1}} \sum_{k=0}^m \left[ \sum_{j=0}^{k+1} (-1)^j { {m+1} \choose j } (k - j + 1)^m \right] q^{m-k}

Fortunately, in our case, m = 1. As such, we can reduce this significantly:
\frac{1}{(1-q)^2} \sum_{k=0}^1 \left[ \sum_{j=0}^{k+1} (-1)^j { 2 \choose j } (k - j + 1) \right] q^{1-k}

\frac{1}{(1-q)^2} \left\{ \left[ \sum_{j=0}^1 (-1)^j { 2 \choose j } (1 - j) \right] q + \left[ \sum_{j=0}^2 (-1)^j { 2 \choose j } (2 - j) \right] \right\}

Now, we note that when j = 2, the last summand is zero. So, \sum_{j=0}^2 (-1)^j { 2 \choose j } (2 - j) = \sum_{j=0}^1 (-1)^j {2 \choose j } (2 - j). As such, we can combine our two summations into one:
\frac{1}{(1-q)^2} \sum_{j=0}^1 (-1)^j { 2 \choose j } \left[ (1 - j) q + (2 - j) \right]

And, since j is only going from zero to one, it’s easy enough to write out both terms of the summation:
\frac{1}{(1-q)^2} \left\{ { 2 \choose 0 } \left[ q + 2 \right] - { 2 \choose 1 } \right\}

\frac{1}{(1-q)^2} \left\{ q + 2 - 2 \right\}

\sum_{k=1}^{\infty} k q^k = \frac{q}{(1-q)^2}

Whew! Big sigh. We’re through the ugly parts. Now, in our case, q = (1-p), and the equation we were interested in was E(p) = \frac{p}{1-p} \sum_{k=1}^{\infty} k \cdot (1 - p)^k. Plugging in (1-p) for the q in our infinite series solution, we find that

E(p) = \frac{p}{1-p} \cdot \frac{1-p}{p^2} = \frac{1}{p}

Two pages of ugly, ugly algebra bears out the simple guess. Wheee! If we want E(p) = n, then we have to pick p = \frac{1}{n}. Hooray!

RSS Feeds

l