Probability question

25
0
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:

tiny-tim

Science Advisor
Homework Helper
25,799
242
Hi dabd! :smile:

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

So how many possiblities are there for the second sequence? :wink:
 
25
0
Hi dabd! :smile:

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

So how many possiblities are there for the second sequence? :wink:
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!
 

CRGreathouse

Science Advisor
Homework Helper
2,771
0
The problem simplifies dramatically if the elements are assumed to be distinct.
 
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!).
 

The Physics Forums Way

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving
Top