Math Is Fun Forum

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

You are not logged in.

#1 2012-07-26 01:46:47

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

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?

This has an analytic solution given in the other thread.

http://www.mathisfunforum.com/viewtopic … 45#p227545

This thread has been created to list the various programming solutions to the problem. Please only programming here. All analytical answers can go in the other thread.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#2 2012-07-26 02:02:52

gAr
Member
Registered: 2011-01-09
Posts: 3,482

Re: An expectation problem:

To check our analytic solution, we may try a simulation:

Here is an example of doing it in python

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."

Offline

#3 2012-07-26 08:28:21

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

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.

fubar[l_]:=Module[{h1,g1},
g1=l;
h1=RandomInteger[{1,Length[l]}];
g1[[h1]]=1;
g1]

Now run this:

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.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#4 2012-07-27 05:40:29

gAr
Member
Registered: 2011-01-09
Posts: 3,482

Re: An expectation problem:

In R, we may speed up the simulation using the sample function:

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."

Offline

#5 2012-07-29 02:08:39

phrontister
Real Member
From: The Land of Tomorrow
Registered: 2009-07-12
Posts: 4,804

Re: An expectation problem:

Hi Bobby,

The Olympic Games have got my attention for now but I thought I'd post this LB attempt anyway. It's a bit scratchy, but it works...so I'm happy enough.

Some better coder would be able to improve its efficiency and speed (the 10000 cycles took just under an hour!). Compared with yours and gAr's solutions, mine seems to be stuck way back in the Dark Ages!

Results: My test run of 10000 cycles yielded an average of 223 picks per cycle.

Got some long nights of TV viewing ahead! sleep

    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

Offline

#6 2012-07-29 02:15:50

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: An expectation problem:

Hi phrontister;

It got the right answer! Efficiency takes second place to that.
Very good work.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#7 2012-07-29 02:39:15

anonimnystefy
Real Member
From: Harlan's World
Registered: 2011-05-23
Posts: 16,049

Re: An expectation problem:

Hi

I get the answer of 2.23058399999999E+002:approx 223.0584 with:

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 (2012-07-29 03:30:03)


“Here lies the reader who will never open this book. He is forever dead.
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Offline

#8 2012-07-29 02:42:15

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: An expectation problem:

Hi;

That is very good!


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#9 2012-07-29 02:45:34

anonimnystefy
Real Member
From: Harlan's World
Registered: 2011-05-23
Posts: 16,049

Re: An expectation problem:

What is the actual number, again?


“Here lies the reader who will never open this book. He is forever dead.
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Offline

#10 2012-07-29 02:53:41

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: An expectation problem:


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#11 2012-07-29 02:57:37

anonimnystefy
Real Member
From: Harlan's World
Registered: 2011-05-23
Posts: 16,049

Re: An expectation problem:

And in the decimal form?


“Here lies the reader who will never open this book. He is forever dead.
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Offline

#12 2012-07-29 02:58:47

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: An expectation problem:

Hi;


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#13 2012-07-29 03:02:29

anonimnystefy
Real Member
From: Harlan's World
Registered: 2011-05-23
Posts: 16,049

Re: An expectation problem:

I ran the simulation once again and got the same number as before.


“Here lies the reader who will never open this book. He is forever dead.
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Offline

#14 2012-07-29 03:05:27

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: An expectation problem:

The exact same number? Then you have a bug in the code.

See you in a bit. Chore time!


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#15 2012-07-29 03:31:49

anonimnystefy
Real Member
From: Harlan's World
Registered: 2011-05-23
Posts: 16,049

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.


“Here lies the reader who will never open this book. He is forever dead.
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Offline

#16 2012-07-29 06:27:19

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

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.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#17 2012-07-29 07:25:46

anonimnystefy
Real Member
From: Harlan's World
Registered: 2011-05-23
Posts: 16,049

Re: An expectation problem:

One was something aroung 222.8 and another one was around 222.9. Let me get the actual figures.


“Here lies the reader who will never open this book. He is forever dead.
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Offline

#18 2012-07-29 07:52:39

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

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.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#19 2012-07-29 07:59:06

anonimnystefy
Real Member
From: Harlan's World
Registered: 2011-05-23
Posts: 16,049

Re: An expectation problem:

Here is what I got now:

 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 (2012-07-29 08:04:28)


“Here lies the reader who will never open this book. He is forever dead.
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Offline

#20 2012-07-29 08:02:29

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: An expectation problem:

That is about right.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#21 2012-07-29 08:03:19

anonimnystefy
Real Member
From: Harlan's World
Registered: 2011-05-23
Posts: 16,049

Re: An expectation problem:

I will add a few more values in a minute.


“Here lies the reader who will never open this book. He is forever dead.
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Offline

#22 2012-07-29 08:08:11

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

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.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#23 2012-07-29 08:11:00

anonimnystefy
Real Member
From: Harlan's World
Registered: 2011-05-23
Posts: 16,049

Re: An expectation problem:

Did you see the edited post 19?


“Here lies the reader who will never open this book. He is forever dead.
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Offline

#24 2012-07-29 08:13:17

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

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.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#25 2012-07-29 08:14:45

anonimnystefy
Real Member
From: Harlan's World
Registered: 2011-05-23
Posts: 16,049

Re: An expectation problem:

Standard deviation?


“Here lies the reader who will never open this book. He is forever dead.
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Offline

Board footer

Powered by FluxBB