11institutetext: Department of Software Engineering, Shamoon College of
Engineering, Israel
11email<EMAIL_ADDRESS>22institutetext: Computer Science Department, Ben-
Gurion University, Israel
22email<EMAIL_ADDRESS>
22email<EMAIL_ADDRESS>33institutetext: Department of Applied
Mathematics and Statistics, Stony Brook University, USA
33email<EMAIL_ADDRESS>
# Geometric Spanning Trees Minimizing the Wiener Index

A. Karim Abu-Affash 11 Paz Carmi 22 Ori Luwisch 22 Joseph S. B. Mitchell 33

###### Abstract

The Wiener index of a network, introduced by the chemist Harry Wiener [30], is
the sum of distances between all pairs of nodes in the network. This index,
originally used in chemical graph representations of the non-hydrogen atoms of
a molecule, is considered to be a fundamental and useful network descriptor.
We study the problem of constructing geometric networks on point sets in
Euclidean space that minimize the Wiener index: given a set $P$ of $n$ points
in $\mathbb{R}^{d}$, the goal is to construct a network, spanning $P$ and
satisfying certain constraints, that minimizes the Wiener index among the
allowable class of spanning networks.

In this work, we focus mainly on spanning networks that are trees and we focus
on problems in the plane ($d=2$). We show that any spanning tree that
minimizes the Wiener index has non-crossing edges in the plane. Then, we use
this fact to devise an $O(n^{4})$-time algorithm that constructs a spanning
tree of minimum Wiener index for points in convex position. We also prove that
the problem of computing a spanning tree on $P$ whose Wiener index is at most
$W$, while having total (Euclidean) weight at most $B$, is NP-hard.

Computing a tree that minimizes the Wiener index has been studied in the area
of communication networks, where it is known as the _optimum communication
spanning tree problem_.

###### Keywords:

Wiener Index Optimum communication spanning tree Minimum routing cost spanning
tree.

##  1 Introduction

The _Wiener index_ of a weighted graph $G=(V,E)$ is the sum, $\sum_{u,v\in
V}\delta_{G}(u,v)$, of the shortest path lengths in the graph between every
pair of vertices, where $\delta_{G}(u,v)$ is the weight of the shortest
(minimum-weight) path between $u$ and $v$ in $G$. The Wiener index was
introduced by the chemist Harry Wiener in 1947 [30]. The Wiener index and its
several variations have found applications in chemistry, e.g., in predicting
the antibacterial activity of drugs and modeling crystalline phenomena. It has
also has been used to give insight into various chemical and physical
properties of molecules [28] and to correlate the structure of molecules with
their biological activity [20]. The Wiener index has become part of the
general scientific culture, and it is still the subject of intensive research
[2, 10, 12, 32]. In its applications in chemistry, the Wiener index is most
often studied in the context of unweighted graphs. The study of minimizing the
sum of interpoint distances also arises naturally in the network design field,
where the problem of computing a spanning tree of minimum Wiener index is
known as the _Optimum Communication Spanning Tree_ (OCST) problem [18, 15].

Given a undirected graph $G=(V,E)$ and a (nonnegative) weight function on the
edges of $G$, representing the delay on each edge, the routing cost $c(T)$ of
a spanning tree $T$ of $G$ is the sum of the weights (delays) of the paths in
$T$ between every pair of vertices: $c(T)=\sum_{u,v\in V}\delta_{T}(u,v)$,
where $\delta_{T}(u,v)$ is the weight of the (unique) path between $u$ and $v$
in $T$. The OCST problem aims to find a minimum routing cost spanning tree of
a given weighted undirected graph $G$, thereby seeking to minimize the
expected cost of a path within the tree between two randomly chosen vertices.
The OCST was originally introduced by Hu [18] and is known to be NP-complete
in graphs, even if all edge weights are 1 [19]. Wu et al. [31] presented a
polynomial time approximation scheme (PTAS) for the OCST problem.
Specifically, they showed that the best $k$-star (a tree with at most $k$
internal vertices) yields a $(\frac{k+3}{k+1})$-approximation for the problem,
resulting in a $(1+\varepsilon)$-approximation algorithm of running time
$O\big{(}n^{2\lceil\frac{2}{\varepsilon}\rceil-2}\big{)}$.

While there is an abundance of research related to the Wiener index, e.g.,
computing and bounding the Wiener indexes of specific graphs or classes of
graphs [16, 17, 24] and explicit formulas for the Wiener index for special
classes of graphs [3, 23, 26, 30, 29], to the best of our knowledge, the
Wiener index has not received much attention in geometric settings. In this
work, we study the Wiener index and the optimum communication spanning tree
problem in selected geometric settings, hoping to bring this important and
highly applicable index to the attention of computational geometry
researchers.

### Our Contributions and Overview.

Let $P$ be a set of $n$ points in the plane. we study the problem of computing
a spanning tree on $P$ that minimizes the Wiener index when the underlying
graph is the complete graph on $P$, with edge weights given by their Euclidean
lengths. In Section 2, we prove that the optimal tree (that minimizes the
Wiener index) has no crossing edges. As our main algorithmic result, in
Section 3, we give a polynomial-time algorithm to solve the problem when the
points $P$ are in convex position; this result strongly utilizes the
structural result that the edges of an optimal tree do not cross, which
enables us to devise a dynamic programming algorithm to optimize. Then, in
Section 4, we prove that the “Euclidean Wiener Index Tree Problem”, in which
we seek a spanning tree on $P$ whose Wiener index is at most $W$, while having
total (Euclidean) weight at most $B$, is (weakly) NP-hard. Finally, in Section
5, we discuss the problem of finding a minimum Wiener index _path_ spanning
$P$.

### Related Work.

A problem related to ours is the minimum latency problem, also known as the
traveling repairman problem TRP: Compute a path, starting at point $s$, that
visits all points, while minimizing the sum of the distances (the “latencies”)
along the path from $s$ to every other point (versus between _all_ pairs of
points, as in the Wiener index). There is a PTAS for TRP (and the $k$-TRP,
with $k$ repairmen) in the Euclidean plane and in weighted planar graphs [27].

Wiener index optimization also arises in the context of computing a
noncontracting embedding of one metric space into another (e.g., a line metric
or a tree metric) in order to minimize the average distortion of the embedding
(defined to be the sum of all pairs distances in the new space, divided by the
sum of all pairs distances in the original space). It is NP-hard to minimize
average distortion when embedding a tree metric into a line metric; there is a
constant-factor approximation (based on the $k$-TRP) for minimizing the
average distortion in embedding a metric onto a line (i.e., finding a spanning
path of minimum Wiener index) [11], which, using [27], gives a
$(2+\varepsilon)$-approximation in the Euclidean plane.

A related problem that has recently been examined in a geometric setting is
the computation of the Beer index of a polygon $P$, defined to be the
probability that two randomly (uniformly) distributed points in $P$ being
visible to each other [1]; the same paper also studies the problem of
computing the expected distance between two random points in a polygon, which
is, like the Wiener index, based on computing the sum of distances (evaluated
as an integral in the continuum) between all pairs of points.

Another area of research that is related to the Wiener index is that of
_spanners_ : Given a weighted graph $G$ and a real number $t>1$, a _$t$
-spanner_ of $G$ is a spanning sub-graph $G^{*}$ of $G$, such that
$\delta_{G^{*}}(u,v)\leq t\cdot\delta_{G}(u,v)$, for every two vertices $u$
and $v$ in $G$. Thus, the shortest path distances in $G^{*}$ approximate the
shortest path distances in the underlying graph $G$, and the parameter $t$
represents the approximation ratio. The smallest $t$ for which $G^{*}$ is a
$t$-spanner of $G$ is known as the _stretch factor_. There is a vast
literature on spanners, especially in geometry (see, e.g., [4, 5, 6, 7, 13,
22, 25]) In a geometric graph, $G$, the _stretch factor_ between two vertices,
$u$ and $v$, is the ratio between the Euclidean length of the shortest path
from $u$ to $v$ in $G$ and the Euclidean distance between $u$ and $v$. The
_average stretch factor_ of $G$ is the average stretch factor taken over all
pairs of vertices in $G$. For a given weighted connected graph $G=(V,E)$ with
positive edge weights and a positive value $W$, the _average stretch factor
spanning tree_ problem seeks a spanning tree $T$ of $G$ such that the average
stretch factor (over $\binom{n}{2}$ pairs of vertices) is bounded by $W$. For
points in the Euclidean plane, one can construct in polynomial time a spanning
tree with constant average stretch factor [9].

##  2 Preliminaries

Let $P$ be a set of $n$ points in the plane and let $G=(P,E)$ be the complete
graph over $P$. For each edge $(p,q)\in E$, let $w(p,q)=|pq|$ denote the
weight of $(p,q)$, given by the Euclidean distance, $|pq|$, between $p$ and
$q$. Let $T$ be a spanning tree of $P$. For points $p,q\in P$, let
$\delta_{T}(p,q)$ denote the weight of the (unique) path between $p$ and $q$
in $T$. Let $W(T)=\sum_{p,q\in P}\delta_{T}(p,q)$ denote the Wiener index of
$T$, given by the sum of the weights of the paths in $T$ between every pair of
points. Finally, for a point $p\in P$, let $\delta_{p}(T)=\sum_{q\in
P}\delta_{T}(p,q)$ denote the total weight of the paths in $T$ from $p$ to
every point of $P$.

###### Theorem 2.1

Let $T^{*}$ be a spanning tree of $P$ that minimizes the Wiener index. Then,
$T^{*}$ is planar.

###### Proof

Assume towards a contradiction that there are two edges $(a,c)$ and $(b,d)$ in
$T$ that cross each other. Let $F$ be the forest obtained by removing the
edges $(a,c)$ and $(b,d)$ from $T$. Thus $F$ contains three sub-trees. Assume,
w.l.o.g., that $a$ and $b$ are in the same sub-tree $T_{ab}$, and $c$ and $d$
are in separated sub-trees $T_{c}$ and $T_{d}$, respectively; see Figure 1.
Let $n_{ab}$, $n_{c}$, and $n_{d}$ be the number of points in $T_{ab}$,
$T_{c}$, and $T_{d}$, respectively. Thus,

$\displaystyle W(T^{*})$
$\displaystyle=W(T_{ab})+n_{c}\cdot\delta_{a}(T_{ab})+n_{d}\cdot\delta_{b}(T_{ab})$
$\displaystyle+W(T_{c})+(n_{ab}+n_{d})\cdot\delta_{c}(T_{c})+n_{c}(n_{ab}+n_{d})\cdot|ac|$
$\displaystyle+W(T_{d})+(n_{ab}+n_{c})\cdot\delta_{d}(T_{d})+n_{d}(n_{ab}+n_{c})\cdot|bd|$
$\displaystyle+n_{c}\cdot n_{d}\cdot\delta_{T^{*}}(a,b)\,.$

Figure 1: The trees $T^{*}$, $T^{\prime}$, and $T^{\prime\prime}$ (from left
to right).

Let $T^{\prime}$ be the spanning tree of $P$ obtained from $T^{*}$ by
replacing the edge $(b,d)$ by the edge $(a,d)$. Similarly, let
$T^{\prime\prime}$ be the spanning tree of $P$ obtained from $T^{*}$ by
replacing the edge $(a,c)$ by the edge $(b,c)$. Thus,

$\displaystyle W(T^{\prime})$
$\displaystyle=W(T_{ab})+(n_{c}+n_{d})\cdot\delta_{a}(T_{ab})$
$\displaystyle+W(T_{c})+(n_{ab}+n_{d})\cdot\delta_{c}(T_{c})+n_{c}(n_{ab}+n_{d})\cdot|ac|$
$\displaystyle+W(T_{d})+(n_{ab}+n_{c})\cdot\delta_{d}(T_{d})+n_{d}(n_{ab}+n_{c})\cdot|ad|\,,$

and

$\displaystyle W(T^{\prime\prime})$
$\displaystyle=W(T_{ab})+(n_{c}+n_{d})\cdot\delta_{b}(T_{ab})$
$\displaystyle+W(T_{c})+(n_{ab}+n_{d})\cdot\delta_{c}(T_{c})+n_{c}(n_{ab}+n_{d})\cdot|bc|$
$\displaystyle+W(T_{d})+(n_{ab}+n_{c})\cdot\delta_{d}(T_{d})+n_{d}(n_{ab}+n_{c})\cdot|bd|\,.$

Therefore,

$\displaystyle W(T^{*})-W(T^{\prime})$
$\displaystyle=n_{d}\big{(}\delta_{b}(T_{ab})-\delta_{a}(T_{ab})\big{)}+n_{d}(n_{ab}+n_{c})\big{(}|bd|-|ad|\big{)}$
$\displaystyle+n_{c}\cdot n_{d}\cdot\delta_{T^{*}}(a,b)\,,$

and

$\displaystyle W(T^{*})-W(T^{\prime\prime})$
$\displaystyle=n_{c}\big{(}\delta_{a}(T_{ab})-\delta_{b}(T_{ab})\big{)}+n_{c}(n_{ab}+n_{d})\big{(}|ac|-|bc|\big{)}$
$\displaystyle+n_{c}\cdot n_{d}\cdot\delta_{T^{*}}(a,b)\,.$

If $W(T^{*})-W(T^{\prime})>0$ or $W(T^{*})-W(T^{\prime\prime})>0$, then this
contradicts the minimality of $T^{*}$, and we are done.

Assume that $W(T^{*})-W(T^{\prime})\leq 0$ and
$W(T^{*})-W(T^{\prime\prime})\leq 0$. Since $n_{c}>0$ and $n_{d}>0$, we have

$\displaystyle\delta_{b}(T_{ab})-\delta_{a}(T_{ab})+(n_{ab}+n_{c})\big{(}|bd|-|ad|\big{)}+n_{c}\cdot\delta_{T^{*}}(a,b)\leq
0\,,$

and

$\displaystyle\delta_{a}(T_{ab})-\delta_{b}(T_{ab})+(n_{ab}+n_{d})\big{(}|ac|-|bc|\big{)}+n_{d}\cdot\delta_{T^{*}}(a,b)\leq
0\,.$

Thus, by summing these inequalities, we have

$\displaystyle(n_{ab}+n_{c})\big{(}|bd|-|ad|\big{)}+(n_{ab}+n_{d})\big{(}|ac|-|bc|\big{)}+(n_{c}+n_{d})\cdot\delta_{T^{*}}(a,b)\leq
0\,.$

That is,

$\displaystyle n_{ab}\big{(}|bd|+|ac|-|ad|-|bc|\big{)}$
$\displaystyle+n_{c}\big{(}|bd|+\delta_{T^{*}}(a,b)-|ad|\big{)}$
$\displaystyle+n_{d}\big{(}|ac|+\delta_{T^{*}}(a,b)-|bc|\big{)}\leq 0\,.$

Since $n_{ab},n_{c},n_{d}>0$, and, by the triangle inequality,
$|bd|+|ac|-|ad|-|bc|>0$, $|bd|+\delta_{T^{*}}(a,b)-|ad|>0$, and
$|ac|+\delta_{T^{*}}(a,b)-|bc|>0$, this is a contradiction. ∎

##  3 An Exact Algorithm for Points in Convex Position

Let $\\{p_{1},p_{2},\ldots,p_{n}\\}$ denote the vertices of the convex polygon
that is obtained by connecting the points in $P$, ordered in clockwise-order
with an arbitrary first point $p_{1}$; see Figure 2. For simplicity of
presentation, we assume that all indices are taken modulo $n$. For each $1\leq
i\leq j\leq n$, let $P[i,j]\subseteq P$ be the set
$\\{p_{i},p_{i+1},\dots,p_{j}\\}$. Let $T_{i,j}$ be a spanning tree of
$P[i,j]$, and let $W(T_{i,j})$ denote its Wiener index. For a point
$x\in\\{i,j\\}$, let $\delta_{x}(T_{i,j})$ be the total weight of the shortest
paths from $p_{x}$ to every point of $P[i,j]$ in $T_{i,j}$. That is
$\delta_{x}(T_{i,j})=\sum_{p\in P[i,j]}\delta_{T_{i,j}}(p_{x},p)$.

Figure 2: The convex polygon that is obtained from $P$. $p_{1}$ is connected
to $p_{j}$ in $T^{*}$.

Let $T^{*}$ be a minimum Wiener index tree of $P$ and let $W^{*}$ be its
Wiener index. Notice that, for any $1\leq i<j\leq n$, the points in $P[i,j]$
are in convex position, since the points in $P$ are in convex position. Since
$T^{*}$ is a spanning tree, each point, particularly $p_{1}$, is adjacent to
at least one edge in $T^{*}$. Let $p_{j}$ be the point with maximum index $j$
that is connected to $p_{1}$ in $T^{*}$. Moreover, there exists an index
$1\leq i\leq j$ such that all the points in $P[1,i]$ are closer to $p_{1}$
than to $p_{j}$ in $T^{*}$, and all the points in $P[i+1,j]$ are closer to
$p_{j}$ than to $p_{1}$ in $T^{*}$. Hence,

$\displaystyle W^{*}$ $\displaystyle=W(T_{1,i})+(n-i)\cdot\delta_{1}(T_{1,i})$
(1) $\displaystyle+W(T_{i+1,j})+(n-j+i)\cdot\delta_{j}(T_{i+1,j})$ (2)
$\displaystyle+W(T_{j,n})+(j-1)\cdot\delta_{j}(T_{j,n})$ (3)
$\displaystyle+i(n-i)\cdot|p_{1}p_{j}|.$ (4)

Thus, in order to compute $W^{*}$, we compute (1), (2), (3), and (4) for each
$i$ between 2 and $n$ and for each $j$ between 1 and $i$, and take the minimum
over the sum of these values. In general, for every $1\leq i<j\leq n$, let
$W_{j}[i,j]=W(T_{i,j})+(n-j+i-1)\cdot\delta_{j}(T_{i,j})$ be the minimum value
obtained by a spanning tree $T_{i,j}$ of $P[i,j]$ rooted at $p_{j}$.
Similarly, let $W_{i}[i,j]=W(T_{i,j})+(n-j+i-1)\cdot\delta_{i}(T_{i,j})$ be
the minimum value obtained by a spanning tree $T_{i,j}$ of $P[i,j]$ rooted at
$p_{i}$. Thus, we can compute $W_{j}[i,j]$ and $W_{i}[i,j]$ recursively using
the following formulas; see also Figure 3.

$W_{j}[i,j]=\underset{k\leq l<j}{\underset{i\leq k<j}{\min}}\
\big{\\{}W_{k}[i,k]+W_{k}[k,l]+W_{j}[l+1,j]+(l-i+1)(n-l+i-1)\cdot|p_{k}p_{j}|\big{\\}}\,,$

and

$W_{i}[i,j]=\underset{i\leq l<k}{\underset{i<k\leq j}{\min}}\
\big{\\{}W_{i}[i,l]+W_{k}[l+1,k]+W_{j}[k,j]+(j-l)(n-j+l)\cdot|p_{i}p_{k}|\big{\\}}\,.$

Figure 3: A sub-problem defined by $P[i,j]$. (a) Computing $W_{j}[i,j]$. (b)
Computing $W_{i}[i,j]$.

We compute $W_{j}[i,j]$ and $W_{i}[i,j]$, for each $1\leq i<j\leq n$, using
dynamic programming as follows. We maintain two tables
$\stackrel{{\scriptstyle\rightarrow}}{{M}}$ and
$\stackrel{{\scriptstyle\leftarrow}}{{M}}$ each of size $n\times n$, such that
$\stackrel{{\scriptstyle\rightarrow}}{{M}}[i,j]=W_{j}[i,j]$ and
$\stackrel{{\scriptstyle\leftarrow}}{{M}}[i,j]=W_{i}[i,j]$, for each $1\leq
i<j\leq n$. We fill in the tables using Algorithm 1.

Algorithm 1 $ComputeOptimal(P)$

1: $n\leftarrow|P|$

2: for each $i\leftarrow 1$ to $n$ do
$\stackrel{{\scriptstyle\rightarrow}}{{M}}[i,i]\leftarrow 0$
$\stackrel{{\scriptstyle\leftarrow}}{{M}}[i,i]\leftarrow 0$

3: for each $j\leftarrow n$ to $1$ do for each $i\leftarrow j$ to $n$ do
$\stackrel{{\scriptstyle\rightarrow}}{{M}}[i,j]\leftarrow\underset{k\leq
l<j}{\underset{i\leq k<j}{\min}}\
\big{\\{}\stackrel{{\scriptstyle\rightarrow}}{{M}}[i,k]+\stackrel{{\scriptstyle\leftarrow}}{{M}}[k,l]+\stackrel{{\scriptstyle\rightarrow}}{{M}}[l+1,j]+(l-i+1)(n-l+i-1)\cdot|p_{k}p_{j}|\big{\\}}$
$\stackrel{{\scriptstyle\leftarrow}}{{M}}[i,j]\leftarrow\underset{i\leq
l<k}{\underset{i<k\leq j}{\min}}\
\big{\\{}\stackrel{{\scriptstyle\leftarrow}}{{M}}[i,l]+\stackrel{{\scriptstyle\rightarrow}}{{M}}[l+1,k]+\stackrel{{\scriptstyle\rightarrow}}{{M}}[k,j]+(j-l)(n-j+l)\cdot|p_{i}p_{k}|\big{\\}}$

4: return $\stackrel{{\scriptstyle\leftarrow}}{{M}}[1,n]$

Notice that when we fill the cell
$\stackrel{{\scriptstyle\rightarrow}}{{M}}[i,j]$, all the cells
$\stackrel{{\scriptstyle\rightarrow}}{{M}}[i,k]$,
$\stackrel{{\scriptstyle\leftarrow}}{{M}}[k,l]$, and
$\stackrel{{\scriptstyle\rightarrow}}{{M}}[l+1,j]$, for each $i\leq k<j$ and
for each $k\leq l<j$, are already computed, and when we fill the cell
$\stackrel{{\scriptstyle\leftarrow}}{{M}}[i,j]$, all the cells
$\stackrel{{\scriptstyle\leftarrow}}{{M}}[i,l]$,
$\stackrel{{\scriptstyle\rightarrow}}{{M}}[l+1,k]$, and
$\stackrel{{\scriptstyle\rightarrow}}{{M}}[k,j]$, for each $i<k\leq j$ and for
each $i\leq l<k$, are already computed. Therefore, each cell in the table is
computed in $O(n^{2})$ time, and the whole table is computed in $O(n^{4})$
time.

The following theorem summarizes the result of this section.

###### Theorem 3.1

Let $P$ be a set of $n$ points in convex position. Then, a spanning tree of
$P$ of minimum Wiener index can be computed in $O(n^{4})$ time.

##  4 Hardness Proof

Let $P$ be a set of points in the plane and let $T$ be a spanning tree of $P$.
We define the Wiener index of $T$ as $W(T)=\sum_{p,q\in P}\delta_{T}(p,q)$ and
the weight of $T$ as $wt(T)=\sum_{(p,q)\in T}|pq|$, where $\delta_{T}(p,q)$ is
the length of the path between $p$ and $q$ in $T$ and $|pq|$ is the Euclidean
distance between $p$ and $q$. For a edge $(p,q)$, let $N_{T}(p)$ (resp.,
$N_{T}(q)$) be the number of points in $T$ that are closer to $q$ than $q$
(resp., to $q$ than $p$). It is well known [21] that $W(T)$ can be formulated
as:

$W(T)=\sum_{(p,q)\in T}N_{T}(p)\cdot N_{T}(q)\cdot|pq|.$

In this section, we prove that the following problem is NP-hard.

### Euclidean Wiener Index Tree Problem:

Given a set $P$ of points in the plane, a cost $W$, and a budget $B$, decide
whether there exists a spanning tree $T$ of $P$, such that $W(T)\leq W$ and
$wt(T)\leq B$.

###### Theorem 4.1

The Euclidean Wiener Index Tree Problem is weakly NP-hard.

###### Proof

Inspired by Carmi and Chaitman-Yerushalmi [8], we reduce the Partition
problem, which is known to be NP-hard [14], to the Euclidean Wiener Index Tree
Problem. In the Partition problem, we are given a set
$X=\\{x_{1},x_{2},\ldots,x_{n}\\}$ of $n$ positive integers with even
$R=\sum_{i=1}^{n}x_{i}$, and the goal is to decide whether there is a subset
$S\subseteq X$, such that $\sum_{x_{i}\in S}x_{i}=\frac{1}{2}R$.

Given an instance $X=\\{x_{1},x_{2},\ldots,x_{n}\\}$ of the Partition problem,
where $x_{i}$’s are integers, we construct a set $P$ of $m=n^{3}+3n$ points as
follows. The set $P$ consists of $n$ points $p_{1},p_{2},\ldots,p_{n}$ located
equally spaced on a circle of radius $nR$, a cluster $C$ of $n^{3}$ points
located on the center of the circle. Moreover, for each $1\leq i\leq n$, we
locate two points $l_{i}$ and $r_{i}$ both of distance $x_{i}$ from $p_{i}$
and the distance between them is $\frac{1}{2}x_{i}$; see Figure 4. Finally, we
set

$\displaystyle B=$ $\displaystyle\ \Big{(}n^{2}+\frac{7}{4}\Big{)}R\text{, and
}$ $\displaystyle W=$ $\displaystyle\
3n^{2}\big{(}m-3\big{)}R+\Big{(}\frac{9}{4}m-\frac{13}{4}\Big{)}R$
$\displaystyle=$ $\displaystyle\
3n^{5}R+\frac{45}{4}n^{3}R-9n^{2}R+\frac{27}{4}nR-\frac{13}{4}R\,.$

Figure 4: The set $P$ produced by the reduction. Connecting the points
$l_{j}$, $r_{j}$, and $p_{j}$ for $x_{j}\in S$ (blue) and connecting the
points $l_{i}$, $r_{i}$, and $p_{i}$ for $x_{i}\in X\setminus S$ (red).

Assume that there exists a set $S\subseteq X$, such that $\sum_{x_{i}\in
S}x_{i}=\frac{1}{2}R$. We construct a spanning tree $T$ for the points in $P$
as follows:

  * •

Select an arbitrary point $s\in C$ and connect it to all the points in
$C\cup\\{p_{1},p_{2},\ldots,p_{n}\\}$ as a star centered at $s$.b

  * •

For each $1\leq i\leq n$, connect the points $p_{i}$ and $l_{i}$.

  * •

For each $x_{i}\in S$, connect the points $p_{i}$ and $r_{i}$.

  * •

For each $x_{i}\in X\setminus S$, connect the points $r_{i}$ and $l_{i}$; see
Figure 4.

It is easy to see that
$wt(T)=n^{2}R+R+\frac{3}{4}R=\big{(}n^{2}+\frac{7}{4}\big{)}R=B$. Moreover,
the Wiener index of $T$ is:

$\displaystyle W(T)=$ $\displaystyle\sum_{(p,q)\in T}N_{T}(p)\cdot
N_{T}(q)\cdot|pq|$ $\displaystyle=$ $\displaystyle\
3(n^{3}+3n-3)n^{2}R+\sum_{x_{i}\in S^{\prime}}2(n^{3}+3n-1)x_{i}$
$\displaystyle\quad+\sum_{x_{i}\notin
S^{\prime}}\Big{(}(n^{3}+3n-1)\frac{1}{2}x_{i}\Big{)}+\sum_{x_{i}\notin
S^{\prime}}\Big{(}2(n^{3}+3n-2)x_{i}\Big{)}$ $\displaystyle=$ $\displaystyle\
3n^{5}R+9n^{3}R-9n^{2}R+(n^{3}+3n-1)R$
$\displaystyle\quad+\frac{1}{4}(n^{3}+3n-1)R+(n^{3}+3n-2)R$ $\displaystyle=$
$\displaystyle\
3n^{5}R+\frac{45}{4}n^{3}R-9n^{2}R+\frac{27}{4}nR-\frac{13}{4}R=W\,.$

Conversely, let $T^{\prime}$ be a spanning tree of $P$ with
$wt(T^{\prime})\leq B$ and $W(T^{\prime})\leq W$.

###### Claim

The number of edges $(p,q)\in T^{\prime}$, such that $p\in C$ and $q\in
P\setminus C$ is $n$.

###### Proof

Assume there are $k$ such edges. The weight of each such edge is at least $nR$
thus the $wt(T^{\prime})\geq knR$, since $B=(n^{2}+\frac{7}{4})R$ we get that
$k\leq n$. We have

$\displaystyle W(T^{\prime})>$ $\displaystyle\ (3knR+3(n-k)(nR+2\pi R))n^{3}$
$\displaystyle=$ $\displaystyle\ (3kn+3n^{2}+6n\pi-3kn-6k\pi)n^{3}R$
$\displaystyle=$ $\displaystyle\ (3n^{2}+6\pi(n-k))n^{3}R$ $\displaystyle=$
$\displaystyle\ 3n^{5}R+6\pi(n-k)n^{3}R\,.$

Thus, if $k<n$, then we get that $W(T^{\prime})>3n^{5}R+6\pi n^{3}R>W$, for
sufficiently large $n$. ∎

Let $G_{i}=\\{p_{i},l_{i},r_{i}\\}$, for every $1\leq i\leq n$. From the proof
of Claim 4, if follows that for every $1\leq i\leq n$, there is an exactly one
edge $(p,q)$ in $T^{\prime}$, where $q\in G_{i}$ and $p\in C$. Moreover, it is
easy to see that $q=p_{i}$. Thus, in every $G_{i}$, we have $(p_{i},l_{i})\in
T^{\prime}$ or $(p_{i},r_{i})\in T^{\prime}$. Assume w.l.o.g., that
$(p_{i},l_{i})\in T^{\prime}$. Therefore, either $(p_{i},r_{i})\in T^{\prime}$
or $(l_{i},r_{i})\in T^{\prime}$. Let $S^{\prime}\subseteq X$, such that
$x_{i}\in S^{\prime}$ if and only if $(p_{i},r_{i})\in T^{\prime}$, and let
$R^{\prime}=\sum_{x_{i}\in S^{\prime}}x_{i}$.

Thus, to finish the proof we show that if $R^{\prime}\neq\frac{1}{2}R$, then
either $wt(T^{\prime})>B$ or $W(T)>W$.

Case 1: $R^{\prime}>\frac{1}{2}R$. In this case, we have

$\displaystyle wt(T^{\prime})\geq$ $\displaystyle\ n^{2}R+\sum_{x_{i}\in
S^{\prime}}2x_{i}+\sum_{x_{i}\notin S^{\prime}}\frac{3}{2}x_{i}\ =\
n^{2}R+2R^{\prime}+\frac{3}{2}(R-R^{\prime})$ $\displaystyle=$ $\displaystyle\
n^{2}R+\frac{1}{2}R^{\prime}+\frac{3}{2}R\ >\
n^{2}R+\frac{1}{4}R+\frac{3}{2}R\ =\ \big{(}n^{2}+\frac{7}{4}\big{)}R\ =B\,.$

Therefore, $wt(T^{\prime})>B$.

Case 2: $R^{\prime}<\frac{1}{2}R$. In this case, we have

$\displaystyle W(T)=$ $\displaystyle\sum_{(p,q)\in T}N_{T}(p)\cdot
N_{T}(q)\cdot|pq|$ $\displaystyle=$ $\displaystyle\
3(n^{3}+3n-3)n^{2}R+\sum_{x_{i}\in S^{\prime}}2(n^{3}+3n-1)x_{i}$
$\displaystyle\quad+\sum_{x_{i}\notin
S^{\prime}}\Big{(}(n^{3}+3n-1)\frac{1}{2}x_{i}\Big{)}+\sum_{x_{i}\notin
S^{\prime}}\Big{(}2(n^{3}+3n-2)x_{i}\Big{)}$ $\displaystyle=$ $\displaystyle\
3n^{5}R+9n^{3}R-9n^{2}R+2(n^{3}+3n-1)R^{\prime}$
$\displaystyle\quad+\frac{1}{2}\Big{(}n^{3}+3n-1\Big{)}(R-R^{\prime})+2(n^{3}+3n-2)(R-R^{\prime})$
$\displaystyle=$ $\displaystyle\ 3n^{5}R+9n^{3}R-9n^{2}R+2(n^{3}+3n-2)R$
$\displaystyle\quad-\Big{(}\frac{1}{2}\Big{(}n^{3}+3n-1\Big{)}-2\Big{)}R^{\prime}+\frac{1}{2}\Big{(}n^{3}+3n-1\Big{)}R$
$\displaystyle\quad-\Big{(}\frac{1}{2}\Big{(}n^{3}+3n-1\Big{)}-2\Big{)}R^{\prime}+\frac{1}{2}\Big{(}n^{3}+3n-1\Big{)}R$
$\displaystyle>$ $\displaystyle\ 3n^{5}R+9n^{3}R-9n^{2}R+2(n^{3}+3n-2)R$
$\displaystyle\quad-\frac{1}{2}\Big{(}\frac{1}{2}\Big{(}n^{3}+3n-1\Big{)}-2\Big{)}R+\frac{1}{2}\Big{(}n^{3}+3n-1\Big{)}R$
$\displaystyle=$ $\displaystyle\
3n^{5}R+\frac{45}{4}n^{3}R-9n^{2}R+\frac{27}{4}nR-\frac{13}{4}R=W\,.$

##  5 Paths that Optimize Wiener Index

We consider now the case of spanning paths that optimize the Wiener index.

###### Theorem 5.1

Let $P$ be a set of $n$ points. The path that minimizes the Wiener index among
all Hamiltonian paths of $P$ is not necessarily planar.

###### Proof

Consider the set $P$ of $n=2m+2$ points in convex position as shown in Figure
5. The set $P$ consists of two clusters $P_{l}$ and $P_{r}$ and two points $p$
and $q$, where $|P_{l}|=|P_{r}|=m$. The points in cluster $P_{l}$ are
arbitrarily close to the origin $(0,0)$, and the points in cluster $P_{r}$ are
arbitrarily close to coordinate $(6,0)$. The point $p$ is located on
coordinate $(5,1)$ and the point $q$ is located on coordinate $(5,-1)$.

Figure 5: A set $P$ of $n=2m+2$ points in a convex position.

For simplicity of computation, we assume that a path connecting the points in
$P_{l}$ has a Wiener index zero, and also a path connecting the points in
$P_{r}$ has a Wiener index zero. Thus, any path $\Pi$ of $P$ that aims to
minimize the Wiener index will connect the points in $P_{l}$ by a path and the
points in $P_{r}$ by a path. We computed the Wiener index of all possible
Hamiltonian paths defined on points $(0,0)$, $(6,0)$, $p$, and $q$; see Figure
6. This computation shows that the Hamiltonian path of the minimum Wiener
index is not planar (for sufficiently large $n$). ∎

Figure 6: The Wiener index of the 12 possible Hamiltonian paths that are
defined on points $(0,0)$, $(6,0)$, $p$, and $q$ (assuming that the $m$ points
on $(0,0)$ are connected by a path, and the $m$ points on $(6,0)$ are
connected by a path, both of Wiener index zero).

###### Theorem 5.2

For points in the Euclidean plane, it is NP-hard to compute a Hamiltonian path
minimizing Wiener index.

###### Proof

We reduce from Hamiltonicity in a grid graph (whose vertices are integer grid
points and whose edges join pairs of grid points at distance one). First,
observe that the Wiener index of a Hamiltonian path of $n$ points, where each
edge is of length one, is $\sum_{i=1}^{n-1}i(n-i)={n+1\choose 3}$; see Figure
7. Thus, it is easy to see that a grid graph $G$ has a Hamiltonian path if and
only if there exists a path of Wiener index ${n+1\choose 3}$. ∎

###### Theorem 5.3

There exists a set $P$ of $n$ points in the plane, such that the Wiener index
of any Hamiltonian path is at least $\Theta(\sqrt{n})$ times the Wiener index
of the complete Euclidean graph over $P$

###### Proof

Let $P$ be a set of $n$ points located on a$\sqrt{n}\times\sqrt{n}$ integer
grid. The Wiener index of any Hamiltonian path of $P$ is at least ${n+1\choose
3}$, which is the Wiener index of a Hamiltonian path whose all its edges are
of length one. Thus, the Wiener index of any Hamiltonian path of $P$ is at
least $\Theta(n^{3})$. On the other hand, the Wiener index of the complete
graph over $P$ is $\Theta(n^{2.5})$. ∎

Figure 7: A grid graph $G$ and a Hamiltonian path with Wiener index
${n+1\choose 3}$ in $G$.

## References

  * [1] M. Abrahamsen and V. Fredslund-Hansen.  Degree of convexity and expected distances in polygons.  arXiv preprint arXiv:2208.07106, 2022.
  * [2] D. Bonchev.  The Wiener number: Some applications and new developments.  In Topology in Chemistry, pages 58–88, 2002.
  * [3] D. Bonchev and N. Trinajstić.  Information theory, distance matrix, and molecular branching.  The Journal of Chemical Physics, 67(10):4517–4533, 1977.
  * [4] P. Bose, P. Carmi, and L. Chaitman-Yerushalmi.  On bounded degree plane strong geometric spanners.  J. Discrete Algorithms, 15:16–31, 2012.
  * [5] P. Bose, J. Gudmundsson, and M. H. M. Smid.  Constructing plane spanners of bounded degree and low weight.  In ESA, pages 234–246, 2002.
  * [6] P. Bose, D. Hill, and M. H. M. Smid.  Improved spanning ratio for low degree plane spanners.  Algorithmica, 80(3):935–976, 2018.
  * [7] J. Cardinal, S. Collette, and S. Langerman.  Local properties of geometric graphs.  Comput. Geom., 39(1):55–64, 2008.
  * [8] P. Carmi and L. Chaitman-Yerushalmi.  Minimum weight Euclidean t-spanner is np-hard.  Journal of Discrete Algorithms, 22:30–42, 2013.
  * [9] S.-W. Cheng, C. Knauer, S. Langerman, and M. H. M. Smid.  Approximating the average stretch factor of geometric graphs.  J. Comput. Geom., 3(1):132–153, 2012.
  * [10] K. Das, I. Gutman, and B. Furtula.  Survey on geometric-arithmetic indices of graphs.  Match (Mulheim an der Ruhr, Germany), 65:595–644, 01 2011.
  * [11] K. Dhamdhere, A. Gupta, and R. Ravi.  Approximation algorithms for minimizing average distortion.  Theory of Computing Systems, 39(1):93–111, 2006.
  * [12] A. A. Dobrynin, R. Entringer, and I. Gutman.  Wiener index of trees: Theory and applications.  Acta Applicandae Mathematica, 66(3):211–249, 2001.
  * [13] A. Filtser and S. Solomon.  The greedy spanner is existentially optimal.  In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing (PODC), pages 9–17, 2016.
  * [14] M. R. Garey and D. S. Johnson.  Computers and Intractability: A Guide to the Theory of NP-Completeness.  W. H. Freeman & Co., USA, 1979.
  * [15] T. F. Gonzalez.  Handbook of Approximation Algorithms and Metaheuristics, Chapter 59.  Chapman & Hall/CRC, 2007.
  * [16] A. Graovac and T. Pisanski.  On the wiener index of a graph.  Journal of Mathematical Chemistry, 8:53–62, 1991.
  * [17] F. Harary.  Graph Theory.  Addison-Wesley, 1969.
  * [18] T. C. Hu.  Optimum communication spanning trees.  SIAM Journal on Computing, 3(3):188–195, 1974.
  * [19] D. S. Johnson, J. K. Lenstra, and A. H. G. Rinnooy Kan.  The complexity of the network design problem.  Networks, 8:279–285, 1978.
  * [20] L. Kier.  Molecular connectivity in chemistry and drug research.  Elsevier, 1976.
  * [21] M. Knor, R. Škrekovski, and A. Tepeh.  Mathematical aspects of Wiener index.  Ars Math. Contemp., 11:327–352, 2015.
  * [22] X. Y. Li and Y. Wang.  Efficient construction of low weighted bounded degree planar spanner.  Int. J. Comput. Geom. Appl., 14(1-2):69–84, 2004.
  * [23] O. Mekenyan, D. Bonchev, and N. Trinajstić.  Structural complexity and molecular properties of cyclic systems with acyclic branches.  Croatica Chemica Acta, 56(2):237–261, 1983.
  * [24] B. Mohar and T. Pisanski.  How to compute the wiener index of a graph.  Journal of Mathematical Chemistry, 2(3):267, 1988.
  * [25] G. Narasimhan and M. Smid.  Geometric Spanner Networks.  Cambridge University Press, 2007.
  * [26] S. Ronghua.  The average distance of trees.  Journal of Systems Science and Complexity, 6:18–24, 1993.
  * [27] R. Sitters.  Polynomial time approximation schemes for the traveling repairman and other minimum latency problems.  SIAM Journal on Computing, 50(5):1580–1602, 2021.
  * [28] N. Trinajstić.  Mathematical and Computational Concepts in Chemistry.  Ellis Horwood, Chichester, 1986.
  * [29] E. Weiszfeld and F. Plastria.  On the point for which the sum of the distances to n given points is minimum.  Annals of Operations Research, 167(1):7–41, 2009.
  * [30] H. Wiener.  Structural determination of paraffin boiling points.  Journal of the American Chemical Society, 69(1):17–20, 1947.
  * [31] B. Ye Wu, G. Lancia, V. Bafna, K.-M. Chao, R. Ravi, and C. Y. Tang.  A polynomial-time approximation scheme for minimum routing cost spanning trees.  SIAM Journal on Computing, 29(3):761–778, 2000.
  * [32] K. Xu, M. Liu, K. Das, I. Gutman, and B. Furtula.  A survey on graphs extremal with respect to distance-based topological indices.  Match (Mulheim an der Ruhr, Germany), 71:461–508, 02 2014.


On a characterization of probability distribution based on
maxima of independent or max-independent random variables
B.L.S. Prakasa Rao111CONTACT B.L.S. Prakasa Rao<EMAIL_ADDRESS>CR Rao
Advanced Institute of Mathematics, Statistics and Computer Science, Hyderabad
500046, India CR Rao Advanced Institute of Mathematics, Statistics and
Computer Science, Hyderabad, India Abstract:
Kotlarski (1978) proved a result on identification of the distributions of
independent random variables $X,Y$ and $Z$ from the joint distribution of the
bivariate random vector $(U,V)$ where $(U,V)=(\max(X,Z),\max(Y,Z)).$ We extend
this result to the case

$(U,V)=(\max(X,aZ_{1},bZ_{2}),\max(Y,cZ_{1},dZ_{2})$

where $X,Y,Z_{1},Z_{2}$ are independent or max-independent random variabkes,
$Z_{1}$ and $Z_{2}$ are identically distributed and $a,b,c,d$ are known
positive constants. Keywords:
Kotlarski’s lemma; Identifiability; Characterization; Max-independent;
Independent; Maxima.

MSC 2020: Primary 62E10

##  1 Introduction

Let $X_{0},X_{1}$ and $X_{2}$ be independent random variables. Define
$Y_{1}=\max(X_{0},X_{1})$ and $Y_{2}=\max(X_{0},X_{2})$. It is of interest to
know whether the joint distribution of $(Y_{1},Y_{2})$ determines the
individual distributions of $X_{0},X_{1}$ and $X_{2}$ uniquely. It is known
that the random variable $Y_{1}$ alone can not determine the distributions of
$X_{0}$ and $X_{1}$ uniquely unless $X_{0}$ and $X_{1}$ are identically
distributed random variables (cf. Prakasa Rao (1992), Section 7.3). Kotlarski
(1978) and Klebanov (1973) obtained characterizations for probability
distributions through maxima or minima of independent random variables.
Prakasa Rao (2024) discussed characterizations of probabilty distributions
based on maxima or minima of some families of dependent random variables. We
now discuss extension of the result in Kotlarski (1978) leading to
characterizations of probability distributions through maxima for some classes
of independent or max-independent random variables.

##  2 Identifiability by maxima for independent random variables

The following result is due to Kotlarski (1978). Theorem 2.1: (Identifiability
by maxima) Suppose $X_{0},X_{1},X_{2}$ are independent random variables.
Define $Y_{1}=\max(X_{0},X_{1})$ and $Y_{2}=\max(X_{0},X_{2})$. Then the joint
distribution of $(Y_{1},Y_{2})$ uniquely determines the distributions of the
independent random variables $X_{0},X_{1}$ and $X_{2}$ provided the supports
of their distribution functions are the same. For a proof of Theorem 2.1, see
Kotlarski (1978) (cf. Prakasa Rao (1992), Theorem 2.2.1, p.24). We will now
generalize Theorem 2.1 in analogy with the results of Li and Zheng (2019) for
linear functions of independent random variables. Theorem 2.2: Let $U$ and $V$
be random variables defined by the relations

$U=\max(X,aZ_{1},bZ_{2});\;V=\max(Y,cZ_{1},dZ_{2})$

where $X,Y,Z_{1}$ and $Z_{2}$ are independent random variables, $Z_{1},Z_{2}$
are identically distributed and $a,b,c,d$ are known positive constants.
Further suppose that the distribution functions of $X,Y,Z_{1}$ have the same
support. Then, the joint distribution function of $(U,V)$ uniquely determines
the distributions of $X,Y,Z_{1}$ if $a=b$ or if $a\neq b$ but the distribution
function of $Z_{1}$ is differentiable and the derivative is continuous. Proof:
Let $G(t_{1},t_{2})$ be the joint distribution function of $(U,V).$ Suppose
that $(N,M,S_{1},S_{2})$ is another set of independent random variables with
$S_{1}$ and $S_{2}$ identically distributed with the same support as that of
$X$ and such that the joint distribution of the random vector

$(\max(N,aS_{1},bS_{2}),\max(M,cS_{1},dS_{2}))$

is the same as that of the random vector $(U,V).$ Let $F_{X}(.)$ denote the
distribution function of the random variable $X.$ It can be seen that, for
any$-\infty<t_{1},t_{2}<\infty,$

$\displaystyle G(t_{1},t_{2})$ $\displaystyle=$ $\displaystyle
P(\max(X,aZ_{1},bZ_{2})\leq t_{1},\max((Y,cZ_{1},dZ_{2})\leq t_{2})$
$\displaystyle=$ $\displaystyle P(X\leq t_{1},aZ_{1}\leq t_{1},bZ_{2}\leq
t_{2};Y\leq t_{2},cZ_{1}\leq t_{2},dZ_{2}\leq t_{2})$ $\displaystyle=$
$\displaystyle P(X\leq t_{1},Y\leq
t_{2},Z_{1}\leq\frac{t_{1}}{a},Z_{1}\leq\frac{t_{2}}{c},Z_{2}\leq\frac{t_{1}}{b},Z_{2}\leq\frac{t_{2}}{d})$
$\displaystyle=$ $\displaystyle P(X\leq t_{1},Y\leq
t_{2},Z_{1}\leq\min(\frac{t_{1}}{a},\frac{t_{2}}{c}),Z_{2}\leq\min(\frac{t_{1}}{b},\frac{t_{2}}{d}))$
$\displaystyle=$ $\displaystyle
F_{X}(t_{1})F_{Y}(t_{2})F_{Z_{1}}(\min(\frac{t_{1}}{a},\frac{t_{2}}{c}))F_{Z_{1}}(\min(\frac{t_{1}}{b},\frac{t_{2}}{d}))$

since $X,YZ_{1},Z_{2}$ are independent random variables and $Z_{1},Z_{2}$ are
identically distributed. By a similar argument it follows that

$\displaystyle G(t_{1},t_{2})$ $\displaystyle=$ $\displaystyle
P(\max(N,aS_{1},bS_{2})\leq t_{1},\max(M,cS_{1},dS_{2})\leq t_{2})$
$\displaystyle=$ $\displaystyle
F_{N}(t_{1})F_{M}(t_{2})F_{S_{1}}(\min(\frac{t_{1}}{a},\frac{t_{2}}{c}))F_{S_{1}}(\min(\frac{t_{1}}{b},\frac{t_{2}}{d}))$

Hence

(2. 3) $\displaystyle
F_{X}(t_{1})F_{Y}(t_{2})F_{Z_{1}}(\min(\frac{t_{1}}{a},\frac{t_{2}}{c}))F_{Z_{1}}(\min(\frac{t_{1}}{b},\frac{t_{2}}{d}))$
$\displaystyle=F_{N}(t_{1})F_{M}(t_{2})F_{S_{1}}(\min(\frac{t_{1}}{a},\frac{t_{2}}{c}))F_{S_{1}}(\min(\frac{t_{1}}{b},\frac{t_{2}}{d}))$

for all $-\infty<t_{1},t_{2}<\infty.$ Let $D\subset R$ be the common support
of $X,Y,Z_{1}$ and $N,M,S_{1}.$ Then, for all $t\in D,$ define

$\eta_{1}(t)=\frac{F_{X}(t)}{F_{M}(t)},\eta_{2}(t)=\frac{F_{Y}(t)}{F_{N}(t)}\;\;\mbox{and}\;\;\eta_{3}(t)=\frac{F_{Z_{1}}(t)}{F_{S_{1}}(t)}.$

Equation (2.3) implies that

(2. 4)
$\eta_{1}(t_{1})\eta_{2}(t_{2})\eta_{3}(\min(\frac{t_{1}}{a},\frac{t_{2}}{c}))\eta_{3}(\min(\frac{t_{1}}{b},\frac{t_{2}}{d}))=1,t_{1},t_{2}\in
D.$

Let $t_{1}\rightarrow\infty$ in equation (2.4). From the properties of the
distribution functions, it follows that

$\eta_{2}(t_{2})\eta_{3}(\frac{t_{2}}{c})\eta_{3}(\frac{t_{2}}{d})=1,t_{2}\in
D.$

Hence

(2. 5)
$\eta_{2}(t_{2})=[\eta_{3}(\frac{t_{2}}{c})\eta_{3}(\frac{t_{2}}{d})]^{-1},t_{2}\in
D.$

Let $t_{2}\rightarrow\infty$ in equation (2.4). From the properties of the
distribution functions again, it follows that

$\eta_{1}(t_{1})\eta_{3}(\frac{t_{1}}{a})\eta_{3}(\frac{t_{1}}{b})=1,t_{1}\in
D$

which implies that

(2. 6)
$\eta_{1}(t_{1})=[\eta_{3}(\frac{t_{1}}{a})\eta_{3}(\frac{t_{1}}{b})]^{-1},t_{1}\in
D.$

Combining the equations (2.4)-(2.6), it follows that

(2. 7)
$\eta_{3}(\min(\frac{t_{1}}{a},\frac{t_{2}}{c}))\eta_{3}(\min(\frac{t_{1}}{b},\frac{t_{2}}{d}))=\eta_{3}(\frac{t_{1}}{a})\eta_{3}(\frac{t_{1}}{b})\eta_{3}(\frac{t_{2}}{c})\eta_{3}(\frac{t_{2}}{d}),t_{1},t_{2}\in
D.$

Fix $t_{1}\in D$ and let $t_{2}\rightarrow\infty$ or $t_{2}$ tend to the right
boundary point of the set $D$. Then the expression on the left side of
equation (2.7) tends to 1 and the expression on the right side tends to

$\eta_{3}(\frac{t_{1}}{a})\eta_{3}(\frac{t_{1}}{b})$

by the properties of the distribution functions. Hence

(2. 8) $\eta_{3}(\frac{t_{1}}{a})\eta_{3}(\frac{t_{1}}{b})=1,t_{1}\in D.$

This in turn implies that

(2. 9) $\eta_{1}(t_{1})=1,t_{1}\in D$

from (2.6). A similar analysis shows that

(2. 10) $\eta_{2}(t_{2})=1,t_{2}\in D$

by fixing $t_{2}\in D$ and letting $t_{1}\rightarrow\infty$ or $t_{1}$ tend to
the right boundary point of the set $D$. In particular, it follows that

$F_{X}(t)=F_{M}(t),t\in D$

and

$F_{Y}(t)=F_{N}(t),t\in D.$

Furthermore, equation (2.8) implies that

(2. 11) $\log\eta_{3}(\frac{t}{a})+\log\eta_{3}(\frac{t}{b})=0,t\in D.$

Let $\zeta(t)=\log\eta_{3}(t),t\in D.$ Equation (2.11) implies that

$\zeta(\frac{t}{a})+\zeta(\frac{t}{b})=0,t\in D$

or equivalently

$\zeta(u)=-\zeta(\lambda u),u\in D^{*}$

where $\lambda=\frac{a}{b}$ and $D^{*}=\\{a^{-1}t,t\in D\\}.$ Suppose that
$\lambda=1.$ Then it follows that $\zeta(u)=0,u\in D^{*}$ which in turn
implies that $\eta_{3}(t)=1,t\in D$ and hence $F_{Z_{1}}(t)=F_{S_{1}}(t),t\in
D.$ If $\lambda\neq 1,$ applying Lemma 2 in Li and Zheng (2019), it follows
that $\zeta(u)=0,u\in D^{*}$ under the additional condition of
differentiability of the function $\zeta(u)$ and continuity of its derivative
which implies that $F_{Z_{1}}(t)=F_{S_{1}}(t),t\in D.$ This completes the
proof of Theorem 2.2. We will now investigate the same problem when the
constants $a>0,b<0,c>0$ and $d<0.$ Theorem 2.3: Let $U$ and $V$ be random
variables defined by the relations

$U=\max(X,aZ_{1},bZ_{2});\;V=\max(Y,cZ_{1},dZ_{2})$

where $X,Y,Z_{1}$ and $Z_{2}$ are independent random variables, $Z_{1},Z_{2}$
are identically distributed and $a>0,b<0,c>0,d<0,$ are known constants.
Further suppose that the distribution functions of $X,Y,Z_{1}$ have the same
support. Then, the joint distribution function of $(U,V)$ are connected by the
distributions of $X,Y,Z_{1}$ and the distributions of $M,N,S_{1}$ by the
equations through the equations (2.12) and (2.13) given below:

(2. 12)
$F_{X}(t)=F_{M}(t)\frac{F_{S_{1}}(\frac{t}{a})(1-F_{S_{1}}(\frac{t}{b}))}{F_{Z_{1}}(\frac{t}{a})(1-F_{Z_{1}}(\frac{t}{b}))}$

and

(2. 13)
$F_{Y}(t)=F_{N}(t)\frac{F_{S_{1}}(\frac{t}{c})(1-F_{S_{1}}(\frac{t}{d}))}{F_{Z_{1}}(\frac{t}{c})(1-F_{Z_{1}}(\frac{t}{d}))}.$

Proof: We follow the same notation as given in the proof of Theorem 2.2. It
easy to see that that the joint distribution of The bivariate random vector
$(U,V)$ is given by

$\displaystyle G(t_{1},t_{2})$ $\displaystyle=$ $\displaystyle P(X\leq
t_{1},Y\leq
t_{2},Z_{1}\leq\frac{t_{1}}{a},Z_{1}\leq\frac{t_{2}}{c},Z_{2}\geq\frac{t_{1}}{b},Z_{2}\geq\frac{t_{2}}{d})$
$\displaystyle=$ $\displaystyle P(X\leq t_{1},Y\leq
t_{2},Z_{1}\leq\min(\frac{t_{1}}{a},\frac{t_{2}}{c}),Z_{2}\geq\max(\frac{t_{1}}{b},\frac{t_{2}}{d}))$
$\displaystyle=$ $\displaystyle
F_{X}(t_{1})F_{Y}(t_{2})F_{Z_{1}}(\min(\frac{t_{1}}{a},\frac{t_{2}}{c}))(1-F_{Z_{1}}(\max(\frac{t_{1}}{b},\frac{t_{2}}{d}))$
$\displaystyle=$ $\displaystyle
F_{M}(t_{1})F_{N}(t_{2})F_{S_{1}}(\min(\frac{t_{1}}{a},\frac{t_{2}}{c}))(1-F_{S_{1}}(\max(\frac{t_{1}}{b},\frac{t_{2}}{d}))$

for all $t_{1},t_{2}\in D.$ Define $\eta_{1}(t),\eta_{2}(t)$ and $\eta_{3}(t)$
as defined in the proof of Theorem 2.2. Then it follows that

(2. 14)
$\eta_{1}(t_{1})\eta_{2}(t_{2})\eta_{3}(\min(\frac{t_{1}}{a},\frac{t_{2}}{c}))\frac{(1-F_{Z_{1}}(\max(\frac{t_{1}}{b},\frac{t_{2}}{d}))}{(1-F_{S_{1}}(\max(\frac{t_{1}}{b},\frac{t_{2}}{d}))}=1,t_{1},t_{2}\in
D.$

Let $t_{2}\rightarrow\infty$ or to the right boundary point of the set $D.$
Then, it follows that,

(2. 15)
$\eta_{1}(t_{1})\eta_{3}(\frac{t_{1}}{a})\frac{(1-F_{Z_{1}}(\frac{t_{1}}{b}))}{(1-F_{S_{1}}(\frac{t_{1}}{b}))}=1$

observing that $\frac{t_{2}}{d}\rightarrow-\infty$ as
$t_{2}\rightarrow\infty.$ Letting $t_{1}\rightarrow\infty,$ it follows that

(2. 16)
$\eta_{2}(t_{2})\eta_{3}(\frac{t_{2}}{c})\frac{(1-F_{Z_{1}}(\frac{t_{2}}{d}))}{(1-F_{S_{1}}(\frac{t_{2}}{d}))}=1.$

These equations in turn show that

(2. 17)
$F_{X}(t)=F_{M}(t)\frac{F_{S_{1}}(\frac{t}{a})(1-F_{S_{1}}(\frac{t}{b}))}{F_{Z_{1}}(\frac{t}{a})(1-F_{Z_{1}}(\frac{t}{b}))}$

and

(2. 18)
$F_{Y}(t)=F_{N}(t)\frac{F_{S_{1}}(\frac{t}{c})(1-F_{S_{1}}(\frac{t}{d}))}{F_{Z_{1}}(\frac{t}{c})(1-F_{Z_{1}}(\frac{t}{d}))}.$

##  3 Identifiability by maxima for max-independent random variables

Definition: A finite collection of random variables $X_{1},\dots,X_{n}$ is
said to be max-independent if there exists a function
$\beta(x_{1},\dots,x_{n})$ such that

$F(x_{1},\dots,x_{n})=F_{1}(x_{1})\dots
F_{n}(x_{n})\beta(x_{1},\dots,x_{n}),x_{i}\in R,1\leq i\leq n$

where $F(x_{1},\dots,x_{n})$ is the joint distribution of
$(X_{1},\dots,X_{n})$ , $F_{i}(x)$ is the distribution function of $X_{i}$ for
$1\leq i\leq n$ and $\beta(x_{1},\dots,x_{n})$ is a function taking values in
the interval $(0,1]$ such that $\beta(x_{1},\dots,x_{n})\rightarrow 1$ if
$x_{i}\rightarrow\infty$ for some $i,1\leq i\leq n$ (cf. Prakasa Rao (2023)).
The function $\beta(x_{1},\dots,x_{n})$ is called the generator of the random
sequence $X_{1},\dots,X_{n}.$ Examples of sequence of max-independent random
variables which are not independent are given in Prakasa Rao (2023). We will
now generalize Theorem 2.2 to max-independent random variables. Theorem 3.1:
Let $X,Y,Z_{1}$ and $Z_{2}$ be max-independent random variables with generator
$\beta(x_{1},x_{2},x_{3},x_{4}).$ Define the random variables $U$ and $V$ by
the relations

$U=\max(X,aZ_{1},bZ_{2});\;V=\max(Y,cZ_{1},dZ_{2})$

where $Z_{1},Z_{2}$ are identically distributed and $a,b,c,d$ are known
positive constants. Further suppose that the distribution functions of
$X,Y,Z_{1}$ have the same support. Then, the joint distribution function of
$(U,V)$ uniquely determines the distributions of $X,Y,Z_{1}$ if $a=b$ or if
$a\neq b$ but the distribution function of $Z_{1}$ is differentiable and the
derivative is continuous. Proof: Let $G(t_{1},t_{2})$ be the joint
distribution function of $(U,V).$ Suppose that $(N,S_{1},S_{2})$ is another
set of max-independent random variables with the generator
$\beta(x_{1},x_{2},x_{3},x_{4})$ such that the joint distribution of the
random vector

$(\max(N,aS_{1},bS_{2}),\max(M,cS_{1},dS_{2}))$

is the same as that of the random vector $(U,V).$ Let $F_{X}(.)$ denote the
distribution function of the random variable $X.$ It can be seen that, for
any$-\infty<t_{1},t_{2}<\infty,$

(3. 1) $\displaystyle G(t_{1},t_{2})$ $\displaystyle=$ $\displaystyle
P(\max(X,aZ_{1},bZ_{2})\leq t_{1},\max((Y,cZ_{1},dZ_{2})\leq t_{2})$
$\displaystyle=$ $\displaystyle P(X\leq t_{1},aZ_{1}\leq t_{1},bZ_{2}\leq
t_{2};Y\leq t_{2},cZ_{1}\leq t_{2},dZ_{2}\leq t_{2})$ $\displaystyle=$
$\displaystyle P(X\leq t_{1},Y\leq
t_{2},Z_{1}\leq\frac{t_{1}}{a},Z_{1}\leq\frac{t_{2}}{c},Z_{2}\leq\frac{t_{1}}{b},Z_{2}\leq\frac{t_{2}}{d})$
$\displaystyle=$ $\displaystyle P(X\leq t_{1},Y\leq
t_{2},Z_{1}\leq\min(\frac{t_{1}}{a},\frac{t_{2}}{c}),Z_{2}\leq\min(\frac{t_{1}}{b},\frac{t_{2}}{d}))$
$\displaystyle=$ $\displaystyle
F_{X}(t_{1})F_{Y}(t_{2})F_{Z_{1}}(\min(\frac{t_{1}}{a},\frac{t_{2}}{c}))F_{Z_{1}}(\min(\frac{t_{1}}{b},\frac{t_{2}}{d}))\beta(t_{1},t_{2},\min(\frac{t_{1}}{a},\frac{t_{2}}{c}),\min(\frac{t_{1}}{b},\frac{t_{2}}{d}))$

since $X,YZ_{1},Z_{2}$ are max-independent random variables,$Z_{1},Z_{2}$ are
identically distributed with generator $\beta(x_{1},x_{2},x_{3},x_{4}).$ By a
similar argument it follows that

(3. 2) $\displaystyle G(t_{1},t_{2})$ $\displaystyle=$ $\displaystyle
P(\max(N,aS_{1},bS_{2})\leq t_{1},\max((M,cS_{1},dS_{2})\leq t_{2}))$
$\displaystyle=$ $\displaystyle
F_{N}(t_{1})F_{M}(t_{2})F_{S_{1}}(\min(\frac{t_{1}}{a},\frac{t_{2}}{c}))F_{S_{1}}(\min(\frac{t_{1}}{b},\frac{t_{2}}{d}))\beta(t_{1},t_{2},\min(\frac{t_{1}}{a},\frac{t_{2}}{c}),\min(\frac{t_{1}}{b},\frac{t_{2}}{d}).$

Hence

(3. 3) $\displaystyle
F_{X}(t_{1})F_{Y}(t_{2})F_{Z_{1}}(\min(\frac{t_{1}}{a},\frac{t_{2}}{c}))F_{Z_{1}}(\min(\frac{t_{1}}{b},\frac{t_{2}}{d}))\beta(t_{1},t_{2},\min(\frac{t_{1}}{a},\frac{t_{2}}{c}),\min(\frac{t_{1}}{b},\frac{t_{2}}{d})$
$\displaystyle=F_{N}(t_{1})F_{M}(t_{2})F_{S_{1}}(\min(\frac{t_{1}}{a},\frac{t_{2}}{c}))F_{S_{1}}(\min(\frac{t_{1}}{b},\frac{t_{2}}{d}))\beta(t_{1},t_{2},\min(\frac{t_{1}}{a},\frac{t_{2}}{c}),\min(\frac{t_{1}}{b},\frac{t_{2}}{d})$

for all $-\infty<t_{1},t_{2}<\infty.$ Let $D\subset R$ be the common support
of $X,Y,Z_{1}$ and $N,M,S_{1}.$ Then, for all $t\in D,$, define

$\eta_{1}(t)=\frac{F_{X}(t)}{F_{M}(t)},\eta_{2}(t)=\frac{F_{Y}(t)}{F_{N}(t)},\mbox{and}\eta_{3}(t)=\frac{F_{Z_{1}}(t)}{F_{S_{1}}(t)}.$

Equation (3.3) implies that

(3. 4)
$\eta_{1}(t_{1})\eta_{2}(t_{2})\eta_{3}(\min(\frac{t_{1}}{a},\frac{t_{2}}{c}))\eta_{3}(\min(\frac{t_{1}}{b},\frac{t_{2}}{d}))=1,t_{1},t_{2}\in
D.$

Let $t_{1}\rightarrow\infty$ or $t_{1}$ tend to the right boundary point of
the set $D$ in equation (3.4). From the properties of the distribution
functions, it follows that

$\eta_{2}(t_{2})\eta_{3}(\frac{t_{2}}{c})\eta_{3}(\frac{t_{2}}{d})=1,t_{2}\in
D.$

Hence

(3. 5)
$\eta_{2}(t_{2})=[\eta_{3}(\frac{t_{2}}{c})\eta_{3}(\frac{t_{2}}{d})]^{-1},t_{2}\in
D.$

Let $t_{2}\rightarrow\infty$ or $t_{1}$ tend to the right boundary point of
the set $D$ in equation (3.4). From the properties of the distribution
functions again, it follows that

$\eta_{1}(t_{1})\eta_{3}(\frac{t_{1}}{a})\eta_{3}(\frac{t_{1}}{b})=1,t_{1}\in
D$

which implies that

(3. 6)
$\eta_{1}(t_{1})=[\eta_{3}(\frac{t_{1}}{a})\eta_{3}(\frac{t_{1}}{b})]^{-1},t_{2}\in
D.$

Combining the equations (3.4)-(3.6), it follows that

(3. 7)
$\eta_{3}(\min(\frac{t_{1}}{a},\frac{t_{2}}{c}))\eta_{3}(\min(\frac{t_{1}}{b},\frac{t_{2}}{d}))=\eta_{3}(\frac{t_{1}}{a})\eta_{3}(\frac{t_{1}}{b})\eta_{3}(\frac{t_{2}}{c})\eta_{3}(\frac{t_{2}}{d}),t_{1},t_{2}\in
D.$

Fix $t_{1}\in D$ and let $t_{2}\rightarrow\infty$ or $t_{2}$ tend to the right
boundary point of the set $D$. Then the expression on the left side of
equation (3.6) tends to 1 and the expression on the right side tends to

$\eta_{3}(\frac{t_{1}}{a})\eta_{3}(\frac{t_{1}}{b}).$

Hence

(3. 8) $\eta_{3}(\frac{t_{1}}{a})\eta_{3}(\frac{t_{1}}{b})=1,t_{1}\in D.$

This in turn implies that

(3. 9) $\eta_{1}(t_{1})=1,t_{1}\in D.$

A similar analysis shows that

(3. 10) $\eta_{2}(t_{2})=1,t_{2}\in D$

by fixing $t_{2}\in D$ and letting $t_{1}\rightarrow\infty$ or $t_{1}$ tend to
the right boundary point of the set $D$. In particular, it follows that

$F_{X}(t)=F_{M}(t),t\in D$

and

$F_{Y}(t)=F_{N}(t),t\in D.$

Furthermore, equation (3.8) implies that

(3. 11) $\log\eta_{3}(\frac{t}{a})+\log\eta_{3}(\frac{t}{b})=1,t\in D.$

Let $\zeta(t)=\log\eta_{3}(t),t\in D.$ Equation (3.11) implies that

$\zeta(\frac{t}{a})+\zeta(t)(\frac{t}{b})=0,t\in D$

or equivalently

$\zeta(u)=-\zeta(\lambda u),u\in D^{*}$

where $\lambda=\frac{a}{b}$ and $D^{*}=\\{a^{-1}t,t\in D\\}.$ Suppose that
$\lambda=1.$ Then it follows that $\zeta(u)=0,u\in D^{*}$ which in turn
implies that $\eta_{3}(t)=1,t\in D$ and hence $F_{Z_{1}}(t)=F_{S_{1}}(t),t\in
D.$ If $\lambda\neq 1,$ applying Lemma 2 in Li and Zheng (2019), it follows
that $\zeta(u)=0,u\in D^{*}$ under the additional condition of
differentiability of the function $\zeta(u)$ and continuity of its derivative
which implies that $F_{Z_{1}}(t)=F_{S_{1}}(t),t\in D.$ This completes the
proof of Theorem 3.1. Acknowledgment: This work was supported under the scheme
“INSA Honorary Scientist” at the CR Rao Advanced Institute of Mathematics,
Statistics and Computer Science, Hyderabad 500046, India. References

Klebanov, L. 1973. Reconstructing the distributions of the components of a
random vector from distributions of certain statistics, Mathematical Notes,
13:71-72.

Kotlarski, I. 1978. On some characterization in probability by using minima
and maxima of random variables, Aequationes Mathematicae, 17:77-82.

Li, Siran., and Zheng, Xunjie. 2019. A generalization of Lemma 1 in Kotlarski
(1967). Preprint.

Prakasa Rao, B.L.S. 1992. Identifiability in Stochastic Models:
Characterization of Probability Distributions. New York: Academic Press.

Prakasa Rao , B.L.S. 2023. On some characterizations of probability
distributions based on maxima or minima of some families of dependent random
variables, Jour. Indian Soc. Probab. and Statist.,
https://doi.org/10.10007/s41096-024-00180-1.