Author: Andrew Dados
Date: 07:57:44 02/08/00
Go up one level in this thread
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-
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.