---
OA_place: repository
OA_type: green
_id: '20572'
abstract:
- lang: eng
  text: "We present an elementary non-recursive formula for the multivariate moments\r\nof
    the Dirichlet distribution on the standard simplex, in terms of the pattern\r\ninventory
    of the moments' exponents. We obtain analog formulas for the\r\nmultivariate moments
    of the Dirichlet-Ferguson and Gamma measures. We further\r\nintroduce a polychromatic
    analogue of Ewens sampling formula on colored integer\r\npartitions, discuss its
    relation with suitable extensions of Hoppe's urn model\r\nand of the Chinese restaurant
    process, and prove that it satisfies an adapted\r\nnotion of consistency in the
    sense of Kingman."
acknowledgement: This research was funded by the Austrian Science Fund (FWF) ESPRIT
  208. For the purpose of open access, the authors have applied a CC BY public copyright
  licence to any Author Accepted Manuscript version arising from this submission.
  F.Q. gratefully acknowledges support by the Austrian Science Fund (FWF), Project
  SFB F65. The authors are grateful to Professor Nathanaël Berestycki for several
  helpful suggestions, and to Nicola Battisti and Dr. Elizabeth Hollwey for enlightening
  discussions on DNA-methylation.
article_number: '2309.11292'
article_processing_charge: No
arxiv: 1
author:
- first_name: Lorenzo
  full_name: Dello Schiavo, Lorenzo
  id: ECEBF480-9E4F-11EA-B557-B0823DDC885E
  last_name: Dello Schiavo
  orcid: 0000-0002-9881-6870
- first_name: Filippo
  full_name: Quattrocchi, Filippo
  id: 3ebd6ba8-edfb-11eb-afb5-91a9745ba308
  last_name: Quattrocchi
  orcid: 0009-0000-9773-1931
citation:
  ama: Dello Schiavo L, Quattrocchi F. Multivariate Dirichlet moments and a polychromatic
    Ewens sampling formula. <i>arXiv</i>. doi:<a href="https://doi.org/10.48550/arXiv.2309.11292">10.48550/arXiv.2309.11292</a>
  apa: Dello Schiavo, L., &#38; Quattrocchi, F. (n.d.). Multivariate Dirichlet moments
    and a polychromatic Ewens sampling formula. <i>arXiv</i>. <a href="https://doi.org/10.48550/arXiv.2309.11292">https://doi.org/10.48550/arXiv.2309.11292</a>
  chicago: Dello Schiavo, Lorenzo, and Filippo Quattrocchi. “Multivariate Dirichlet
    Moments and a Polychromatic Ewens Sampling Formula.” <i>ArXiv</i>, n.d. <a href="https://doi.org/10.48550/arXiv.2309.11292">https://doi.org/10.48550/arXiv.2309.11292</a>.
  ieee: L. Dello Schiavo and F. Quattrocchi, “Multivariate Dirichlet moments and a
    polychromatic Ewens sampling formula,” <i>arXiv</i>. .
  ista: Dello Schiavo L, Quattrocchi F. Multivariate Dirichlet moments and a polychromatic
    Ewens sampling formula. arXiv, 2309.11292.
  mla: Dello Schiavo, Lorenzo, and Filippo Quattrocchi. “Multivariate Dirichlet Moments
    and a Polychromatic Ewens Sampling Formula.” <i>ArXiv</i>, 2309.11292, doi:<a
    href="https://doi.org/10.48550/arXiv.2309.11292">10.48550/arXiv.2309.11292</a>.
  short: L. Dello Schiavo, F. Quattrocchi, ArXiv (n.d.).
corr_author: '1'
date_created: 2025-10-28T13:13:08Z
date_published: 2023-09-20T00:00:00Z
date_updated: 2025-11-24T13:53:48Z
day: '20'
department:
- _id: GradSch
- _id: JaMa
doi: 10.48550/arXiv.2309.11292
external_id:
  arxiv:
  - '2309.11292'
keyword:
- Dirichlet distribution
- Ewens sampling formula
- Hoppe urn model
- colored partitions
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.48550/arXiv.2309.11292
month: '09'
oa: 1
oa_version: Preprint
project:
- _id: 34dbf174-11ca-11ed-8bc3-afe9d43d4b9c
  grant_number: E208
  name: Configuration Spaces over Non-Smooth Spaces
- _id: 260482E2-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: F06504
  name: Taming Complexity in Partial Differential Systems
publication: arXiv
publication_status: draft
status: public
title: Multivariate Dirichlet moments and a polychromatic Ewens sampling formula
type: preprint
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2023'
...
---
_id: '10004'
abstract:
- lang: eng
  text: 'Markov chains are the de facto finite-state model for stochastic dynamical
    systems, and Markov decision processes (MDPs) extend Markov chains by incorporating
    non-deterministic behaviors. Given an MDP and rewards on states, a classical optimization
    criterion is the maximal expected total reward where the MDP stops after T steps,
    which can be computed by a simple dynamic programming algorithm. We consider a
    natural generalization of the problem where the stopping times can be chosen according
    to a probability distribution, such that the expected stopping time is T, to optimize
    the expected total reward. Quite surprisingly we establish inter-reducibility
    of the expected stopping-time problem for Markov chains with the Positivity problem
    (which is related to the well-known Skolem problem), for which establishing either
    decidability or undecidability would be a major breakthrough. Given the hardness
    of the exact problem, we consider the approximate version of the problem: we show
    that it can be solved in exponential time for Markov chains and in exponential
    space for MDPs.'
acknowledgement: We are grateful to the anonymous reviewers of LICS 2021 and of a
  previous version of this paper for insightful comments that helped improving the
  presentation. This research was partially supported by the grant ERC CoG 863818
  (ForM-SMArt).
article_processing_charge: No
arxiv: 1
author:
- first_name: Krishnendu
  full_name: Chatterjee, Krishnendu
  id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
  last_name: Chatterjee
  orcid: 0000-0002-4561-241X
- first_name: Laurent
  full_name: Doyen, Laurent
  last_name: Doyen
citation:
  ama: 'Chatterjee K, Doyen L. Stochastic processes with expected stopping time. In:
    <i>Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science</i>.
    Institute of Electrical and Electronics Engineers; 2021:1-13. doi:<a href="https://doi.org/10.1109/LICS52264.2021.9470595">10.1109/LICS52264.2021.9470595</a>'
  apa: 'Chatterjee, K., &#38; Doyen, L. (2021). Stochastic processes with expected
    stopping time. In <i>Proceedings of the 36th Annual ACM/IEEE Symposium on Logic
    in Computer Science</i> (pp. 1–13). Rome, Italy: Institute of Electrical and Electronics
    Engineers. <a href="https://doi.org/10.1109/LICS52264.2021.9470595">https://doi.org/10.1109/LICS52264.2021.9470595</a>'
  chicago: Chatterjee, Krishnendu, and Laurent Doyen. “Stochastic Processes with Expected
    Stopping Time.” In <i>Proceedings of the 36th Annual ACM/IEEE Symposium on Logic
    in Computer Science</i>, 1–13. Institute of Electrical and Electronics Engineers,
    2021. <a href="https://doi.org/10.1109/LICS52264.2021.9470595">https://doi.org/10.1109/LICS52264.2021.9470595</a>.
  ieee: K. Chatterjee and L. Doyen, “Stochastic processes with expected stopping time,”
    in <i>Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science</i>,
    Rome, Italy, 2021, pp. 1–13.
  ista: 'Chatterjee K, Doyen L. 2021. Stochastic processes with expected stopping
    time. Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science.
    LICS: Logic in Computer Science, 1–13.'
  mla: Chatterjee, Krishnendu, and Laurent Doyen. “Stochastic Processes with Expected
    Stopping Time.” <i>Proceedings of the 36th Annual ACM/IEEE Symposium on Logic
    in Computer Science</i>, Institute of Electrical and Electronics Engineers, 2021,
    pp. 1–13, doi:<a href="https://doi.org/10.1109/LICS52264.2021.9470595">10.1109/LICS52264.2021.9470595</a>.
  short: K. Chatterjee, L. Doyen, in:, Proceedings of the 36th Annual ACM/IEEE Symposium
    on Logic in Computer Science, Institute of Electrical and Electronics Engineers,
    2021, pp. 1–13.
conference:
  end_date: 2021-07-02
  location: Rome, Italy
  name: 'LICS: Logic in Computer Science'
  start_date: 2021-06-29
date_created: 2021-09-12T22:01:25Z
date_published: 2021-07-07T00:00:00Z
date_updated: 2025-09-08T14:54:13Z
day: '07'
department:
- _id: KrCh
doi: 10.1109/LICS52264.2021.9470595
ec_funded: 1
external_id:
  arxiv:
  - '2104.07278'
  isi:
  - '000947350400036'
isi: 1
keyword:
- Computer science
- Heuristic algorithms
- Memory management
- Automata
- Markov processes
- Probability distribution
- Complexity theory
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/2104.07278
month: '07'
oa: 1
oa_version: Preprint
page: 1-13
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
  call_identifier: H2020
  grant_number: '863818'
  name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer
  Science
publication_identifier:
  eisbn:
  - 978-1-6654-4895-6
  isbn:
  - 978-1-6654-4896-3
  issn:
  - 1043-6871
publication_status: published
publisher: Institute of Electrical and Electronics Engineers
quality_controlled: '1'
related_material:
  record:
  - id: '18630'
    relation: later_version
    status: public
scopus_import: '1'
status: public
title: Stochastic processes with expected stopping time
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2021'
...
---
_id: '11685'
abstract:
- lang: eng
  text: We consider the problem of sampling URLs uniformly at random from the Web.
    A tool for sampling URLs uniformly can be used to estimate various properties
    of Web pages, such as the fraction of pages in various Internet domains or written
    in various languages. Moreover, uniform URL sampling can be used to determine
    the sizes of various search engines relative to the entire Web. In this paper,
    we consider sampling approaches based on random walks of the Web graph. In particular,
    we suggest ways of improving sampling based on random walks to make the samples
    closer to uniform. We suggest a natural test bed based on random graphs for testing
    the effectiveness of our procedures. We then use our sampling approach to estimate
    the distribution of pages over various Internet domains and to estimate the coverage
    of various search engine indexes.
article_processing_charge: No
article_type: original
author:
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: Allan
  full_name: Heydon, Allan
  last_name: Heydon
- first_name: Michael
  full_name: Mitzenmacher, Michael
  last_name: Mitzenmacher
- first_name: Marc
  full_name: Najork, Marc
  last_name: Najork
citation:
  ama: Henzinger M, Heydon A, Mitzenmacher M, Najork M. On near-uniform URL sampling.
    <i>Computer Networks</i>. 2000;33(1-6):295-308. doi:<a href="https://doi.org/10.1016/s1389-1286(00)00055-4">10.1016/s1389-1286(00)00055-4</a>
  apa: Henzinger, M., Heydon, A., Mitzenmacher, M., &#38; Najork, M. (2000). On near-uniform
    URL sampling. <i>Computer Networks</i>. Elsevier. <a href="https://doi.org/10.1016/s1389-1286(00)00055-4">https://doi.org/10.1016/s1389-1286(00)00055-4</a>
  chicago: Henzinger, Monika, Allan Heydon, Michael Mitzenmacher, and Marc Najork.
    “On Near-Uniform URL Sampling.” <i>Computer Networks</i>. Elsevier, 2000. <a href="https://doi.org/10.1016/s1389-1286(00)00055-4">https://doi.org/10.1016/s1389-1286(00)00055-4</a>.
  ieee: M. Henzinger, A. Heydon, M. Mitzenmacher, and M. Najork, “On near-uniform
    URL sampling,” <i>Computer Networks</i>, vol. 33, no. 1–6. Elsevier, pp. 295–308,
    2000.
  ista: Henzinger M, Heydon A, Mitzenmacher M, Najork M. 2000. On near-uniform URL
    sampling. Computer Networks. 33(1–6), 295–308.
  mla: Henzinger, Monika, et al. “On Near-Uniform URL Sampling.” <i>Computer Networks</i>,
    vol. 33, no. 1–6, Elsevier, 2000, pp. 295–308, doi:<a href="https://doi.org/10.1016/s1389-1286(00)00055-4">10.1016/s1389-1286(00)00055-4</a>.
  short: M. Henzinger, A. Heydon, M. Mitzenmacher, M. Najork, Computer Networks 33
    (2000) 295–308.
date_created: 2022-07-28T15:11:53Z
date_published: 2000-06-01T00:00:00Z
date_updated: 2024-11-06T08:11:55Z
day: '01'
doi: 10.1016/s1389-1286(00)00055-4
extern: '1'
intvolume: '        33'
issue: 1-6
keyword:
- URL sampling
- Random walks
- Internet domain distribution
- Search engine size
language:
- iso: eng
month: '06'
oa_version: None
page: 295-308
publication: Computer Networks
publication_identifier:
  issn:
  - 1389-1286
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: On near-uniform URL sampling
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 33
year: '2000'
...
---
_id: '4317'
article_processing_charge: No
author:
- first_name: Nicholas H
  full_name: Barton, Nicholas H
  id: 4880FE40-F248-11E8-B48F-1D18A9856A87
  last_name: Barton
  orcid: 0000-0002-8548-5240
citation:
  ama: 'Barton NH. Speciation. In: Myers A, Giller P, eds. <i>Analytical Biogeography:
    An Integrated Approach to the Study of Animal and Plant Distributions</i>. 1st
    ed. Springer; 1988:185-218. doi:<a href="https://doi.org/10.1007/978-94-009-0435-4">10.1007/978-94-009-0435-4</a>'
  apa: 'Barton, N. H. (1988). Speciation. In A. Myers &#38; P. Giller (Eds.), <i>Analytical
    biogeography: An integrated approach to the study of animal and plant distributions</i>
    (1st ed., pp. 185–218). Springer. <a href="https://doi.org/10.1007/978-94-009-0435-4">https://doi.org/10.1007/978-94-009-0435-4</a>'
  chicago: 'Barton, Nicholas H. “Speciation.” In <i>Analytical Biogeography: An Integrated
    Approach to the Study of Animal and Plant Distributions</i>, edited by Alan Myers
    and Paul Giller, 1st ed., 185–218. Springer, 1988. <a href="https://doi.org/10.1007/978-94-009-0435-4">https://doi.org/10.1007/978-94-009-0435-4</a>.'
  ieee: 'N. H. Barton, “Speciation,” in <i>Analytical biogeography: An integrated
    approach to the study of animal and plant distributions</i>, 1st ed., A. Myers
    and P. Giller, Eds. Springer, 1988, pp. 185–218.'
  ista: 'Barton NH. 1988.Speciation. In: Analytical biogeography: An integrated approach
    to the study of animal and plant distributions. , 185–218.'
  mla: 'Barton, Nicholas H. “Speciation.” <i>Analytical Biogeography: An Integrated
    Approach to the Study of Animal and Plant Distributions</i>, edited by Alan Myers
    and Paul Giller, 1st ed., Springer, 1988, pp. 185–218, doi:<a href="https://doi.org/10.1007/978-94-009-0435-4">10.1007/978-94-009-0435-4</a>.'
  short: 'N.H. Barton, in:, A. Myers, P. Giller (Eds.), Analytical Biogeography: An
    Integrated Approach to the Study of Animal and Plant Distributions, 1st ed., Springer,
    1988, pp. 185–218.'
date_created: 2018-12-11T12:08:13Z
date_published: 1988-01-01T00:00:00Z
date_updated: 2022-02-08T09:19:50Z
day: '01'
doi: 10.1007/978-94-009-0435-4
edition: '1'
editor:
- first_name: Alan
  full_name: Myers, Alan
  last_name: Myers
- first_name: Paul
  full_name: Giller, Paul
  last_name: Giller
extern: '1'
keyword:
- biogeography
- biology
- complexity
- distribution
- evolution
- geology
language:
- iso: eng
main_file_link:
- url: https://link.springer.com/book/10.1007/978-94-009-0435-4#toc
month: '01'
oa_version: None
page: 185 - 218
publication: 'Analytical biogeography: An integrated approach to the study of animal
  and plant distributions'
publication_identifier:
  eissn:
  - 978-94-009-0435-4
  isbn:
  - 978-0-412-40050-6
publication_status: published
publisher: Springer
publist_id: '1736'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Speciation
type: book_chapter
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
year: '1988'
...