Results 1 to 2 of 2

Math Help - Expected value of a particular substring in a string

  1. #1
    Newbie
    Joined
    Apr 2009
    Posts
    17

    Expected value of a particular substring in a string

    I have a random string X of 100 letters in which each letter is equally likely to be any 1 of the 26 in the alphabet. What is the expected value of the number of times the substring 'ABCD' occurs in X? Also, is the expected value the same for every substring of length 4?

    Also, what is the expected value for the substring 'AAAA'? Since it can overlap, would the expected value be greater?
    Last edited by cubrikal; February 22nd 2010 at 08:08 PM. Reason: add
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Dec 2009
    Posts
    226
    The probability of A is \frac{1}{26}, the probability of a B is \frac{1}{26}, the probability of a C is \frac{1}{26}, and the probability of a D is \frac{1}{26}. Therefore, the probability of ABCD is \frac{1}{26} \times \frac{1}{26} \times \frac{1}{26} \times \frac{1}{26} = (\frac{1}{26})^4 = \frac{1^4}{26^4} = \frac{1}{456,967}. If ABCD occurs 1 time out of 456,967 times, then out of 100 times it should occur 0 times.

    No, the expected value of any substring of length 4 is constant. For example, the expected value of the substring "AAAA" is greater than the expected value of the substring "ABCD".

    The probability of the substring AAAA occuring starting at the first character is \frac{1}{456,967}. The probability of AAAA occuring starting at the second character is \frac{1}{456,967}. The position of the last character at which AAAA can occur is 97 (97th character = A, 98th character = A, 99th character = A, and 100th character = A). Therefore, the probability of AAAA occuring anywhere in the string of 100 characters is 97 \times \frac{1}{456,967} = \frac{97}{456,967}. However, you still can't expect to find AAAA in the string of 100 characters since it rarely occurs out of even 456,967 times.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Prob. of substring occurring k times
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: March 30th 2010, 08:29 PM
  2. Bit String Length
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 3rd 2009, 11:19 AM
  3. bit strings and substring
    Posted in the Advanced Applied Math Forum
    Replies: 1
    Last Post: September 7th 2009, 01:16 PM
  4. String
    Posted in the Algebra Forum
    Replies: 4
    Last Post: March 23rd 2009, 05:04 PM
  5. Bit string question
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: April 13th 2008, 07:22 AM

Search Tags


/mathhelpforum @mathhelpforum