Source author record

Irène Marcovici

Irène Marcovici appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

math.CO Discrete Mathematics math.PR math.DS math.NT nlin.CG

Catalog footprint

What is connected

4works

6topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2023arXiv

On a probabilistic extension of the Oldenburger-Kolakoski sequence

The Oldenburger-Kolakoski sequence is the only infinite sequence over the alphabet $\{1,2\}$ that starts with $1$ and is its own run-length encoding. In the present work, we take a step back from this largely known and studied sequence by introducing some randomness in the choice of the letters written. This enables us to provide some results on the convergence of the density of $1$'s in the resulting sequence. When the choice of the letters is given by an infinite sequence of i.i.d. random variables or by a Markov chain, the average densities of letters converge. Moreover, in the case of i.i.d. random variables, we are able to prove that the densities even almost surely converge.

preprint2020arXiv

Bijections between walks inside a triangular domain and Motzkin paths of bounded amplitude

This paper solves an open question of Mortimer and Prellberg asking for an explicit bijection between two families of walks. The first family is formed by what we name triangular walks, which are two-dimensional walks moving in six directions (0°, 60°, 120°, 180°, 240°, 300°) and confined within a triangle. The other family is comprised of two-colored Motzkin paths with bounded height, in which the horizontal steps may be forbidden at maximal height. We provide several new bijections. The first one is derived from a simple inductive proof, taking advantage of a $2^n$-to-one function from generic triangular walks to triangular walks only using directions 0°, 120°, 240°. The second is based on an extension of Mortimer and Prellberg's results to triangular walks starting not only at a corner of the triangle, but at any point inside it. It has a linear-time complexity and is in fact adjustable: by changing some set of parameters called a scaffolding, we obtain a wide range of different bijections. Finally, we extend our results to higher dimensions. In particular, by adapting the previous proofs, we discover an unexpected bijection between three-dimensional walks in a pyramid and two-dimensional simple walks confined in a bounded domain shaped like a waffle.

preprint2020arXiv

Discrete correlations of order 2 of generalised Rudin-Shapiro sequences: a combinatorial approach

We introduce a family of block-additive automatic sequences, that are obtained by allocating a weight to each couple of digits, and defining the $n$th term of the sequence as being the total weight of the integer $n$ written in base $k$. Under an additional difference condition on the weight function, these sequences can be interpreted as generalised Rudin-Shapiro sequences, and we prove that they have the same correlations of order 2 as sequences of symbols chosen uniformly and independently at random. The speed of convergence is very fast and is independent of the prime factor decomposition of $k$. This extends recent work of Tahay. The proof relies on direct observations about base-$k$ representations of integers and combinatorial considerations. We also provide extensions of our results to higher-dimensional block-additive sequences.

preprint2016arXiv

Two-dimensional traffic rules and the density classification problem

The density classification problem is the computational problem of finding the majority in a given array of votes in a distributed fashion. It is known that no cellular automaton rule with binary alphabet can solve the density classification problem. On the other hand, it was shown that a probabilistic mixture of the traffic rule and the majority rule solves the one-dimensional problem correctly with a probability arbitrarily close to one. We investigate the possibility of a similar approach in two dimensions. We show that in two dimensions, the particle spacing problem, which is solved in one dimension by the traffic rule, has no cellular automaton solution. However, we propose exact and randomized solutions via interacting particle systems. We assess the performance of our models using numeric simulations.