What do the following problems all have in common?
What’s the number of permutations in the symmetric group on n letters Sn without fixed points? What happens to the ratio of this number to the size of the group |Sn|=n! as n→∞?
Suppose you draw n samples with replacement from the set S={1,2,3,…,n−1,n} uniformly at random. Say the set of all elements you get is A, where we don’t distinguish between two draws of the same element. What’s E[|S−A|], i.e. the expected value of the cardinality of the set difference S−A? What happens to E[|S−A|]/n as n→∞?
Two players A and B play the following zero-sum game: they take turns sampling from a probability distribution on the real numbers R with a continuous probability density function. The first player to draw a value that’s smaller than the maximum of all previous values drawn by both players loses. If A goes first, what’s the probability that B wins the game?
The secretary problem: there’s a totally ordered finite set S with distinct elements. You know the cardinality n of S. You play the following single-player game: you get to sample one element at a time from Swithout replacement and uniformly at random. At any point you may choose to stop sampling and keep the last element you’ve sampled. You win if you halt on the maximum element of S and lose otherwise.
For n large, what’s the strategy that maximizes the chance of victory in this game? What’s the probability of victory achieved by the optimal strategy?
There’s a type of problem that is recognizably a “1/e problem”, in the sense that you expect the answer will somehow involve 1/e, but I haven’t been able to make this intuition precise. What properties about a problem make it likely that 1/e shows up?
Some of the above problems involve use of the inclusion-exclusion principle, which is a typical way 1/e can show up in these problems, but e.g. the secretary problem does not.
What do the following problems all have in common?
What’s the number of permutations in the symmetric group on n letters Sn without fixed points? What happens to the ratio of this number to the size of the group |Sn|=n! as n→∞?
Suppose you draw n samples with replacement from the set S={1,2,3,…,n−1,n} uniformly at random. Say the set of all elements you get is A, where we don’t distinguish between two draws of the same element. What’s E[|S−A|], i.e. the expected value of the cardinality of the set difference S−A? What happens to E[|S−A|]/n as n→∞?
Two players A and B play the following zero-sum game: they take turns sampling from a probability distribution on the real numbers R with a continuous probability density function. The first player to draw a value that’s smaller than the maximum of all previous values drawn by both players loses. If A goes first, what’s the probability that B wins the game?
Shoutout to Jane Street for this problem!
The secretary problem: there’s a totally ordered finite set S with distinct elements. You know the cardinality n of S. You play the following single-player game: you get to sample one element at a time from S without replacement and uniformly at random. At any point you may choose to stop sampling and keep the last element you’ve sampled. You win if you halt on the maximum element of S and lose otherwise.
For n large, what’s the strategy that maximizes the chance of victory in this game? What’s the probability of victory achieved by the optimal strategy?
The answer to all of them is 1/e?
That’s right :)
There’s a type of problem that is recognizably a “1/e problem”, in the sense that you expect the answer will somehow involve 1/e, but I haven’t been able to make this intuition precise. What properties about a problem make it likely that 1/e shows up?
Some of the above problems involve use of the inclusion-exclusion principle, which is a typical way 1/e can show up in these problems, but e.g. the secretary problem does not.