Question about a simple game

04232019, 08:09 PM
Post: #1




Question about a simple game
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 userchosen value T, the user is the winner. If the summation variable reaches T or less, the the calculator win. Here is the pseudocode: Code: Sum = 0 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 

04232019, 08:38 PM
Post: #2




RE: Question about a simple game
That sounds like a onedimensional 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! 

04232019, 11:05 PM
(This post was last modified: 04242019 01:55 AM by Albert Chan.)
Post: #3




RE: Question about a simple game
(04232019 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) 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 C1C2; SUBC> uniform 0 1. MTB > let C3 = C1C2 MTB > describe C3 Code: N MEAN MEDIAN TRMEAN STDEV SEMEAN C3 looks triangular. Below histogram from Minitab command: hist C3 Code: 1.0 4 * 

04242019, 02:14 AM
(This post was last modified: 04252019 07:01 AM by Albert Chan.)
Post: #4




RE: Question about a simple game  
04242019, 03:15 AM
Post: #5




RE: Question about a simple game
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^2300*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 

04242019, 02:25 PM
Post: #6




RE: Question about a simple game
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 

04242019, 03:10 PM
Post: #7




RE: Question about a simple game
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 

04242019, 03:14 PM
Post: #8




RE: Question about a simple game
I originally wrote the game on an HP41CX 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 

« Next Oldest  Next Newest »

User(s) browsing this thread: 1 Guest(s)