Comparing two ordered lists

Question

Hi I would appreciate it if someone can point me in the right direction. I'm looking for an algorithm or mathematical theory which I would use to compute the similarity between two ordered lists, where each list element can have n sub-elements. I will explain with an example:

Suppose I go to a baseball game and I record the sequence of strikes and balls for each of the first 30 players at bat. My list looks like this, where P is a player, S is a strike and B is a ball. Order matters.

L1: {P1=(S,S,S)}, {P2=(B,B,S)}, {P3=(B,B,S,S)}, ...

My friend goes to a baseball game and does the same thing. Later, we meet up and compare our lists. We find that our lists are almost identical except that I recorded a strike for player 16 where my friend recorded a ball. What are the chances we were at the same game and one of us made a mistake at player 16?

Thanks in advance...

Answer 1

What about a model stating that you have two vectors of size N (where N is the total number of players, maybe unknown to us) where each element belongs to a space of {B,S} sequences, maybe empty. If you then define a distance function between two arbitrary sequences (say, normalized Levenshtein distance for two non-empty ones and some fixed cost when one is missing), you can define cosine similarity between the vectors.

(Obviously, you just consider your sequence a compact representation of sparse vector in this case.)

Answer 2

Alex's answer is spot on in how you would go about figuring out similarity. One more step required, to answer your question, is to come up with a threshold of similarity. I.e. some similarity threshold beyond which you can say that the discrepancies are probably errors.

If you are looking for resources to learn more about this, I'd recommend Data Mining Concepts and Techniques by Han et all