The teacher in a certain class room allows you to pass a paper with an assignment around, and whomever it ends up on has to do it. The only two rules are you can't pass it to someone who already has had it and you can only pass it to the person to the left, right, forward, or backward.
In a room of 30 students arranged in a 6 by 5 grid, the teacher starts out with the assignment somewhere on the front row of 6 students. At some point someone is stuck holding the assignment because all his neighbors have had it and passed it on to someone else. If this happens after every student in the room has had it, what is the probablity, for each individual, that he or she turns out to be the lucky winner of the assignment?
This version of the simulation has a different algorithm for randomizing the direction, changed on the theory that the second call to RND might be influence by the first or some such thing. The results look more symmetric now:
DEFINT A-Z
DIM drCt(-2 TO 2) AS LONG
DIM dcCt(-2 TO 2) AS LONG
RANDOMIZE TIMER
DO
REDIM student(6, 7)' unused elements outside bound
f = INT(RND(1) * 6 + 1)
student(1, f) = 1
row = 1: col = f
FOR pass = 2 TO 30
DO
DO
rNo = INT(RND(1) * 9)
dr = rNo \ 3 - 1
dc = rNo MOD 3 - 1
LOOP UNTIL (dr OR dc) AND (dr = 0 OR dc = 0)
drCt(dr) = drCt(dr) + 1
dcCt(dc) = dcCt(dc) + 1
newRow = row + dr: newCol = col + dc
LOOP UNTIL newRow > 0 AND newRow < 6 AND newCol > 0 AND newCol < 7 AND student(newRow, newCol) = 0
row = newRow: col = newCol
p = pass
surr = 1
FOR dr = -1 TO 1
FOR dc = -1 TO 1
IF ABS(dr) <> ABS(dc) THEN
newRow = row + dr: newCol = col + dc
IF newRow > 0 AND newRow < 6 AND newCol > 0 AND newCol < 7 THEN
IF student(newRow, newCol) = 0 THEN
surr = 0: EXIT FOR
END IF
END IF
END IF
NEXT
IF surr = 0 THEN EXIT FOR
NEXT
IF surr THEN EXIT FOR
student(row, col) = 1
NEXT
IF p = 30 THEN
tot(row, col) = tot(row, col) + 1: overTot = overTot + 1
fCount = fCount + 1
PRINT row, col, fCount, tr&
' FOR i = -2 TO 2: PRINT drCt(i); : NEXT
' PRINT
' FOR i = -2 TO 2: PRINT dcCt(i); : NEXT
' PRINT
END IF
tr& = tr& + 1
LOOP UNTIL fCount = 10000
FOR row = 1 TO 5
FOR col = 1 TO 6
PRINT USING "#####"; tot(row, col);
NEXT
PRINT
NEXT
PRINT
FOR row = 1 TO 5
FOR col = 1 TO 3
PRINT USING "#####"; tot(row, col) + tot(row, 7 - col);
NEXT
PRINT
NEXT
PRINT
PRINT tr&
In a sample run it took 1,660,656 trials to get 10,000 in which all 30 students held the assignment.
The array of final hits per seat is:
673 302 409 384 261 813
187 550 318 226 308 205
275 225 278 271 261 468
112 440 303 285 548 121
494 111 195 275 97 605
Which is much more nearly symmetric.
Combining the left and right corresponding number, and plotting on the left, the totals are:
1486 563 793
392 858 544
743 486 549
233 988 588
1099 208 470
Implying the percentages, rounded to the nearest percent are half of the below figures (as it's based on the number combined left and right, and duplicated):
15 6 8 8 6 15
4 9 5 5 9 4
7 5 5 5 5 7
2 10 6 6 10 2
11 2 5 5 2 11
So the most dangerous places are the corners of the room, with about 7 1/2% probability for each of the front-left and front-right seats, and 5 1/2% each for rear-left and rear-right. The safest places are just to the front of or next to the guy in a back corner--only about 1% chance of landing there.
Of course this counts only those cases which extend all the way to having everyone having seen the paper, and so is a conditional probability. In only about 1 in 166 trials does this happen altogether.
If we count all the cases when the passing is forced to stop by the holder being surrounded by previous seers, we get:
919 400 420 410 396 969
210 359 252 207 341 205
243 248 194 228 221 223
181 309 204 206 341 166
780 116 167 198 129 758
1888 796 830
415 700 459
466 469 422
347 650 410
1538 245 365
For percentages that are half of:
19 8 8 8 8 19
4 7 5 5 7 4
5 5 4 4 5 5
3 7 4 4 7 3
15 2 4 4 2 15
|
|
Posted by Charlie
on 2004-06-24 21:56:34 |
Better randomization for simulation.
