Proving The Hamming Metric: Open Subsets and Basis of X

In summary, the conversation discusses the concept of open sets and balls in a metric space. It also touches on the concept of a basis of open sets and how it can be used to prove that a set is open. The conversation concludes with finding the ball around a specific point with a given radius.
  • #36
So, did you figure out why

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

if one of the xk is 0?
 
Physics news on Phys.org
  • #37
Isn't it because that means the sum above is the difference of two other sums?
 
  • #38
Metric_Space said:
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?
 
  • #39
one that sums to one, and one that has a zero at the kth entry?
 
  • #40
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?
 
  • #41
Would it be all entries are 1? But it wouldn't be finite...would it?
 
  • #42
Metric_Space said:
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\right\}[/tex]

So...
 
  • #43
Isn't that just all the (x_1,x_2, ...) minus the entry with (1,1,1,1...)?
 
  • #44
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?
 
  • #45
would it be everything but (a_1,a_2, a_3, ...)?
 
  • #46
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...
 
  • #47
...I think I'll need another hint
 
  • #48
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?
 
  • #49
|X_k-a_k| --> 0 as k--> infinity?
 
  • #50
Metric_Space said:
|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...
 
  • #51
Oh...does |X_k-a_k|=1 for k=1..infinity?
 
  • #52
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).
 
  • #53
x_k=1, a_k=0 or a_k=1,x_k=0 ...is that right?
 
  • #54
Metric_Space said:
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...
 
  • #55
Would (x_1,x_2,x_3...) = (0,1,1,...)?
 
  • #56
Metric_Space said:
Would (x_1,x_2,x_3...) = (0,1,1,...)?

Yes that's good, but there is one more possibility!
 
  • #57
oh right...or (1,0,0,0..)
 
  • #58
Yes, very good! So elements in the ball around 0 with radius 1/2 consist of those elements with more zeroes than either (1,0,0,...) or (0,1,1,...).

Now, can you describe the ball around an arbitrary a with radius 1/2?
 
  • #59
balls of radius (1/2)^k have elements

with 1's starting in the kth position and 0's afterwards OR 1's in the (K+1)st position...right?
 
  • #60
Metric_Space said:
balls of radius (1/2)^k have elements

with 1's starting in the kth position and 0's afterwards OR 1's in the (K+1)st position...right?

No, but you have the right idea. What you describe are the sequences such that

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

To describe the balls, you'll need < instead of =. So the balls would be the elements which has less 1's than the elements that you describe.

Also, that only describes the balls around 0. It would be fun if you would find the balls around arbitrary elements...
 
  • #61
around an arbitrary element...wouldn't it be similar to before.

ie. (sum,k=1..infinity, (x_k-a_k)/2^k) < (1/2)^n

either x_k is with 1's starting in the kth position and 0's afterwards
and a_k is ..not sureOR 1's in the (K+1)st position

and a_k is not sure
 
  • #62
Well, the balls around a with radius 1/2 are either:

1) elements which agree with a in it's first coordinate
2) elements which agree with a except possibly in it's first coordinate.

Can you see why?
Can you extend this to balls with radius (1/2)k??
 
  • #63
no...I don't follow
 
  • #64
Can you see why it is true for a=0?
 
  • #65
I think so?
 
  • #66
OK, npw apply the same reasoning to arbitrary a instead of 0...
 
  • #67
...I think I need a hint
 
  • #68
Well, when does

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

??
 
  • #69
x_k=(1,0,0,0,0...) and a_k=(0,0,0,...)

or

x_k=(0,1,0,0...) and a_k=(0,0,0,...)

or

a_k=(1,0,0,0,0...) and x_k=(0,0,0,...)

a_k=(0,1,0,0...) and x_k=(0,0,0,...)
 
  • #70
No, can you show my how you got that?

If

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

then what must hold for [itex]|x_k-a_k|[/itex].
 
<h2>1. What is the Hamming metric?</h2><p>The Hamming metric is a way to measure the distance between two points in a finite set. It is commonly used in coding theory and computer science to compare strings of characters.</p><h2>2. How is the Hamming metric calculated?</h2><p>The Hamming metric is calculated by counting the number of positions in which two strings of characters differ. This is also known as the "Hamming distance".</p><h2>3. What are open subsets?</h2><p>Open subsets are subsets of a larger set that do not contain any of the boundary points of the larger set. In other words, they are sets that are entirely contained within another set.</p><h2>4. How are open subsets related to the Hamming metric?</h2><p>In the context of proving the Hamming metric, open subsets are used to show that the Hamming distance between two points is always greater than or equal to 0. This is because open subsets do not contain any boundary points, so the Hamming distance cannot be negative.</p><h2>5. What is the basis of X?</h2><p>The basis of X is a set of elements that can be used to represent all other elements in the set X. In the context of proving the Hamming metric, the basis of X is used to show that any two points in X can be represented by a finite number of elements, which is necessary for calculating the Hamming distance.</p>

1. What is the Hamming metric?

The Hamming metric is a way to measure the distance between two points in a finite set. It is commonly used in coding theory and computer science to compare strings of characters.

2. How is the Hamming metric calculated?

The Hamming metric is calculated by counting the number of positions in which two strings of characters differ. This is also known as the "Hamming distance".

3. What are open subsets?

Open subsets are subsets of a larger set that do not contain any of the boundary points of the larger set. In other words, they are sets that are entirely contained within another set.

4. How are open subsets related to the Hamming metric?

In the context of proving the Hamming metric, open subsets are used to show that the Hamming distance between two points is always greater than or equal to 0. This is because open subsets do not contain any boundary points, so the Hamming distance cannot be negative.

5. What is the basis of X?

The basis of X is a set of elements that can be used to represent all other elements in the set X. In the context of proving the Hamming metric, the basis of X is used to show that any two points in X can be represented by a finite number of elements, which is necessary for calculating the Hamming distance.

Similar threads

  • Calculus and Beyond Homework Help
Replies
1
Views
1K
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
20
Views
2K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
4
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
1K
  • Calculus and Beyond Homework Help
Replies
16
Views
2K
  • Calculus and Beyond Homework Help
Replies
4
Views
2K
  • Calculus and Beyond Homework Help
Replies
1
Views
805
Back
Top