| I assume you are asking for the mean value of the number of times the
unopenable nut will be selected.
Let f(n) be the mean number of times the unopenable nut will be selected before
a single openable nut is selected, where n is the number of nuts in the pocket.
Thus, the sum of f(100), f(99), . . ., f(2), will be the mean number of times
the unopenable nut will be selected in reducing the number of nuts to one.
If there are n nuts in the pocket, there is an (n-1)/n chance that an openable
nut will be selected, in which case the unopenable nut is not selected, and the
situation becomes one with n-1 nuts in the pocket. There is a 1/n chance that
the unopenable nut is selected, in which case it is selected once and the
situation is reset, so that it will be selected a mean of f(n) more times.
Thus
f(n) = (n-1)/n * 0 + 1/n * (1 + f(n)).
f(n) = 1/n * (1 + f(n)).
f(n) = 1/n + f(n)/n.
(1-1/n) * f(n) = 1/n.
(n-1)/n * f(n) = 1/n.
(n-1) * f(n) = 1.
f(n) = 1/(n-1).
Finally, the mean number of selections of the unopenable nut when 100 nuts are
initially in the pocket is f(100)+f(99)+ . . . f(2), or 1/99+1/98+ . . . + 1/1.
This is approximately 5.177378.
-- edp
|
| I wrote the following BASIC program. It seems to concur with the answer
given above. n is the number of experiments, where an experiment is eating
a whole handful of nuts.
a is the accumulated average of how many times the unopenable nut is picked.
l is the number of nuts left in the pocket for the current experiment.
c is the count of how many times the unopenable nut has been picked so far
in the current experiment.
r is always chosen as a random number between 1 and l inclusive. Without
loss of generality, I always represent a pick of the unopenable nut by the
random number coming out equal to l.
For the heck of it, I start with an answer of -1000 which quickly converges
towards the expected answer.
The program prints out two columns. The first column is always the result
of the latest experiment. The second column is the average so far.
--------------------------------------cut here--------------------------------
10 n = 1
20 a = -1000
65 l = 100
70 c = 0
80 r = 1 + int (rnd * l)
90 if r = l then goto 500
100 l = l - 1
110 if l = 1 then goto 600
120 goto 80
500 c = c + 1
510 goto 80
600 a = (a*n+c)/(n+1)
610 n = n + 1
620 print c, a
630 goto 65
|
| Something's been bothering me about edp's answer, and I haven't said anything
about it, because I see no real flaw in his math.
Consider 2 nuts in the pocket (no wisecracks please :-). According to edp,
the expected number of times the unopenable one will be picked is 1/2.
Intuitively (to me anyway), half the time the good nut will be picked
first. So half the time the unopenable one will be picked 0 times.
The other half the time, the unopenable one will be picked first, after
which IF the good nut were guaranteed to be picked next, we'd have an
answer of 1/2. BUT the good nut is NOT guaranteed to be picked next, so
it seems to me that the answer is actually a bit LARGER than 1/2.
Ignoring edp's math, I figure the answer like this:
Half the time, we get the good nut first, so we have
a = 1/2 * 0 + . . . (where a is the total number of times unopenable nut
is picked by the time it's the only one left)
The other half the time, which totals to 1/2, half the time we get the
bad nut again, and half the time we get the good one. So
a = 1/2 * 0 + 1/4 * 1 + . . .
Continuing, the total answer looks like:
a = 1/4 * 1 + 1/8 * 2 + 1/16 * 3 . . .
hence
a = 1/4 + 2/8 + 3/16 + 4/32 + 5/64 + 6/128 + 7/256 + 8/512 + 9/1024 . . .
or
a = 1/2 + 3/16 + 4/32 + 5/64 + 6/128 + 7/256 + 8/512 + 9/1024 . . .
Let's reduce where we can, just to see what it looks like:
a = 1/2 + 3/16 + 1/8 + 5/64 + 3/64 + 7/256 + 1/64 + 9/1024 + 10/2048 + 11/4096..
Reduction shows some common denominators, so let's collect and use extra
room to show more terms:
a = 1/2 + 5/16 + 9/64 + 9/1024 + 5/1024 + 11/4096 + 12/8192 + 13/16384 +...
a = 1/2 + 5/16 + 9/64 + 14/1024 + 11/4096 + . . .
Does anyone know what this adds to ?
Actually, my BASIC program seemed to be converging to 5.2xxx instead of
edp's answer of 5.17xxx. I didn't take too much stock of it since my program
is quite likely susceptible to all sorts of computer squaring errors (a joke
on "rounding" errors :-). However, perhaps the discrepancy supports my
reasoning ? In which case what's wrong with edp's math ?
/eric
|
| I suppose I was asking for POSTPISCHIL or edp even though I gave a reference to
my note in WHOAREYOU (note 329) the first few times I entered notes here.
Please feel free to call me Eric.
The function I describe which gives the expected number of times the unopenable
nut will be selected with a given number of nuts is 1/(n-1), not 1/n. Thus,
when there are two nuts, the mean is one.
The series Eric Osman (hmmm, maybe I should remain edp) brought up,
0/2 + 1/4 + 2/8 + 3/16 + . . . + i/2^(i+1) + . . .,
can be rewritten
1/4 + 1/8 + 1/16 + 1/32 + . . .
+ 1/8 + 1/16 + 1/32 + . . .
+ 1/16 + 1/32 + . . .
+ 1/32 + . . .
. . .
You should be aware that this is cheating slightly -- everything after the
first ". . ." is done after an infinite number of additions, so this is not
well-defined. But it works, and we would get the same answer if it were done
correctly.
Anyway, each of the above lines is a geometric series. The sum of the first
is 1/2. The next is 1/4, followed by 1/8, and so on. This is also a
geometric series, and its sum is one, which is what my function predicts.
-- edp
|