All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Probability
The Random Problem (Posted on 2004-02-09) Difficulty: 4 of 5
Suppose there are 20 problems on the site the Sunday evening a user looks at the site the first time. She doesn't read the newest problem of the day, but instead ONLY reads problems that come up on the "Random Problem" page. She reads 5 random problems each day, always in the evening. The only problem is she can see the same problem more than once.

The other problem is problems continue to come in from the infinite queue. Two per week day and one per weekend.

What is the probability she will have read all the problems after her next Sunday evening check? What is the probability she will have read all the problems after the Sunday evening after that?

Note: The problems displayed when you click on "Random Problem" are independent of each other. There isn't anything to make sure that you are getting five different problems if you click on random problem five times.

See The Solution Submitted by Gamer    
Rating: 4.1429 (7 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution solution | Comment 1 of 8
This problem presents a Markov chain of probabilities that the user will have x unseen problems at any given stage of the two-week period. At each time there is a certain probability there are no problems left unseen, a certain probability that 1 is still unseen, etc. Call these probabilities u(0), u(1), etc. They change as time progresses.

After that first Sunday's problem posting, there are 20 problems on the site, all of them unseen by this user. So the probability that 20 are unseen--i.e., u(20), at this stage, is 1 and all the other probabilities are zero.

Each time the user looks at a random problem, the probability that the number of unseen problems goes down by 1 is just the number of unseen problems divided by the total number of problems on the site. So, if n is the number of problems on the site at a given stage, the new value for each u(i) is equal to the old value of u(i) times (1-u(i))/n plus the old value of u(i+1) times u(i+1)/n, as each old probability has conditional probabilities of u(i)/n of going one lower, or (1-u(i))/n of remaining at the same value.

Of course every time a puzzle is posted, it is unseen by the user, so each probability is advanced one position in the array, that is each new u(i+1) is equal to the old u(i).

When two problems are posted, it's perfectly OK to transition the new u(i+2) = the old u(i) for all i. However, you can't do that when transitioning for the user's seeing new problems, as the transition probabilities change, and each transition has to be done individually, five times per evening.

The program shown below computes this Markov chain for the 15 days asked for, and shows the reciprocal of the probability u(0) (i.e., the probability that zero remain unseen), at the end of days 8 and 15.

The results are:

15 16 17 18 20
1 .581 .363 .053 .002

12 13 14 15 16 17 22
2 .084 .298 .365 .197 .050 .006

9 10 11 12 13 14 15 16 17 24
3 .003 .029 .122 .257 .298 .197 .076 .017 .002

8 9 10 11 12 13 14 15 16 17 26
4 .004 .027 .094 .199 .266 .228 .126 .045 .010 .001

7 8 9 10 11 12 13 14 15 16 17 28
5 .003 .015 .054 .133 .218 .244 .188 .099 .036 .009 .001

6 7 8 9 10 11 12 13 14 15 16 17 30
6 .001 .005 .023 .070 .146 .217 .228 .171 .092 .035 .009 .002

5 6 7 8 9 10 11 12 13 14 15 16 31
7 .001 .006 .024 .068 .140 .207 .222 .175 .100 .042 .013 .003

4 5 6 7 8 9 10 11 12 13 14 15 16 32
8 .001 .004 .018 .055 .119 .189 .220 .189 .121 .057 .020 .005 .001
563860447.1492637

5 6 7 8 9 10 11 12 13 14 15 16 34
9 .003 .013 .041 .097 .167 .212 .202 .144 .077 .031 .009 .002

5 6 7 8 9 10 11 12 13 14 15 16 17 36
10 .002 .008 .029 .075 .141 .198 .209 .167 .102 .047 .017 .004 .001

5 6 7 8 9 10 11 12 13 14 15 16 17 38
11 .001 .005 .020 .055 .113 .176 .207 .187 .129 .068 .028 .009 .002

5 6 7 8 9 10 11 12 13 14 15 16 17 18 40
12 .001 .003 .012 .038 .087 .149 .196 .198 .155 .094 .044 .016 .005 .001

6 7 8 9 10 11 12 13 14 15 16 17 18 42
13 .002 .008 .025 .063 .120 .176 .200 .177 .122 .066 .028 .009 .002

5 6 7 8 9 10 11 12 13 14 15 16 17 18 43
14 .001 .004 .014 .041 .088 .147 .190 .193 .153 .096 .047 .019 .006 .001

5 6 7 8 9 10 11 12 13 14 15 16 17 18 44
15 .001 .006 .022 .056 .110 .166 .195 .181 .132 .077 .035 .013 .004 .001
1291015550.712306

-------
The numbers in the left column are the day numbers. The numbers on the right are the total number of problems on the site at the end of that day. The top row of numbers in the middle for each day show the values of x for which u(x)>.0005 for that day, and just below that is the corresponding u(x).

We see that the probability the user would have seen all the problems (non left unseen) on day 8 would be 1/563,860,447. At the end of day 15 it would be 1/1,291,015,551.

Note that on the first day, the most likely unseen amount is 15, but the drop from day to day slows down quite soon.

The program is:

CLS
DEFDBL A-Z
maxSub = 100
DIM unseen(maxSub), newRow(maxSub)
'unseen contains the prob that that many (its subscript) are still unseen

totProbs = 19
unseen(19) = 1

FOR day = 1 TO 15
  IF day MOD 7 = 1 OR day MOD 7 = 0 THEN
    totProbs = totProbs + 1
    shift = 1
  ELSE
    totProbs = totProbs + 2
    shift = 2
  END IF
  FOR i = maxSub TO 0 STEP -1
    IF i >= shift THEN
     unseen(i) = unseen(i - shift)
    ELSE
     unseen(i) = 0
    END IF
  NEXT
  FOR rProb = 1 TO 5
    REDIM newRow(maxSub)
    FOR i = 0 TO totProbs
      pNew = i / totProbs
      IF i > 0 THEN newRow(i - 1) = newRow(i - 1) + pNew * unseen(i)
      newRow(i) = newRow(i) + (1 - pNew) * unseen(i)
    NEXT
    FOR i = 0 TO totProbs
      unseen(i) = newRow(i)
    NEXT
  NEXT
 
  FOR i = 0 TO totProbs
   IF unseen(i) >= .0005 THEN
    PRINT USING " ##"; i;
   END IF
  NEXT
  PRINT TAB(75); totProbs
  PRINT USING "##"; day;
  FOR i = 0 TO totProbs
   IF unseen(i) >= .0005 THEN
    PRINT USING " .###"; unseen(i);
   END IF
  NEXT
  PRINT
  IF day MOD 7 = 1 AND day > 1 THEN
    PRINT 1 / unseen(0)
  END IF
  PRINT
NEXT


  Posted by Charlie on 2004-02-09 12:28:05
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (7)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information