# An impossibility result for process discrimination

1 SEQUEL - Sequential Learning
LIFL - Laboratoire d'Informatique Fondamentale de Lille, LAGIS - Laboratoire d'Automatique, Génie Informatique et Signal, Inria Lille - Nord Europe
Abstract : Two series of binary observations $x_1,x_1,\dots$ and $y_1,y_2,\dots$ are presented: at each time $n\in\N$ we are given $x_n$ and $y_n$. It is assumed that the sequences are generated independently of each other by two B-processes. We are interested in the question of whether the sequences represent a typical realization of two different processes or of the same one. We demonstrate that this is impossible to decide, in the sense that every discrimination procedure is bound to err with non-negligible frequency when presented with sequences from some B-processes. This contrasts earlier positive results on B-processes, in particular those showing that there are consistent $\bar d$-distance estimates for this class of processes.
Keywords :
Type de document :
Communication dans un congrès
International Symposium on Information Theory, 2009, Seoul, South Korea. pp.1734-1738, 2009
Domaine :

Littérature citée [16 références]

https://hal.inria.fr/inria-00319076
Contributeur : Daniil Ryabko <>
Soumis le : vendredi 10 juillet 2009 - 11:30:56
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13
Document(s) archivé(s) le : vendredi 24 septembre 2010 - 14:39:50

### Fichiers

discr.pdf
Fichiers produits par l'(les) auteur(s)

### Identifiants

• HAL Id : inria-00319076, version 7
• ARXIV : 0809.1053

### Citation

Daniil Ryabko. An impossibility result for process discrimination. International Symposium on Information Theory, 2009, Seoul, South Korea. pp.1734-1738, 2009. 〈inria-00319076v7〉

### Métriques

Consultations de la notice

## 248

Téléchargements de fichiers