Random Magic Paths - is it truly random?

[alexti]

Ivan Pedroso said:
In fact you could choose any two small positive numbers, epsilon >0 and delta >0, (could be 0.00000001 and 0.000000001) and it will then be possible to find a laaaarge number N that insures that:

If N dies are rolled then the probability of getting an observed frequency that deviates from 1/8 with more than the small number epsilon, is smaller than delta.

That is:
Probability( |"observed frequency" - 1/8| > epsilon ) < delta

Do you know how to proof it? I don't see any obvious one. Let us consider frequency of death picks.
Code:

---

Probability to roll exactly k out of n P(k,n) = C(k,n)*p0^k*(1-p0)^(n-k). (p0 = 1/8)



For simplicity, let's consider overrunning your range up. Probability of that P(m+,n) = sum[k=m..n]{P(k,n)},

where m is smallest that satisfy m/n > p0 + epsilon.

Ignoring rounding effects we can write m=a*n, where a = p0 + epsilon.

Then P(m+,n) = sum[k=m..n]{P(k,n)}

 = p0^(a*n) * sum[k=a*n..n]{C(k,n)*p0^(k-a*n)*(1-p0)^(n-k)}.



And that's where I'm getting stuck. p0^(a*n) quickly goes to 0 when n grows,

but the sum part has number of elements proportional to n,

with the dominant n! on the top, so it will grow very quickly.

Does this P(m+,n) converge to anything? And if it does, to what value?

---

I have tried to run a test program to see what is happening.
I didn't have few billion years to wait until the probability to get within the epsilon = 0.00000001 will become distinguishable from 0, so I took 0.002 as epsilon. Unfortunately, at around n=3000 my program is running out of precision of double. At that moment P(m+,n) is around 40%. Until then it was slowly going down, but the rate of descend was decrementing. So, the experiment didn't suggest any conclusion

Ivan Pedroso said:
And then adding up the three largest observed frequencies will then result in a value that is in the interval
[3/8 - 3*epsilon ; 3/8 + 3*epsilon]

That looks wrong. You could do this if your frequencies were independent random processes. However, in our case they are dependent from each other, because the total of all frequencies is always 1. And of course, sum of three largest frequencies is always >= 3/8, but that isn't a problem.

I'm still unsure if your theorem is right or not, but your proof needs fixing.

[alexti]

To everybody who submits statistics from the real games. Please make sure that you were not conducting any particular strategy with those random mages (meaning that you sure that some of them couldn't have been killed in the battles or by assasins, remote spells etc). Also if you were buying those mages until you got some particular pick, your statistics is also invalid (because it's guaranteed that it doesn't contain more than once instance of that pick)

[Kristoffer O]

Hmm, strangest thread I've seen in a while. I have a feeling it tells us something. Perhaps not about the topic of the thread. Interesting reading anyway

[bone_daddy]

Yeah. It tells us that we're all a bunch of nerds. :-)
Not that that's a bad thing. I'm a nerd, my wife's a nerd, and hopefully my son will grow up to be nerd.

[Ivan Pedroso]

alexti said:

Do you know how to proof it? I don't see any obvious one.

"the Law of Large Numbers" (or is it called something else, can't remember it) ensures that:
"The more you repeat the random process the more the empirically measured frequencies approach the values of the ''true'' underlying probabilities"
- repeatedly roll some eight-sided dies and your observed frequencies will get closer and closer to 1/8 as you go along.

alexti said:

That looks wrong. You could do this if your frequencies were independent random processes. However, in our case they are dependent from each other, because the total of all frequencies is always 1. And of course, sum of three largest frequencies is always >= 3/8, but that isn't a problem.

I'm still unsure if your theorem is right or not, but your proof needs fixing.

Sure... I should have used the interval: [3/8 ; 3/8+3*epsilon]
Adding up any three empirical frequencies will (very likely) result in a value that is included in the interval [3/8-3*e ; 3/8+3*e]. Adding the three largest will make the value end up in the smaller interval above.

(hehehe I could be a pedantic arse and state that the smaller interval is contained in the larger and still claim my statement to be true - but I simply just forgot about the obvious lower limit of 3/8 - made me look a bit foolish.)

I made a crude program to empirically calculate the Duck_Number: (I like MatLab )

Code:

---

clear                            %%% Clears stuff.

rand('state',sum(100*clock));    %%% Random seed gets mixed up a bit.

m=[0 0 0 0 0 0 0 0];             %%% A vektor is created:

                                 %%% The first entry could be FIRE

                                 %%% the second AIR, and so on.

N=100000                         %%% Number of mages to be generated.

for I=1:N                       

    roll=randint(1,1,8)+1;       %%% Random integer between 1 and 8.

    m(roll)=m(roll)+1;           %%% The appropriate entry (FIRE, AIR...

end                              %%% gets bumped up by one.

f=m/N                            %%% The generated frequencies are computed.

sf=sort(f);                      %%% Frequencies are sorted (ascending order).

duck=sf(8)+sf(7)+sf(6)           %%% The three highest values are added.

---

Doing a handfull of runs (N=100000) resulted in:
Duck_Number ~ 0.377
as a reference: 3/8 = 0.375

[alexti]

Ivan Pedroso said:

"the Law of Large Numbers" (or is it called something else, can't remember it) ensures that:
"The more you repeat the random process the more the empirically measured frequencies approach the values of the
''true'' underlying probabilities"
- repeatedly roll some eight-sided dies and your observed frequencies will get closer and closer to 1/8 as you go along.

Ahh... I think your statement comes from Chebyshev's inequality. So it solves it. I guess to learn how to prove it I'll have to look up in the book

Ivan Pedroso said:

Sure... I should have used the interval: [3/8 ; 3/8+3*epsilon]
Adding up any three empirical frequencies will (very likely) result in a value that is included in the interval [3/8-3*e ; 3/8+3*e]. Adding the three largest will make the value end up in the smaller interval above.

(hehehe I could be a pedantic arse and state that the smaller interval is contained in the larger and still claim my statement to be true - but I simply just forgot about the obvious lower limit of 3/8 - made me look a bit foolish.)

What is wrong is that if you select N for epsilon, delta for the first path, using the same N for the second path is wrong, because after you've fixed one path, the distribution of the other remaining picks between paths is not the same as before. The interval didn't really matter, it was just a consequence of not considering that those variables became dependent.

However, you can prove by applying your reasoning to the random variables X1...Xm (m = C(3,8)) which represent rolling one of the 3 picks (for each combination of 3 paths), with mean = 3/8 for each variable. Than applying your original logic, selecting such N that
Probability( |"observed frequency of Xi" - mean| > epsilon ) < delta
Here, max ("observed frequency of Xi") is a "duck number", so it proves it.

So this case looks closed

[Ivan Pedroso]

(Sure - "choosing a large N" was always meant as: "as large as needed for the stuff to be correct".)

Back to the original question - has anyone found any significant deviations that suggest any hokey-pokey in the randomness ?!?

[alexti]

It doesn't look likely to happen, the sample needed to find anything with a reasonable probability of correctness seems to be too big. My test with sample of 3000 wasn't even close to the point when the distribution significantly condenses, in your 100000 sample result is still 0.5% off.

What is the size of the sample required to show that there's a problem (using duck number indicator) with a 99.99% probability?

I think we'd need the code of RNG to test it on large samples...

[Alneyan]

I suppose there would be no way to create a program able to count the magic paths on Spectres? Getting high number of mages is not difficult, but counting them is (I currently have 4,000 spectres or so, with 128 spectres summoning a spectre every month). Of course, the game *will* crash sooner or later, but I think having as many mages as the game can handle should be good enough for this purpose. Or perhaps several such tests could be run?

Now, the question would be how to count all those magic paths without spending a lifetime on the matter. With further experimentation, I noticed the Nation Overview wouldn't work with that many commanders, and only one hundred commanders can be moved at once to another province. The game also hangs up sometimes when running a turn, but brute force seems to solve the problem, for now at least.

[Arralen]

Err.. folks, I don't think, and the original claim wasn't about it either, that the RNG code is broken per se.

It's just that you e.g. get the "same" mage three times in a row in one game, say with earth/air as random pick, and in the next game, you only get nature and something, but never an air mage (while playing the same nation again).
And sometime the behaviour changes suddenly mid-game.

Would this be "singular" happenings, I woulnd't bother, but I have seen this way to often to write it off as Murphy's law or statistical effects or whatever.

But the error is not with the RNG, but with either the seed that is fed to it (and not re-set for some turns, essentially resulting in the same random number again) or with the code that turns that random num into the actual commander (maybe using old data from the previous turn, or copying the last build commander or something).

Wild guess: That bug about strangely ressurected commanders/heros, which turn up with other nations isn't fixed, too, as noone can figure out how and when it happens, right? Maybe there's some connection ???