# An extremal value distribution from monotone sequences

Pick two integer sequences $$d>a_n\geq a_{n-1}\geq\dots a_1\geq0$$ and $$d>b_n\geq b_{n-1}\geq\dots b_1\geq0$$ where $$d$$ is an integer bound with following method:

1. Pick $$a_n$$ uniformly from $$[0,d]$$ and rest of $$i\in\{1,\dots,n-1\}$$ uniformly from $$[0,a_{i+1}]$$.

2. Do similar picking for $$b_i$$'s.

What is the distribution of $$\max_i\log|a_i-b_i|$$ and expected value of $$\max_i\log|a_i-b_i|$$ as a function of $$d$$ and $$n$$?

• because it is a discrete problem there is a positive probability that the a's and b's are exactly the same, and the expected value is -inf – mike Sep 16 '19 at 8:17

The distribution of absolute difference of two uniform random variable is: $$P(|a_n-b_n| \leqslant t) = \frac{t(2d-t)}{d^2}$$ Since $$\log \ \& \ \exp$$ are increasing functions we have: $$P_n = P(\log|a_n-b_n| \leqslant t') = P(|a_n-b_n| \leqslant e^{t'}) = \frac{e^{t'}(2d-e^{t'})}{d^2}$$ Now notice that: $$a_m,b_m \longrightarrow 0 \Longrightarrow |a_m-b_m| \longrightarrow 0 \Longrightarrow \log|a_m-b_m| \longrightarrow -\infty$$ So the final answer must be a decreasing series $$\sum_{i=n}^{0}P_i$$. Since $$\{P_i\}$$ is a sequence that decreases by high rate, we have: $$\sum_{i=n}^{0}P_i \simeq P_n$$ And also for its expected value: $$E(\sum_{i=n}^{0}P_i) \simeq E(P_n) = \frac{e^{2d}-4de^d+2d^3+4d-1}{2d^2}$$
I doubt there's a closed-form expression, but one can obviously find the distribution recursively. Let us consider a more general scenario, where $$a_n$$ is chosen uniformly from $$\{0,1,2,\ldots,A\}$$, while $$b_n$$ — from $$\{0,1,2,\ldots,B\}$$. Write $$p(A,B,n,x)$$ for the probability that the maximum of $$|a_i - b_i|$$ is no greater than $$x$$. Then $$p(A,B,n,x) = \frac{1}{(A+1)(B+1)} \sum_{i = 0}^A \sum_{j = 0}^B \mathbb{1}_{\{|i - j| \leqslant x\}} p(i, j, n-1, x) ,$$ and $$p(i,j,0,x) = 1$$ for every $$x$$.
If I am not mistaken, the expectation for $$A = B = n = 5$$ turns out to be $$\frac{48733041639733}{33592320000000}$$, which does not resemble anything nice. The $$n \to \infty$$ limit might be more tractable.
• denominator factored by $2,3,5$ and numerator square free. – VS. Sep 16 '19 at 23:34
• If anyone wants to play with it, here is a Mathematica code for evaluating $p$: p[a_, b_, 0, x_] = 1; p[a_, b_, n_, x_] := p[a, b, n, x] = Sum[p[i, j, n - 1, x], {i, 0, a}, {j, Max[0, i - x], Min[b, i + x]}]/(a + 1)/(b + 1); – Mateusz Kwaśnicki Sep 17 '19 at 8:24