> I hate the term “dynamic programming”. It sounds so cool, but then you find out that all it means is “I memoized the results in a table”. Ho hum.
The Wikipedia section on the history of the term[1] is quite amusing. Basically, the guy who invented the idea picked the name that was most likely to get his research grant applications approved.
Really Bellman did nothing new when he used the word programming as that had already been used in the phrase "linear programming" for one or two decades. Mathematical programming was the optimization of military programs.
Let c_{n,m} be the expectation value of the number of remaining half pills starting from n whole pills and m half pills. Then we get the following recursion:
c_{n,m}=n/(n+m) c_{n-1,m+1} + m/(n+m) c_{n,m-1}
Boundary condition: c_{0,m} = m
After some experimenting I got the following closed form solution: c_{n,m}=H_n+m/(n+1) where H_n=sum_{i=1}^n 1/i (nth harmonic number). This can be shown by induction. We want to know what happens if we start from n whole pills and 0 half pills: c_{n,0} = H_n. Indeed, they are the harmonic numbers.
If you have a half pill and k - 1 whole pills remaining, then because we stop once all the whole pills are broken, then thinking about the order in which the pills will get picked next/again, by symmetry the probability that the half pill will remain at the end (i.e. be the last one to get picked next/again) is 1 / k.
If p_k is the k'th last pill broken (so p_n is the first pill), then because at the point p_k is broken there are k - 1 whole pills remaining we get
E[N] = sum_k (probability p_k has half a pill remaining at the end) = sum_k (1 / k)
Standupmaths on YouTube recently produced a video called the "frog problem", which also reduces to the harmonic numbers. I believe it's for kind of the same reasons, though it's harder to see quite why.
Bingo. I read the code to be sure there wasn't a factor to model this. The answer should depend on the relative probability of choosing a whole pill or a half pill. The code assumes equal odds, with no state dependence on the remaining ratio.
I was startled by the formula, though. It's the same as the Gilbert-Shannon-Reeds model for card shuffling, where the probability of a card falling from each packet scales to the number of cards left in each packet. (I wrote the "seven shuffles" paper with Persi Diaconis.)
I played with this exact pill bottle problem as Mark last year but had a different interest. It turns out the triangular numbers pop out of the same problem. Thanks, OEIS.
> I hate the term “dynamic programming”. It sounds so cool, but then you find out that all it means is “I memoized the results in a table”. Ho hum.
Wrong. Plenty of memoized functions aren't "dynamic programming" and it's not always obvious whether or how a given problem can be decomposed as recursive sub-problems. Not "ho hum" at all.
I know another problem with the same solution. Imagine a ferry with n cars that drive on land onto a narrow road that prevents passing, and each car has a unique random preferred speed > 0. The cars start driving and starts clumping together in groups. The expected number of groups is the harmonic series up to n.
If anyone is interested in a proof, I think this works:
The slowest car will with probability 1 be the first car in its own clump. The second slowest car will be the first car in a clump if it is in front of the slowest car. This happens with a probability of 1/2. The third slowest car will form a clump without the second and first slowest cars if it is in front of both of them, which will happen with probability 1/3. The fastest car will only form its own clump if it's the first car, which will happen with probability 1/n.
So the total number of clumps will be 1 + 1/2 + 1/3 + ... + 1/n
It's a very nice proof. Note that this implicitly relies on a great trick used in probability theory, namely that E(X_1 + X_2 + ... + X_n) = E(X_1) + E(X_2) + ... + E(X_n), even if the random variables are not independent. In this specific case X_i = "the number of clumps where the ith slowest car is in front of" which is either 0 or 1.
Sorry, I never have been good at titles. I think the addiction-struggling post, if it existed, would just be sad and boring.
But if you hang around you'll probably start to hear about the gradual disintegration of my body as I begin my slide into old age and eventually death. So you have that to look forward to at least!
this reminds me of a system to eat M&M candies. Take two M&M and place between fingers, squash. One will break, one will crack. Eat the cracked one. Winner moves on to next round. Repeat until bag is empty. Send final winner back to Mars company for breeding purposes.
The Wikipedia section on the history of the term[1] is quite amusing. Basically, the guy who invented the idea picked the name that was most likely to get his research grant applications approved.
[1]: https://en.wikipedia.org/wiki/Dynamic_programming#History