Title:The distributions of sliding block patterns in finite samples and the inclusion-exclusion principles for partially ordered sets.
Author: Hayato Takahashi
Abstract:The sliding block patterns are the random variables that count the number of the appearance of words in finite samples.
In this paper we show a new formula of the distributions of sliding block patterns for Bernoulli processes with finite alphabet.
In particular we show a new inclusion-exclusion principle on partially ordered sets with multivariate generating function, and
give a simple formula of the distribution of the sliding block patterns with generating functions.
We also show the formula of higher moments of the sliding block patterns.
By comparing the powers of tests, we show the significant performance of the sliding block patterns tests.
We show that the sliding block patterns tests reject the BSD Library RNG with p-value almost zero.
Key words: suffix tree, combinatorics, inclusion-exclusion principles, statistical tests, pseudo random numbers
Title:Computation of the exact distributions of the words
Author: Hayato Takahashi
Poster presentation at Bernoulli-IMS One World Symposium 2020
Title:The explicit formulae for the distributions of nonoverlapping words and its applications to statistical tests for
pseudo random numbers
Author: Hayato Takahashi
Abstract:
The distributions of the number of occurrences of words (the distributions of words for short) play key roles
in information theory, statistics, probability theory, ergodic theory, computer science, and DNA analysis.
Bassino et al. 2010 and Regnier et al. 1998 showed
generating functions of the distributions of words for all sample sizes.
Robin et al. 1999 presented
generating functions of the distributions for the return time of words and demonstrated a recurrence formula for these distributions.
These generating functions are rational functions; except for simple cases, it is difficult to expand them into power series.
In this paper, we study finite-dimensional generating functions of the distributions of nonoverlapping words for each fixed sample size
and demonstrate the explicit formulae for the distributions of words for the Bernoulli models.
Our results are generalized to nonoverlapping partial words.
We study statistical tests that depend on the number of occurrences of words and
the number of block-wise occurrences of words, respectively. We demonstrate that the power of the test that depends on the number of occurrences of words is significantly large compared to the other one.
Finally, we apply our results to statistical tests for pseudo random numbers.
Title:The explicit formula for the distributions of the nonoverlapping words
Author: Hayato Takahashi
IEICE online presentation.
Title:Some explicit formulae for the distributions of words
Author: Hayato Takahashi
Abstract for MSJ2023.
Title:Explicit formulae for the distributions of runs
Author: Hayato Takahashi
IEICT IT.
Title: A unified approach to explicit formulae for the distributions of runs
Author: Hayato Takahashi
Workshop Number theory and Ergodic theory.
Title: The explicit formulae for the distributions of words
Author: Hayato Takahashi
Title: Test of randomness with distributions of words
Author: Hayato Takahashi
Title: Explicit formulae for distributions of words and their computational complexity
Author: Hayato Takahashi