I have a string of randomly generated numbers between 1-4. i.e.
234123423321124........
I want to know what the average "number of numbers" is before the first four numbers repeat themselves.
I have an idea myself but want some other boffins to have a look as my method seems messy.
[Edited on 24/3/10 by cd.thomson]
Never liked probability much, I,ll give it a go though -
To generate a matching number you would traditionally say it would be 1 in 256.
However, as this is a constant string an the first number would have to be correct before you start to look for the other three matching I would go
for 1 in 64.
yes i got 1 in 256 and suspected having a fixed four digits to begin with would scupper this.
I expressed it as
(0.25^4)n = 1
n = 256
How would you express it considering the constant start?
This is actually a genetics question I have heavily simplified. The second part of the question asks what if it was a 6 digit number you were
attempting to match.
Obviously my (0.25^6)n = 1 is wrong...
I've just written a program to test.
I made the assumption that this sequence matched with the first 4 characters included (i.e. shortest match would be 11111).
The average position of the match was at number 255.17886 over 100000 tests.
For 6 digit matches I get 4111.2098 over 5000 tests. Intuitively I'd suggest that 4096 might be the mathematically correct answer when you get
it worked out
ah thats great, that would confirm that my first expression was correct. Thanks ianK and the power of computing
I was thinking probability of generating a correct result rather than how long the string would be, sorry. I think the tricky bit is that you are not
generating discrete sets of four numbers. It is more like check the first and if correct check the second, if not correct try for the first again.
256 attempts would be correct for random sets and this would generate 1024 individual digits. For this problem you need 64 attempts to generate three
digits in a row following the correct start digit. So to generate the correct start digit 64 times with a probability of 0.25 you get 256 numbers in
the string.
There is the chance that the first two digits of the string are the same
i.e 2241
So if the string generates
132422241
it looks like this would be easier to get a match, however I think this is not the case as each instance of the correct first digit is just the
'seed' for the next three digits and the 'seed' needs to occur on average 64 times to get the correct following three.
This has a bearing on the next part of your question with six digits.
For six digits you have to generate the seed on average 1024 times so the total is going to be 4096 or 0.25 to the sixth power.
No idea if I am right, hope it throws some ideas in though.
ETA - Nothing like an experiment to confirm the theory, nicely done Ian.
[Edited on 24/3/10 by Toltec]
I'd have thought the answer should be 260 for the 4-digit case, since you're after total string length and that includes the first 4 digits.
I.e. the first 'attempt' to get a match is in fact a total string length of 5 digits. So as you'd take 256 attempts to get your match
on average (as there are 256 combinations), your string length is 256+4 = 260. Similarly 5002 for the six-digit case.
Liam
[Edited on 24/3/10 by Liam]
Why would you want to know?
Build your self a car, much more useful!
quote:
Originally posted by Mark Allanson
Why would you want to know?
Build your self a car, much more useful!
quote:
Originally posted by Liam
I'd have thought the answer should be 260 for the 4-digit case, since you're after total string length and that includes the first 4 digits. I.e. the first 'attempt' to get a match is in fact a total string length of 5 digits. So as you'd take 256 attempts to get your match on average (as there are 256 combinations), your string length is 256+4 = 260. Similarly 5002 for the six-digit case.
Liam
[Edited on 24/3/10 by Liam]