Intersection algorithm: Difference between revisions

Revision as of 23:05, 16 April 2014

Revision as of 09:54, 5 May 2014

Line 6:

==Method==

Given ''M'' intervals of the form ''c''&nbsp;&plusmn;±&nbsp;''r'' (which means [''c''&minus;''r'',''c''+''r'']), the algorithm seeks to find an interval with ''M''&minus;''f'' sources. The value ''f'' is referred to as the number of falsetickers, those sources which are in error (the actual value is outside the [[confidence band]]). The best estimate is that which assumes the least number of falsetickers, ''f''. The results will be considered valid if ''f''&nbsp;<&nbsp;''M''/2, otherwise the algorithm will return failure instead of an interval.

The intersection algorithm begins by creating a table of tuples <offset,type>. For each interval there are three entries: the lower endpoint, the midpoint and the upper endpoint, labelled with types &minus;1, 0 and +1 respectively. Thus the interval ''c''&nbsp;&plusmn;±&nbsp;''r'' results in the entries <''c''&minus;''r'',&minus;1>, <''c'',0> and <''c''+''r'',+1>. These entries are then sorted by offset.

Variables: This algorithm uses ''f'' as number of false tickers, ''endcount'' and ''midcount'' are integers. ''Lower'' and ''upper'' are values of offsets.

# <li value="0">[initialize best f] Start with ''f''=0, assuming all input intervals are valid. Each time no interval is found f will be incremented until either an interval is found or ''f''&nbsp;&ge;≥&nbsp;''M''/2.</li>

# [initialize] ''endcount''=0 and ''midcount''=0.

# [find lower endpoint] Start at beginning of the list (lowest offset) consider each tuple in order. ''endcount''&nbsp;=&nbsp;''endcount''&minus;''type''. If ''endcount''&nbsp;&ge;≥&nbsp;''M''&minus;''f'' then ''lower''&nbsp;=&nbsp;''offset'' and goto step 3 because the (possible) lower endpoint has been found. If the ''type''&nbsp;=&nbsp;0 then ''midcount''&nbsp;=&nbsp;''midcount''+1. Repeat with next tuple. If reach end of list then goto step 6.

# [tentative lower endpoint found, initialize to find upper endpoint] set ''endcount''=0.

# [determine number of midpoints] Start from end of list and work towards lower offsets. ''endcount''&nbsp;=&nbsp;''endcount''+''type''. If ''endcount''&nbsp;&ge;≥&nbsp;''M''&minus;''f'' then ''upper''&nbsp;=&nbsp;''offset'', goto step 5. If ''type''&nbsp;=&nbsp;0 then ''midcount''&nbsp;=&nbsp;''midcount''+1. Repeat for next tuple. If reach end of list then goto step 6.

# if ''lower''&nbsp;&le;≤&nbsp;''upper'' and ''midcount''&nbsp;&le;≤&nbsp;''f'' then return interval [''lowerendpoint'',''upperendpoint''] as resulting confidence interval.

#[increment number of falsetickers] ''f''&nbsp;=&nbsp;''f''+1. If ''f''&nbsp;&ge;≥&nbsp;''M''/2 then terminate and return FAILED, otherwise goto step 1.

==References ==