Discussion about math, puzzles, games and fun. Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ ¹ ² ³ °
 

You are not logged in. #1 20120726 23:46:47
An expectation problem:A list of 1000 zeroes is created called M. A random number is picked from 1 to 1000. Each time one of these is picked, the zero in the list ( at that index ) is changed to a 1. For instance if the random number is 276 then M[276]=1. What is the average number of random numbers that must be picked to have 200 ones in the list? In mathematics, you don't understand things. You just get used to them. I have the result, but I do not yet know how to get it. All physicists, and a good many quite respectable mathematicians are contemptuous about proof. #2 20120727 00:02:52
Re: An expectation problem:To check our analytic solution, we may try a simulation: Code:from random import randint zeroes = [0]*1000 tries = 10000 hit = 0 for i in range(tries): while sum(zeroes) < 200: zeroes[randint(0, 999)] = 1 hit += 1 zeroes = [0]*1000 print hit / float(tries) "Believe nothing, no matter where you read it, or who said it, no matter if I have said it, unless it agrees with your own reason and your own common sense"  Buddha? "Data! Data! Data!" he cried impatiently. "I can't make bricks without clay." #3 20120727 06:28:21
Re: An expectation problem:This idea uses a different approach. Instead of finding the number of picks it uses the analytical answer and then uses a simulation to test if it is correct. Code:fubar[l_]:=Module[{h1,g1}, g1=l; h1=RandomInteger[{1,Length[l]}]; g1[[h1]]=1; g1] Now run this: Code:Table[s=Table[0,{1000}];Count[Table[s=fubar[s],{223}]//Last,1],{100}]//Mean//N The output is 200.03. In mathematics, you don't understand things. You just get used to them. I have the result, but I do not yet know how to get it. All physicists, and a good many quite respectable mathematicians are contemptuous about proof. #4 20120728 03:40:29
Re: An expectation problem:In R, we may speed up the simulation using the sample function: Code:sa < c(1:1000)*0 trials < 10000 hit < 0 for (i in 1:trials) { sa[sample(1:1000, 200, replace = TRUE)] < 1 hit < hit + 200 while (sum(sa) < 200) { sa[sample(1:1000,1)] < 1 hit < hit + 1 } sa < c(1:1000)*0 } print (hit / trials) "Believe nothing, no matter where you read it, or who said it, no matter if I have said it, unless it agrees with your own reason and your own common sense"  Buddha? "Data! Data! Data!" he cried impatiently. "I can't make bricks without clay." #5 20120730 00:08:39
Re: An expectation problem:Hi Bobby, Code:FOR cycles = 1 TO 10000 M$ = "" FOR zeroes = 1 TO 1000 M$ = M$ + "0" NEXT zeroes 'initial 199 picks FOR picks = 1 TO 199 random = INT(RND(1) * 1000) + 1 M$ = LEFT$(M$,random  1) + "1" + RIGHT$(M$,1000  random) NEXT picks picks = picks  1 [morepicks] FOR count = 1 TO 1000 sum = sum + VAL(MID$(M$,count,1)) NEXT count IF sum = 200 THEN GOTO [nextcycle] random = INT(RND(1) * 1000) + 1 M$ = LEFT$(M$,random  1) + "1" + RIGHT$(M$,1000  random) sum = 0 picks = picks + 1 GOTO [morepicks] [nextcycle] totalpicks = totalpicks + picks NEXT cycles cycles = cycles  1 'results PRINT "Cycles: ";cycles PRINT "Total picks: ";totalpicks PRINT "Average picks per cycle: ";totalpicks / cycles END "The good news about computers is that they do what you tell them to do. The bad news is that they do what you tell them to do."  Ted Nelson #6 20120730 00:15:50
Re: An expectation problem:Hi phrontister; In mathematics, you don't understand things. You just get used to them. I have the result, but I do not yet know how to get it. All physicists, and a good many quite respectable mathematicians are contemptuous about proof. #7 20120730 00:39:15
Re: An expectation problem:Hi Code:program Expectation; type arr=array[1..1000] of boolean; function count(a:arr):integer; var i,cnt:integer; begin cnt:=0; for i:=1 to 1000 do cnt:=cnt+ord(a[i]); count:=cnt; end; var a:arr; i,j,number:integer; expect:real; begin randomize; expect:=0; for i:=1 to 10000 do begin for j:=1 to 1000 do a[j]:=false; number:=0; while count(a)<200 do begin a[random(1000)+1]:=true; number:=number+1; end; expect:=expect+number; end; writeln(expect/10000); end. Last edited by anonimnystefy (20120730 01:30:03) The limit operator is just an excuse for doing something you know you can't. “It's the subject that nobody knows anything about that we can all talk about!” ― Richard Feynman “Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment #8 20120730 00:42:15
Re: An expectation problem:Hi; In mathematics, you don't understand things. You just get used to them. I have the result, but I do not yet know how to get it. All physicists, and a good many quite respectable mathematicians are contemptuous about proof. #9 20120730 00:45:34
Re: An expectation problem:What is the actual number, again? The limit operator is just an excuse for doing something you know you can't. “It's the subject that nobody knows anything about that we can all talk about!” ― Richard Feynman “Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment #11 20120730 00:57:37
Re: An expectation problem:And in the decimal form? The limit operator is just an excuse for doing something you know you can't. “It's the subject that nobody knows anything about that we can all talk about!” ― Richard Feynman “Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment #13 20120730 01:02:29
Re: An expectation problem:I ran the simulation once again and got the same number as before. The limit operator is just an excuse for doing something you know you can't. “It's the subject that nobody knows anything about that we can all talk about!” ― Richard Feynman “Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment #14 20120730 01:05:27
Re: An expectation problem:The exact same number? Then you have a bug in the code. In mathematics, you don't understand things. You just get used to them. I have the result, but I do not yet know how to get it. All physicists, and a good many quite respectable mathematicians are contemptuous about proof. #15 20120730 01:31:49
Re: An expectation problem:Changed my code a little, but now it always gives output less then, but close to the actual answer. Haven't gotten a number over 223 with the new code. The limit operator is just an excuse for doing something you know you can't. “It's the subject that nobody knows anything about that we can all talk about!” ― Richard Feynman “Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment #16 20120730 04:27:19
Re: An expectation problem:What is the output of a couple of runs? In mathematics, you don't understand things. You just get used to them. I have the result, but I do not yet know how to get it. All physicists, and a good many quite respectable mathematicians are contemptuous about proof. #17 20120730 05:25:46
Re: An expectation problem:One was something aroung 222.8 and another one was around 222.9. Let me get the actual figures. The limit operator is just an excuse for doing something you know you can't. “It's the subject that nobody knows anything about that we can all talk about!” ― Richard Feynman “Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment #18 20120730 05:52:39
Re: An expectation problem:That seems reasonable. Over many runs you will average out to around 223. In mathematics, you don't understand things. You just get used to them. I have the result, but I do not yet know how to get it. All physicists, and a good many quite respectable mathematicians are contemptuous about proof. #19 20120730 05:59:06
Re: An expectation problem:Here is what I got now: Code:2.23019100000000E+002 2.23065900000000E+002 2.23091500000000E+002 2.23027800000000E+002 2.23021100000000E+002 2.22971200000000E+002 2.23048500000000E+002 2.23036800000000E+002 2.22945700000000E+002 2.23067400000000E+002 2.23025500000000E+002 2.23024000000000E+002 Last edited by anonimnystefy (20120730 06:04:28) The limit operator is just an excuse for doing something you know you can't. “It's the subject that nobody knows anything about that we can all talk about!” ― Richard Feynman “Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment #20 20120730 06:02:29
Re: An expectation problem:That is about right. In mathematics, you don't understand things. You just get used to them. I have the result, but I do not yet know how to get it. All physicists, and a good many quite respectable mathematicians are contemptuous about proof. #21 20120730 06:03:19
Re: An expectation problem:I will add a few more values in a minute. The limit operator is just an excuse for doing something you know you can't. “It's the subject that nobody knows anything about that we can all talk about!” ― Richard Feynman “Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment #22 20120730 06:08:11
Re: An expectation problem:The answer is a little more than 223, I think. In mathematics, you don't understand things. You just get used to them. I have the result, but I do not yet know how to get it. All physicists, and a good many quite respectable mathematicians are contemptuous about proof. #23 20120730 06:11:00
Re: An expectation problem:Did you see the edited post 19? The limit operator is just an excuse for doing something you know you can't. “It's the subject that nobody knows anything about that we can all talk about!” ― Richard Feynman “Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment #24 20120730 06:13:17
Re: An expectation problem:Yes, it looks fine to me. The sd is very small on this problem. In mathematics, you don't understand things. You just get used to them. I have the result, but I do not yet know how to get it. All physicists, and a good many quite respectable mathematicians are contemptuous about proof. #25 20120730 06:14:45
Re: An expectation problem:Standard deviation? The limit operator is just an excuse for doing something you know you can't. “It's the subject that nobody knows anything about that we can all talk about!” ― Richard Feynman “Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment 