Vlad,
Thanks for your below reply to my prior email of Tue 10/21/2008 7:08 PM I agreed with most of your reply. There are only two major issues upon which I wanted further confirmation, clarification, or comment. 1. WHY C(N,S) IS DIVIDED BY T(N,S,O) TO FORM A LOWER BOUNDS FOR A(N,S,O) You have stated that C(N,S) / T(N,S,O) is a lower bounds for the value A(N,S,O) where A is the number of sets of length S (which I will also refer to as "assemblies") that can be formed from N nodes, where none of the A assemblies overlap the population of any other of such assemblies by an overlap of O or larger. I want to see if my understanding of this is correct. I understand what C(N,S) is. Thanks to your explanations I think I understand what T(N,S,O) is. And as is explained below under heading 2, I think I understand why T(N,S,O) is likely to over count the number of assemblies that impermissibly overlap the population of any allowed assembly that is counted as part of A. But until a few minutes ago I didn't understand the mathematical bases for A => C(N,S) / T(N,S,O) I understood why T(N,S,O) could be subtracted from C(N,S), but not why should be its divisor. Now I think I do. PLEASE CONFIRM IF MY NEW UNDERSTANDING IS CORRECT. For purposes of simplicity, until I state otherwise let us assume there is no multiple counting of excluded assemblies in the calculation of T(N,S,O), and, thus, that T(N,S,O) is exact. As I understand your argument you are saying every time you increase the count of allowable assemblies by 1, you increase the count of unallowable assemblies --- i.e., those having an impermissible overlap --- by T. Thus if you had A allowable assemblies, you would have A x T unallowable assemblies and, thus, A + A x T = C(N,S) This says all the allowable and unallowable sets of length S would equal the total number of different possible sets of length S that can be made from N elements. If one solves this for A one gets A(1 + T) = C(N,S) A = C(N,S) / (1 + T) And since T is normally much, much larger than 1, we can forget the 1 to give your formula A = C(N,S) / T Now lets take into account the fact that it appears T(N,S,O) is normally larger than the number of actual sets excluded by the addition of each allowable set. That makes A smaller than it should be in the above equation and thus, changes the equation to A => C(N,S) / T Which is equivalent to saying C(N,S) / T is a lower bounds for A, just as you have been saying. IS THIS EXPLANATION CORRECT? 2. THE SOURCE OF THE OVER COUNTING ASSOCIATED WITH T(S,N,O) I think I understand why there would be over counting in the formula T(N,S,O) used in your formula A => C(N,S) / T(N,S,O). It appears to results from the fact that --- when you calculate T for a given allowable assembly of length S using the formula: T(N,S,O) = SUM FROM X =O TO S OF C(S,X)*C(N-S,S-X) to estimate the number T of possible assemblies that have impermissible overlap with the given allowable assembly --- it would appear that some assemblies counted as excluded by an iteration of T with a smaller value of X would also be counted as excluded in other iterations having a larger value of X. This is because all the overlapping sub-combinations C(S,X) that would occur for a smaller value of X, would also occur as part of one or more of the sub-combinations C(S,X) that would occur for a larger value of X. Thus, T would create a number that is larger than the actual number of assemblies that would have impermissible overlap with a given allowable assembly. IS THIS CORRECT? IS THERE ANY OTHER SOURCE OF OVERCOUNTING? I though their might also be over counting because it appears --- as is stated under heading 1 --- that in the formula A => C(N,S) / T(N,S,O), T is implicitly calculated for each allowable assembly in A, and I though their might be overlap between the count T of excluded assembles made for different allowable assemblies. But it now appears to me that since none of the allowable assemblies share any overlaps X of length O to S with any other allowable set, it would appear that there would be no overlap between any of the T(N,S,O) assemblies counted as being unallowable for any first allowed assembly and those calculated as unallowable for any second allowed assembly. That is, none of the C(S,X) sub-combinations, with X > O, that could be made from any first allowable assembly of length S, would be shared with any other allowable assemblies, meaning that none of the assemblies excluded by the calculation of T for one allowable assembly, could be included in the calculation of T for another allowable assembly. IS THIS CORRECT? ===================== Finally, I have to ask if you came up with the equation A => C(N,S) / T yourself, or if you got it from some other source (and if so which source). I AM VERY THANKFUL IF YOU FOUND IT FROM ANOTHER SOURCE, BUT IF YOU CALCULATED IT YOURSELF, YOU MUST BE VERY TALENTED, INDEED. Either way I look forward to your confirmation, comments, or corrections about what I have said in this email, and I thank you for your efforts to enlight me. Ed Porter -----Original Message----- From: Vladimir Nesov [mailto:[EMAIL PROTECTED] Sent: Tuesday, October 21, 2008 7:52 PM To: agi@v2.listbox.com Subject: Re: [agi] Who is smart enough to answer this question? (I agree with the points I don't quote here) General reiteration on notation: O-1 is the maximum allowed overlap, overlap of O is already not allowed (it was this way in your first message). On Wed, Oct 22, 2008 at 3:08 AM, Ed Porter <[EMAIL PROTECTED]> wrote: > > T(N,S,O) = SUM FROM X = 0 TO S-O OF C(S, S-X)*C(N-S, X) > To match with the explanation of the size of the overlap, I intended T(N,S,O)= C(S,S)*C(N-S,S-S)+ C(S,S-1)*C(N-S,S-(S-1))+ ..+C(S,O)*C(N-S,S-O) to be parsed as T(N,S,O) = SUM FROM X =O TO S OF C(S,X)*C(N-S,S-X) > > Comparing this to C(S,X)*C(N-S,S-X) --- it appears that T(N,S,O) is equal to > the number of all combinations calculated by C(S,X)*C(N-S,S-X) where X is > greater than O, Thus it is an attempt to enumerate all such combinations in > which the overlap is more than O and thus which should be excluded from A. > I don't exclude them from A, as I don't know which of them will go to A and which will get banned multiple times. I exclude them from overall pool of C(N,S). > > --First, yes, each new assembly of length S added to the working set lowers > the number of remaining assemblies that we'll be able to add later, but > adding a given new assembly will ban not T(N,S,O) assemblies, but rather > only all those assemblies that overlap with it by more than O nodes. > But T(N,S,O) IS the number of all those assemblies that overlap with a given assembly by O or more nodes (having from X=O to X=S nodes of overlap). > > --Second, what are the cases where assemblies will be banned multiple times > that you mentioned in the above text? > It's one of the reasons it's a lower bound: in reality, some of the assemblies are banned multiple times, which leaves more free assemblies that could be added to the working set later. > > --Third --- as mentioned in my last group of comments --- why doesn't A = > C(N,S) - T(N,S,O), since C(N,S) is the total number of combinations of > length S that can be formed from N nodes, and T(N,S,O) appears to enumerate > all the combinations that occur with each possible overlap value greater O. > It's only overlap with one given assembly, blind to any other interactions, it says nothing about ideal combination of assemblies that manages to keep the overlap between each pair in check. > > --Fifth, is possible that even though T(N,S,O) appears to enumerate all > possible combinations in which all sets overlap by more than O, that it > fails to take into account possible combinations of sets of size S in which > some sets overlap by more than O and others do not? > > --in which case T(N,S,O) would be smaller than the number of all prohibited > combinations of sets of length S. Or would all the possible sets of length > S which overlap be have been properly taken into account in the above > formula for T? > T doesn't reason about combinations of sets, it's a filter on the individual sets from the total of C(N,S). > > --Sixth, if C(S,X)*C(N-S,S-X) enumerates all possible combinations having an > overlap of X, why can't one calculate A as follows? > > A = SUM FROM X = 0 TO O OF C(S,X)*C(N-S,S-X) > Because some of these sets intersect with each other, you can't include them all. -- Vladimir Nesov [EMAIL PROTECTED] http://causalityrelay.wordpress.com/ ------------------------------------------- agi Archives: https://www.listbox.com/member/archive/303/=now RSS Feed: https://www.listbox.com/member/archive/rss/303/ Modify Your Subscription: https://www.listbox.com/member/?&; Powered by Listbox: http://www.listbox.com ------------------------------------------- agi Archives: https://www.listbox.com/member/archive/303/=now RSS Feed: https://www.listbox.com/member/archive/rss/303/ Modify Your Subscription: https://www.listbox.com/member/?member_id=8660244&id_secret=117534816-b15a34 Powered by Listbox: http://www.listbox.com
