Search

Your search keyword '"Chassaing, Philippe"' showing total 103 results
Start Over Author "Chassaing, Philippe"

Refine your results

more »

more »

more »

more »
103 results on '"Chassaing, Philippe"'

1. Pascal's formulas and vector fields

Author

Chassaing, Philippe, Flin, Jules, and Zevio, Alexis

Subjects
Mathematics - Combinatorics
Abstract

We consider four examples of combinatorial triangles $\left(T(n,k)\right)_{0\le k\le n}$ (Pascal, Stirling of both types, Euler) : through saddle-point asymptotics, their \emph{Pascal's formulas} define four vector fields, together with their field lines that turn out to be the conjectured limit of sample paths of four well known Markov chains. We prove this asymptotic behaviour in three of the four cases.

Published
2022

2. The impatient collector

Author

Amri, Anis and Chassaing, Philippe

Subjects
Mathematics - Probability, Computer Science - Discrete Mathematics, Mathematics - Combinatorics
Abstract

In the coupon collector problem with $n$ items, the collector needs a random number of tries $T_n\simeq n\ln n$ to complete the collection. Also, after $nt$ tries, the collector has secured approximately a fraction $\zeta_\infty(t)=1-e^{-t}$ of the complete collection, so we call $\zeta_\infty$ the (asymptotic) \emph{completion curve}. In this paper, for $\nu>0$, we address the asymptotic shape $\zeta (\nu,.) $ of the completion curve under the condition $T_n\leq \left( 1+\nu \right) n$, i.e. assuming that the collection is \emph{completed unlikely fast}. As an application to the asymptotic study of complete accessible automata, we provide a new derivation of a formula due to Kor\v{s}unov.

Published
2019

3. A non-ergodic probabilistic cellular automaton with a unique invariant measure

Author

Chassaing, Philippe and Mairesse, Jean

Subjects
Computer Science - Formal Languages and Automata Theory, Computer Science - Discrete Mathematics, Mathematics - Probability
Abstract

We exhibit a Probabilistic Cellular Automaton (PCA) on the integers with an alphabet and a neighborhood of size 2 which is non-ergodic although it has a unique invariant measure. This answers by the negative an old open question on whether uniqueness of the invariant measure implies ergodicity for a PCA., Comment: To appear in Stochastic Processes and their Applications

Published
2010

4. Asymptotic behavior of some factorizations of random words

Author

Azad, Elahe Zohoorian and Chassaing, Philippe

Subjects
Mathematics - Probability
Abstract

In this paper we consider the normalized lengths of the factors of some factorizations of random words. First, for the \emph{Lyndon factorization} of finite random words with $n$ independent letters drawn from a finite or infinite totally ordered alphabet according to a general probability distribution, we prove that the limit law of the normalized lengths of the smallest Lyndon factors is a variant of the stickbreaking process. Convergence of the distribution of the lengths of the longest factors to a Poisson-Dirichlet distribution follows. Secondly we consider the \emph{standard factorization} of random \emph{Lyndon word} : we prove that the distribution of the normalized length of the standard right factor of a random $n$-letters long Lyndon word, derived from such an alphabet, converges, when $n$ is large, to: $$\mu(dx)=p_1 \delta_{1}(dx) + (1-p_1) \mathbf{1}_{[0,1)}(x)dx,$$ in which $p_1$ denotes the probability of the smallest letter of the alphabet., Comment: Random Structures and Algorithms, Wiley, In press

Published
2010

5. On the Convergence of Population Protocols When Population Goes to Infinity

Author

Bournez, Olivier, Chassaing, Philippe, Cohen, Johanne, Gerin, Lucas, and Koegler, Xavier

Subjects
Computer Science - Distributed, Parallel, and Cluster Computing
Abstract

Population protocols have been introduced as a model of sensor networks consisting of very limited mobile agents with no control over their own movement. A population protocol corresponds to a collection of anonymous agents, modeled by finite automata, that interact with one another to carry out computations, by updating their states, using some rules. Their computational power has been investigated under several hypotheses but always when restricted to finite size populations. In particular, predicates stably computable in the original model have been characterized as those definable in Presburger arithmetic. We study mathematically the convergence of population protocols when the size of the population goes to infinity. We do so by giving general results, that we illustrate through the example of a particular population protocol for which we even obtain an asymptotic development. This example shows in particular that these protocols seem to have a rather different computational power when a huge population hypothesis is considered., Comment: Submitted to Applied Mathematics and Computation. 2009

Published
2009

6. Efficient estimation of the cardinality of large data sets

Author

Chassaing, Philippe and Gerin, Lucas

Subjects
Mathematics - Statistics Theory, Mathematics - Probability
Abstract

F.Giroire has recently proposed an algorithm which returns the approximate number of distincts elements in a large sequence of words, under strong constraints coming from the analysis of large data bases. His estimation is based on statistical properties of uniform random variables in $[0,1]$. In this note we propose an optimal estimation, using Kullback information and estimation theory., Comment: Extended and improved version of the published paper

Published
2007

8. Merging costs for the additive Marcus-Lushnikov process, and Union-Find algorithms

Author

Chassaing, Philippe and Marchand, Regine

Subjects
Mathematics - Probability, Computer Science - Data Structures and Algorithms, Mathematics - Combinatorics, 68P10 (Primary) 60C05, 60J65, 68R05 (Secondary)
Abstract

Starting with a monodisperse configuration with $n$ size-1 particles, an additive Marcus-Lushnikov process evolves until it reaches its final state (a unique particle with mass $n$). At each of the $n-1$ steps of its evolution, a merging cost is incurred, that depends on the sizes of the two particles involved, and on an independent random factor. This paper deals with the asymptotic behaviour of the cumulated costs up to the $k$th clustering, under various regimes for $(n,k)$, with applications to the study of Union--Find algorithms., Comment: 28 pages, 1 figure

Published
2004

9. Local limit of labeled trees and expected volume growth in a random quadrangulation

Author

Chassaing, Philippe and Durhuus, Bergfinnur

Subjects
Mathematics - Probability, Mathematics - Combinatorics, 60C05 (Primary) 05C30, 05C05, 82B41 (Secondary)
Abstract

Exploiting a bijective correspondence between planar quadrangulations and well-labeled trees, we define an ensemble of infinite surfaces as a limit of uniformly distributed ensembles of quadrangulations of fixed finite volume. The limit random surface can be described in terms of a birth and death process and a sequence of multitype Galton--Watson trees. As a consequence, we find that the expected volume of the ball of radius $r$ around a marked point in the limit random surface is $\Theta(r^4)$., Comment: Published at http://dx.doi.org/10.1214/009117905000000774 in the Annals of Probability (http://www.imstat.org/aop/) by the Institute of Mathematical Statistics (http://www.imstat.org)

Published
2003
Full Text
View/download PDF

10. The center of mass of the ISE and the Wiener index of trees

Author

Janson, Svante and Chassaing, Philippe

Subjects
Mathematics - Probability, 60K35 (Primary), 60J85 (Secondary)
Abstract

We derive the distribution of the center of mass $S$ of the integrated superBrownian excursion (ISE) {from} the asymptotic distribution of the Wiener index for simple trees. Equivalently, this is the distribution of the integral of a Brownian snake. A recursion formula for the moments and asymptotics for moments and tail probabilities are derived., Comment: 11 pages

Published
2003

11. Random Planar Lattices and Integrated SuperBrownian Excursion

Author

Chassaing, Philippe and Schaeffer, Gilles

Subjects
Mathematics - Combinatorics, Mathematical Physics, Mathematics - Probability, 05C80 (Primary) 60C05 (Secondary)
Abstract

In this paper, a surprising connection is described between a specific brand of random lattices, namely planar quadrangulations, and Aldous' Integrated SuperBrownian Excursion (ISE). As a consequence, the radius r_n of a random quadrangulation with n faces is shown to converge, up to scaling, to the width r=R-L of the support of the one-dimensional ISE. More generally the distribution of distances to a random vertex in a random quadrangulation is described in its scaled limit by the random measure ISE shifted to set the minimum of its support in zero. The first combinatorial ingredient is an encoding of quadrangulations by trees embedded in the positive half-line, reminiscent of Cori and Vauquelin's well labelled trees. The second step relates these trees to embedded (discrete) trees in the sense of Aldous, via the conjugation of tree principle, an analogue for trees of Vervaat's construction of the Brownian excursion from the bridge. From probability theory, we need a new result of independent interest: the weak convergence of the encoding of a random embedded plane tree by two contour walks to the Brownian snake description of ISE. Our results suggest the existence of a Continuum Random Map describing in term of ISE the scaled limit of the dynamical triangulations considered in two-dimensional pure quantum gravity., Comment: 44 pages, 22 figures. Slides and extended abstract version are available at http://www.loria.fr/~schaeffe/Pub/Diameter/ and http://www.iecn.u-nancy.fr/~chassain/

Published
2002

17. Asymptotic behavior of some factorizations of random words.

Author

Zohoorian Azad, Elahe and Chassaing, Philippe

Subjects
DISTRIBUTION (Probability theory), VOCABULARY, FACTORIZATION
Abstract

In this paper, we consider the normalized lengths of the factors of some factorizations of random words. First, for the Lyndon factorization of finite random words with n independent letters drawn from a finite or infinite totally ordered alphabet according to a general probability distribution, we prove that the limit law of the normalized lengths of the smallest Lyndon factors is a variant of the stickbreaking process. Convergence of the distribution of the lengths of the longest factors to a Poisson–Dirichlet distribution follows. Second, we consider the standard factorization of random Lyndon word: we prove that the distribution of the normalized length of the standard right factor of a random n‐letters long Lyndon word, derived from such an alphabet, converges, when n is large, to: μ(dx)=p1δ1(dx)+(1−p1)1[0,1)(x)dx,$$ \mu (dx)={p}_1{\delta}_1(dx)+\left(1-{p}_1\right){\mathbf{1}}_{\left[0,1\right)}(x) dx, $$ in which p1$$ {p}_1 $$ denotes the probability of the smallest letter of the alphabet. [ABSTRACT FROM AUTHOR]

Published
2022
Full Text
View/download PDF

24. Asymptotic behavior of some factorizations of random words

Author

Zohoorian Azad, Elahe, Chassaing, Philippe, Institut Élie Cartan de Nancy (IECN), Institut National de Recherche en Informatique et en Automatique (Inria)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS), Damghan University of Basic Sciences, Mathematics faculty, ANR-08-BLAN-0190,A3,Arbres Aléatoires (continus) et Applications(2008), Damghan University, Institut Élie Cartan de Lorraine (IECL), and Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)

Subjects
convergence in distribution, standard right factor, Applied Mathematics, General Mathematics, Probability (math.PR), Poisson-Dirichlet distribution, 0102 computer and information sciences, Lyndon word, 01 natural sciences, Computer Graphics and Computer-Aided Design, MSC : 60F05, 60C05, 68R15, 05A05, [MATH.MATH-PR]Mathematics [math]/Probability [math.PR], 010104 statistics & probability, random word, 010201 computation theory & mathematics, 60F05, FOS: Mathematics, 0101 mathematics, longest run, Lyndon factor, Mathematics - Probability, Software, Computer Science::Formal Languages and Automata Theory
Abstract

In this paper we consider the normalized lengths of the factors of some factorizations of random words. First, for the \emph{Lyndon factorization} of finite random words with $n$ independent letters drawn from a finite or infinite totally ordered alphabet according to a general probability distribution, we prove that the limit law of the normalized lengths of the smallest Lyndon factors is a variant of the stickbreaking process. Convergence of the distribution of the lengths of the longest factors to a Poisson-Dirichlet distribution follows. Secondly we consider the \emph{standard factorization} of random \emph{Lyndon word} : we prove that the distribution of the normalized length of the standard right factor of a random $n$-letters long Lyndon word, derived from such an alphabet, converges, when $n$ is large, to: $$\mu(dx)=p_1 \delta_{1}(dx) + (1-p_1) \mathbf{1}_{[0,1)}(x)dx,$$ in which $p_1$ denotes the probability of the smallest letter of the alphabet., Comment: Random Structures and Algorithms, Wiley, In press

Published
2010
Full Text
View/download PDF

25. On the Convergence of a Population Protocol When Population Goes to Infinity

Author

Bournez, Olivier, Chassaing, Philippe, Cohen, Johanne, Gerin, Lucas, Koegler, Xavier, Theoretical adverse computations, and safety (CARTE), Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Institut Élie Cartan de Nancy (IECN), Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique de Lorraine (INPL)-Université Nancy 2-Université Henri Poincaré - Nancy 1 (UHP)-Institut National de Recherche en Informatique et en Automatique (Inria), ANR-05-SSIA-0016,SOGEA,Sécurité des Jeux. Equilibres et Algorithmes Répartis.(2005), Institut National de Recherche en Informatique et en Automatique (Inria)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS), Cohen épouse Bournez, Johanne, ARA Sécurité des systèmes embarqués et Intelligence Ambiante - Sécurité des Jeux. Equilibres et Algorithmes Répartis. - - SOGEA2005 - ANR-05-SSIA-0016 - SSIA - VALID, Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), and Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)

Subjects
[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], ComputingMilieux_MISCELLANEOUS
Abstract

International audience

Published
2008

26. Average-Case Analysis of the Chip Problem

Author

Alonso, Laurent, Chassaing, Philippe, Reingold, E.M., Schott, René, Models, algorithms and geometry for computer graphics and vision (ISA), INRIA Lorraine, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS), Institut Élie Cartan de Nancy (IECN), Institut National de Recherche en Informatique et en Automatique (Inria)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS), Illinois Institute of Technology (IIT), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique de Lorraine (INPL)-Université Nancy 2-Université Henri Poincaré - Nancy 1 (UHP)-Institut National de Recherche en Informatique et en Automatique (Inria), and Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)

Subjects
[MATH.MATH-PR]Mathematics [math]/Probability [math.PR], chip problem, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], majority problem, Hardware_PERFORMANCEANDRELIABILITY, algorithm analysis, probabilistic algorithms, Fault diagnosis
Abstract

URL : http://ijmcs.future-in-tech.net/R-Schott.pdf; International audience; In the system level, adaptive fault diagnosis problem we must determine which components (chips) in a system are defective, assuming the majority of them are good. Chips are tested as follows: Take two chips, say x and y, and have x report whether y is good or bad. If x is good, the answer is correct, but if x is bad, the answer is unreliable and can be either wrong with probability α or right with probability 1 − α. The key to identifying all defective chips is to identify a single good chip which can then be used to diagnose the other chips; the chip problem is to identify a single good chip. In [1] we have shown that the chip problem is closely related to a modified majority problem in the worst case and have used this fact to obtain upper and lower bounds on algorithms for the chip problem. In this paper, we show the limits of this relationship by showing that algorithms for the chip problem can violate lower bounds on average performance for the modified majority problem and we give an algorithm for the “biased chip” problem (a chip is bad with probability p) whose average performance is better than the average cost of the best algorithm for the biased majority problem.

Published
2006

27. Optimal Sequencing of Contract Algorithms

Author

Zilberstein, Shlomo, Charpillet, François, Chassaing, Philippe, Department of physics and astronomy (UMASS), University of Massachusetts [Amherst] (UMass Amherst), University of Massachusetts System (UMASS)-University of Massachusetts System (UMASS), Autonomous intelligent machine (MAIA), INRIA Lorraine, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS), Probabilistic numerical methods (OMEGA), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Centre National de la Recherche Scientifique (CNRS), Institut Élie Cartan de Nancy (IECN), and Institut National de Recherche en Informatique et en Automatique (Inria)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS)

Subjects
mathematical foundation, flexible computation, real time, mata-level control, IA, AI, temps reel, [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH], contract algorithms, real-time problem solving, algorithmes par contrat
Abstract

Article dans revue scientifique avec comité de lecture. internationale.; International audience; We address the problem of building an interruptible real-time system using non-interruptible components. Some artificial intelligence techniques offer a tradeoff between computation time and quality of results, but their run-time must be determined when they are activated. These techniques, called contract algorithms, introduce a complex scheduling problem when there is uncertainty about the amount of time available for problem-solving. We show how to optimally sequence contract algorithms to create the best possible interruptible system with or without stochastic information about the deadline. These results extend the foundation of real-time problem-solving and provide useful guidance for embedding contract algorithms in applications.

Published
1999
Full Text
View/download PDF

28. The Chip Problem

Author

Alonso, Laurent, Chassaing, Philippe, Reingold, Edward M., Schott, René, Models, algorithms and geometry for computer graphics and vision (ISA), INRIA Lorraine, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS), Institut Élie Cartan de Nancy (IECN), Institut National de Recherche en Informatique et en Automatique (Inria)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique de Lorraine (INPL)-Université Nancy 2-Université Henri Poincaré - Nancy 1 (UHP)-Institut National de Recherche en Informatique et en Automatique (Inria), and Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)

Subjects
chip problem, probabilité, [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH], analyse, majority problem, fault diagnosis, algorithm analysis, probabilistic algorithms, algorithme
Abstract

Rapport interne.; The ``chip problem'' is a fault diagnosis problem in which we must determine which components (chips) in a system are defective, assuming the majority of them are good. Chips are tested as follows: Take two chips, say $x$ and $y$, and have $x$ report whether $y$ is good or bad. If $x$ is good, the answer is correct, but if $x$ is bad, the answer is unreliable and can be either wrong with probability $\alpha$ or right with probability $1-\alpha$. We show that the chip problem is closely related to a modified majority problem in the {\em worst case} and use this fact to obtain upper and lower bounds on algorithms for the chip problem. We show the limits of this relationship by showing that algorithms for the chip problem can violate lower bounds on {\em average performance} for the modified majority problem and we give an algorithm for the ``biased chip'' problem (in which $p$ is the probability that a chip is bad) whose average performance is better than the average cost of the best algorithm for the biased majority problem.

Published
1998

33. Sorting with unreliable comparisons: a probabilistic analysis

Author

Janson, Svante, Alonso, Laurent, Chassaing, Philippe, Gillet, Florent, Reingold, Edward M., Schott, René, Janson, Svante, Alonso, Laurent, Chassaing, Philippe, Gillet, Florent, Reingold, Edward M., and Schott, René

Published
2003

34. Phase Transition for Parking Blocks, Brownian Excursion and Coalescence

Author

Chassaing, Philippe, Louchard, Guy, Chassaing, Philippe, and Louchard, Guy

Abstract

In this paper, we consider hashing with linear probing for a hashing table with m places, n items (n < m), and ℓ = m - n empty places. For a noncomputer science-minded reader, we shall use the metaphore of n cars parking on m places: each car ci, chooses a place pi at random, and if pi is occupied, ci tries successively p i + 1, pi + 2, until it finds an empty place. Pittel proves that when ℓ/m goes to some positive limit β < 1, the size B1m, ℓ of the largest block of consecutive cars satisfies 2(β - 1 - log β) B1m, ℓ = 2 log m - 3 log log m + Ξm, where Ξm converges weakly to an extreme-value distribution. In this paper we examine at which level for n a phase transition occurs between B1m,l = o(m) and m - B1m,l = o(m). The intermediate case reveals an interesting behavior of sizes of blocks, related to the standard additive coalescent in the same way as the sizes of connected components of the random graph are related to the multiplicative coalescent. © 2002 Wiley Periodicals, Inc., SCOPUS: ar.j, FLWIN, info:eu-repo/semantics/published

Published
2002

46. A Cross Entropy Algorithm for Classification with $\delta$−Patterns

Author

Gabriela Alexe, Gyan Bhanot, Adriana Climescu-Haulica, Computational Biology Center (IBM T.J. Watson Research Center), IBM, Department of Biomedical Engineering [Boston], Boston University [Boston] (BU), The Simons Center for Systems Biology (Institute for Advanced Study), Laboratoire de Modélisation et Calcul (LMC - IMAG), Université Joseph Fourier - Grenoble 1 (UJF)-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS), Laboratoire Biologie-Informatique-Mathématique (LBIM), Commissariat à l'énergie atomique et aux énergies alternatives (CEA), and Chassaing, Philippe and others

Subjects
Clique, Theoretical computer science, General Computer Science, Genomic data, Cross-entropy method, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Combinatorial optimization problem, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], delta patterns, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Theoretical Computer Science, [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], Cross entropy, classification, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], Discrete Mathematics and Combinatorics, Graph (abstract data type), [INFO.INFO-HC]Computer Science [cs]/Human-Computer Interaction [cs.HC], [INFO.INFO-HC] Computer Science [cs]/Human-Computer Interaction [cs.HC], Algorithm, genome, Mathematics
Abstract

A classification strategy based on $\delta$-patterns is developed via a combinatorial optimization problem related with the maximal clique generation problem on a graph. The proposed solution uses the cross entropy method and has the advantage to be particularly suitable for large datasets. This study is tailored for the particularities of the genomic data.

Published
2006
Full Text
View/download PDF

47. Spanning trees of finite Sierpiński graphs

Author

Elmar Teufl, Stephan Wagner, Fakultät für Mathematik = Faculty of Mathematics [Bielefeld], Universität Bielefeld = Bielefeld University, Institut für Mathematik [Graz] (IM), Karl-Franzens-Universität [Graz, Autriche], and Chassaing, Philippe and others

Subjects
Discrete mathematics, combinatorial enumeration, Spanning tree, General Computer Science, 010102 general mathematics, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, spanning trees, Graph, Theoretical Computer Science, Sierpinski triangle, Combinatorics, [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], finite Sierpiński graphs, 010201 computation theory & mathematics, Iterated function, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], Discrete Mathematics and Combinatorics, 0101 mathematics, Mathematics
Abstract

We show that the number of spanning trees in the finite Sierpiński graph of level $n$ is given by $\sqrt[4]{\frac{3}{20}} (\frac{5}{3})^{-n/2} (\sqrt[4]{540})^{3^n}$. The proof proceeds in two steps: First, we show that the number of spanning trees and two further quantities satisfy a $3$-dimensional polynomial recursion using the self-similar structure. Secondly, it turns out, that the dynamical behavior of the recursion is given by a $2$-dimensional polynomial map, whose iterates can be computed explicitly.

Published
2006

48. Analytic Combinatorics of Lattice Paths: Enumeration and Asymptotics for the Area

Author

Cyril Banderier, Bernhard Gittenberger, Laboratoire d'Informatique de Paris-Nord (LIPN), Université Sorbonne Paris Cité (USPC)-Institut Galilée-Université Paris 13 (UP13)-Centre National de la Recherche Scientifique (CNRS), Institut für Diskrete Mathematik und Geometrie [Wien], Vienna University of Technology (TU Wien), and Chassaing, Philippe and others

Subjects
General Computer Science, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Lattice path, Theoretical Computer Science, 010104 statistics & probability, Mathematics::Probability, 0502 economics and business, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], analytic combinatorics, Discrete Mathematics and Combinatorics, Brownian Excursion, [INFO.INFO-HC]Computer Science [cs]/Human-Computer Interaction [cs.HC], 0101 mathematics, Finite set, 050205 econometrics, Mathematics, Discrete mathematics, 05 social sciences, singularity analysis, Brownian excursion, Brownian bridge, [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], Symmetric function, [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], kernel method, algebraic function, Reflected Brownian motion, generating function, Analytic combinatorics, Algebraic function, [INFO.INFO-HC] Computer Science [cs]/Human-Computer Interaction [cs.HC]
Abstract

This paper tackles the enumeration and asymptotics of the area below directed lattice paths (walks on $\mathbb{N}$ with a finite set of jumps). It is a nice surprise (obtained via the "kernel method'') that the generating functions of the moments of the area are algebraic functions, expressible as symmetric functions in terms of the roots of the kernel. For a large class of walks, we give full asymptotics for the average area of excursions ("discrete'' reflected Brownian bridge) and meanders ("discrete'' reflected Brownian motion). We show that drift is not playing any role in the first case. We also generalise previous works related to the number of points below a path and to the area between a path and a line of rational slope.

Published
2006

49. On the spectral dimension of random trees

Author

Bergfinnur Durhuus, Thordur Jonsson, John F. Wheater, Department of Mathematical Sciences [Copenhagen], Faculty of Science [Copenhagen], University of Copenhagen = Københavns Universitet (KU)-University of Copenhagen = Københavns Universitet (KU), Science Institute, Faculty of Science of the University of Iceland, Rudolf Peierls Center for Theoretical Physics, University of Oxford [Oxford], and Chassaing, Philippe and others

Subjects
Class (set theory), General Computer Science, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Theoretical Computer Science, [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], Combinatorics, [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], random combs, Random tree, Spectral dimension, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], Discrete Mathematics and Combinatorics, Probability distribution, Variety (universal algebra), spectral dimension, random trees, Mathematics
Abstract

We determine the spectral dimensions of a variety of ensembles of infinite trees. Common to the ensembles considered is that sample trees have a distinguished infinite spine at whose vertices branches can be attached according to some probability distribution. In particular, we consider a family of ensembles of $\textit{combs}$, whose branches are linear chains, with spectral dimensions varying continuously between $1$ and $3/2$. We also introduce a class of ensembles of infinite trees, called $\textit{generic random trees}$, which are obtained as limits of ensembles of finite trees conditioned to have fixed size $N$, as $N \to \infty$. Among these ensembles is the so-called uniform random tree. We show that generic random trees have spectral dimension $d_s=4/3$.

Published
2006

50. Some exactly solvable models of urn process theory

Author

Philippe Flajolet, Philippe Dumas, Vincent Puyhaubert, Algorithms (ALGORITHMS), Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), and Chassaing, Philippe and others

Subjects
Pure mathematics, Monomial, General Computer Science, 010102 general mathematics, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Asymptotic distribution, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], Type (model theory), [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Theoretical Computer Science, [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], 010104 statistics & probability, [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], Simple (abstract algebra), [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], Discrete Mathematics and Combinatorics, Ehrenfest model, Isomorphism, 0101 mathematics, Hypergeometric function, Coupon collector's problem, urn process, Mathematics
Abstract

We establish a fundamental isomorphism between discrete-time balanced urn processes and certain ordinary differential systems, which are nonlinear, autonomous, and of a simple monomial form. As a consequence, all balanced urn processes with balls of two colours are proved to be analytically solvable in finite terms. The corresponding generating functions are expressed in terms of certain Abelian integrals over curves of the Fermat type (which are also hypergeometric functions), together with their inverses. A consequence is the unification of the analyses of many classical models, including those related to the coupon collector's problem, particle transfer (the Ehrenfest model), Friedman's "adverse campaign'' and Pólya's contagion model, as well as the OK Corral model (a basic case of Lanchester's theory of conflicts). In each case, it is possible to quantify very precisely the probable composition of the urn at any discrete instant. We study here in detail "semi-sacrificial'' urns, for which the following are obtained: a Gaussian limiting distribution with speed of convergence estimates as well as a characterization of the large and extreme large deviation regimes. We also work out explicitly the case of $2$-dimensional triangular models, where local limit laws of the stable type are obtained. A few models of dimension three or greater, e.g., "autistic'' (generalized Pólya), cyclic chambers (generalized Ehrenfest), generalized coupon-collector, and triangular urns, are also shown to be exactly solvable.

Published
2006
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results