I thought of some interesting questions based off of this game I saw. I don’t know what the game is called, but I call it death roll now. The rules of the game are simple:
- Start with a natural number $n$
- Roll a number $m$ from $1$ to $n$ uniformly randomly
- If $m=1$, then you lose.
- Otherwise, set $n=m$ and go back to step 2
This turns into a game between friends by taking turns rolling the number. I figured I might be able to pull this out as a drinking game, but that made me wonder if there was any way to rig the game by choosing the initial number in a certain way. For example, if there are $k$ players, could I choose $n$ inconspicuously so that I can expect the game to end before the $k$th player even has a chance to roll? Or in general, how much shenanigans would I be able to get away with?
So I began messing around with the numbers. Let $T(n)$ be the expected number of turns by starting with $n$. If we roll $n$, then the expected number of turns is $T(n)+1$, because we ended where we started, except we wasted a turn. In general, if we roll $i$, then the expected number of turns is $T(i)+1$. By properties of expectation, $T(n)$ follows this recursive formula:
$$T(n) = \mathbb{P}(n)(T(n)+1)+\mathbb{P}(n-1)(T(n-1)+1)+\ldots+\mathbb{P}(1)$$
where $\mathbb{P}(i)$ is the probability to roll $i$, which should be uniformly distributed but is noted for generalization.
Doing some algebra will yield that $T(n+1)=T(n)+\frac{1}{n}$. I’d like to remark that this is an exceptionally simple and elegant formula to capture this game.
I also wondered if there was a non-recursive definition for $T(n)$. I tried solving the recurrence by using advancement functions, but I had no luck. I turned to Wolfram Alpha to look for a computerized solution, and I found that $T(n)=H_{n-1}$, where $H_n$ are the harmonic numbers. I’m not very familiar with the harmonic numbers, so I’m not sure why it shows up here, but it was a curious connection to the uninformed me.
I also have to look at the variance of the number of turns as a function of $n$. I haven’t done that yet, but it seems to have quite high of a variance, which is not surprising. I wrote a script to simulate the game and after a million samples of $n=50,000$, we get that the expectation is around $12.40$ and the variance is $13.03$. The variance is way too high for me to have any hope of rigging the game unfortunately. I’m too lazy to calculate the variance by hand, but if I ever do, I’ll come back and update the post to show the actual formula.
Death roll will eventually complete, and my questions above were in regards to how long it would take. However, what if we modify death roll a little bit? Let $f: \mathbb{N}\to\mathbb{N}$ and modify death roll into $f$-death roll by keeping the same rules as death roll except in step 4, set $n=f(m)$. I’ll also introduce another variance $f2$-death roll, where $f:\mathbb{N}\times\mathbb{N}\to\mathbb{N}$ and in step 4, set $n=f(m,n)$. I’ll mainly be concerned about the first variant for now, but the second is something to think about.
I wonder what are necessary conditions such that $f$-death roll doesn’t last forever? For example, I would guess that if $f(n)=n!$, then the game would never end. What’s the boundary between when the game ends and when it doesn’t though? Certainly a sufficient condition would be that $f(n)\leq n$. I also posited of a necessary condition that $f(n)>n$ for only finitely many $n$.
Upon discussion with a colleague, we discovered that the posit is incorrect. Consider the function
\[
f(n) = \begin{cases}
n+1, &n \text{ odd}\\
1, &n \text{ even}
\end{cases}
\]
Certainly, $f(n)>n$ for infinitely many $n$, but we’ve proven that $T(n)$ with respect to this $f$ is finite. It’s not quite constant, but taking $n\to\infty$ gives a bounded $T(n)$.
Of course, $f$ lives among a family of functions where
\[
f(n) = \begin{cases}
n+1, &n\not\equiv0\mod m\\
1, &n \text{ otherwise}
\end{cases}
\]
I’ll call this family of functions the ideal functions, given by the behavior of “absorbing” elements from the ideals of ring theory, and of course by the fact that $f$ acts on the ring generated by modding out an ideal of the integers. It’s not hard to see that ideal functions do violate $f(n)>n$ for infinitely many $n$, but also that $T(n)$ is finite and $\lim_{n\to\infty}T(n)$ is finite (and although not proven yet, it seems likely that this limit is equal to $m$, the element generated by the principle ideal $f$ acts on).
I think what makes the ideal functions special is not the fact that they act on the ideal generated, but that the limit of $T(n)$ is finite. Knowing the existence of ideal functions, it’s a simple exercise to construct a function living outside of the ideal functions that violate $f(n)\leq n$ for infinitely many $n$ but still have finite expectation for all $n$. We’ll call functions with finite limiting $T(n)$ the limited functions, of which the ideal functions are a subset of. It may not be such a simple task to construct a non-limited functions violating $f(n)\leq n$ for infinitely many $n$ with finite $T(n)$ for all $n$. Naturally, this is my next posit:
Given $f:\mathbb{N}\to\mathbb{N}$, if $T(n)$ is finite, then $f(n)\leq n$ for infinitely many $n$ or $f$ is a limited function.
If any more progress is made, I will update this post again.