Consider \(\{Z_i=(X_i,Y_i), i=1,\ldots, n\}\) a (random) set of \(n\) i.i.d. points on \([0,1]^2\), with common distribution \(P_{X,Y}\). A subset \(\{ Z_{i} \}_{i\in I}\) is said to be *increasing* if there exists a permutation \(\pi:I\to I\) such that \(X_{\pi(i)} < X_{\pi(i+1)}\) and \(Y_{\pi(i)} <Y_{\pi(i+1)}\) for all \(i\in I\). In other words, the set \(\{ Z_{i} \}_{i\in I}\) is increasing if its points can be connected by an up/right path. We are interested in the number of points of the longest *increasing* subset of \(\{Z_i\}_{i=1,\ldots, n}\), that we denote \(\ell_n\). One motivation is that in the case where \(P_{X,Y}\) is uniform on \([0,1]^2\), this is equivalent to Ulam's problem of the longest increasing subsequence of a random permutation \(\sigma\) taken uniformly in \(\mathfrak{S}_n\), which has turned out to have many connection with different areas of probability theory and combinatorics.

We offer here an illustration of a result by Deuschel and Zeitouni (Annals of Probability, 1995): under some mild conditions on \(P_{X,Y}\), we have

- \(\ell_n /\sqrt{n}\) converges in probability to a constant (which is explicit);
- maximal increasing subsets of \(\{Z_i\}_{i=1,\ldots, n}\) converge to a limiting curve (also explicit).

For the sake of the simulations, we focus on the simpler case when \(X\) and \(Y\) are independent: in that specific case, \(\ell_n /\sqrt{n} \to 2\) in probability (as found in Ulam's problem), and the limiting curve is parametrized as \((F_X(t), F_Y(t))_{t\in[0,1]}\), with \(F_X\) (resp. \(F_Y\)) the c.d.f. of \(X\) (resp. of \(Y\)). Let us consider here the case \(X\sim \text{Beta}(a,b)\), \(Y\sim \text{Beta}(c,d)\) independent (we recover the case where \(P_{X,Y}\) is uniform on \([0,1]^2\) by taking \(a=b=c=d=1\)).

Realized by Quentin Berger & Mihir John

Developed by Daphné Giorgi and Altaïr Pelissier