Results 1 to 10 of about 45 (45)
The number of distinct adjacent pairs in geometrically distributed words: a probabilistic and combinatorial analysis [PDF]
Discrete Mathematics & Theoretical Computer Science, 2023 The analysis of strings of $n$ random variables with geometric distribution has recently attracted renewed interest: Archibald et al. consider the number of distinct adjacent pairs in geometrically distributed words.
Guy Louchard +2 more
doaj +1 more source
A note on limits of sequences of binary trees [PDF]
Discrete Mathematics & Theoretical Computer Science, 2023 We discuss a notion of convergence for binary trees that is based on subtree sizes. In analogy to recent developments in the theory of graphs, posets and permutations we investigate some general aspects of the topology, such as a characterization of the ...
Rudolf Grübel
doaj +1 more source
Bounded affine permutations I. Pattern avoidance and enumeration [PDF]
Discrete Mathematics & Theoretical Computer Science, 2021 We introduce a new boundedness condition for affine permutations, motivated by the fruitful concept of periodic boundary conditions in statistical physics. We study pattern avoidance in bounded affine permutations.
Neal Madras, Justin M. Troyka
doaj +1 more source
On an alternative sequence comparison statistic of Steele [PDF]
Discrete Mathematics & Theoretical Computer Science, 2020 The purpose of this paper is to study a statistic that is used to compare the similarity between two strings, which is first introduced by Michael Steele in 1982.
Ümit Işlak, Alperen Y. Özdemir
doaj +1 more source
Expected size of a tree in the fixed point forest [PDF]
Discrete Mathematics & Theoretical Computer Science, 2019 We study the local limit of the fixed-point forest, a tree structure associated to a simple sorting algorithm on permutations. This local limit can be viewed as an infinite random tree that can be constructed from a Poisson point process configuration on
Samuel Regan, Erik Slivken
doaj +1 more source
Asymptotic distribution of fixed points of pattern-avoiding involutions [PDF]
Discrete Mathematics & Theoretical Computer Science, 2017 For a variety of pattern-avoiding classes, we describe the limiting distribution for the number of fixed points for involutions chosen uniformly at random from that class.
Samuel Miner +2 more
doaj +1 more source
Expected Number of Distinct Subsequences in Randomly Generated Binary Strings [PDF]
Discrete Mathematics & Theoretical Computer Science, 2018 When considering binary strings, it's natural to wonder how many distinct subsequences might exist in a given string. Given that there is an existing algorithm which provides a straightforward way to compute the number of distinct subsequences in a fixed
Yonah Biers-Ariel +2 more
doaj +1 more source
Pattern Avoidance for Random Permutations [PDF]
Discrete Mathematics & Theoretical Computer Science, 2018 Using techniques from Poisson approximation, we prove explicit error bounds on the number of permutations that avoid any pattern. Most generally, we bound the total variation distance between the joint distribution of pattern occurrences and a ...
Harry Crane, Stephen DeSalvo
doaj +1 more source
Variance and Covariance of Several Simultaneous Outputs of a Markov Chain [PDF]
Discrete Mathematics & Theoretical Computer Science, 2016 The partial sum of the states of a Markov chain or more generally a Markov source is asymptotically normally distributed under suitable conditions. One of these conditions is that the variance is unbounded.
Sara Kropf
doaj +1 more source
The Largest Component in Critical Random Intersection Graphs
Discussiones Mathematicae Graph Theory, 2018 In this paper, through the coupling and martingale method, we prove the order of the largest component in some critical random intersection graphs is n23$n^{{2 \over 3}}$ with high probability and the width of scaling window around the critical ...
Wang Bin, Wang Longmin, Xiang Kainan
doaj +1 more source