Author: Tijs van Dam
Date: 06:25:32 02/08/00
Go up one level in this thread
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
This page took 0.01 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.