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

Home > Probability
Evaluate further probabilities (Posted on 2016-02-03) Difficulty: 3 of 5
Generate a number by the following process:

1) Pick a number from 0 to 9 for the first digit. If the number is 0 the process terminates with the number 0.
2) Pick another number from 0 to 9. If it is greater than the previous number, append it to the previous to create a number with one more digit. If not then terminate the process.
3) Repeat step 2 until the process terminates.

The resulting number will be n digits long and have strictly increasing digits where n is an integer from 0 to 9.

Find the probability distribution for n.

Notes: Numbers are chosen with a uniform random probability.
0 is considered a 0 digit number.
This is an extension of Evaluate probabilities.

No Solution Yet Submitted by Jer    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution computer-aided solution Comment 1 of 1
 Probability of reaching, at least temporarily, any given length and final digit:
         
     \   last digit
lngth \   0       1       2       3       4       5       6       7       8       9
 1    0.00000 0.10000 0.10000 0.10000 0.10000 0.10000 0.10000 0.10000 0.10000 0.10000
 2    0.00000 0.00000 0.01000 0.02000 0.03000 0.04000 0.05000 0.06000 0.07000 0.08000
 3    0.00000 0.00000 0.00000 0.00100 0.00300 0.00600 0.01000 0.01500 0.02100 0.02800
 4    0.00000 0.00000 0.00000 0.00000 0.00010 0.00040 0.00100 0.00200 0.00350 0.00560
 5    0.00000 0.00000 0.00000 0.00000 0.00000 0.00001 0.00005 0.00015 0.00035 0.00070
 6    0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00001 0.00002 0.00006
 7    0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000
 8    0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000
 9    0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000
 
or in rational form: 
 
   1       2     3      4        5       6          7             8            9
 1/10   1/10   1/10   1/10     1/10     1/10       1/10         1/10        1/10   
 0      1/100  1/50   3/100    1/25     1/20       3/50         7/100       2/25   
 0         0   1/1000 3/1000   3/500    1/100      3/200        21/1000     7/250  
 0         0    0     1/10000  1/2500   1/1000     1/500        7/2000      7/1250 
 0         0    0       0    1/100000   1/20000    3/20000      7/20000      7/10000 
 0         0    0       0         0    1/1000000   3/500000    21/1000000   7/125000   
 0         0    0       0         0       0        1/10000000  7/10000000   7/2500000     
 0         0    0       0         0       0         0          1/100000000   1/12500000   
 0         0    0       0         0       0         0                 0      1/1000000000   
 
 
 Then, per row, are the sums of the given probability above, multiplied by the probability that the number would terminate at that point: 
 
 1   27/50           =   0.54 
 2   69/250          =   0.276 
 3   357/5000        =   0.0714 
 4   567/50000       =   0.01134 
 5   147/125000      =   0.001176 
 6   201/2500000     =   0.0000804 
 7   351/100000000   =   0.00000351 
 8   89/1000000000   =   0.000000089 
 9   1/1000000000    =   0.000000001 
 
These do add up to 0.9, and with the 1/10 probability of terminating at zero, comes to 1.

For example, the probability of length 1 was found by:

1/10 * 2/10 + 1/10 * 3/10 + 1/10 * 4/10 + ... + 1/10 * 9/10 + 1/10 * 10/10

= 54/100 = 27/50

The probability of length 2 by:

1/100 * 3/10 + 1/50 * 4/10 + 3/100 * 5/10 + ... + 7/100 * 9/10 + 2/25 * 10/10 = 69/250

in each case, each term being the probability of reaching that length/terminal-digit combination multiplied by the probability of actually terminating given that that was the terminal digit at that point.

etc.


    4   kill "evalfurt.txt"
    5   open "evalfurt.txt" for output as #2
   10   dim Lastdig(10,9)
   20   Lastdig(0,0)=1
   30   for Lngth=1 to 9
   40     for PrevHi=0 to 8
   50       for NewHi=PrevHi+1 to 9
   60          Lastdig(Lngth,NewHi)=Lastdig(Lngth,NewHi)+Lastdig(Lngth-1,PrevHi)//10
   70       next NewHi
   80     next PrevHi
   90   next Lngth
  100   for Lngth=1 to 9
  110     for Lst=0 to 9
  120       print #2,using(2,5),Lastdig(Lngth,Lst)/1;
  130     next Lst
  140     print #2,
  150   next Lngth
  155   Tprob=1//10
  160   for Lngth=1 to 9
  170     Prob=0
  180     for Lst=1 to 9
  190       Prob=Prob+Lastdig(Lngth,Lst)*(Lst+1)//10
  200     next
  210     print #2,Lngth,Prob,Prob/1:Tprob=Tprob+Prob
  220   next Lngth
  230   print #2,Tprob
  360   for Lngth=1 to 9
  380     for Lst=1 to 9
  390       print #2,Lastdig(Lngth,Lst);" ";
  400     next
  410     print #2,
  420   next Lngth


Simulation results:

length  count
0        9974
1       53914
2       27606
3        7285
4        1085
5         125
6          11
7           0
8           0
9           0

DefDbl A-Z
Dim crlf$, lenct(9)


Private Sub Form_Load()
 Form1.Visible = True
 
 Text1.Text = ""
 crlf = Chr$(13) + Chr$(10)
 Randomize
 For tr = 1 To 100000
   l = 0
   dig = Int(10 * Rnd(2))
   If dig = 0 Then
     lenct(0) = lenct(0) + 1
   Else
     l = 1
     Do
       prevdig = dig
       dig = Int(10 * Rnd(1))
       If dig <= prevdig Then Exit Do
       l = l + 1
     Loop
     lenct(l) = lenct(l) + 1
   End If
 Next

 For l = 0 To 9
   Text1.Text = Text1.Text & l & mform(lenct(l), "#######0") & crlf
 Next

 Text1.Text = Text1.Text & crlf & " done"
  
End Sub

Function mform$(x, t$)
  a$ = Format$(x, t$)
  If Len(a$) < Len(t$) Then a$ = Space$(Len(t$) - Len(a$)) & a$
  mform$ = a$
End Function

repeated runs:

0   10192
1   53753
2   27646
3    7133
4    1143
5     121
6      12
7       0
8       0
9       0

0   10126
1   53993
2   27541
3    7069
4    1151
5     116
6       4
7       0
8       0
9       0

0   10077
1   54029
2   27518
3    7119
4    1131
5     114
6      11
7       1
8       0
9       0







  Posted by Charlie on 2016-02-03 11:18:01
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 (3)
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