Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Based on this question, I'm trying to work out how much worse a passphrase with a grammatical structure is compared to a passphrase made up of a random bunch of words. Is my maths correct in this worked example (and thus, my overarching logic for counting combinations in phrases)?

Assume a dictionary containing a total of 19010 words, broken up like so:

  • 3000 nouns, each with plural forms (3000 * 2 = 6000)
  • 1500 verbs, each with 4 tenses and plural forms (1500 * 4 * 2 = 12000)
  • 1000 adjectives, no additional variations (= 1000)
  • 10 determiners, made up of:
    • the articles the and a
    • the demonstratives this and that
    • the personal pronouns my, your, their, his, her, its

I realise some words don't have all 4 tenses or plural forms, but it shouldn't matter too much for my reasoning.

Grammar

Assume I'm going to generate a phrase based on the structure: det noun verb det adjective noun. And assume I'll choose words based on a uniform distribution, and I won't re-use words.

total combinations = 
    count(determiners) 
    * count(noun forms) 
    * count(verb forms) 
    * count(adjective) 
    * count(determiners) 
    * (count(noun forms) - 1)
= 10 * 6000 * 12000 * 1000 * 10 * (6000-1)
~ 4.32E+16 (~ 55.3 bits)

And without the determiners:

~ 4.32E+14 (~ 48.6 bits)

Random Words

Assume I'll choose 4 words at random (representing the 4 major forms from the grammar version), also based on uniform distribution, and don't re-use words.

total combinations = 
    count(all forms) 
    * (count(all forms) - 1)
    * (count(all forms) - 2)
    * (count(all forms) - 3)
= 19010 * (19010-1) * (19010-2) * (19010-3)
~ 1.31E+17 (~ 56.9 bits)

And if I choose 6 words (same number of words as when determiners are included):

~ 4.72E+25 (~ 85.3 bits)

(I'm sure there's a proper notation for this pattern (NPR?? permutations?? combinations??), but my high school maths have long deserted me).

Differences

All in orders of base 10 magnitude.

                    Grammar   Random Words   Diff
No-Det vs 4 words    14        17             2
Det vs 4 words       16        17             1
No-Det vs 6 words    14        25             11
Det vs 6 words       16        25             9

And, just to repeat my question: is my math and logic correct here?

And a bonus question: what's a "fair" comparison between numbers of words / determiners, because that makes all the difference (though that's probably a question for the security StackOverflow)? My thinking here is the determiners are all pretty short (1-5 letters), so they're probably equivalent to 1 but not 2 extra words, which gives 5-6 orders of magnitude difference.

share|improve this question
    
It seems fine to me, except, since you're using English as an example, the adjective should come after the determiner ;-) –  joriki Feb 21 '13 at 11:00
    
Woops. Fixed that word order! You might as well pad out your "yes" into a more substantial answer! –  ligos Feb 22 '13 at 8:25
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.