Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Probability question

  1. Feb 23, 2009 #1
    Hi,

    Given two arrays (or sequences) of size n. What is the probability that they are in the same relative order?

    Ex: s = [5, 10, 18, 3, 7] and t = [6, 9, 20, 1, 7] are in the same relative order.

    Note: The elements of the sequence are drawn from a set with a total order defined, say the natural numbers.

    Thanks.
     
    Last edited: Feb 23, 2009
  2. jcsd
  3. Feb 23, 2009 #2

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    Hi dabd! :smile:

    Hint: the first sequence can be anything, in any order.

    So how many possiblities are there for the second sequence? :wink:
     
  4. Feb 23, 2009 #3
    Of course there infinitely many possibilities for the second sequence.

    Putting it in other way, two sequences of length n are in the same relative order if we sort them and their elements positions (in the original sequences) are the same.

    s = [5, 10, 18, 3, 7] positions = [1, 2, 3, 4, 5]

    and t = [6, 9, 20, 1, 7] positions = [1, 2, 3, 4, 5]


    s'= [3, 5, 7, 10, 18] positions = [4, 1, 5, 2, 3]
    and t' = [1, 6, 7, 9, 20] positions = [4, 1, 5, 2, 3]

    Given the first sequence just sort it and note the positions (4, 1, 5, 2, 3) in the example.
    For the second sequence any sorted sequence will do, and of course there are infinitely many different sorted sequences, and to get the same relative order sequence just "unshuffle" its positions.

    But, I don't get how can I compute the probability!
     
  5. Feb 23, 2009 #4

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    The problem simplifies dramatically if the elements are assumed to be distinct.
     
  6. Feb 25, 2009 #5
    I think that for an array of n numbers, there are n! possible permutations... so I guess that for your example the prob would be 1/(5!).
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Probability question
  1. Probability question (Replies: 4)

  2. Probability Question (Replies: 21)

  3. Probability Question (Replies: 3)

  4. Probability questions (Replies: 1)

Loading...