A Quantitative Study on Average Number of Spins of Two-Player Dreidel
Thotsaporn "Aek'' Thanatipanonda
math.HO math.CO math.PR






A Quantitative Study on Average Number of Spins of Two-Player Dreidel
    Thotsaporn “Aek” Thanatipanonda

Science Division,
Mahidol University International College

Nakornpathom, Thailand 

thotsaporn@gmail.com

    June 28, 2019
===============================================================================================================================================


We give a high precision approximation of the average number of spins in a simplified version of a two-player version of the game Dreidel. We also make a conjecture on the average number of spins of the full version of the game.




§ INTRODUCTION

In 2006, Robinson and Vijay <cit.> showed that the average number of spins of the Dreidel with k ≥ 2 players where each player starts with n nuts is 𝒪(n^2). In this paper, we give a quantitative analysis of the average number of spins of a two-player simplified version of this game, where players start with a and b nuts, respectively.

Motivation: Gambler's Ruin:

We will first motivate our work with a well known statistical concept, gambler's ruin, which is interpreted in terms of a game that starts with a gambler who has zero chips.  For each play, s/he could gain one chip or lose one chip with equal probability p=q=1/2. The game continues until the gambler gains M chips or loses N chips. We are interested in the expected number of plays until the game ends.

Let G(a) be the expected number of plays until the game ends when the gambler initially has a chips. The system of recurrence relations that G satisfies is as follows: 

    G(M)=  G(-N) =0,


    G(a)=1+12G(a+1)+12G(a-1), -N <a < M.


The solution to this system is well known, 

    G(a)= (N+a)·(M-a) ,        -N ≤ a ≤ M,


i.e. <cit.>. This beautiful result is a cornerstone of probability models 
and is the source of inspiration for our research problem.





§ ANALYSIS OF SIMPLIFIED DREIDEL






    < g r a p h i c s >




A Dreidel is a four-sided spinning top, and the game associated with it is played during the Jewish holiday of Hanukkah. Each side of the Dreidel bears a letter of the Hebrew alphabet: gimel, hay, nun and shin. This is an n-player pot game where  player i begins with a_i nuts, contributing or taking away nuts from the pot as the game progresses. At the start of the game, everyone donates one nut to the pot and takes their turn to spin the Dreidel. The player who spins the Dreidel takes a certain action depending on how the Dreidel lands:


  * Gimel: Player takes the whole pot, after which everyone donates one nut to the pot and then the next person spins.

  * Hay: Player takes the smaller half of the pot and the next person spins.

  * Nun: Player takes and gives nothing and the next person spins.

  * Shin: Player gives one nut to the pot and the next person spins.

The game ends when one person has all of the nuts in their possession.

We consider the simplest non-trivial version where two players spin with only two outcomes: Gimel (player takes the whole pot) and Shin (player gives one to the pot), and we answer the question of how long the game will last if the two players start with a and b nuts, respectively.

Let D(a,p,b) denote the average number of spins until the game ends where the first player has a nuts, the second player has b nuts, and p nuts are in the pot. We can derive the following recurrences for the simplified game:

    D(a,p,b)    = 1+12[  D(b-1,2,a+p-1) + D(b,p+1,a-1)   ],  
    
      D(0,p,b)    = D(a,p,0) =0 ,      for any  a ≥ 0,  p ≥ 0,  b≥ 0.
 

Example. Some values of D(a,p,b) when a+b+p=6 are

    D(1,1,4) = 3316,    D(1,2,3) = 52,    D(1,3,2) = 94,    D(1,4,1) = 1,


    D(2,1,3) = 5716,    D(2,2,2) = 3,    D(2,3,1) = 32,


    D(3,1,2) = 154,    D(3,2,1) = 178,    D(4,1,1) = 94.


Experimental Math in Action:

We are interested in the average number of spins until the game ends, 
    T(a,b) := D(a,2,b).
 It would be too much to ask for an exact formula for T(a,b) because we can see that the recurrence (<ref>) is quite complicated. The best we could hope for is a good approximation of it. The first thing that comes to mind is to compare T(a,b) with the result of gambler's ruin (i.e., see (<ref>)). It is reasonably safe to guess that T(a,b) ≤ ab for a,b ≥ 0. 

After experimenting with different values of D(a,p,b), we see that the sequence 
    Δ_a := D(a+1,p,b)-D(a,p,b)
 quickly converges to a constant for each p,b. A similar thing happens for 
    Δ_b := D(a,p,b+1)-D(a,p,b).
 This implies that 
    Δ_a^2≈ 0 ,     Δ_b^2≈ 0.
 In other words, 

    D(a+2,p,b)-2D(a+1,p,b)+D(a,p,b) ≈ 0
 or

    T(a+2,b)-2T(a+1,b)+T(a,b) ≈ 0.
 

As a consequence, we learn that T(a,b) is almost linear in both a and b. T(a,b) must be of the form 
    T(a,b) = c_3· ab + c_2· a + c_1· b +c_0 +ϵ_a,b,
 
where ϵ_a,b is some small error in which we shall see that it is exponentially small in a and b, i.e. the leading terms are 1/4^a and 1/4^b.  
This is a fairly nice observation, but how could we prove it rigorously?


Symbolic Computation in Action:

Since we are only interested in T(a,b) (in the situation where p=2), we will rewrite the system of equations (<ref>) recursively in terms of T(a,b) only. 

Example:

    T(1,3)    = 1+12[ T(2,2)+0   ], 
    
    T(2,2)    = 1+12[ T(1,3)+D(2,3,1) ] 
    = 1+12[ T(1,3)+ 1+12[ 0+1] ] 
       = 1+ 12+14+12T(1,3), 
    
    T(3,1)    = 1+12[ T(0,4)+D(1,3,2) ]
     = 1+12[ T(0,4)+ 1+12[ T(1,3)+0] ] 
       = 1+ 12+12T(0,4)+14T(1,3)
     = 1+ 12+14T(1,3).


The process appears to get out of hand pretty quickly. But we can sort and check these relations with the actual values using the computer. As a result, we obtain

    Key
    T(a,b) = ∑_i=0^min(2a-2,2b-1)(12)^i +
     ∑_i=1^min(a,b)T(b-i,a+i)2^2i-1+
    ∑_i=2^min(a,b+1)T(a-i,b+i)2^2i-2 .
          

The first sum comes from both players landing on shin (pay one) until one of them runs out of nuts. The second/third sum comes from the first/second player landing on gimel (takes the whole pot) respectively for the first time.


The Guess and Check Method:

So far so good! Equation (<ref>) is the key! We simply plug in the conjectured equation (<ref>) into (<ref>). We consider two different cases according to the upper limits of the sums:
case 1: a ≥ b+1,
case 2: a ≤ b.

Indeed, with the help of Maple, the conjectured polynomial for T(a,b) fits (<ref>), where the terms with 1/4^a and 1/4^b have been ignored. All of these cases produce the same solution where c_3= 12/19 and c_1=c_2+2/19 and there are no restrictions on c_2 and c_0. 


The Approximation of T(a,b): 

The two free variables c_2 and c_0 could be approximated using the least squares method. In principle, we should work on the two cases separately. However, doing it all at once gives a very nice approximation, so we choose to do it this way. We use the least squares method over the values of T(a,b)  where 30 ≤ a,b ≤ 60 to obtain 

    T(a,b) ≈T(a,b) =  1219ab+c_2a +(c_2+219)b+c_0,

in which  
    c_2 = -0.304636562751640396971893222635…

and

    c_0= 2.13102617218341081870452144156… .
 

This approximation is astonishing, for example, 
|T(100,100)-T(100,100)| < 10^-12. 



The approximation of D(a,p,b)!: 

We don't only have a good approximation for every starting position
but also a good approximation for every position!! 
For any numbers of nuts a and b, we notice that the sequence 

    h_a,b(p) := D(a,p+1,b)-D(a,p,b)

converges to a constant. 
Moreover these constants are linear in a and b i.e.

    h_a,b(p) = s_2· a + s_1 · b + s_0.

 By combining these two ideas i.e. (<ref>) and (<ref>),
 it is reasonable to set up the solution form of D(a,p,b) as 

    GOOD GUESS
       D(a,p,b)  = T(a,b) + (p-2)(s_2· a + s_1 · b + s_0)  + ϵ_a,p,b.

This is a nice idea! But how can we prove it? We make use of the original recurrence relation

    D(a,p,b) = 1+ 12D(b-1,2,a+p-1)+12D(b,p+1,a-1).

Plug in (<ref>) on both sides and equate the coefficients of 
ab, a ,b and the constant term. The conjectured equation fits. We obtain that 
s_2 = 419, s_1 = 819 and
s_0 = c_2-1819. The final solution is

    D(a,p,b)
       ≈1219ab+(c_2+4p19-819)a 
    +(c_2+8p19-1419)b+c_0 + (p-2)(c_2-1819),

where c_2 and c_0 were defined earlier. 
We stress that the approximation works better for large a and b.



The Main Conjecture: 

After successfully finding a good solution to the simplified Dreidel game, it is natural to try to see whether the same method works for the full version (that is, where all four outcomes can occur). Let us denote the average number of spins for the full version by Dr(a,p,b). We notice that each of the sequences

    Δ_a := Dr(a+1,p,b)-Dr(a,p,b)
 
and 

    Δ_b := Dr(a,p,b+1)-Dr(a,p,b).

converge to constants as before. Therefore, the same technique should work once we figure out relations similar to (<ref>). For now, we only conjecture how long the Dreidel game lasts and denote
Q(a,b) := Dr(a,2,b). 




    Q(a,b) ≈Q(a,b)    = 
    2.21814151862618181904832628843 · ab 
        -1.09709667033405910669478639669 · a 
        -0.447079544643588135688652268182 · b 
        +2.83880783734231869675987135868 .



We obtain Q(a,b) by the least-squares method on 15 ≤ a,b ≤ 25. This function agrees with Zeilberger <cit.>, if we let a=b=nuts-1. The approximation also comes with incredible accuracy, for example 
|Q(35,22)-Q(35,22)| < 10^-10.

For a practical perspective, 
we may assume that it takes 10 seconds per play,
if both players start with 10 nuts, 
an average game will last 28.10 minutes.  
And if both players start with 15 nuts, 
an average game will last 69.33 minutes.

99
RV T. Robinson, S. Vijay, 
Dreidel Lasts O(N^2) Spins,
Advances in Applied Mathematics 36, 85–94, 2006.

Ross Sheldon M. Ross, 
Introduction to Probability Models,
Academic Press, sixth edition, 1997.

Z1 D. Zeilberger, Does Dreidel Last O(NUTS**2) Spins?,
The Personal Journal of Shalosh B. Ekhad and Doron Zeilberger,
Kislev 30, 5760.



