Matthew ConroySep 14

I added another problem and solution to my dice collection. It's problem 77. https://www.madandmoonly.com/doctormatt/mathematics/dice1.pdf

Here's the problem statement: "Suppose we play a game with a die. We roll once, and this first roll is the score. We may continue to roll and add to the score, but if the roll ever divides the score we start with (e.g., if our score is 15 and we roll a 1, 3, or 5), then we lose everything and end up with nothing. If instead we choose to stop, we win an amount proportional to the score. What strategy will yield the maximum expected value of our final score?"

This is an optimal stopping problem. I've been interested in optimal stopping problems for quite a while, as a result of these dice problems and other things. However, I haven't found an introductory text to the general theory of optimal stopping that really appeals to me, so I end up doing things "from scratch" whenever I solve such problems. I feel like I might be missing some useful tools, but I'm not sure that is the case for the simple problems I'm solving.

Anyone have any optimal stopping texts or papers they'd recommend?

#math #mathematics #optimalStopping #probability

Show threadpglpmSep 14

@matthewconroy Sounds like a very interesting problem! But I don't fully understand it. For example, how can the score we start with be 15? are we using a die of a special kind?

It sounds like it could be solved by brute force recursively exploring a decision tree, if we limit the max number of rolls. My favourite book, simply written and very clear, that explains the basics of decision theory (of which optional stopping is a particular instance) is Howard Raiffa's "Decision Analysis: Introductory Lectures on Choices under Uncertainty" (Addison-Wesley 1970) <https://archive.org/details/decisionanalysis00raif>.

Decision analysis; introductory lectures on choices under uncertainty : Raiffa, Howard, 1924- : Free Download, Borrow, and Streaming : Internet Archive

Includes bibliographies

Internet Archive
Show threadMatthew Conroy

@pglpm Hello! We can't start the whole game with a score of 15. We start with a single roll, and the first score is the result of that roll. We then continue to roll as long as we like, until we choose to stop or the roll divides our current score. So we might start with 5, then roll a 4, to get a score of 9, then roll a 6, to get a score of 15. Starting then from a score of 15, what can happen? A 1, 3, or 5 will end the game, and give us nothing, any other roll will increase our score.

So, "starting from a score of x" means you are playing the game and your score is x and you have to decide whether or not you want to roll.

The maximum number of rolls is not automatically bounded, but in my solution I argue that one does not benefit, on average, by rolling with a score of 20 or more, and so this puts an upper bound on the number of rolls one would want to make.

Thanks for the reference (and archive link!)!

Cheers!

Sep 14 at 5:42amWeb
Show threadpglpmSep 14

@matthewconroy Ah now it's clear! As you phrase it in your explanation, "with a current score of x" is maybe clearer than "starting from a score of x" (it made me think of the initial score).

In principle the problem can be solved exactly (optimal sequence of decisions) by constructing a decision tree. Owing to the branching structure, I'm not sure about the maximum expected value "5 (x+6)/6". At every outcome/inference/chance branch, the utility of some branches keeps increasing, while the corresponding probabilities seem to have a lower bound. Maybe it's possible that this leads to infinite expected utilities. BUT I haven't sat down to properly think about the problem, so mine is mostly babbling :)

Show threadpglpmSep 14

@matthewconroy

Thank you for this fun decision problem!

To start getting a picture I examined the much simpler case of a "two-sided die" or a coin with faces 1 and 2. Same rules otherwise.

Below is a sketch of a truncated decision tree for this case, when the initial roll is "1". Decision nodes are blue squares with decisions as solid blue lines; the decisions are "K" for "keep" and "R" for "roll". Inference/chance nodes are red circles with outcomes as dashed red lines; outcomes are "1" and "2"; it's understood that each has 50% probability.

The expected utility of each decision is in grey at the end of the corresponding line. The fold-back value at each decision branch is in grey above the corresponding decision node.

If the first roll is "2" then it's clearly best to keep it, as the subsequent roll would yield a divisor and a 0$ outcome.

If the first roll is "1", the best decision apparently is to roll once more, and then, if the outcome is "2", keep the result.

Assume that the player stops in any case with "Keep" at the Nth decision, say N = 5. Then the expected utility of the previous "Roll" decision is 9$/2, which is less that the utility of the "Keep" decision, $7. So the previous decision should be "Keep". Folding backwards this situation remains up to the very first decision, for which the expected utility of "Roll" is 3$/2, whereas that for "Keep" is 1$.

It *seems* that the reasoning above would still apply if the player could continue indefinitely, since at each decision the utility of "Keep" is (1+2N)$, whereas that of "Roll" is (1.5 + N)$. But I'm not completely sure about this, there may be some logical gap.

Unfortunately this simplest case is too special, owing to its binary nature, to say something about your score-bound-strategy assumption. It'll be cool to check a 3-sided die :)

#decisiontheory

Show threadMatthew ConroySep 16

@pglpm I'm glad you find this problem interesting! I'd love to see what you do with a die with more than 2 sides: the decision tree is barely a tree when the die has 2 sides (i.e., there is only one sequence of rolls to get to any score), so I would be interested to see how more branches are handled.

Cheers!