Results 1 to 8 of 8

Math Help - birthday paradox

  1. #1
    Newbie
    Joined
    Nov 2009
    Posts
    9

    birthday paradox

    hello everyone
    this problem is in cryptography but it's a pure Probability problem.

    if we have a text of "M" length and we randomly pick 3 number between 1 and M.
    we observe the letters in those places.
    what is the Probability that we will have two identical letters?

    i thought i could calculate it using the birthday paradox..

    am i right?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    May 2010
    Posts
    1,028
    Thanks
    28
    I think you need to make an assumption about the distribution of letters in the text to answer this. if so, what is your assumption?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2009
    Posts
    9
    the distribution of letters in the text is known.
    I assume that the language is English
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    May 2010
    Posts
    1,028
    Thanks
    28
    by all means, dont keep the distribution to yourself!


    For arguments sake, suppose all letters are independant and each letter is equally likely to occur in all positions. This is exactly the problem solved in the link below:

    http://en.wikipedia.org/wiki/Birthda...he_probability
    (except there are 26 possibilities instead of 365)

    In that case i would say the answer to your original question is "yes".
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Nov 2009
    Posts
    9
    here is a link :

    Frequency Table
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    May 2010
    Posts
    1,028
    Thanks
    28
    First, since your sample is 3 letters, at most 1 letter can occur twice.

    This means that your probability can be rewritten:
    P(Something occurs twice) =
    P(a occurs twice)
    +P(b occurs twice)
    +P(c occurs twice)
    ...
    +P(Z occurs twice)


    Provided the letters in each position of the text are i.i.d according the that frequency table, and your sample is random & independant: each of the above terms is easy to calculate; although 26 computations will be needed, so i may be missing a simpler method!


    Dont forget at the end to note that:
    p() = 1 if M < 3.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Nov 2009
    Posts
    9
    so using frequencies of letters in English calculation will be kind of a long way, isn't it?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by mormor83 View Post
    so using frequencies of letters in English calculation will be kind of a long way, isn't it?
    You could just estimate the probability from a simple Monte-Carlo simulation.

    CB
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Social Security Number/Birthday Paradox problem
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: September 16th 2010, 06:21 AM
  2. Birthday Paradox
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: March 27th 2010, 01:58 PM
  3. Birthday Paradox
    Posted in the Advanced Statistics Forum
    Replies: 3
    Last Post: March 26th 2010, 04:29 PM
  4. Birthday Paradox Math Project
    Posted in the Statistics Forum
    Replies: 8
    Last Post: November 29th 2009, 02:50 PM
  5. Birthday Paradox Problem!!
    Posted in the Advanced Statistics Forum
    Replies: 4
    Last Post: December 9th 2008, 12:56 PM

Search Tags


/mathhelpforum @mathhelpforum