| T.R | Title | User | Personal
Name | Date | Lines |
|---|
| 435.1 | | CLT::GILBERT | Juggler of Noterdom | Sat Feb 08 1986 06:50 | 5 |
| Why not use a Monte Carlo method? That is, randomly choose the state
for each number, and count the number of different states. Repeat this
(say) 10,000 times, and compute the expected number of states.
For safety's sake, repeat this using a different random number generator.
|
| 435.2 | | CLT::GILBERT | Juggler of Noterdom | Sat Feb 08 1986 07:37 | 20 |
| It sounded so easy, so I tried it:
n Expectation
-------------------
3 2.2469
4 2.8172
5 3.4193
6 4.0369
7 4.6549
8 5.2857
9 5.9169
10 6.5485
11 7.1503
12 7.7874
13 8.4202
14 9.0629
The random number generator used was one I made up 'on the spot'.
Interestingly, the growth is nearly linear! Anyone care to make
a better analysis of the data for larger n?
|
| 435.3 | "on the spot" random numbers? | LATOUR::JMARTIN | Joseph A. Martin | Mon Feb 10 1986 12:43 | 7 |
| re .2
Just how "on the spot" was this random number generator? May we
assume that its design was informed by Knuth's discussion of the
pitfalls of ad hoc random number generation? (Art of Computer
Programming, Vol. 2, Seminumerical Algorithms, sorry I don't have
it at hand for an exact citation) Just checking. :-)
--Joe
|
| 435.4 | | CLT::GILBERT | Juggler of Noterdom | Wed Feb 12 1986 05:08 | 40 |
| After improving the random-number generator, and using 100,000 runs:
3 elements: 2.25022 states
4 elements: 2.81283 states
5 elements: 3.41470 states
6 elements: 4.03550 states
7 elements: 4.65285 states
8 elements: 5.27464 states
9 elements: 5.90891 states
10 elements: 6.53611 states
11 elements: 7.16415 states
12 elements: 7.79032 states
13 elements: 8.41640 states
14 elements: 9.05649 states
15 elements: 9.68359 states
16 elements: 10.31365 states
17 elements: 10.94743 states
18 elements: 11.58232 states
19 elements: 12.21007 states
20 elements: 12.84442 states
21 elements: 13.47232 states
22 elements: 14.11090 states
23 elements: 14.74552 states
24 elements: 15.36363 states
25 elements: 16.00355 states
26 elements: 16.63078 states
27 elements: 17.25824 states
28 elements: 17.89047 states
29 elements: 18.52810 states
30 elements: 19.15207 states
31 elements: 19.77882 states
32 elements: 20.42421 states
So there's more data for you -- can somone suggest why this is so nearly
linear? Can someone suggest why the coefficient is roughly 0.63? Would
it help to have the corresponding data for the case where element x *may*
be in state x?
(Note that I've given 5 fractional digits because that's precisely what
the simulation gives. Only the hundredths have any real significance.)
|
| 435.5 | What I had ended up using. | SUSTAR::THALLER | Kurt (Tex) Thaller | Wed Feb 12 1986 11:50 | 63 |
|
The following is the simulation program I ended up using to determine
the values. The program prints out its guesses and you can watch
as it zeroes in to a more accurate value. I'm not sure what is
meant by a "monte carlo" and am curious if this program is doing
the same calculations as used in .2 and .3.
The values I get are within .5 % of those listed in .2. I don't
know which is more accurate but it doesn't matter. For my purposes
I only needed accuracy to within .1 or so.
Just as another note, for n=100, I get 63.5 which supports the linear
relation noted in .3 as do all other values I calculated up to
n=256 => 162.
Kurt*
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
00001 dim z(500)
00002 dim x(500)
00003 dim w(500)
00004 d=0
00005 print "number of nodes:";
00010 input a
00011 maxe=0
00012 mine=99999
00020 for q=1 to 500
00025 z(q)=0
00026 x(q)=0
00027 w(q)=0
00030 next q
00035 y=0
00040 for t=1 to 50
00050 for s=1 to a
00060 r=int(rnd*a+1)
00070 if r=s then 60
00080 x(s)=r
00090 next s
00100 for s=1 to a
00110 z(s)=0
00120 next s
00130 for s=1 to a
00140 z(x(s))=1
00150 next s
00155 e=0
00160 for s=1 to a
00170 e=e+z(s)
00180 next s
00181 if e <= maxe then 184
00182 maxe=e
00183 print "new MAX = ";maxe
00184 if e >= mine then 190
00185 mine=e
00186 print "new MIN = ";mine
00190 w(e)=w(e)+1
00200 next t
00205 y=y+1
00210 d=0
00220 for t=1 to a
00230 d=d+(w(t)*t)
00240 next t
00250 print d/y/50
00260 goto 40
09999 end
|
| 435.6 | | SERF::POWERS | | Mon Feb 17 1986 12:50 | 9 |
| re: .4
0.63 ~= 1 - 1/e
a well-known magic number for people who deal in exponential decay
(time constants)
- tom powers]
|
| 435.7 | how about a relationship to pi? | CIMLAB::HAINSWORTH | Many pages make a thick book. | Thu Jul 30 1987 22:43 | 3 |
| I noticed that the ratio is very close to 2/pi. This suggests to
me a relationship with the normal distribution function, because
the integral from 0 to infinity of e^(-x^2)dx is SQRT(pi)...
|