Author: Ricardo Gibert
Date: 08:23:32 02/08/00
Go up one level in this thread
On February 08, 2000 at 10:57:44, Andrew Dados wrote: >On February 08, 2000 at 09:25:32, Tijs van Dam wrote: > >>On February 08, 2000 at 08:36:27, Andrew Dados wrote: >> >>>On February 08, 2000 at 08:05:40, Les Fernandez wrote: >>> >>>>Does anyone know given a string of "x" numbers (ie 237496) how large must a >>>>string of random numbers be so that you can have a 95% chance of finding that >>>>exact string within the larger string of numbers. If there is a way that I can >>>>calculate it please provide info. Keep in mind although the above example >>>>contains 6 numbers it is used only for an example so that I may understand the >>>>concept. I am interested in being able to calculate how long the length of the >>>>longer string needs to be for numbers up to about 60 in length if this is >>>>possible. Thanks >>>> >>>>Les >>> >>>My naive approach: given x: length of your substring and y: length of string... >>>(1-1/x^10) - probability that there is *no* match in one slot; >>>(1-1/x^10)^n - probability of *no* match in n slots; >>>1-(1-1/x^10)^n - probability of at least one match in n slots...n slots means: >>>y=n+x; >>>so you need to solve equation: >>>1-(1-1/x^10)^(y-x)>=0.95 >>>given I didn't have my coffee yet it's all correct with some 0.15% chance..:) >> >>I think you mixed some variables and numbers here. The probability of having a >>number the same is 1/10, so for a string of x numbers it is 1/10^x and not >>1/x^10. Without coffee, I would have made the same mistake :) >> >>When finding a string of 10 in 100, there are 91 possible starting points (there >>a 90 numbers before the last, so the last one is the 91th). So n=y-x+1. >> >>Therefore, you need to calculate y for >> >>1-(1-1/10^x)^(y-x+1)>=0.95 for the smallest integer y that is possible >> >>I did have my coffee :) and i think the answer should be >> >>y=x-1+log(0.05)/log(1-1/10^x) and round up. >> >>If you want another chance than 0.95, say p, you need to replace 0.05 with >>(1-p). >> >>To find a string of 6 with a chance of 0.95, you need a larger string of 2995736 >>numbers. To find a string of 60 with equal chance, you need a larger string of >>about -[E- numbers. My handcalculator wouldn't do 1/10^60 :) >> >>Greets, >>Tijs > >Below are string lengths for 0.95 chance of finding at least one match for >substring lengths 1-10: (above formula run in Mathematica): > >28.4332 >299.073 >2996.23 >29958.8 >299576. >2.99574 10^6 >2.99573 10^7 >2.99573 10^8 >2.99573 10^9 >2.99573 10^10 > >Looks like 3*10^n is a good approximation of our formula. > >-Andrew- It is often worthwhile considering a simpler problem. What are the _odds_ that a 3-bit binary number contains a given 2-bit binary substring? If the substring is 11 or 00 then it is 3:5. If it is 01 or 10 then it is 4:4. --- 00 01 10 11 000 1 001 2 1 010 2 1 011 3 1 100 3 2 101 4 3 110 4 2 111 3
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.