HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information

# An impossibility result for process discrimination

1 SEQUEL - Sequential Learning
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe, LAGIS - Laboratoire d'Automatique, Génie Informatique et Signal
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 :
Document type :
Conference papers
Domain :

Cited literature [16 references]

https://hal.inria.fr/inria-00319076
Contributor : Daniil Ryabko Connect in order to contact the contributor
Submitted on : Friday, July 10, 2009 - 11:30:56 AM
Last modification on : Thursday, January 20, 2022 - 4:16:30 PM
Long-term archiving on: : Friday, September 24, 2010 - 2:39:50 PM

### Files

discr.pdf
Files produced by the author(s)

### Identifiers

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

### Citation

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

Record views