Ball-avoiding randomness in an Hamming metric

This is an open ended question, I don't know the answer and would like your ideas on the topic.

Let me first give you a practical setting where this kind of problem arise: Banks need to issue account numbers for their customer. For example , let's say that A,BA, B are two customers of Tartaglia Bank and that they are issued the following 6-digits account numbers:

  • A:A: 21-33-45
  • B:B: 27-33-45

Now, it should be pretty evident that, by chance, the two account numbers happened to be pretty similar: they only differ in the second digit. This is not good! One digit is easily mistaken and A could possibly receive the money that someone inteded to send to B and viceversa.

It's clear that we would like any two random account numbers to be as different as possible, that is, in this case, to differ in all 6 digits.

This has now the following generalization, that is our actual question:

Let VV be a vocabulary set (a set of "letters", in our previous case it was the set of natural numbers) , let nn be a positive integer and W=VnW = V^n the set of n-length words (in our previous example n=6n=6 and WW was the set of all possible 6-digits account numbers). Define for a,bWa,b \in W H(a,b)H(a,b) to be the number of letters in which the two words differ (this is called an Hamming Distance and it can be shown to induce a Metric Space on W). Given any two words a,bWa,b \in W , what is the chance that their distance is maxmised, i.e. that H(a,b)=nH(a,b)=n ? Generalising further, given d>0d > 0 what is the chance that k2k \geq 2 words a1,...,akWa_1,...,a_k \in W are such that H(ai,aj)dH(a_i,a_j)\geq d for all 1ai<ajk1\leq a_i < a_j \leq k?

I am fairly sure this problem or one of its variant should be fairly doable and I'll try to spend some time on it when I finish publishing these notes. It was just one of those real life inspired problems that I felt like to share on this platform as a way to test it (this is my first post here) and perhaps to interest some other people, so I am looking forward for your answers/ideas/generalisations/link to papers/critiques/suggestions.

Thanks for reading!

Note by Ermes Trismegisto
3 years, 3 months ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

Hey there! Nice job on your first post! Welcome to the community.

I do not know a lot about Hamming Codes. Could you explain the question to me in some informal way?

Agnishom Chattopadhyay Staff - 3 years, 3 months ago

Log in to reply

Thank you very much! To be honest with you, I don't know much about them myself, just happened to know the name and learnt about metric space and it's a pretty popular example. I was a bit worried that I might have added some useless complications , so I'll try to rexpress the final question informally: basically, take kk different nn- letters words . (Here the words "letter" and "word" are to be intended in a more general mathematical fashion: for example £$$$%&??£ is a valid 9-letters word where each letter belong to the set of "keyboard keys". This set is called in general a vocabulary set and we can assume it to be finite: so your answer is also going to contain the number of element of this set (the cardinality of the set) as one of the parameters!).

So now you have kk nn-letter words.Given any two of these, you can count in how many characters or letters they differ: for example:

  • % % £ & & % $ %

  • % $ £ & & ? ? %

Those two words above are both 8 letters long and they differ in the 2nd,6th and 7th postion. We say that their Hamming distance is three, that is , they differ in three places, very easy!

Now you fix a positive number dd and you ask what is the chance that taken any pair of the kk words is such that their distance is at least dd, i.e. each pair ar at least dd words "apart".

I hope this reformulation makes sense, let me know!

Ermes Trismegisto - 3 years, 3 months ago

Log in to reply

With you, so far.

So, we are trying to find the probability that a set of kk nn length words over some alphabet has the property that no two strings are closer than dd. Right?

Agnishom Chattopadhyay Staff - 3 years, 3 months ago

Log in to reply

@Agnishom Chattopadhyay Replace "closer" with "further apart" and that's precisely it. (H(ai,aj)dH(a_i,a_j) \geq d) so we want the distance to be at least d.

Ermes Trismegisto - 3 years, 3 months ago

Log in to reply

Given any two words a,bWa,b \in W , what is the chance that their distance is maxmised, i.e. that H(a,b)=nH(a,b)=n ?

Isn't it (V1)n(V-1)^ n

Lokesh Sharma - 3 years, 3 months ago

Log in to reply

Yeah, I agree with you that's pretty easy: you choose the letters the first word aa and then when you choose the letters of bb you can't use one character for each letter, so that one is farily easy.

Ermes Trismegisto - 3 years, 3 months ago

Log in to reply

Generalising further, given d>0d > 0 what is the chance that k2k \geq 2 words a1,...,akWa_1,...,a_k \in W are such that H(ai,aj)dH(a_i,a_j)\geq d ?

I assume both ii and jj can take any value from 11 to kk except the case i=j i = j . Right?

Lokesh Sharma - 3 years, 3 months ago

Log in to reply

@Lokesh Sharma Oh shit, good point ,yes! I'll edit it now, thanks!

Ermes Trismegisto - 3 years, 3 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...