Register to reply

Hamming metric

by Metric_Space
Tags: hamming, metric
Share this thread:
Metric_Space
#37
May25-11, 12:29 PM
P: 98
Isn't it because that means the sum above is the difference of two other sums?
micromass
#38
May25-11, 12:30 PM
Mentor
micromass's Avatar
P: 18,345
Quote Quote by Metric_Space View Post
Isn't it because that means the sum above is the difference of two other sums?
I'm not sure what you mean. Which other sums?
Metric_Space
#39
May25-11, 12:32 PM
P: 98
one that sums to one, and one that has a zero at the kth entry?
micromass
#40
May25-11, 12:35 PM
Mentor
micromass's Avatar
P: 18,345
Yes, indeed!

So, now we have shown that only (1,1,1,...) has the property that

[tex]\sum_{k=1}^{+\infty}{\frac{x_k}{2^k}}=1[/tex].

So, can you now describe the ball around (0,0,0,...) with radius 1?
Metric_Space
#41
May25-11, 12:40 PM
P: 98
Would it be all entries are 1? But it wouldn't be finite...would it?
micromass
#42
May25-11, 12:46 PM
Mentor
micromass's Avatar
P: 18,345
Quote Quote by Metric_Space View Post
Would it be all entries are 1? But it wouldn't be finite...would it?
No, this isn't correct. I want you to find the set

[tex]\left\{(x_1,x_2,x_3,...)~\mid~\sum_{k=1}^{+\infty}{\frac{x_k}{2^k}}<1\r ight\}[/tex]

So...
Metric_Space
#43
May25-11, 12:52 PM
P: 98
Isn't that just all the (x_1,x_2, ...) minus the entry with (1,1,1,1...)?
micromass
#44
May25-11, 12:58 PM
Mentor
micromass's Avatar
P: 18,345
Indeed, so the ball around (0,0,0,...) with radius 1 is everything except (1,1,1,1,...).
So, now the obvious generalization: what is the ball around [itex](a_1,a_2,a_3,...)[/itex] with radius 1?
Metric_Space
#45
May25-11, 01:04 PM
P: 98
would it be everything but (a_1,a_2, a_3, ...)?
micromass
#46
May25-11, 01:10 PM
Mentor
micromass's Avatar
P: 18,345
Uuh, no, I get the impression that you're just guessing here.

Obviously a=(a1,a2,a3,...) will be in the ball, since d(a,a)=0<1.
Moreover, we have just calculated that the ball around (0,0,0,...) is everything but (1,1,1,...). Thus (0,0,0,...) is in the ball...
Metric_Space
#47
May26-11, 07:16 PM
P: 98
...I think I'll need another hint
micromass
#48
May26-11, 07:23 PM
Mentor
micromass's Avatar
P: 18,345
For what sequence [itex](x_n)_n[/itex], does

[tex]\sum_{k=1}^{+\infty}{\frac{|x_k-a_k|}{2^k}}=1[/tex]

It's basically the same as my last question (when the ak were simply 0). What must hold for |xk-ak| in order for the above series to be 1?
Metric_Space
#49
May26-11, 07:33 PM
P: 98
|X_k-a_k| --> 0 as k--> infinity?
micromass
#50
May26-11, 07:44 PM
Mentor
micromass's Avatar
P: 18,345
Quote Quote by Metric_Space View Post
|X_k-a_k| --> 0 as k--> infinity?
No. I don't know how you got that?
You do know that [itex]\frac{1}{2^k}|X_k-a_k|\rightarrow 0[/itex], but I fail to see how it is relevant here...
Metric_Space
#51
May26-11, 07:51 PM
P: 98
Oh...does |X_k-a_k|=1 for k=1..infinity?
micromass
#52
May26-11, 07:54 PM
Mentor
micromass's Avatar
P: 18,345
Yes!!! Very good!!

So, if |xk-ak|=1, then what will xk be? (Remember that xk and ak can only take on 0 and 1 here).
Metric_Space
#53
May26-11, 07:58 PM
P: 98
x_k=1, a_k=0 or a_k=1,x_k=0 ...is that right?
micromass
#54
May26-11, 08:05 PM
Mentor
micromass's Avatar
P: 18,345
Quote Quote by Metric_Space View Post
x_k=1, a_k=0 or a_k=1,x_k=0 ...is that right?
Very nice!! So, basically, ak has the opposite value of xk...
Remark that this correspons nicely with the previous thingies where a was (0,0,0,...), then x was (1,1,1,...).

So, the ball around a with radius 1 is just everything except the "opposite of a")!

Now, we're going to make it a little harder. We're going to figure out what the ball around (0,0,0,...) is with radius 1/2. So, for which vectors does

[tex]\sum_{k=1}^{+\infty}{\frac{x_k}{2^k}}<\frac{1}{2}[/tex]

As above, you may remark that it suffices to calculate when equality holds, thus

[tex]\sum_{k=1}^{+\infty}{\frac{x_k}{2^k}}=\frac{1}{2}[/tex]

Since if x has a distance of 1/2 of 0, then all vectors with less 1's than x, have distance <1/2. And this is exactly what we wanted...


Register to reply

Related Discussions
Hamming Disatnce General Math 1
The Hamming Disatance Calculus & Beyond Homework 1
Hamming Coder Engineering, Comp Sci, & Technology Homework 0
Hamming Distance Linear & Abstract Algebra 9
Hamming Code Engineering, Comp Sci, & Technology Homework 1