Page 47 / Lecture 6 (10 min) Partitioning the table

[markact]

I am struggling with one of more simpler bits of chapter 2.

On page 47 (Lecture 6 - 9 ~ 12 mins), I do not understanding how the table is constructed.

"Some dichotomies on these N-1 points appear only once" Okay, so to me, this implies we have 2^(n-1) rows for the first set (S1).

"The remaining dichotomies on the first n-1 appear twice, once with +1 and once with -1" How can this be true...?

To me, "the remaining dichotomies on the first n-1" would mean (2^n) less (2^n-1) = 2^n-1. But these appear twice! So we have 2*(2^n-1) = 2^n for set S2.

This seems as though we are counting twice.

S1 = 2^n-1
S2 = 2^n

The total of S1 + S2 is greater than 2^n.

Surely, I must be missing something really simple here. But what...? Please help.

Thanks,

Mark

[yaser]

Originally Posted by markact

"Some dichotomies on these N-1 points appear only once" Okay, so to me, this implies we have 2^(n-1) rows for the first set (S1).

At most since it's not necessary that all of them are there. The fact that there may be that many does not play a role in the argument.

"The remaining dichotomies on the first n-1 appear twice, once with +1 and once with -1" How can this be true...?

The and are the entries in the last () column. The dichotomies on the first columns appear twice as they appear once with and once with in the last column.

[markact]

Thank you very much for replying.

I read the answers and think that I understand the points being made in regards to the maximum being 2^(n-1).

But on reflection, perhaps my misunderstanding could have been expressed more clearly. So, I am sorry about the following tables, but perhaps these help to demonstrate what I am missing in regards to partitioning the original set into 3 disjoint sets.

The following assumes a space of 4 points - a maximum of 16 dichotomies. I have labelled each row with its base 10 equivalence.

Here is alpha (N-1 appears once, with XN either 1 or 0)

X1 X2 X3 XN ID
0 0 0 0 0
0 0 1 1 3
0 1 0 0 4
0 1 1 1 7
1 0 0 0 8
1 0 1 1 11
1 1 0 0 12
1 1 1 1 15

We are left with 8 rows remaining If these have XN being either 1 or -1, then these 8 rows are split into the following two partitions (S2+ and S2-).


[S2+]
X1 X2 X3 XN ID
0 0 0 1 1
0 1 0 1 5
1 0 0 1 9
1 1 0 1 13


[S2-]
X1 X2 X3 XN ID
0 0 1 0 2
0 1 1 0 6
1 0 1 0 10
1 1 1 0 14

So, given the partitions above, I seem to get that X1, X2 appears twice but this is not N-1 appearing twice (i.e. X1, X2, X3).

I understand we are attempting to describe situations were there is a break point and all the combinations listed above will not exist.

But given the instructions in the book and using a nice-and-neat 2n construction, I do not understand how the exhaustive and exclusive 3 sets are derived.

Thanks in advance,

Mark

[yaser]

Originally Posted by markact

these help to demonstrate what I am missing in regards to partitioning the original set into 3 disjoint sets.

The following assumes a space of 4 points - a maximum of 16 dichotomies. I have labelled each row with its base 10 equivalence.

Here is alpha (N-1 appears once, with XN either 1 or 0)

X1 X2 X3 XN ID
0 0 0 0 0
0 0 1 1 3
0 1 0 0 4
0 1 1 1 7
1 0 0 0 8
1 0 1 1 11
1 1 0 0 12
1 1 1 1 15

We are left with 8 rows remaining If these have XN being either 1 or -1, then these 8 rows are split into the following two partitions (S2+ and S2-).


[S2+]
X1 X2 X3 XN ID
0 0 0 1 1
0 1 0 1 5
1 0 0 1 9
1 1 0 1 13


[S2-]
X1 X2 X3 XN ID
0 0 1 0 2
0 1 1 0 6
1 0 1 0 10
1 1 1 0 14

Thank you for the detailed example. I can now see where the misunderstanding is. The set contains all the patterns that appear once, and none of the patterns that appear twice, of the original matrix. Therefore, if all the above patterns are indeed in that matrix, then the decimal pattern 0 should not be in since the decimal pattern 1 makes that pattern appear twice (on the first 3 columns). Similarly, the set contains all patterns that appear twice, and none that appear once.

[markact]

Got it!!

Thank you very much for your patience.