Hamming metric

by Metric_Space
Tags: hamming, metric
 Share this thread:
 P: 98 Isn't it because that means the sum above is the difference of two other sums?
Mentor
P: 18,072
 Quote by Metric_Space 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?
 P: 98 one that sums to one, and one that has a zero at the kth entry?
 Mentor P: 18,072 Yes, indeed! So, now we have shown that only (1,1,1,...) has the property that $$\sum_{k=1}^{+\infty}{\frac{x_k}{2^k}}=1$$. So, can you now describe the ball around (0,0,0,...) with radius 1?
 P: 98 Would it be all entries are 1? But it wouldn't be finite...would it?
Mentor
P: 18,072
 Quote by Metric_Space 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

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

So...
 P: 98 Isn't that just all the (x_1,x_2, ...) minus the entry with (1,1,1,1...)?
 Mentor P: 18,072 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 $(a_1,a_2,a_3,...)$ with radius 1?
 P: 98 would it be everything but (a_1,a_2, a_3, ...)?
 Mentor P: 18,072 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...
 P: 98 ...I think I'll need another hint
 Mentor P: 18,072 For what sequence $(x_n)_n$, does $$\sum_{k=1}^{+\infty}{\frac{|x_k-a_k|}{2^k}}=1$$ 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?
 P: 98 |X_k-a_k| --> 0 as k--> infinity?
Mentor
P: 18,072
 Quote by Metric_Space |X_k-a_k| --> 0 as k--> infinity?
No. I don't know how you got that?
You do know that $\frac{1}{2^k}|X_k-a_k|\rightarrow 0$, but I fail to see how it is relevant here...
 P: 98 Oh...does |X_k-a_k|=1 for k=1..infinity?
 Mentor P: 18,072 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).
 P: 98 x_k=1, a_k=0 or a_k=1,x_k=0 ...is that right?
Mentor
P: 18,072
 Quote by Metric_Space 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

$$\sum_{k=1}^{+\infty}{\frac{x_k}{2^k}}<\frac{1}{2}$$

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

$$\sum_{k=1}^{+\infty}{\frac{x_k}{2^k}}=\frac{1}{2}$$

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...

 Related Discussions General Math 1 Calculus & Beyond Homework 1 Engineering, Comp Sci, & Technology Homework 0 Linear & Abstract Algebra 9 Engineering, Comp Sci, & Technology Homework 1