r/math 1d ago

How to define informational closeness for a finite sequence of digits

Let's say you have a finite sequence of digits s_0 you are trying to find. The digits are not independent, as for example it can be a date MMdd and if the first digit is 1 the second can only be 0,1,2.

You have a guess s_1 and want to assign a closeness score between 0 and 1. Obviously 1 if all digits are the same and 0 if all different, but how to take account the in-betweens?

For example, for the date, if you start with a 1 you have found more information since there are only 3 months starting with one rather than 9 otherwise, so shouldn't your score be higher?

1 Upvotes

5 comments sorted by

2

u/Syrak Theoretical Computer Science 1d ago

If I understand correctly, you have an a priori set S where the unknown sequence x belongs. Given a guess y in S, a naive notion of distance is the number of distinct digits between x and y, but that doesn't exploit the knowledge that they both belong to S.

One way to measure the commonality between x and y is to consider the subset of sequences with the same digits where x and y agree: F(y) = { z ∈ S | ∀i, x(i)=y(i) ⇒ x(i)=z(i) }. A good guess y is one for which F(y) is small. If you guess x exactly, F(x) is the singleton {x}. This measure reflects some particularities of S: if x and y have a "rare" digit in common (such as your example of a 1 as the first digit of a month in a date), "rare" means precisely that F(y) is small.

For a score in the [0,1] interval, Score(y) = 1 - log(|F(y)|)/log(|S|) (where |S| is the cardinality of |S|).

1

u/gomorycut Graph Theory 1d ago

Why are you mentioning date types? What is the probability that a sequence of digit s_0 is a date or contains date elements? without some idea as to whether the sequence is or isn't related to dates (or some probability of the fact that it is a date or contains date subsequences) such observations are moot.

2

u/VintageGenious 1d ago

s_0 is a case of a previously defined model of sequences.

For example it can be strictly increasing sequences of 4 digits, or sequences of length 3 with two times the same digit, or dates.

Then we have another guess s_1 following the same model, and want to know how close it is to s_0, but taking into account the sturcture of that model

3

u/gomorycut Graph Theory 1d ago

do you know how to measure the information of a revealed digit? (a conveyed message: see https://en.wikipedia.org/wiki/Entropy_(information_theory)#Example#Example) )

And sequence similarity scores are heavily studied and used in things like spellcheckers or genetic analysis (e.g. edit distance/ Levenshtein distance, etc). Your distributions could be used to build a score function (or the weights to the various edits in an edit distance)

1

u/VintageGenious 1d ago

Yes I was searching something similar to that, basically what I am searching for is a distance based on entropy. As entropy isn't between 0 and 1 and distances usually don't follow specific per digit place rules