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.
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 |
computer-aided solution
