0
$\begingroup$

I have a machine that generates 16 character long sentences made up of (I think kinda) random letters. I can get it to spit out up to 1 million such sentences before I loose the ability to store them (as there will be too many by then). From the million, there is not a single duplicate sentence detected. They are all different.

Is there a way I can infer at least how many possible unique sentences the machine might be capable of generating? I am testing the hypothesis whether the sentences are made from totally random characters, or do some sentences repeat?

It is possible that the generated sentences /characters are not random or have strong correlations. I don't know and that is the purpose of this experiment. I think that it's a bit of a count-distinct problem, but I can actually store a million sentences so have not used the min hash or hyperloglog technique. It takes too long to generate more than a million sentences anyway.

Is this an impossible test? I had thought that if totally random, there should be some collisions (or not) and this might be some sort of indicator with a confidence interval. Hence the Birthday Problem approach.

It's difficult for me to phrase the question without revealing the true nature of this experiment, as it would just get marked off-topic. So please bear with me.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ It's basic combinatorics problem: mathsisfun.com/combinatorics/combinations-permutations.html $\endgroup$
    – Tim
    Commented Dec 21, 2016 at 22:37
  • 2
    $\begingroup$ @Tim Another interpretation is that there may be dependencies among the characters in each "sentence" that would limit the total number of unique values the machine will produce, so how might one go about searching for such dependencies? However, that doesn't sound like a statistical question--if the dependencies are not certain to hold, they won't prevent any particular sentence from occurring--so it looks like we could use some clarification from Paul. $\endgroup$
    – whuber ♦
    Commented Dec 21, 2016 at 22:57
  • $\begingroup$ @whuber I'm trying to find out if the sentences are truly random or not. I don't know what the appropriate statistics tag for this is... $\endgroup$
    – Paul Uszak
    Commented Dec 21, 2016 at 23:20
  • $\begingroup$ You ought to remove the reference to "possible unique sentences," then, because it looks like it might be confusing people. $\endgroup$
    – whuber ♦
    Commented Dec 21, 2016 at 23:34
  • $\begingroup$ The question as posted is a legitimate statistical problem. Its motivation doesn't matter and therefore revealing its "true nature" wouldn't make the question off-topic - unless you are using it for cracking bank passwords or hacking missile launch codes. $\endgroup$
    – Pere
    Commented Dec 22, 2016 at 0:53

2 Answers 2

Reset to default
2
$\begingroup$

It sounds like what you are looking for are randomness tests. Check out the Diehard test suite.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ +1 These have worked well for me. But there are details you should discuss. As I recall, the Diehard tests require a sequence of at least 32 million bits and they test that sequence for randomness. Thus, one has to convert 16 million "sentences" into at least that number of bits in a meaningful way: that is, so that the conversion doesn't introduce any additional non-randomness and doesn't lose information. $\endgroup$
    – whuber ♦
    Commented Dec 21, 2016 at 23:47
  • $\begingroup$ Seems I misunderstood the aim of the question. However, I'll leave my answer here for now but won't edit it with more details as I assume there is a good chance the question will be removed. $\endgroup$
    – Johan Falkenjack
    Commented Dec 22, 2016 at 7:57
1
$\begingroup$

Assuming you are using a 26 letters alphabet, there are $26^{16}$ different possible 16 letter sentences. This is about $4,3·10^{22}$ sentences and that is $4,3·10^{16}$ times the one million of sentences you are going to generate. Therefore, if your sentences are random and independent you should never expect to repeat any sentence - even if you repeat the experiment every day for the remaining of the century.

We could compute the probability, although the size of the numbers involved makes it a bit tricky. I'll start with the probability of not repeating any sentence:

The number of possible lists of 1,000,000 random sentences is $(2^{16})^{1,000,000}$.

The number of possible lists of 1,000,000 unique random sentences (that is, not repeating any of them) is $26^{16}·(26^{16}-1)·(26^{16}-2)·...·(26^{16}-999,999)$, that is approximately equal to $(26^{16})^{1,000,000}-(26^{16})^{999,999}·(1+2+...+999,999)$ (here I'm neglecting lower potences of $26^{16}$).

$(1+2+...+999,999)=\frac{999,999^2+999,999}{2}=499,999,500,000$

Therefore:

$P(\text{not repeating any sentence})=\frac{(26^{16})^{1,000,000}-499,999,500,000}{(26^{16})^{1,000,000}}=1-\frac{499,999,500,000}{(26^{16})^{1,000,000}}$

$P(\text{repeating 1 or more sentences})=\frac{499,999,500,000}{(26^{16})^{1,000,000}}\approx1.35·10^{-22,639,262}$

As said before, the probability is so close to zero that if you ever get a repeated sentence you can be sure that your sentences don't come from independent random variables.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I am puzzled by your conclusion. Taking it literally, if all sentences were the same one would "get a repeated sentence." Would you really conclude they "come from independent random variables"? I was unable to follow the analysis: clearly there are typographical errors, because almost none of the calculations is correct. For instance, the final probability is approximately $10^{-4816468}$, not $10^{-11}$! $\endgroup$
    – whuber ♦
    Commented Dec 22, 2016 at 15:01
  • $\begingroup$ @whuber Yes, there were too many typographical, and one of them changed the conclusion. I should remember not to post answers so late in the night. Anyway, the conclusion is the same outlined in the first paragraph: the probability of coincidence is so small that if there is a coincidence, sentences are not random. $\endgroup$
    – Pere
    Commented Dec 22, 2016 at 15:38

Not the answer you're looking for? Browse other questions tagged or ask your own question.