Breaking Pills | Hacker News Reader

Breaking Pills

blog.plover.com

128 pointsweinzierl33 comments

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

[1]: https://en.wikipedia.org/wiki/Dynamic_programming#History

If you majored in CS at university, you probably suffered through a lot of it. It sinks in after awhile and is rather useful.

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.

A slightly more intuitive argument.

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)

Thanks for the hint! I wrote this up a little more explicitly: http://kevinkle.in/jekyll/update/2019/09/23/breaking_pills.h...

Interesting.

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.

This is the video: https://www.youtube.com/watch?v=ZLTyX4zL2Fc

I think the similarity is that you start with a pool that you deplete with a random action.

In real life, smaller particles tend to sink to the bottom of a container. So you're more likely to grab a whole pill as time goes by.

I wanted to get quarters out of a change jar and remembered exactly this. Just shook it around (lightly) until there were quarters at the top.

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.)

> The code assumes equal odds

This is stated explicitly in the problem: Each day you select a pill at random

Clearly stating that the model is unrealistic doesn't make the model realistic.

On the other hand, you always put the half pills you create on top of the pills already in there, not in a random spot in the bottle.

I find a great way to find the rule for a numeric sequence when only having a few examples is to plug it into to OEIS:

https://oeis.org/search?q=0%2C1%2C3%2C11&language=english&go...

https://oeis.org/wiki/Rational_sequences

OEIS tells us that E(n) is the harmonic numbers.

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.

https://github.com/mnp/pill-bottle

> 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 love to see a rather esoteric math problem that applies to daily life.

God knows quite a number of us split pills.

If you combine those split pills with a bottle of full ones as per the article, you are not a programmer whose code I think I would enjoy!

I do. It works fine. Sometimes you don't have to split a pill, sometimes you do :)

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.

Beautiful.

I love the internet. I posted this question 20 years ago. Got an answer right away. And even more interesting answers today. Thanks!

https://groups.google.com/forum/?hl=en#!searchin/alt.math.re...

I thought this was going to be a gritty memoir of MJD struggling with addiction, and I feel bamboozled.

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!

Does anyone else find the use of E(N) to be the expected value of a random value that is not denoted N to be confusing?

MJD, this would be better written E_N(H) where H is an RV giving the number of half pills, right?

I'd probably write it as E(H_N), but then that would be awkward when the solution turns out to involve the harmonic numbers.

After the addendum that the solution is harmonic numbers, it would be interesting to see an analytical solution.

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.

This probably isn't the earliest source of that, but it's from 2007-08-30 and a good plain text copy of it: https://www.craigslist.org/about/best/tpa/409930561.html

Very interesting

Reply on news.ycombinator.com