Alexander Gnedin
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Alexander Gnedin has a total of 16 co-authors. Here are the top co-authors by number of shared publications:
- Alexander Iksanov
Faculty of Computer Science and Cybernetics, Taras Shevchenko National University of Kyiv, Kyiv, Ukraine
9 shared publications - Alexander Marynych
Department of Mathematics, Kyiv School of Economics, Kyiv, Ukraine
6 shared publications - Vadim Gorin
Departments of Statistics and Mathematics University of California Berkeley CA United States
5 shared publications - Martin Möhle
Mathematisches Institut, Eberhard Karls Universität Tübingen, Auf der Morgenstelle 10, 72076 Tübingen, Germany
3 shared publications - Zakaria Derbazi
School of Mathematical Sciences, Queen Mary University of London, London, UK
3 shared publications - Alexander Marynych
Technical University of Eindhoven
2 shared publications
Latest Publications
- Open Access
- 25 August 2026
- Published by Springer Nature in Order
- Vol. 43 (3) , 29
Infinite Size-Biased Orders
The infinite random size-biased order with arbitrary positive size parameters is introduced and represented in terms of independent exponential random variables. We collect basic properties and constructions of the order, some of which belong to the folklore and some are new. Our central result shows how the isomorphism type of the order (e.g. $${\mathbb {Z}}_{>0}, {\mathbb {Q}}$$ or any other possible) depends on the parameters. In most cases, for a given set of parameters the type is the same almost surely.- 25 August 2026
- Published by Springer Nature in Order
- Vol. 43 (3) , 29
Open AccessInfinite Size-Biased Orders
The infinite random size-biased order with arbitrary positive size parameters is introduced and represented in terms of independent exponential random variables. We collect basic properties and constructions of the order, some of which belong to the folklore and some are new. Our central result shows how the isomorphism type of the order (e.g. $${\mathbb {Z}}_{>0}, {\mathbb {Q}}$$ or any other possible) depends on the parameters. In most cases, for a given set of parameters the type is the same almost surely. - Open Access
Maximal Counts in the Stopped Occupancy Problem
We revisit a version of the classic occupancy scheme, where balls are thrown until almost all boxes receive a given number of balls. Special cases are widely known as coupon-collectors and dixie cup problems. We show that as the number of boxes tends to infinity, the distribution of the maximal occupancy count does not converge, but can be approximated by a convolution of two Gumbel distributions, with the approximating distribution having oscillations close to periodic on a logarithmic scale. We pursue two approaches: one relies on lattice point processes obtained by poissonisation of the number of balls and boxes, and the other employs interpolation of the multiset of occupancy counts to a point process on reals. This way we gain considerable insight in known asymptotics obtained previously by mostly analytic tools. Further results concern the moments of maximal occupancy counts and ties for the maximum.
Open AccessMaximal Counts in the Stopped Occupancy Problem
We revisit a version of the classic occupancy scheme, where balls are thrown until almost all boxes receive a given number of balls. Special cases are widely known as coupon-collectors and dixie cup problems. We show that as the number of boxes tends to infinity, the distribution of the maximal occupancy count does not converge, but can be approximated by a convolution of two Gumbel distributions, with the approximating distribution having oscillations close to periodic on a logarithmic scale. We pursue two approaches: one relies on lattice point processes obtained by poissonisation of the number of balls and boxes, and the other employs interpolation of the multiset of occupancy counts to a point process on reals. This way we gain considerable insight in known asymptotics obtained previously by mostly analytic tools. Further results concern the moments of maximal occupancy counts and ties for the maximum.
- Open Access
- 19 October 2024
- Published by Springer Nature in Mathematical Methods of Operations Research
- Vol. 101 (1) , 1-27
The last-success stopping problem with random observation times
Suppose N independent Bernoulli trials with success probabilities $$p_1, p_2,\ldots $$ are observed sequentially at times of a mixed binomial process. The task is to maximise, by using a nonanticipating stopping strategy, the probability of stopping at the last success. The case $$p_k=1/k$$ has been studied by many authors as a version of the familiar best choice problem, where both N and the observation times are random. We consider a more general profile $$p_k=\theta /(\theta +k-1)$$ and assume that the prior distribution of N is negative binomial with shape parameter $$\nu $$ , so the arrivals occur at times of a mixed Poisson process. The setting with two parameters offers a high flexibility in understanding the nature of the optimal strategy, which we show is intrinsically related to monotonicity properties of the Gaussian hypergeometric function. Using this connection, we find that the myopic stopping strategy is optimal if and only if $$\nu \ge \theta $$ . Furthermore, we derive formulas to assess the winning probability and discuss limit forms of the problem for large N.- 19 October 2024
- Published by Springer Nature in Mathematical Methods of Operations Research
- Vol. 101 (1) , 1-27
Open AccessThe last-success stopping problem with random observation times
Suppose N independent Bernoulli trials with success probabilities $$p_1, p_2,\ldots $$ are observed sequentially at times of a mixed binomial process. The task is to maximise, by using a nonanticipating stopping strategy, the probability of stopping at the last success. The case $$p_k=1/k$$ has been studied by many authors as a version of the familiar best choice problem, where both N and the observation times are random. We consider a more general profile $$p_k=\theta /(\theta +k-1)$$ and assume that the prior distribution of N is negative binomial with shape parameter $$\nu $$ , so the arrivals occur at times of a mixed Poisson process. The setting with two parameters offers a high flexibility in understanding the nature of the optimal strategy, which we show is intrinsically related to monotonicity properties of the Gaussian hypergeometric function. Using this connection, we find that the myopic stopping strategy is optimal if and only if $$\nu \ge \theta $$ . Furthermore, we derive formulas to assess the winning probability and discuss limit forms of the problem for large N. - 1 January 2024
- Published by Institute for Applied and Pure Mathematics (IMPA) in Latin American Journal of Probability and Mathematical Statistics
- Vol. 21 (2) , 1475-1493
Records in the Infinite Occupancy Scheme
- 1 January 2024
- Published by Institute for Applied and Pure Mathematics (IMPA) in Latin American Journal of Probability and Mathematical Statistics
- Vol. 21 (2) , 1475-1493
Records in the Infinite Occupancy Scheme
- Open Access
- 17 November 2023
- Published by Wiley in Bulletin of the London Mathematical Society
- Vol. 56 (2) , 662-680
A random graph growth model
A growing random graph is constructed by successively sampling without replacement an element from the pool of virtual vertices and edges. At start of the process, the pool contains virtual vertices and no edges. Each time a vertex is sampled and occupied, the edges linking the vertex to previously occupied vertices are added to the pool of virtual elements. We focus on the edge‐counting at times when the graph has occupied vertices. Two different Poisson limits are identified for and . For the bulk of the process, when , the scaled number of edges is shown to fluctuate about a deterministic curve, with fluctuations being of the order of and approximable by a Gaussian bridge.
- 17 November 2023
- Published by Wiley in Bulletin of the London Mathematical Society
- Vol. 56 (2) , 662-680
Open AccessA random graph growth model
A growing random graph is constructed by successively sampling without replacement an element from the pool of virtual vertices and edges. At start of the process, the pool contains virtual vertices and no edges. Each time a vertex is sampled and occupied, the edges linking the vertex to previously occupied vertices are added to the pool of virtual elements. We focus on the edge‐counting at times when the graph has occupied vertices. Two different Poisson limits are identified for and . For the bulk of the process, when , the scaled number of edges is shown to fluctuate about a deterministic curve, with fluctuations being of the order of and approximable by a Gaussian bridge.
- Open Access
- 29 November 2022
- Published by Springer Nature in Extremes
- Vol. 26 (1) , 157-182
Running minimum in the best-choice problem
The full-information best choice problem asks one to find a strategy maximising the probability of stopping at the minimum (or maximum) of a sequence $$X_1,\cdots ,X_n$$ of i.i.d. random variables with continuous distribution. In this paper we look at more general models, where independent $$X_j$$ ’s may have different distributions, discrete or continuous. A central role in our study is played by the running minimum process, which we first employ to re-visit the classic problem and its limit Poisson counterpart. The approach is further applied to two explicitly solvable models: in the first the distribution of the jth variable is uniform on $$\{j,\cdots ,n\}$$ , and in the second it is uniform on $$\{1,\cdots , n\}$$ .- 29 November 2022
- Published by Springer Nature in Extremes
- Vol. 26 (1) , 157-182
Open AccessRunning minimum in the best-choice problem
The full-information best choice problem asks one to find a strategy maximising the probability of stopping at the minimum (or maximum) of a sequence $$X_1,\cdots ,X_n$$ of i.i.d. random variables with continuous distribution. In this paper we look at more general models, where independent $$X_j$$ ’s may have different distributions, discrete or continuous. A central role in our study is played by the running minimum process, which we first employ to re-visit the classic problem and its limit Poisson counterpart. The approach is further applied to two explicitly solvable models: in the first the distribution of the jth variable is uniform on $$\{j,\cdots ,n\}$$ , and in the second it is uniform on $$\{1,\cdots , n\}$$ . - 1 March 2022
- Published by Elsevier in Stochastic Processes and their Applications
- Vol. 145, 226-240
The best choice problem with random arrivals: How to beat the 1 / e -strategy
- 1 March 2022
- Published by Elsevier in Stochastic Processes and their Applications
- Vol. 145, 226-240
The best choice problem with random arrivals: How to beat the 1 / e -strategy
- Open Access
- 5 January 2022
- Published by MDPI AG in Mathematics
- Vol. 10 (1) , 158
Trapping the Ultimate Success
We introduce a betting game where the gambler aims to guess the last success epoch in a series of inhomogeneous Bernoulli trials paced randomly in time. At a given stage, the gambler may bet on either the event that no further successes occur, or the event that exactly one success is yet to occur, or may choose any proper range of future times (a trap). When a trap is chosen, the gambler wins if the last success epoch is the only one that falls in the trap. The game is closely related to the sequential decision problem of maximising the probability of stopping on the last success. We use this connection to analyse the best-choice problem with random arrivals generated by a Pólya-Lundberg process.
- 5 January 2022
- Published by MDPI AG in Mathematics
- Vol. 10 (1) , 158
Open AccessTrapping the Ultimate Success
We introduce a betting game where the gambler aims to guess the last success epoch in a series of inhomogeneous Bernoulli trials paced randomly in time. At a given stage, the gambler may bet on either the event that no further successes occur, or the event that exactly one success is yet to occur, or may choose any proper range of future times (a trap). When a trap is chosen, the gambler wins if the last success epoch is the only one that falls in the trap. The game is closely related to the sequential decision problem of maximising the probability of stopping on the last success. We use this connection to analyse the best-choice problem with random arrivals generated by a Pólya-Lundberg process.
- 1 September 2021
- Published by Elsevier in Stochastic Processes and their Applications
- Vol. 139, 298-320
Diffusion approximations in the online increasing subsequence problem
- 1 September 2021
- Published by Elsevier in Stochastic Processes and their Applications
- Vol. 139, 298-320
Diffusion approximations in the online increasing subsequence problem
- Open Access
- 26 February 2020
- Published by Springer Nature in Probability Theory and Related Fields
- Vol. 177 (3-4) , 855-890
On nested infinite occupancy scheme in random environment
We consider an infinite balls-in-boxes occupancy scheme with boxes organised in nested hierarchy, and random probabilities of boxes defined in terms of iterated fragmentation of a unit mass. We obtain a multivariate functional limit theorem for the cumulative occupancy counts as the number of balls approaches infinity. In the case of fragmentation driven by a homogeneous residual allocation model our result generalises the functional central limit theorem for the block counts in Ewens’ and more general regenerative partitions.
- 26 February 2020
- Published by Springer Nature in Probability Theory and Related Fields
- Vol. 177 (3-4) , 855-890
Open AccessOn nested infinite occupancy scheme in random environment
We consider an infinite balls-in-boxes occupancy scheme with boxes organised in nested hierarchy, and random probabilities of boxes defined in terms of iterated fragmentation of a unit mass. We obtain a multivariate functional limit theorem for the cumulative occupancy counts as the number of balls approaches infinity. In the case of fragmentation driven by a homogeneous residual allocation model our result generalises the functional central limit theorem for the block counts in Ewens’ and more general regenerative partitions.