3
$\begingroup$

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$?

$\endgroup$
1
  • $\begingroup$ 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 $\endgroup$
    – mike
    Sep 16, 2019 at 8:17

2 Answers 2

1
$\begingroup$

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}$$

$\endgroup$
1
$\begingroup$

(Too long for a comment.)

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.

$\endgroup$
2
  • $\begingroup$ denominator factored by $2,3,5$ and numerator square free. $\endgroup$
    – VS.
    Sep 16, 2019 at 23:34
  • $\begingroup$ 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); $\endgroup$ Sep 17, 2019 at 8:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.