[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

Title:Mathematics at DEC
Moderator:RUSURE::EDP
Created:Mon Feb 03 1986
Last Modified:Fri Jun 06 1997
Last Successful Update:Fri Jun 06 1997
Number of topics:2083
Total number of notes:14613

796.0. "USENET: A probability problem" by ZFC::DERAMO (Daniel V. D'Eramo) Wed Dec 02 1987 21:19

Newsgroups: sci.math
Path: decwrl!labrea!jade!ucbcad!ames!nrl-cmf!ukma!psuvm.bitnet!cunyvm!byuvax!forcader
Subject: Simple problem???
Posted: 29 Nov 87 22:52:49 GMT
Organization: 
 
Here's a "simple" problem for which I don't know a simple answer.  Is
there one?
     
   Let  k, n  be positive integers,  1 < k < n.    For  i = 1, 2, 3, ...
let  a(i)  be chosen randomly from the set  {1,2, ...,k}.
   Let  m  be the smallest positive integer for which the sum
 
              a(1) + a(2) +  . . .  + a(m)
 
 is congruent to zero modulo  n.  It isn't difficult to show that  m
 is, with probability one, defined.  What is the average value of  m?
T.RTitleUserPersonal
Name		DateLines
796.1CLT::GILBERTBuilderThu Dec 03 1987 14:513
To get started, first try the simpler problem with k = n.

BTW, this problem feels suspiciously akin to the one in 639.2.
796.2Yes, just like 639CLT::GILBERTBuilderMon Dec 07 1987 15:3425
Let E(m) = expected # of random selections (from the set {1..k}),
		starting with Sum(a(i)) congruent to m modulo n.
		Note that the subscripts are all modulo n.

Then
	E(0) = 1 + E(1)/k + E(2)/k + ... + E(k)/k	(must choose once)
	E(1) = 1          + E(2)/k + ... + E(k)/k + E(1+k)/k
	...
	E(i) = 1 +   Sum  E(i+j)/k
		    j=1..k
		i+j <> 0 mod n
	...
	E(n-1) = 1 + E(1)/k + ... E(k-1)/k

Summing both sides of these n equations, we get:

	   Sum   E(i) = n +    Sum   k* E(i)/k
	i=0..n-1            i=0..n-1
			  i <> 0 mod n

So that
	   Sum   E(i) = n +    Sum   E(i)  - E(0)
	i=0..n-1            i=0..n-1
and
	E(0) = n
796.3Oh, now I get it.ZFC::DERAMOMy very own personal nameThu Dec 10 1987 21:4940
     It took me a while, but I finally figured out what you were
     saying in .-1.  For those who still don't believe that the
     expected value is n:

                                     n   k
                                    -------
     The average of 1000 trials for (10, 2) was 10.222.
     The average of 1000 trials for (10, 3) was  9.917.
     The average of 1000 trials for (10, 4) was 10.127.
     The average of 1000 trials for (10, 5) was  9.763.
     The average of 1000 trials for (10, 6) was  9.559.
     The average of 1000 trials for (10, 7) was  9.788.
     The average of 1000 trials for (10, 8) was 10.247.
     The average of 1000 trials for (10, 9) was 10.022.

     Try it again, with n prime:

     The average of 1000 trials for (13, 2) was 12.975.
     The average of 1000 trials for (13, 3) was 13.422.
     The average of 1000 trials for (13, 4) was 13.037.
     The average of 1000 trials for (13, 5) was 13.035.
     The average of 1000 trials for (13, 6) was 13.196.
     The average of 1000 trials for (13, 7) was 13.161.
     The average of 1000 trials for (13, 8) was 13.038.
     The average of 1000 trials for (13, 9) was 14.271.
     The average of 1000 trials for (13,10) was 12.752.
     The average of 1000 trials for (13,11) was 12.742.
     The average of 1000 trials for (13,12) was 13.213.

     This n has lots of factors (k is random):

     The average of 1000 trials for (36, 4) was 35.313.
     The average of 1000 trials for (36,23) was 36.890.
     The average of 1000 trials for (36,28) was 36.164.
     The average of 1000 trials for (36, 5) was 37.466.
     The average of 1000 trials for (36, 4) was 37.087.

     Dan

     P.S.  The variance appears to be rather high.
796.4CLT::GILBERTBuilderFri Dec 11 1987 13:251
    Alright, what is the variance for this?