|
|
|
|
|
Let be the (lexicographical least) set of cardinality j such that, for , with and , we have . |
|
|
|
|
|
|
|
|
For each s , let and be such that: |
|
|
|
|
|
|
|
|
Claim: The team consisting of and witnesses that . |
|
|
|
|
|
|
|
|
Proof: Let T be a text. If j + 1 of the first 2j + 1 converging scientists on T converge to a correct grammar, then clearly converges to a correct grammar. Otherwise, in its selection of S s , removes j + 1 incorrect scientists from the first 2j + 1 converging scientists, ensuring that at least j + 1 of the scientists captured in S s and the next j + 1 converging scientists (that is, scientists converging in order 2j + 2, . . . , 3j + 2) converge to a correct grammar. This will guarantee that converges to a correct grammar. Thus, the claim and the proposition follow. |
|
|
|
|
|
|
|
|
The picture for team success ratio is completed by Proposition 9.44 below. The proof is complicated; the reader is directed to Jain and Sharma [92] for the details. We leave it to the reader to verify the corollary following the proposition. |
|
|
|
|
|
|
|
|
9.44 Proposition For all m and such that 2n does not divide m, we have that . |
|
|
|
|
|
|
|
|
9.45 Corollary For all m and , divides n or m is odd. |
|
|
|
|
|
|
|
|
Proposition 9.44 can also be used to show the next result that shows that probabilistic identification of languages with probability of success at least is strictly more powerful than team identification of languages with success ratio (see Jain and Sharma [92]). |
|
|
|
|
|
|
|
|
9.46 Proposition . |
|
|
|
|
|
|
|
|
The next proposition notes a similar fact about the power of probability over teams. Again, we direct the reader to Jain and Sharma [92] for the details. |
|
|
|
|
|
|
|
|
9.47 Proposition For all , . |
|
|
|
|