On two random search problems (Q1058449)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3900484
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | On two random search problems |
scientific article; zbMATH DE number 3900484 |
Statements
On two random search problems (English)
0 references
1985
0 references
The paper is concerned with static search on a finite set. An unknown subset of cardinality k of the finite set is to be found by testing its subsets. We investigate two problems: in the first, the number of common elements of the tested and the unknown subset is given; in the second, only the information whether the tested and the unknown subset are disjoint or not is given. Both problems correspond to problems on false coins. If the unknown subset is taken from the family of k-element sets with uniform distribution, we determine the minimum of the lengths of the strategies that find the unknown element with small error probability. The strategies are constructed by probabilistic means.
0 references
sequential
0 references
static strategies
0 references
random search
0 references
separating systems
0 references
static search on a finite set
0 references
false coins
0 references
0.783916175365448
0 references
0.7738110423088074
0 references
0.7725279927253723
0 references
