Question about a simple game

[Namir]

Hi All,

I wrote a simple game where the user plays against the calculator/PC. The game is an iterative one. In ach iteration the user and the PC generate random numbers (0,1). The user’s random value is added to a summation variable, while the calculator’s random number is subtracted from that summation variable. If the summation variable reaches or exceeds a user-chosen value T, the user is the winner. If the summation variable reaches -T or less, the the calculator win. Here is the pseudo-code:

Code:

Sum = 0
I = 0
Do
  Me = Rand(0,1)
  Sum = Sum + Me
  PC = Rand(0,1)
  Sum = Sum – PC
  I   = I + 1
Until Sum >= T or Sum <= -T

if Sum >= T Then 
  Show "You Win"
else
  Show "You lose"
end

I noticed that the average iterations, I, for either player (the user or the calculator) to win is a function of T. I used quadratic fit of I as a function of T. The curves I obtained from the numerous runs indicate that the underlying relation between I and T is:

I = 0.5*T^2 + T = T*(T/2 + 1)

My question is, can someone derive the above equation based on whatever statistical assumptions?

Namir

[Thomas Okken]

That sounds like a one-dimensional random walk, where the expected distance from the starting point is indeed proportional to the square root of the number of steps.

I remember this being covered in calculus of probabilities in college, but I don't recall if we were expected to be able to derive the proof on our own, and I certainly don't remember the proof itself after all these years. But you're definitely on the right track!

[Albert Chan]

(04-23-2019 08:09 PM)Namir Wrote:  I = 0.5*T^2 + T = T*(T/2 + 1)

That can't be right ... If T=1, expected iterations *only* 1½ ?

Tried Lua simulation, expected iterations vary so much that the linear term can not be predicted.

Code:

function loops(t)
    local n, sum, r, abs = 0, 0, math.random, math.abs
    repeat sum = sum + r() - r(); n=n+1 until abs(sum) >= t
    return n
end

function average(f, t, n) -- above vary too much, so do average of loops
    local sum = 0
    for i=1,n do sum = sum + f(t) end
    return sum / n
end

lua> average(loops, 10, 1000) -- 5 times: 640 633 651 584 628 ≈ 627
lua> average(loops, 20, 1000) -- 5 times: 2450 2433 2360 2492 2438 ≈ 2435
lua> average(loops, 40, 1000) -- 5 times: 9606 9680 9687 9690 10083 ≈ 9749

9749 / 2435 = 4.00, so curve shape should be N = K T^2
K = N/T^2 = 9749 / 40^2 = 6.093
N = 6.093 T^2

However, for small T, the curve does not fit quite right.

lua> average(loops, 1, 1e6) --> Expected iterations for T=1 ~ 9.26

T/sqrt(N) = sqrt(1/6.093) = 0.405

0.405 is roughly the standard deviation of rand(0,1) - rand(0,1)

MTB > rand 1000 C1-C2;
SUBC> uniform 0 1.
MTB > let C3 = C1-C2
MTB > describe C3

Code:

                N     MEAN   MEDIAN   TRMEAN    STDEV   SEMEAN
C3           1000  -0.0311  -0.0284  -0.0333   0.4044   0.0128

              MIN      MAX       Q1       Q3
C3        -0.9574   0.9448  -0.3223   0.2442

C3 looks triangular. Below histogram from Minitab command: hist C3

Code:

    -1.0       4  *
    -0.8      46  **********
    -0.6      86  ******************
    -0.4     127  **************************
    -0.2     175  ***********************************
     0.0     182  *************************************
     0.2     171  ***********************************
     0.4     105  *********************
     0.6      68  **************
     0.8      30  ******
     1.0       6  **

[Albert Chan]

(04-23-2019 11:05 PM)Albert Chan Wrote:  0.405 is roughly the standard deviation of rand(0,1) - rand(0,1)

To be more precise, standard deviation = sqrt(1/6) ≈ 0.40825

With rand(0,1) - rand(0,1) mean of 0, and apply symmetry:

Variance = 2 * integrate((1/2 - x/2)², x=0 to 1) = 1/6

[Namir]

I need to apologize for my big math mistake. The equation relating the number of iterations and the threshold is wrong because I deduced it by taking the sum AND NOT the difference between two subsequent random numbers.

After correcting my VBA code in Excel, I recalculated the number of iterations and looked at the correlation. I came with results close to Albert's results!! Good call Albert.

I noticed that for T <=8 the following GENERAL relation seems to hold:

I = 7*T^2.5

For T > 8, a quadratic fit between I and T does better:

I = 50*T^2-300*T+450

The above two equations are based on averaging the correlation coefficients.

The above results cast doubt in my mind that there is a theoretical background for relating the number of iterations with the threshold. I feel that the statistics involved go beayond the stats for the difference between two random numbers.

Namir

[Albert Chan]

Hi, Namir

Your different results probably due to quality of the random generator.
This is especially true here since we are subtracting two random outputs.

Also, many random generator have low linearity complexity issues.
That meant it is ok to use the randoms as *values*, but not in pairs.
The pairs may not be independent enough to give good result.

This also meant jamming random bits to make bigger random numbers is a bad idea.
see http://www.azillionmonkeys.com/qed/random.html

My patched Lua were using xoroshiro128+ PRNG, with decent randomness properties.
Just to be sure, I redid the simulation using *two* random generators:

With 5000 runs, ME = xoroshiro128+, PC = Mersenne Twister, results are similar:

For T=40, N ≈ 6.12 T^2
For T=1, N ≈ 9.26

[Namir]

I took another look at the results I obtained for the threshold value T and the number of iterations I. The best general equations I can come up with are:

I = 9 *T^2.3 for T <= 6 and T >= 1

I = 3.5*T^2.85

The (T, I) points can fit fit well with cubic polynomials. Unfortunately, the polynomial coefficients (and especially the constant term) vary significantly based on the calculation set.

So the above two equation are the best estimates for the number of iterations.

Namir

[Namir]

I originally wrote the game on an HP-41CX emulator on the iPhone. I used teh formula:

r = frac((r + pi)^5)

Since the 41CX was no match for the speed of Excel VBA, I did the testng using VBA and its RND(1) function.

Namir