Which number is hardest to guess?

I finally figured out how to compute the "devil's distribution", a probability distribution that produces a random positive integer that's in a sense the hardest to guess.

I've known for a long time that this thing must exist, but didn't know until recently what it looked like. Here it is:

The setup is not too complicated: Two people, the Selector and the Devil, play a game with a deck of cards. Some cards are item cards and the rest are, well, ordinary cards. If we play with a standard 52-card deck we might decide for instance that the kings, queens and jacks are item cards.

First, the Devil removes 11 cards of their choice from the deck without showing the Selector. Since there were 12 item cards from the start, at least one and at most 12 are still in the game. Now the remaining 41-card deck is shuffled and the cards turned up one by one. The Selector's task is to choose online the last item card. "Online" means that whenever you see an item, you have to decide immediately whether to accept or reject it, and you can't later go back and change your mind.

If the Selector accepts the last item card, they win the game. Otherwise (if they accept an item that turns out not to be the last one, or end up not accepting anything), the Devil wins.

If you are the Selector, your task is basically to guess how many items there are in the deck. If you had to guess from the start you'd have 1 chance in 12 of winning, but it's better than that because the times when the items arrive will give you a clue. If you see many items early on, you can expect there to be more of them, but if you see only a few you might want to accept before it's too late.

But what's a good strategy? And if you play the Devil, how many item cards should you keep in the deck? If you keep many of them, is that generally going to make it harder or easier for the Selector than if there are only a few? Not so obvious!

An interesting thing about it is that if instead we play with a super-mega-giant deck of cards, the game roughly stays the same. We assume then that the Selector knows the size of the deck and that the Devil can put any number of items in it as long as there's at least one.

There is an "infinite deck limit" where instead the Devil chooses an arbitrary positive integer, and that many items arrive at random times in the interval from 0 to 1 (representing the percentage of the deck that we have seen by the time the item card is drawn).

This is where the devil's distribution enters. It represents the optimal way for the Devil to choose the number of items. Of all the ways you might randomize the number of items, this particular one makes the Selector's task hardest.

To me this distribution is special, because it's a mathematical object that I first didn't think would exist. I came to think of this game when I was working on a different problem, the secretary problem on partially ordered sets (that I eventually solved together with Ragnar Freij). At some point I thought I might have a really neat solution to that problem, but in order for it to work, the Selector would have to have a strategy that wins the continuous time Selector-Devil game with probability at least $1/e$, or approximately 36.8%.

Initially it looked promising. The number $1/e$ is what the Selector's winning chances would have been if the game had simply become harder with more items. And there was a perfect analogy, by change of time-scale, to the classical secretary problem where $1/e$ is indeed the Selector's probability of success, and that indeed gets harder with more items. Ah, mathematics is so beautiful!

And so devilish! Because in the middle of a computation, a coefficient in a taylor expansion had the wrong sign. It should have been positive, but it was $-1/2$. Well actually it didn't matter what I thought it should have been. It was negative, and you can't negotiate with the truth.

At first it seemed almost paradoxical to me, because it was clear that it can't be optimal for the Devil to randomize the number of items from a finite list of numbers. They must sometimes choose a large number. At the same time the calculation seemed to show that the Selector's task would get easier with many items.

The only possibility that didn't lead to a contradiction was that the Devil must have a specific optimal strategy consisting of most of the time choosing reasonably small numbers, and then to let the probabilities of larger numbers decay exponentially.

I proved this and described the Selector's optimal policy in a paper published on the arXiv in 2011. But it wasn't until recently that I realized that computing the devil's distribution with any degree of precision was feasible. It seemed at first that errors would propagate and grow to the point where any results obtained in reasonable time would be meaningless. But it turned out it wasn't that hard, and if we start with a precision of say 100 decimals, then ten or so will still be correct in the end.

So here are some data: The Selector, using an optimal policy, wins with probability approximately \[0.35291700020719554668690761575691114631783787927644651520731735696011.\] The Devil has a unique probability distribution to choose from that makes the Selector's task this hard. With any other, the Selector can increase their winning chances by adjusting their strategy.
Facts about the distribution: The probability of choosing only one item is about 4.444% (but no, it's not $2/45$). The number most frequently chosen is 5, which occurs with probability a little more than 8%. From then on the probabilities decrease, and for large numbers they decay in each step with a factor of approximately 1.316496. The distribution approximately has mean 8.873 and standard deviation 5.956.

And I can't relate any of these numbers to known mathematical constants. Except 5.