一個隨機抽卡的遊戲

A simulation was made by designing a Visual Basic Macro. The listing of the program can be found in the link below:
http://www.funp.net/241486
The algorithm for the simulation is:
1.Initialise 31 variables to the same value of 10,000
2.Simulate a random sequence for 31 cards using Visual Basic instructions “Randomize” and “Rnd”.
3.The values of the 31 variables are then modified according to the generated sequence, using the multiplication factor defined in the problem description.
4.Step 2 and 3 are repeated 30 times, to represent 30 days.
5.The maximum of the 31 variables are then recorded, representing the winning amount among 31 participants.
6.The maximum of the first 10 variables are also recorded, representing the winning amount among 10 participants. The remaining 21 data are irrelevant in this particular step.
7.Steps 1 through 6 are repeated 2 million times.
The above simulation took 3 hours 1 minute and 17 seconds to complete. The resulting Excel data file is 72 Mbytes in size and is not easily shareable over the internet.
Note :
1.Since the behaviour of Visual Basic instructions “Randomize” and “Rnd” are not fully known, there is uncertainty regarding how “random” the generated sequences are.
2.Although a significant amount of data were generated, it is very very small compared to the order of magnitude of 31^30, so the reliability of the data pattern generated hinges very much on the randomness of the data generation process.
The obtained average for the case with 31 participants is $25,222.53 while the average for the case with 10 participants is $19,833.42.
If the 2 million data points are segmented into 32 sub-groups with 62,500 data points each, and the average for these 32 sub-groups are compiled, 2 ranges of averages are obtained:
31 participants : $25,154 - $25,305
10 participants : $19,781 - $19,882

Distribution histograms are plotted for the two cases as below, green for 10 participants.

圖片參考：http://img84.imageshack.us/img84/2444/frequencydistribution.png

http://img84.imageshack.us/img84/2444/frequencydistribution.png

asasas

goluckyryan:

your concept is basically correct. Can you extend the logic to the problem above?

2009-09-18 01:26:40 補充：
For your coin tossing problem, it may not be possible to obtain a closed form answer, but according to Random Walk theory, the expected translation distance shuold be of order Sqrt[N]

2009-09-18 01:26:53 補充：
In this case, the translation distance for A is just the absolute value of the gain, which is exactly the same as the 1st Player's value.

2009-09-18 01:27:56 補充：
However, for many body random walk, is the same still true? We possibly need a computer to simulate.

2009-09-18 12:28:01 補充：
Well, Binomial distribution only works for your simplified 2 player game.
I think for more player game, we need the Multinomial coefficients...

2009-09-20 00:24:59 補充：
No I don't... so I asked the question........

2009-09-20 02:15:51 補充：
I expect 3 steps is less, because there are more possibility of "not winning"
e.g. in 3 player game, when A = (1,0,0)
A may win if B=(0,1,-1) C = (-1,-1,1)
A may lose if B=(0,1,1) C = (-1,-1,-1)
so the same configuration does not guarantee winning

2009-09-20 02:18:49 補充：
Yes. But after our discussion seems it is better to consider zero sum game first =.="

i wonder the meaning or definition of "expected value" in this situation.

consider a simplest Zero-Sum game -- coin tossing. win = +1, lose = -1

there is no such "winner" in this game, everyone can be.

so, the "winner expectation", is somewhat ill defined. am i correct??

2009-09-17 18:30:42 補充：
may be,

for the 1st game, A win, and so, the expectation of winner is +1.
for the 2nd game, there are +2 (win again) or 0 (lost) for A, while B may be 0 (win) or -2 (lost again).
so, the "expectation value" of winner, A, is +2 (1/2) + 0 (1/2) = +1 ??

and this keep going on?

2009-09-17 18:36:34 補充：
thing gets complicated in 3rd game. where B can win this time.

outcome of A:

+3 (P = 1/4) , +1 (P = 1/2) and -1 (P = 1/4)

outcome of B :

+1 (P = 1/4), -1 (P=1/2) and -3 (P = 1/4)

2009-09-17 18:36:40 補充：
A has total 3/4 chance to be winner again, while B has 1/4 chance to win.

is the expectation of winner is 3(1/4) + 1(1/2) + 1(1/4) = 3/2 ???

2009-09-18 10:28:47 補充：
hi,

we can see that it is kind of Binomial distribution.

so, i guess the expectation:

the peak of the following:
the function of earn * the function of Binomial distribution.

i will work it out and check the Random walk theory soon.

2009-09-19 19:09:39 補充：
the Multinomial coefficient is just the number of permutation among n objects in r boxes.

n!/(k1!k2!k3!...kr!)

so, the expectation is:
Sum[ PI[gi^ki]*n!/(k1!k2!k3!...kr!), {i, such that PI[gi^ki] > 0} ]
where gi is the gain(lost) for i.

2009-09-19 19:09:46 補充：
First we need to found out what combination can give positive gain. is the upper triangle of n-D matrix.

2009-09-19 19:10:07 補充：
by the way, you have the answer?

2009-09-20 02:09:47 補充：
i have checked that for 1-D 2 steps random walk, the root mean square value of distance is equal to a*Sqrt[n], a is the step side.

but when i go to 1-D 3 steps RW, the root mean square value is not equal to a*Sqrt[n]... and i cannot simplify the summation.

may be we can chat on MSN.

2009-09-20 02:16:14 補充：
by the way, it is not a Zero-Sum game when we use % gain.

2009-09-20 02:41:00 補充：
it does matter who is winning. we sum them all.

if a configuration made A win, then, we use A's winning amount*the possibility of this confi. Do this for B and C. the final sum is out expectation value.

2009-09-20 02:45:42 補充：
Therefore, we don't need to know who win, but how much the win and the prob.

for 1-D, 3-Steps RW,

let (a,b,c) be the vector for the amount of (A,B,C) win (or lose).

in each run, we either add (1,0,-1), (1,-1,0), (0,1,-1),(0, -1,1), (-1,0,1) or (-1,1,0) into the starting (0,0,0)

2009-09-20 02:48:40 補充：
there are 6= (3!) way to do so.

for n-run, there are 6^n possible outcome (some are same) and we use the winning (largest number) outcome * 1/6^n and sum them up.

2009-09-20 03:02:42 補充：
(000) = 1*0 = 0

(10-1)..... = 1*(1/6)+...+1*1/6 = 1

(20-2), (2-1-1),(1,1,-2)..... = 2*(1/36)+2*(2/36)+1*(2/36)+...

i dun know how to count. >