Ask HN: Dreidel Expected Value?
For those unfamiliar with the game, it's very simple. It's a turn-taking game where players get one of four equally likely outcomes: nothing happening, putting one token from your pile into the pool, taking half of the tokens in the pool (it can be rounded up or down, take your pick), or taking all the tokens. If the pool is empty, every player puts in one token.
It seems obvious that in most cases you can expect to come out with more than you came in. For one player, stopping after one round (so the refill never comes into play; if it does, subtract another 0.25) and assuming infinitely divisible tokens, the expected value is given by 3/8g-0.25, where g is the number of tokens in the pool initially. Simple enough.
But when attempting the real(er) version, things got complicated. There are a fair number of new considerations: the number of players (which also determines g's value after the pool has been emptied), someone's position in the turn order (since those before wil impact things) and the order in which rolls are made (adding one to the pool, emptying it, refilling it and dividing it by two yields different results than adding one to the pool, dividing it by two, emptying it and refilling it).
Do you have any ideas, or know of anyone who's tried to answer this question or analogous ones? Is it even possible to quantify (in a reasonable amount of time) the average expected value of one complete round for a random player in a game of dreidel with p players?