# Extremes of Sums and Maxima with Application to Random Networks

Natalia Markovich<EMAIL_ADDRESS>V.A. Trapeznikov Institute of
Control Sciences, Russian Academy of Sciences, Moscow, Russian Federation

###### Abstract

The sums and maxima of non-stationary random length sequences of regularly
varying random variables may have the same tail and extremal indices,
Markovich and Rodionov (2020). The main constraint is that there exists a
unique series in a scheme of series with the minimum tail index. The result is
now revised allowing a random bounded number of series to have the minimum
tail index. This new result is applied to random networks.

###### keywords:

Random length sequence , Tail index , Extremal index , Random network

††journal: ICSM-5

##  1 Introduction

Random length sequences and distribution tails of their sums and maxima
attract the interest of many researchers due to numerous applications
including queues, branching processes and random networks [1], [10], [15],
[16], [18], [20], [21], [22].
Let $\\{Y_{n,i}:n,i\geq 1\\}$ be a doubly-indexed array of nonnegative random
variables (r.v.s) in which the ”row index” $n$ corresponds to time, and the
”column index” $i$ enumerates the series. On the same probability space, the
existence of a sequence of non-negative integer-valued r.v.s $\\{N_{n}:n\geq
1\\}$ is assumed. Let $\\{Y_{n,i}:n\geq 1\\}$ be a strict-sense stationary
sequence with extremal index $\theta_{i}$ having a regularly varying tail

$\displaystyle P\\{Y_{n,i}>x\\}$ $\displaystyle=$
$\displaystyle\ell_{i}(x)x^{-k_{i}}$ (1)

with tail index $k_{i}>0$ and a slowly varying function $\ell_{i}(x)$. There
are no assumptions on the dependence structure in $i$. In [18], the weighted
sums and maxima

$\displaystyle
Y_{n}^{*}(z,N_{n})=\max(z_{1}Y_{n,1},...,z_{N_{n}}Y_{n,N_{n}}),~{}~{}Y_{n}(z,N_{n})=z_{1}Y_{n,1}+...+z_{N_{n}}Y_{n,N_{n}}$

for positive constants $z_{1},z_{2},...$ were considered. A similar result was
obtained in [13] for random sequences of a fixed length $l\geq 1$ and when
$\\{Y_{n,i}:n\geq 1\\}$ has a power-type tail, i.e. $P(Y_{n,i}>x)\sim
c^{(i)}x^{-k_{i}}$ as $x\to\infty$, where $c^{(i)}$ is a real-valued positive
constant.

######  Definition 1.

A stationary sequence $\\{Y_{n}\\}_{n\geq 1}$ with distribution function
$F(x)$ and $M_{n}=\bigvee_{j=1}^{n}Y_{j}=\max_{j}Y_{j}$ is said to have
extremal index $\theta\in[0,1]$ if for each $0<\tau<\infty$ there is a
sequence of real numbers $u_{n}=u_{n}(\tau)$ such that

$\displaystyle\lim_{n\to\infty}n(1-F(u_{n}))=\tau\qquad\mbox{and}$
$\lim_{n\to\infty}P\\{M_{n}\leq u_{n}\\}=e^{-\tau\theta}$ (2)

hold ([14], p.63).

I.i.d. r.v.s $\\{Y_{n}\\}$ give $\theta=1$. The converse may be incorrect. An
extremal index that is close to zero implies a kind of a strong local
dependence.
Let us recall Theorem 4 derived in [18]. It is assumed that the ”column”
sequences $\\{Y_{n,i}:i\geq 1\\}$ have stationary distributions (1) in $n$
with positive tail indices $\\{k_{1},k_{2},...\\}$ and extremal indices
$\\{\theta_{1},\theta_{2},...\\}$ for each fixed $i$, where
$\\{\ell_{i}(x)\\}$ are restricted by the condition: for all $A>1$, $\delta>0$
there exists $x_{0}(A,\delta)$ such that for all $i\geq 1$

$\displaystyle\ell_{i}(x)\leq Ax^{\delta},\ \ x>x_{0}(A,\delta)$ (3)

holds. $N_{n}$ has a regularly varying distribution with tail index
$\alpha>0,$ that is

$\displaystyle P(N_{n}>x)=x^{-\alpha}\tilde{\ell}_{n}(x).$ (4)

There is a minimum tail index $k_{1}$ and $k:=\lim_{n\to\infty}\inf_{2\leq
i\leq l_{n}}k_{i},$

$\displaystyle l_{n}=[n^{\chi}],\qquad$ (5)

and $\chi$ satisfies

$0<\chi<\chi_{0},\qquad\chi_{0}=\frac{k-k_{1}}{k_{1}(k+1)}.$ (6)

An arbitrary dependence structure between $\\{Y_{n,i}\\}$ and $\\{N_{n}\\}$ is
allowed. The tail of $N_{n}$ does not dominate the tail of the most heavy-
tailed term $Y_{n,1}$. Let $u_{n}=yn^{1/k_{1}}\ell_{1}^{\sharp}(n)$, $y>0$,
where $\ell_{1}^{\sharp}(n)$ is the de Brujin conjugate of
$\ell(x)=(\ell_{1}(x))^{-1/k_{1}}$, and the positive weights $\\{z_{i}\\}$ are
assumed to be bounded as in [18].

######  Theorem 1.

[18] Let the sets of slowly varying functions
$\\{\tilde{\ell}_{n}(x)\\}_{n\geq 1}$ in (4) and $\\{\ell_{i}(x)\\}_{i\geq 1}$
in (1) satisfy the condition (3). Suppose that $k_{1}<k$ and

$\displaystyle P\\{N_{n}>l_{n}\\}$ $\displaystyle=$ $\displaystyle
o\left(P\\{Y_{n,1}>u_{n}\\}\right),~{}~{}n\to\infty$ (7)

hold, where the sequence $l_{n}$ satisfies (5) and (6). Then the sequences
$Y_{n}^{*}(z,N_{n})$ and $Y_{n}(z,N_{n})$ have the same tail index $k_{1}$ and
the same extremal index $\theta_{1}$.

Theorem 1 is based on Theorem 2 we recall further. Let us denote
$Y_{n}^{*}(z)=Y_{n}^{*}(z,l_{n})$ and $Y_{n}(z)=Y_{n}(z,l_{n})$.

######  Theorem 2.

[18] Let $k_{1}<k$, (3), (5) and (6) hold. Then the sequences $Y_{n}^{*}(z)$
and $Y_{n}(z)$ have the same tail index $k_{1}$ and the same extremal index
$\theta_{1}$.

Our objectives are twofold. At first, we revise Theorem 1 for the case when a
random number of ”column” series may have the minimum tail index. At second,
we modify Theorem 1 with regard to random networks. Each node pair in a random
network is connected with some probability [3].
Let $G_{n}=(V_{n},E_{n})$ be a directed graph with a set of vertices
$V_{n}=\\{1,...,n\\}$, and a set of directed edges $E_{n}$. Google’s PageRank
vector $R=(R_{1},...,R_{n})$ is the unique solution to the following system of
linear equations:

$\displaystyle R_{i}$ $\displaystyle=$ $\displaystyle c\sum_{j:(j,i)\in
E_{n}}\frac{R_{j}}{D_{j}}+(1-c)q_{i},\qquad i=1,...,n,$ (8)

where the summation is taken over a number of pages $j$ that link to page $i$
(in-degree), $D_{j}$ is the number of outgoing links of page $j$ (out-degree),
$c\in(0,1)$ is a damping factor, $q=(q_{1},q_{2},...,q_{n})$ is a
personalization probability vector or user’s preferences such that $q_{i}\geq
0$ and $\sum_{i=1}^{n}q_{i}=1$, and $n$ is the total number of pages. The
World Wide Web (Web) is a very large interconnected graph where nodes
correspond to pages. The PageRank was designed to rank pages on the Web in
such a way that a page is important if many important pages have a hyperlink
to it [6].
A stochastic approach to analyze (8) is the following. The PageRank of a
randomly chosen Web page (i.e. a vertex on a Web graph) considered as a root
node of a Galton-Watson tree with random in- and out-degrees may be modeled as
a r.v. $R$ which is the solution of the fixed-point problem (cf. [20], [23],
[5], [8])

$R=^{D}\sum_{j=1}^{N}A_{j}R_{j}+Q$ (9)

assuming that $\\{R_{j}\\}$ are independent identically distributed (i.i.d.)
copies of $R$ and $E(Q)<1$ holds. $(Q,N,\\{A_{j}\\})$ is a real-valued vector.
$N$ denotes the in-degree. $Q$ is a personalization value of the vertex [23].
$=^{D}$ means equality in distribution. Under the assumptions (we shall call
it Assumptions A) that $\\{R_{j}\\}$ are i.i.d. and independent of
$(Q,N,\\{A_{j}\\})$ with $\\{A_{j}\\}$ independent of $(N,Q)$, and that $N$
and $Q$ are allowed to be dependent, it is stated in [23], [8] that the
stationary distribution of $R$ in (9) is regularly varying and its tail index
is determined by the most heavy-tailed distributed term in the regularly
varying distributed pair $(N,Q)$.
This result was generalized by [1], and the unique solution of (9) is proved
to be intermediate regularly varying111The class of intermediate regularly
varying distributions such that $\lim_{\alpha\uparrow
1}\limsup_{x\to\infty}\overline{F}(\alpha x)/\overline{F}(x)=1$ includes
regularly varying distributions., if $Q$ or $N$ has an intermediate regularly
varying distribution, or $(Q,N)$ has a two-dimensional regularly varying
distribution. The multivariate version of (9)

$\displaystyle R(i)=^{D}\sum_{k=1}^{K}\sum_{m=1}^{N^{(k)}(i)}R_{m}(k)+Q(i),$

where $R_{m}(k)=^{D}R(k)$ holds, is considered with similar assumptions and
regularly varying statements by thinking that $N^{(k)}(i)$ is a number of
type-$k$ children of a type-$i$ ancestor and considering a multi-type Galton-
Watson tree.
A Max-Linear Model [12] is obtained by substitution sums in (8) by maxima,
i.e.

$\displaystyle R(i)$ $\displaystyle=$ $\displaystyle\bigvee_{j\to
i}A_{j}R(j)\vee Q_{i},~{}~{}i=1,...,n.$ (10)

Under Assumptions A the power law tail $P\\{|R|>x\\}\sim Hx^{-\alpha}$,222The
symbol $\sim$ means asymptotically equal to or $f(x)\sim g(x)$
$\Leftrightarrow$ $f(x)/g(x)\rightarrow 1$ as $x\rightarrow a$, $x\in M$ where
the functions $f(x)$ and $g(x)$ are defined on some set $M$ and $a$ is a limit
point of $M$. $\alpha>0$, $H>0$ as $x\to\infty$ of the so called
’minimal/endogeneous’ solution of the equation

$R=^{D}\left(\bigvee_{j=1}^{N}A_{j}R_{j}\right)\vee Q,$ (11)

is derived in [9]. We propose to apply Theorem 1 to the right-hand sides of
(9) and (11) under weaker assumptions than the Assumptions A. Namely, the
conditions that PageRanks $\\{R_{j}\\}$ of the first generation are i.i.d. and
the mutual independence of $\\{R_{j}\\}$ and $N$ are omitted. By a modified
Theorem 1 (Theorem 5) we obtain that the most heavy-tailed terms $\\{R_{j}\\}$
determine the heaviness of the tail and the extremal index of both the sum and
maximum.
The paper is organized as follows. The revision of Theorems 1 and 2 by
Theorems 3 and 4 is given in Section 2. The modification of Theorem 4 by
Theorem 5 to find the extremal and tail indices of PageRank and the Max-Linear
Model as influence measures of nodes in random direct graphs is presented in
Section 3. Conclusions and a discussion are presented in Section 4. The proofs
are given in Section 5.

##  2 Revision of Theorem 1

We revise Theorem 1 by Theorem 4 allowing a random bounded number $d\geq 1$ of
series to have a minimum tail index. To this end, we extend Theorem 2 by
Theorem 3. We assume in Theorems 3 and 4 that $k_{i}=k_{1}$,
$i\in\\{1,...,d\\}$, $1\leq d\leq l_{n}-1$, $k_{1}<k$, where

$\displaystyle k$ $\displaystyle:=$
$\displaystyle\lim_{n\to\infty}\inf_{d+1\leq i\leq l_{n}}k_{i},$ (12)

and that (5), (6) hold.
We introduce the following independence condition:
(A1) The stationary sequences $\\{Y_{n,i}\\}_{n\geq 1}$, $i\in\\{1,...,d\\}$
are mutually independent, and independent of the sequences
$\\{Y_{n,i}\\}_{n\geq 1}$, $i\in\\{d+1,...,l_{n}\\}$.
Denote
$M_{n}^{(i)}=\max\\{Y_{1,i},Y_{2,i},...,Y_{n,i}\\},~{}i\in\\{1,..,l_{n}\\}$.

######  Theorem 3.

Let (3) hold for all $d+1\leq i\leq l_{n}$. Then the sequences
$Y_{n}^{*}(z,l_{n})$ and $Y_{n}(z,l_{n})$ have the same tail index $k_{1}$.

  1. 1.

If, in addition, (A1) holds, then $Y_{n}^{*}(z,l_{n})$ and $Y_{n}(z,l_{n})$
have the same extremal index

$\displaystyle\theta(z)$ $\displaystyle=$
$\displaystyle\sum_{j=1}^{d}\theta_{j}z_{j}^{k_{1}}/\sum_{j=1}^{d}z_{j}^{k_{1}}.$
(13)

  2. 2.

If, instead, (A1) does not hold and $d=1$, then their extremal index is equal
to $\theta_{1}$, but it may not exist, if $d>1$. Assuming for $d>1$ that all
elements in pairs of the ”column” sequences $\\{Y_{n,i}\\}_{n\geq 1}$,
$i\in\\{1,...,d\\}$ have the same mutual dependence, and

$\displaystyle\sum_{j=1}^{d-1}P\\{z_{j}M_{n}^{(j)}>u_{n},z_{j+1}M_{n}^{(j+1)}\leq
u_{n},...,z_{d}M_{n}^{(d)}\leq u_{n}\\}=o(P\\{z_{d}M_{n}^{(d)}\leq u_{n}\\})$
(14)

holds as $n\to\infty$, $Y_{n}^{*}(z,l_{n})$ and $Y_{n}(z,l_{n})$ have the
extremal index $\theta_{d}$.

######  Remark 1.

Since an enumeration of the first $d$ ”column” sequences is not significant,
one can rewrite the condition (14) with regard to the $i$th column and obtain
the same statement for any $\theta_{i}$, $i\in[1,d]$.

######  Corollary 1.

Let $Y_{n,i}=Y_{n,1}$, $n\geq 1$, $i\in\\{1,...,d\\}$. Then
$Y_{n}^{*}(z,l_{n})$ and $Y_{n}(z,l_{n})$ have the same tail index $k_{1}$ and
the same extremal index $\theta_{1}$.

######  Remark 2.

If there are in total $d+1$ stationary mutually independent ”column” sequences
having the same tail index $k_{1}$ and extremal indices
$\theta_{1},...,\theta_{d+1}$, then $Y_{n}^{*}(z,l_{n})$ and $Y_{n}(z,l_{n})$
have the tail index $k_{1}$ and the extremal index that is a superposition of
$\theta_{1},...,\theta_{d+1}$ as derived in [13], see Theorem 2 in [18].

######  Example 1.

In case of an arbitrary dependence among elements of the $d$ ”columns” series
with the minimum tail index, the extremal index of maxima $Y_{n}^{*}(z,l_{n})$
and sums $Y_{n}(z,l_{n})$ may not exist. Suppose elements of odd ”row”
sequences coincide and elements of the even rows are i.i.d.. Then sums and
maxima over rows are differently distributed and the sequences
$Y_{n}^{*}(z,l_{n})$ and $Y_{n}(z,l_{n})$ are nonstationary.

######  Example 2.

The assumption (14) is valid for the following $d$ ”column” sequences. Let
elements of each ”column” sequence be sums of corresponding elements of all
previous ”columns”, i.e. $Y_{n,i}=\sum_{j=1}^{i-1}Y_{n,j}$ and $z_{1}\leq
z_{2}\leq...\leq z_{d}$. Each of $d$ ”column” sequences has the tail index
$k_{1}$ that follows from the first statement of Theorem 3. Since
$M_{n}^{(1)}=M_{n}^{(2)}<M_{n}^{(3)}<...<M_{n}^{(d)}$ holds, then
$\sum_{j=1}^{d-1}P\\{z_{j}M_{n}^{(j)}>u_{n},z_{j+1}M_{n}^{(j+1)}\leq
u_{n},...,z_{d}M_{n}^{(d)}\leq u_{n}\\}=0$ holds.

Now we reformulate Theorem 1.

######  Theorem 4.

Let the sets of slowly varying functions $\\{\tilde{\ell}_{n}(x)\\}_{n\geq 1}$
in (4) and $\\{\ell_{i}(x)\\}_{d+1\leq i\leq l_{n}}$ in (1) satisfy the
condition (3). Assume that $d$ is a bounded discrete r.v. such that
$d<d_{n}=\min(C,l_{n})$, $C>1$ holds, and $d$ and $\\{Y_{n,i}\\}$ are mutually
independent. Let (7) hold. Then $Y_{n}^{*}(z,N_{n})$ and $Y_{n}(z,N_{n})$ have
the same tail index $k_{1}$, but their extremal indices do not exist.

######  Corollary 2.

The results of Theorems 3 and 4 remain true if the tail indices
$\\{k_{n,i}\\}$ of elements in the ”columns” $\\{Y_{n,i}:n\geq 1\\}$ are
different, apart of those columns with the minimum tail index. The elements of
the columns with non-minimum tail indices may be partly light-tailed
distributed.

The corollary follows from the proof of Theorem 3 and Lemma 1 in [18].

##  3 Application to Random Networks

Each node in a random network may be considered as a root of some directed
graph of its followers (i.e. nodes with incoming links to the root node) which
may contain cycles. Thus, generations of followers may be overlapping. The
$r$th generation implies the set of nodes in the tree at distance $r$ from the
root node [6]. There may exist links between nodes within generations.
Influence characteristics of nodes such as PageRanks or the Max-Linear Models
calculated by these generations may be dependent.
Generations may be non-stationary distributed since their nodes may belong to
communities with different distributions and the graph is not necessarily
fully connected, Fig.1. A community structure is ’the organization of vertices
in clusters, with many edges joining vertices of the same cluster and
comparatively few edges joining vertices of different clusters’ [7]. There are
methods to extract the community structure of large networks, see, for
instance, [4], [19].

Figure 1: The (disconnected) graph with nodes from different communities (a
dashed arrow may be absent). Nodes from dominating communities with the most
heavy-tailed distributed influence indices having the minimum tail index
$k_{1}$ are marked by filled circles, and nodes from other communities by open
circles and filled rings.

Theorem 4 is further reformulated in the context of PageRank and the Max-
Linear Model. Denote an in-degree of the node $i$ as $N_{i}$. $N_{i}$
determines the random size of the generation of a one-link neighborhood from
the node $i$. Let us denote $A_{j}R(j)=cR(j)/D_{j}$, $j\in\\{1,...,N_{i}\\}$
in (8) and (10) as $z_{j}Y_{i,j}$ with $z_{j}=c$. Then one can rewrite the
right-hand sides of (9) and (11) in notations of Theorems 1 and 4 as

$\displaystyle Y_{i}(c,N_{i})$ $\displaystyle=$ $\displaystyle
c\sum_{j=1}^{N_{i}}Y_{i,j}+Q_{i},~{}~{}Y^{*}_{i}(c,N_{i})=c\bigvee_{j=1}^{N_{i}}Y_{i,j}\vee
Q_{i},~{}~{}i\in\\{1,...,n\\},$ (15)

where $\\{Y_{i,j}\\}$ are not i.i.d. r.v.s. $\\{Y_{i,j}\\}$ and $Q_{i}$ as
well as $\\{Y_{i,j}\\}$ and $N_{i}$ are not necessarily mutually independent.
$N_{i}$ satisfies (7). In the context of PageRank $Q_{i}=(1-c)q_{i}$ holds.
Let us consider the matrix (16) of the array $\\{Y_{n,i}:n,i\geq 1\\}$
corresponding to (15), and the tail and extremal indices of its columns are
shown in matrix (17):

$\left(\begin{array}[]{ccccccc}cY_{1,1}&cY_{1,2}&cY_{1,N_{1}}&...&0&0&Q_{1}\\\
cY_{2,1}&0&cY_{2,3}&~{}~{}...&cY_{n,N_{2}}&0&Q_{2}\\\
...&...&...&...&...&...\\\
0&cY_{n,2}&cY_{n,3}&~{}~{}...&0&cY_{n,N_{n}}&Q_{n}\\\ \end{array}\right),$
(16)
$\left(\begin{array}[]{ccccccc}k_{1}{}{}{}&k_{2}{}{}{}&k_{3}{}{}{}&...{}{}&...&~{}~{}~{}~{}k_{N_{n}}&~{}\beta\\\
\theta_{1}{}{}{}&\theta_{2}{}{}{}&\theta_{3}{}{}{}&...{}{}&...&~{}~{}~{}~{}\theta_{N_{n}}&1\\\
\end{array}\right).$ (17)

The sequence $\\{N_{n}\\}$ is equal to the number of non-zero elements in the
rows and it is not necessarily increasing. Row elements in (16) (excluding
$\\{Q_{i}\\}$) correspond to the first generations of followers of nodes that
can be arbitrary enumerated as $1,2,...,n$. The column $i$ contains a
community and has the extremal index $\theta_{i}$. Zeroes in the rows imply
that the first generations do not contain followers from the corresponding
communities. ”Column” series may be mutually dependent and have tails (1) with
tail indices $\\{k_{i}\\}$. The latter columns may (partly) coincide. In
random networks the column dependence reflects the fact that communities may
be overlapping.
The last column in (16) contains i.i.d. r.v.s of user preferences
$\\{Q_{i}\\}$. Theorem 4 is valid if $\\{Q_{i}\\}$ are heavy- or light-tailed
distributed. In- and out-degrees of nodes are available statistics in
practice, but the user preference has to be simulated [23]. The preference is
often expected to be uniformly distributed, i.e. an arbitrary page can be
selected by a user uniformly among the nodes of the network. In [23] Pareto
distributed $\\{Q_{i}\\}$ were studied by real data. The tail of $\\{N_{i}\\}$
is assumed here to be lighter than the regularly varying tails of
$\\{Y_{i,j}\\}$ and $\\{Q_{i}\\}$. We assume that there exist columns with a
minimum tail index $k_{1}$, $k_{1}<k$.
Let the graph be partitioned into communities of nodes whose PageRanks are
stationary regularly varying distributed with tail indices
$\\{k_{1},k_{2},...\\}$ and extremal indices
$\\{\theta_{1},\theta_{2},...\\}$. We assume that at least one neighbor of a
root-node $i$ belongs to one of the $d$ most heavy-tailed (dominating)
communities (i.e. there exists a type-$k_{1}$ child of the ancestor $i$). The
number of such neighbors is random and they may belong to different dominating
communities. It means that all row sequences $\\{Y_{n,i}:n\geq 1\\}$ in (16)
must have at least one element with the smallest tail index.

######  Theorem 5.

PageRanks and the Max-Linear Models of $n$ root-nodes have the same minimum
tail index as one of the $d$ most heavy-tailed distributed communities within
a random graph associated with the roots as $n\to\infty$. Their extremal index
is equal to the extremal index of the most heavy-tailed distributed community
if the latter is unique, and it is calculated by (13) using extremal indices
of the $d$ most heavy-tailed communities if the latter are mutually
independent and independent of the rest of communities, or it may not exist if
the latter independence condition is not valid.

Theorem 5 determines the extremal index of the node in the directed graph
(except for the graph leaves).

######  Remark 3.

There are three important practical assumptions in Theorem 5.
(1) By Corollary 2 the node influence indices within non-dominating
communities are allowed to be non-stationary distributed. This property allows
us to use non-stationary distributed communities if they are not tail
dominant.
(2) All elements of the dominating communities have to be regularly varying
distributed. To our best knowledge, PageRanks are proved to be power law
distributed for branching trees in [23], the directed configuration model in
[17] and directed generalized random graphs in [5] under Assumptions A. The
existence of an asymptotic PageRank distribution for directed graphs is proved
assuming a local weak convergence of a sequence of directed graphs to a
limiting graph [11]. The conditions under which the PageRank of the root in
the limiting graph shows a power-law tail was not found in [11].
(3) The dependence between communities impacts the extremal index of PageRanks
and the Max-Linear Models of the root-nodes.

Our approach can be used to simulate an enlargement of graphs with given
values of the tail and extremal indices of the nodes. To this end, one can
simulate communities of nodes with given tail and extremal indices connected
to a sequence of root-nodes which do not belong to the communities. If there
is a unique community with the minimum tail index among them, then the
sequence of the root nodes inherits its tail and extremal indices. Selecting
$d$ mutually independent communities with a minimum tail index $k_{1}$ and
extremal indices $\theta_{1},...,\theta_{d}$, PageRank and the Max-Linear
Model sequences of the associated root nodes will have the same tail index
$k_{1}$ and the extremal index $\theta(z)$ calculated by (13) using
$\theta_{1},...,\theta_{d}$ and taking weights $z_{j}=c$, $j\in\\{1,...,d\\}$.
Adding the sequence of roots as a new community does not change the dependence
structure and the heaviness of tail of PageRank and the Max-Linear Model of
the next sequence of roots, namely, it will be $(k_{1},\theta(z))$.
Since the reciprocal of the extremal index approximates the mean cluster size
[14], the extremal index can also be used as the node influence. Namely, a
node with the extremal index close to zero may be considered as an influential
one since there are generations (the clusters) of followers in its coupled
graph with a large number of nodes whose influence measures exceed a
sufficiently high threshold $u$. One can consider the generations as random
length blocks that can be overlapping.
Theorem 5 is valid both for directed and undirected graphs. The calculation of
PageRank by undirected graphs is considered in [2], for instance.

##  4 Conclusions and discussion

This paper makes a fundamental step forward by extending the analysis of
PageRank and the Max-Linear Model to its extremes and to graphs that are not
necessarily trees. Our approach to find the asymptotic distributions and local
cluster properties of PageRank and the Max-Linear Model is based on results
derived for the sums and maxima of non-stationary random lengths sequences in
[18]. The main constraint of these results is that a unique series with the
minimum tail index in a scheme of series with regularly varying tails is
assumed. This assumption may not be realistic in practice since a node in a
random network may have a random number of followers (not necessarily a unique
follower) belonging to the most heavy-tailed communities. Another important
assumption is that the mutually dependent series are allowed to be regularly
varying. Regarding PageRank and the Max-Linear Model the regularly varying
assumption of the latter characteristics is crucial, since the power-law tails
are proved to our best knowledge only for mutually independent series.
Our results are twofold. At first, we extend Theorems 3 and 4 in [18] by
Theorems 3 and 4. Secondly, we interpret these results to PageRank and the
Max-Linear Model. Theorem 5 is the analogue of Theorem 4 for random networks.
To our best knowledge, the extremal index of PageRank and the Max-Linear Model
is considered at first time. The extremal index may serve as a new influence
measure of nodes.

##  5 Proofs

###  5.1 Proof of Theorem 3

The proof is similar to that of Theorem 3 [18]. We just indicate the
modifications. The numeration of Theorem 3 [18] is preserved throughout the
proof. Let us take the same sequence of thresholds
$u_{n}=yn^{1/k_{1}}\ell^{\sharp}_{1}(n)$, $y>0$ as in [18].

#### Tail index

At first, we show that the tail index of $Y_{n}(z)$ and $Y_{n}^{*}(z)$ is the
same. The right-hand side of (12) in [18] can be rewritten as

$\displaystyle P\\{Y_{n}(z)>u_{n}\\}$ $\displaystyle\leq$ $\displaystyle
P\\{\sum_{i=1}^{d}z_{i}Y_{n,i}>u_{n}(1-\varepsilon)\\}+\sum_{i=d+1}^{l_{n}}P\\{z_{i}Y_{n,i}>u_{n}\varepsilon_{i}\\},$
(18)

where $\sum_{i=1}^{l_{n}}\varepsilon_{i}=1$ holds and $\\{\varepsilon_{i}\\}$
is a sequence of positive elements. Let us denote
$\varepsilon=\sum_{i=d+1}^{l_{n}}\varepsilon_{i}$. One may take
$\varepsilon_{i}$, $i\in\\{d+1,...,l_{n}\\}$, in such a way to satisfy
$\varepsilon_{i}\to 0$ and $\varepsilon\to 0$ as $n\to\infty$. Moreover,
choosing $\\{\varepsilon_{i}=1/l_{n}^{\eta+1}\\}$, $\eta>0$ as in Lemma 1 in
[18] one can derive (13) in [18] substituting $2$ by $d+1$, namely, the
following

$\displaystyle\sum_{i=d+1}^{l_{n}}P\\{z_{i}Y_{n,i}>u_{n}\varepsilon_{i}\\}=o(1/n)$
(19)

as $n\to\infty$. To prove the latter, we need to assume (3) for $d+1\leq i\leq
l_{n}$. For simplicity, let us consider the case $d=2$. Then by (7) in [18]

$\displaystyle
P\\{z_{1}Y_{n,1}>u_{n}\\}=(z_{1}/y)^{k_{1}}n^{-1}(1+o(1)),~{}~{}n\to\infty$
(20)

and (13) in [18] we obtain

$\displaystyle P\\{z_{1}Y_{n,1}+z_{2}Y_{n,2}>u_{n}(1-\varepsilon)\\}$
$\displaystyle\leq$ $\displaystyle
P\\{z_{1}Y_{n,1}>u_{n}(1-\varepsilon)\varepsilon_{1}^{*}\\}+P\\{z_{2}Y_{n,2}>u_{n}(1-\varepsilon)\varepsilon_{2}^{*}\\}$
$\displaystyle=$
$\displaystyle\frac{n^{-1}}{(y(1-\varepsilon))^{k_{1}}}\left[\left(\frac{z_{1}}{\varepsilon_{1}^{*}}\right)^{k_{1}}+\left(\frac{z_{2}}{\varepsilon_{2}^{*}}\right)^{k_{1}}\right](1+o(1)),$

where $\varepsilon_{1}^{*}+\varepsilon_{2}^{*}=1$ holds. Let us denote

$\displaystyle(z^{*})^{k_{1}}$ $\displaystyle=$
$\displaystyle\left(\frac{z_{1}}{\varepsilon_{1}^{*}}\right)^{k_{1}}+\left(\frac{z_{2}}{\varepsilon_{2}^{*}}\right)^{k_{1}}.$

By (14) in [18] it follows

$\displaystyle P\\{Y_{n}(z)>u_{n}\\}$ $\displaystyle\leq$
$\displaystyle\left(\frac{z^{*}}{y(1-\varepsilon)}\right)^{k_{1}}n^{-1}(1+o(1))+o(1/n).$
(21)

From another side, we have

$\displaystyle P\\{Y_{n}(z)>u_{n}\\}$ $\displaystyle\geq$ $\displaystyle
P\\{z_{1}Y_{n,1}>u_{n}\\}=\left(\frac{z_{1}}{y}\right)^{k_{1}}n^{-1}(1+o(1))$
(22)

and the left-hand side of (9) in [18] does not change. The heaviness of tail
of both $Y_{n}(z)$ and $Y_{n}^{*}(z)$ coincides. The proof is the same for
$d>2$.

#### Extremal index for $d$ independent ”column” sequences

We assume the condition (A1). Denoting

$\displaystyle
M_{n}^{*}(z)=\max\\{Y_{1}^{*}(z),...,Y_{n}^{*}(z)\\}=\max\\{z_{1}M_{n}^{(1)},...,z_{l_{n}}M_{n}^{(l_{n})}\\},~{}n\geq
1,$

where $Y^{*}_{n}(z)=Y^{*}_{n}(z,l_{n})$ as in (18) [18], we have due to
independence

$\displaystyle P\\{M_{n}^{*}(z)\leq
u_{n}\\}=\prod_{j=1}^{d}P\\{z_{j}M_{n}^{(j)}\leq
u_{n}\\}P\\{z_{d+1}M_{n}^{(d+1)}\leq u_{n},...,z_{l_{n}}M_{n}^{(l_{n})}\leq
u_{n}\\}.$

Since the extremal index of the sequence $\\{Y_{n,j}\\}_{n\geq 1}$, $1\leq
j\leq d$ is assumed to be equal to $\theta_{j},$ by (2) and (20) we get

$\displaystyle\lim_{n\to\infty}\prod_{j=1}^{d}P\\{z_{j}M_{n}^{(j)}\leq
u_{n}\\}$ $\displaystyle=$
$\displaystyle\exp(-\sum_{j=1}^{d}\theta_{j}(z_{j}/y)^{k_{1}}).$

By (19) and (21) in [18] and by (2), we obtain

$\displaystyle P\\{z_{d+1}M_{n}^{(d+1)}\leq
u_{n},...,z_{l_{n}}M_{n}^{(l_{n})}\leq u_{n}\\}=P\\{z_{d+1}M_{n}^{(d+1)}\leq
u_{n}\\}(1+o(1))\to 1,$

since

$\displaystyle nP\\{z_{d+1}Y_{n,d+1}>u_{n}\\}\sim n\cdot
n^{-k_{d+1}/k_{1}}\ell(n)\to 0$

as $n\to\infty$ due to $k_{d+1}>k_{1}$. We obtain

$\displaystyle\lim_{n\to\infty}nP\\{Y_{n}^{*}(z)>u_{n}\\}=\sum_{j=1}^{d}\left(\frac{z_{j}}{y}\right)^{k_{1}}$
(23)

since it holds

$\displaystyle
P\\{Y_{n}^{*}(z)>u_{n}\\}=P\\{\max(z_{1}Y_{n,1},...,z_{d}Y_{n,d},z_{d+1}Y_{n,d+1},...,z_{l_{n}}Y_{n,l_{n}})>u_{n}\\}$
$\displaystyle\sim$
$\displaystyle\\!\\!\\!\sum_{i=1}^{d}P\\{z_{i}Y_{n,i}>u_{n}\\}+P\\{\max(z_{1}Y_{n,1},...,z_{d}Y_{n,d})\leq
u_{n}\\}P\\{\max(z_{d+1}Y_{n,d+1},...,z_{l_{n}}Y_{n,l_{n}})>u_{n}\\}$
$\displaystyle=$
$\displaystyle\sum_{j=1}^{d}\left(\frac{z_{j}}{y}\right)^{k_{1}}\cdot
n^{-1}(1+o(1))+o(1/n)$

due to (9), (12), (13) and Lemma 1 all in [18]. Then from

$\displaystyle P\\{M_{n}^{*}(z)\leq
u_{n}\\}=\exp(-\sum_{j=1}^{d}\theta_{j}(z_{j}/y)^{k_{1}})(1+o(1))$ (24)

we obtain that the extremal index of $Y_{n}^{*}(z)$ is equal to (13). In the
same way as in the proof of Theorem 3 in [18] one can show that $Y_{n}(z)$ has
the same extremal index.

#### Extremal index for $d$ arbitrary dependent ”column” sequences

We show that the extremal indices of the sequences $Y_{n}^{*}(z)$ and
$Y_{n}(z)$ may not exist if the condition (A1) is not valid. If $d=1$, i.e.
there is a unique ”column” series with the minimum tail index, we are in the
conditions of Theorem 2. Let us consider the case $d>1$.
Note, that $Y_{n}^{*}(z)$ and $Y_{n}(z)$ may be non-stationary distributed if
the pair-wise dependence between elements of ”column” sequences is different
as in Example 1. Assume further that $Y_{n}^{*}(z)$ and $Y_{n}(z)$ are
stationary distributed. Let us rewrite (19) in [18] as

$\displaystyle P\\{M_{1,d}\leq
u_{n}\\}-\sum_{i=d+1}^{l_{n}}P\\{z_{i}M_{n}^{(i)}>u_{n}\\}$ (25)
$\displaystyle\leq$ $\displaystyle P\\{z_{1}M_{n}^{(1)}\leq
u_{n},...,z_{l_{n}}M_{n}^{(l_{n})}\leq u_{n}\\}=P\\{M_{n}^{*}(z)\leq u_{n}\\}$
$\displaystyle\leq$ $\displaystyle P\\{M_{1,d}\leq u_{n}\\}\leq
P\\{z_{d}M_{n}^{(d)}\leq u_{n}\\},$

where
$M_{1,d}=\max\\{z_{1}M_{n}^{(1)},z_{2}M_{n}^{(2)},...,z_{d}M_{n}^{(d)}\\}$. By
(21) in [18] and assuming (3), we have

$\displaystyle\sum_{i=d+1}^{l_{n}}P\\{z_{i}M_{n}^{(i)}>u_{n}\\}$
$\displaystyle=$ $\displaystyle o(1),~{}~{}n\to\infty.$ (26)

We get

$\displaystyle P\\{M_{1,d}\leq u_{n}\\}=1-P\\{M_{1,d}>u_{n}\\}$
$\displaystyle=$ $\displaystyle
1-P\\{z_{d}M_{n}^{(d)}>u_{n}\\}-\sum_{j=1}^{d-1}P\\{z_{j}M_{n}^{(j)}>u_{n},z_{j+1}M_{n}^{(j+1)}\leq
u_{n},...,z_{d}M_{n}^{(d)}\leq u_{n}\\}.$

Assuming that (14) holds, the expression

$\displaystyle P\\{M_{n}^{*}(z)\leq u_{n}\\}$ $\displaystyle=$ $\displaystyle
P\\{z_{d}M_{n}^{(d)}\leq
u_{n}\\}(1+o(1))=\exp(-\theta_{d}(z_{d}/y)^{k_{1}})(1+o(1))$

that is required to obtain the extremal index $\theta_{d}$ for $Y_{n}^{*}(z)$
follows, otherwise not. The same holds for $Y_{n}(z)$ since

$\displaystyle P\\{M_{n}^{*}(z)\leq u_{n}\\}=P\\{M_{n}(z)\leq
u_{n}\\}(1+o(1))$ (27)

can be derived similarly to (23) in [18] due to the common tail index of
$Y_{n}^{*}(z)$ and $Y_{n}(z)$.

###  5.2 Proof of Corollary 1

The existence of a common tail index $k_{1}$ for $Y_{n}^{*}(z,l_{n})$ and
$Y_{n}(z,l_{n})$ can be shown the same way as in the proof of Theorem 3. Since
$Y_{n}^{*}(z,d)=\bigvee_{i=1}^{d}z_{i}Y_{n,1}=z^{**}Y_{n,1}$ and
$Y_{n}(z,d)=\sum_{i=1}^{d}z_{i}Y_{n,1}=z^{*}Y_{n,1}$ hold and by (18), (19),
(20) we get

$\displaystyle
P\\{Y_{n}(z,l_{n})>u_{n}\\}=\left(z^{*}/y\right)^{k_{1}}n^{-1}(1+o(1)),$

as $n\to\infty$. The same is valid for $Y_{n}^{*}(z,l_{n})$ since
$z^{**}<z^{*}$. Due to $M_{1,d}=M_{n}^{(1)}z^{**}$ and by (25), (26) we obtain

$\displaystyle P\\{M_{n}^{*}(z)\leq u_{n}\\}=P\\{M_{n}^{(1)}z^{**}\leq
u_{n}\\}(1+o(1))=\exp(-\theta_{1}(z^{**}z_{1}/y)^{k_{1}})(1+o(1))$

due to (20). The same is valid for $M_{n}(z)$ as in Theorem 3 in [18]. Thus,
the statement follows.

###  5.3 Proof of Theorem 4

Denote $S_{n,d}=\sum_{i=1}^{d}z_{i}Y_{n,i}$ and
$S_{n,l_{n}-d}=\sum_{i=d+1}^{l_{n}}z_{i}Y_{n,i}$. Since $d$ is bounded by
$d_{n}=\min(C,l_{n})$ we get

$\displaystyle P\\{Y_{n}(z)>u_{n}\\}=P\\{S_{n,d}+S_{n,l_{n}-d}>u_{n}\\}$
$\displaystyle=$ $\displaystyle P\\{S_{n,d}+S_{n,l_{n}-d}>u_{n},1\leq
d\leq\lfloor d_{n}-1\rfloor\\}+P\\{S_{n,d}+S_{n,l_{n}-d}>u_{n},d>d_{n}-1\\}$
$\displaystyle=$ $\displaystyle\sum_{m=1}^{\lfloor
d_{n}-1\rfloor}P\\{S_{n,m}+S_{n,l_{n}-m}>u_{n}\\}P\\{d=m\\}+o(1),~{}~{}n\to\infty.$

In the same way it follows

$\displaystyle P\\{Y_{n}(z)>u_{n}\\}\geq P\\{S_{n,d}>u_{n},1\leq d\leq\lfloor
d_{n}-1\rfloor\\}=\sum_{m=1}^{\lfloor
d_{n}-1\rfloor}P\\{S_{n,m}>u_{n}\\}P\\{d=m\\}.$

Similarly, one can obtain the lower bound of $P\\{Y_{n}^{*}(z)>u_{n}\\}$
replacing sums by maxima. Applying the same steps of the proof to
$P\\{S_{n,m}+S_{n,l_{n}-m}>u_{n}\\}$ and $P\\{S_{n,m}>u_{n}\\}$ as in Theorem
3 we obtain that the sequences $Y_{n}^{*}(z,l_{n})$ and $Y_{n}(z,l_{n})$ have
the same tail index $k_{1}$.
We investigate the extremal indices of $Y_{n}^{*}(z,l_{n})$ and
$Y_{n}(z,l_{n})$ in case of the independence condition (A1). If $d_{n}=C$
holds, then by (23) and (24) it follows

$\displaystyle P\\{M_{n}^{*}(z)\leq u_{n}\\}=\sum_{m=1}^{\lfloor
C-1\rfloor}\exp\left(-\sum_{j=1}^{m}\theta_{j}(z_{j}/y)^{k_{1}}\right)P\\{d=m\\}(1+o(1))=A(y),$
$\displaystyle\lim_{n\to\infty}nP\\{Y_{n}^{*}(z)>u_{n}\\}=\sum_{m=1}^{\lfloor
C-1\rfloor}\sum_{j=1}^{m}(z_{j}/y)^{k_{1}}P\\{d=m\\}=\tau(y).$

The expression

$\displaystyle\\!\\!\\!\theta(z)$ $\displaystyle=$
$\displaystyle-\ln\left(A(y)\right)/\tau(y)$

cannot be considered as an extremal index of $Y_{n}^{*}(z)$ due to the
presence of the arbitrary constant $y>0$ which is included in $u_{n}$. The
same result is valid for $Y_{n}(z)$ due to (27). The same proof follows for
$d_{n}=l_{n}<C$ because of the majorant converging series.
If (A1) does not hold, then the extremal indices of $Y_{n}^{*}(z)$ and
$Y_{n}(z)$ do not exist by similar reasons. In case that (5.1) is fulfilled,
one can indicate only bounds for $P\\{Y_{n}>u_{n}\\}$ and
$P\\{Y^{*}_{n}>u_{n}\\}$ by (21) and (22).

###  5.4 Proof of Theorem 5

The statement is based on the proof of Theorems 3 and 4. According to (15)
sums $\\{Y_{i}(c,N_{i})\\}$ and maxima $\\{Y_{i}^{*}(c,N_{i})\\}$,
$i\in\\{1,...,n\\}$ determine PageRanks and the Max-Linear Models of $n$ nodes
in the graph, where $Y_{i}(c,N_{i})$ and $Y_{i}^{*}(c,N_{i})$ are built by
PageRanks of neighbors of node $i$ considered as the root of the coupled tree.
These neighbors belong to some communities. In the same way as in the proof of
Theorem 4, one can get that $Y_{n}(c,N_{n})$ and $Y^{*}_{n}(c,N_{n})$ have the
minimum tail index as the most heavy-tailed distributed communities, let’s say
$k_{1}$, as $n\to\infty$. Following the proof of Theorem 4 in [18] and
considering the maxima of sequences $\\{Y_{i}(c,N_{i})\\}$ and
$\\{Y^{*}_{i}(c,N_{i})\\}$, $i\in\\{1,...,n\\}$ one can confirm that these
maxima have the same asymptotic distribution as $n\to\infty$ and thus,
PageRanks and the Max-Linear Models of $n$ root-nodes have the extremal index
$\theta_{1}$ of the most heavy-tailed distributed community in case the latter
is unique. If the number of the most heavy-tailed distributed communities
related to $n$ root-nodes is fixed and the PageRanks of the neighbors from
these communities are mutually independent, then according to Theorem 3 the
extremal index of the PageRanks and the Max-Linear Models of the roots is
calculated by (13). Otherwise, the extremal index of the characteristics of
the roots may not exist.

## Acknowledgments

The author was partly supported by Russian Foundation for Basic Research
(grant 19-01-00090).

## References

  * [1] Asmussen, S., Foss, S. (2018). Regular variation in a fixed-point problem for single- and multi-class banching processes and queues. Branching Processes and Applied Probability. Papers in Honour of Peter Jagers. Adv. Appl. Prob., _50A_ , 47-61.
  * [2] Avrachenkov, K., Kadavankandy, A. & Litvak, N. (2018). Mean Field Analysis of Personalized PageRank with Implications for Local Graph Clustering. J. Stat. Phys., _173_ , 895-916.
  * [3] Barabási, A. L. Network science, Cambridge University Press, 2016
  * [4] Blondel, V.D., Guillaume, J.-L., Lambiotte, R., Lefebvre, E. Fast unfolding of communities in large networks, Journal of Statistical Mechanics: Theory and Experiment, P10008, 10 (2008)
  * [5] Chen, N., Litvak, N., Olvera-Cravioto, M. (2014). PageRank in Scale-Free Random Graphs. _WAW 2014, LNCS 8882, ed. A. Bonato et al._ (pp. 120-131). Switzerland: Springer.
  * [6] Chen,N., Litvak,N., Olvera-Cravioto, M. Ranking algorithms on directed configuration networks (2014)
  * [7] Fortunato, S. Community detection in graphs, Physics Reports, 486, 3, 75 - 174 (2010)
  * [8] Jelenkovic, P. R., Olvera-Cravioto, M. (2010). Information ranking and power laws on trees. Adv. Appl. Prob., _42_(4), 1057-1093.
  * [9] Jelenkovic, P. R., Olvera-Cravioto, M. (2015). Maximums on trees. Stoch. Process. Appl., _125_ , 217-232.
  * [10] Jessen, A. H., Mikosch, T. (2006). Regularly varying functions. Publ. Inst. Math. (Beograd) (N.S.), _80_ , 171-192.
  * [11] Garavaglia, A., van der Hofstad, R. & Litvak, N. (2020). Local weak convergence for PageRank. Ann. Appl. Prob., _30_(1), 40-79 .
  * [12] Gissibl, N., Klüppelberg, C. (2018). Max-linear models on directed acyclic graphs. Bernoulli, _24_(4A), 2693-2720.
  * [13] Goldaeva, A. A. (2013). Indices of multivariate recurrent stochastic sequences. _In Shiryaev A. N. (ed.): Modern problem of mathematics and mechanics VIII(3), Moscow State University_ , 42-51. ISBN 978–5–211–05652–7 (in Russian)
  * [14] Leadbetter, M.R., Lingren, G. & Rootz$\acute{e}$n, H. (1983). _Extremes and Related Properties of Random Sequence and Processes_. ch.3, New York: Springer.
  * [15] Lebedev, A. V. (2015). Activity maxima in some models of information networks with random weights and heavy tails. Problems of Information Transmission, _51_(1), 66-74.
  * [16] Lebedev, A. V.: Extremal indices in the series scheme and their applications. Informatics Appl. 9(3), 39-54. (in Russian) (2015b)
  * [17] Lee, J., Olvera-Cravioto, M. PageRank on inhomogeneous random digraphs, Stochastic Processes and their Applications, 130, 4, 2312-2348 (2020)
  * [18] Markovich, N.M., Rodionov I.V. (2020a). Maxima and sums of non-stationary random length sequences. Extremes, _23_(3), 451-464. DOI: 10.1007/s10687-020-00372-5
  * [19] Newman, M. E. J., Girvan, M. Finding and evaluating community structure in networks, Phys. Rev. E, 69, 026113 (2004)
  * [20] Olvera-Cravioto, M.: Asymptotics for weighted random sums. Adv. Appl. Prob. 44(4), 1142-1172 (2012)
  * [21] Robert, C.Y., Segers, J. Tails of random sums of a heavy-tailed number of light-tailed terms. Insurance: Mathematics and Economics, _43_ , 85-92 (2008)
  * [22] Tillier, C., Wintenberger, O.: Regular variation of a random length sequence of random variables and application to risk assessment. Extremes. 21, 27-56 (2018)
  * [23] Volkovich, Y. V., Litvak, N. Asymptotic analysis for personalized web search. _Adv. Appl. Prob._ , _42_(2), 577-604 (2010)


#  __
Semirelativistic $1s-2s$ excitation of atomic hydrogen by electron impact

S. Taj1, B. Manaut1 and L. Oufni2
1 Université Sultan Moulay Slimane, FPBM, LIRST, BP : 523, 23000, Béni Mellal,
Morocco.
2 Université Sultan Moulay Slimane, FSTBM, LPMM, BP : 523, 23000, Béni Mellal,
Morocco<EMAIL_ADDRESS>
###### Abstract

In the framework of the first Born approximation, we present a
semirelativistic theoretical study of the inelastic excitation
($1s_{1/2}\longrightarrow 2s_{1/2}$) of hydrogen atom by electronic impact.
The incident and scattered electrons are described by a free Dirac spinor and
the hydrogen atom target is described by the Darwin wave function.
Relativistic and spin effects are examined in the relativistic regime. A
detailed study has been devoted to the nonrelativistic regime as well as the
moderate relativistic regime. Some aspects of this dependence as well as the
dynamic behavior of the DCS in the relativistic regime have been addressed.
PACS number(s): 34.80.Dp, 12.20.Ds

##  1 Introduction

The theoretical study of relativistic electron-atom collisions is fundamental
to our understanding of many aspects in plasma physics and astrophysics. The
development of electron-atom collision studies has also been strongly
motivated by the need of data for testing and developing suitable theories of
the scattering and collision process, and providing a tool for obtaining
detailed information on the structure of the target atoms and molecules. Many
authors have studied this process using numerical tools. Thus, Kisielius et
al. [1] employed, the R-matrix method with nonrelativistic and relativistic
approximations for the hydrogen like $He^{+}$, $Fe^{25+}$ and $U^{91+}$ ions,
where the case of transitions $1s\longrightarrow 2s$ and $1s\longrightarrow
2p$ as well as those between fine structure $n=2$ levels was considered.
Andersen et al. [2] have applied the semirelativistic Breit Pauli R-matrix to
calculate the electron-impact excitation of the ${}^{2}S_{1/2}$
$\longrightarrow$ ${}^{2}P^{o}_{1/2,3/2}$ resonance transitions in heavy
alkali atoms. Payne et al. [3] have studied the electron-impact excitation of
the $5s\longrightarrow 5p$ resonance transition in rubidium by using a semi-
relativistic Breit Pauli R-matrix with pseudo-states (close-coupling)
approach. Attaourti et al. [4] have investigated the exact analytical
relativistic excitation $1S_{1/2}\longrightarrow 1S_{1/2}$ of atomic hydrogen,
by electron impact in the presence of a laser field. They have found that a
simple formal analogy links the analytical expressions of the unpolarized
differential cross section without laser and the unpolarized differential
cross section in the presence of a laser field.

The aim of this contribution is to add some new physical insights and to show
that the non-relativistic formalism becomes enable to describe particles with
hight kinetic energies. Before we present the results of our investigation, we
first begin by sketching the main steps of our treatment. For pedagogical
purposes, we begin by the most basic results of our work using atomic units
(a.u) in which one has ($\hbar=m_{e}=e=1$), where $m_{e}$ is the electron mass
at rest, and which will be used throughout this work. We will also work with
the metric tensor $g^{\mu\nu}=diag(1,-1,-1,-1)$ and the Lorentz scalar product
which is defined by $(a.b)=a^{\mu}b_{\mu}$. The layout of this paper is as
follows. We present the necessary formalism of this work in section [2,3 and
4], the result and discussion in section 5 and we end by a brief conclusion in
section 6.

##  2 Theory of the inelastic collision $1s_{1/2}\longrightarrow 2s_{1/2}$

In this section, we calculate the exact analytical expression of the
semirelativistic unpolarized DCS for the relativistic excitation of atomic
hydrogen by electron impact. The transition matrix element for the direct
channel (exchange effects are neglected) is given by

$\displaystyle S_{fi}$ $\displaystyle=$ $\displaystyle-i\int
dt\langle\psi_{p_{f}}(x_{1})\phi_{f}(x_{2})\mid
V_{d}\mid\psi_{p_{i}}(x_{1})\phi_{i}(x_{2})\rangle$ (1) $\displaystyle=$
$\displaystyle-i\int_{-\infty}^{+\infty}dt\int
d\mathbf{r}_{1}\overline{\psi}_{p_{f}}(t,\mathbf{r}_{1})\gamma^{0}\psi_{p_{i}}(t,\mathbf{r}_{1})\langle\phi_{f}(x_{2})\mid
V_{d}\mid\phi_{i}(x_{2})\rangle$

where

$V_{d}=\frac{1}{r_{12}}-\frac{Z}{r_{1}}$ (2)

is the direct interaction potential, $\mathbf{r}_{1}$ are the coordinates of
the incident and scattered electron, $\mathbf{r}_{2}$ the atomic electron
coordinates, $r_{12}=$ $\mid\mathbf{r}_{1}-\mathbf{r}_{2}\mid$ and
$r_{1}=\mid\mathbf{r}_{1}\mid$. The function
$\psi_{p_{i}}(x_{1})=\psi_{p}(t,\mathbf{r}_{1})=u(p,s)\exp(-ip.x)/\sqrt{2EV}$
is the electron wave function, described by a free Dirac spinor normalized to
the volume $V$, and $\phi_{i,f}(x_{2})=\phi_{i,f}(t,\mathbf{r}_{2})$ are the
semirelativistic wave functions of the hydrogen atom where the index $i$ and
$f$ stand for the initial and final states respectively. The semirelativistic
wave function of the atomic hydrogen is the Darwin wave function for bound
states [5], which is given by :

$\phi_{i}(t,\mathbf{r}_{2})=\exp(-i\mathcal{E}_{b}(1s_{1/2})t)\varphi_{1s}^{(\pm)}(\mathbf{r}_{2})$
(3)

where $\mathcal{E}_{b}(1s_{1/2})$ is the binding energy of the ground state of
atomic hydrogen and $\varphi_{1s}^{(\pm)}(\mathbf{r}_{2})$ is given by :

$\varphi_{1s}^{(\pm)}(\mathbf{r}_{2})=(\mathsf{1}_{4}-\frac{i}{2c}\mathbf{\alpha.\nabla}_{(2)})u^{(\pm)}\varphi_{0}(\mathbf{r}_{2})$
(4)

it represents a quasi relativistic bound state wave function, accurate to
first order in $Z/c$ in the relativistic corrections (and normalized to the
same order), with $\varphi_{0}$ being the non-relativistic bound state
hydrogenic function. The spinors $u^{(\pm)}$ are such that
$u^{(+)}=(1,0,0,0)^{T}$ and $u^{(-)}=(0,1,0,0)^{T}$ and represent the basic
four-component spinors for a particle at rest with spin-up and spin-down,
respectively. The matrix differential operator $\alpha.\Delta$ is given by :

$\displaystyle\alpha.\Delta=\begin{pmatrix}0&0&\partial_{z}&\partial_{x}-i\partial_{y}\\\
0&0&\partial_{x}+i\partial_{y}&-\partial_{z}\\\
\partial_{z}&\partial_{x}-i\partial_{y}&0&0\\\
\partial_{x}+i\partial_{y}&-\partial_{z}&0&0\end{pmatrix}$ (5)

For the spin up, we have :

$\displaystyle\varphi_{1s}^{(+)}(\mathbf{r}_{2})$ $\displaystyle=$
$\displaystyle N_{D_{1}}\left(\begin{array}[]{c}1\\\ 0\\\
\frac{i}{2cr_{2}}z\\\
\frac{i}{2cr_{2}}(x+iy)\end{array}\right)\frac{1}{\sqrt{\pi}}e^{-r_{2}}$ (10)

and for the spin down, we have :

$\displaystyle\varphi_{1s}^{(-)}(\mathbf{r}_{2})$ $\displaystyle=$
$\displaystyle N_{D_{1}}\left(\begin{array}[]{c}0\\\ 1\\\
\frac{i}{2cr_{2}}(x-iy)\\\
-\frac{i}{2cr_{2}}z\end{array}\right)\frac{1}{\sqrt{\pi}}e^{-r_{2}}$ (15)

where

$N_{D_{1}}=2c/\sqrt{4c^{2}+1}$ (16)

is a normalization constant lower but very close to 1. Let us mention that the
function $\phi_{f}(t,\mathbf{r}_{2})$ in Eq. (1) is the Darwin wave function
for bound states [6], which is also accurate to the order $Z/c$ in the
relativistic corrections. This is expressed as
$\phi_{f}(t,\mathbf{r}_{2})=\exp(-i\mathcal{E}_{b}(2s_{1/2})t)\varphi_{2s}^{(\pm)}(\mathbf{r}_{2})$
with $\mathcal{E}_{b}(2s_{1/2})$ as the binding energy of the $2s_{1/2}$ state
of atomic hydrogen.

$\displaystyle\varphi_{2s}^{(+)}(\mathbf{r}_{2})$ $\displaystyle=$
$\displaystyle N_{D_{2}}\left(\begin{array}[]{c}2-r_{2}\\\ 0\\\
\frac{i(4-r_{2})}{4r_{2}c}z\\\
\frac{(4-r_{2})}{4rc}(-y+ix)\end{array}\right)\frac{1}{4\sqrt{2\pi}}e^{-r_{2}}$
(21)

for the spin up and

$\displaystyle\varphi_{2s}^{(-)}(\mathbf{r}_{2})$ $\displaystyle=$
$\displaystyle N_{D_{2}}\left(\begin{array}[]{c}0\\\ 2-r_{2}\\\
\frac{4-r_{2}}{4cr_{2}}(y+ix)\\\
i\frac{(r_{2}-4)}{4cr_{2}}z\end{array}\right)\frac{1}{4\sqrt{2\pi}}e^{-r_{2}}$
(26)

for the spin down. The transition matrix element in Eq. (1) becomes :

$\displaystyle S_{fi}$ $\displaystyle=$
$\displaystyle-i\int_{-\infty}^{+\infty}dt\int
d\mathbf{r}_{1}d\mathbf{r}_{2}\overline{\psi}_{p_{f}}(t,\mathbf{r}_{1})\gamma^{0}\psi_{p_{i}}(t,\mathbf{r}_{1})\phi^{{\dagger}}_{f}(t,r_{2})\phi_{i}(t,r_{2})V_{d}$
(27)

and it is straightforward to get, for the transition amplitude,

$\displaystyle S_{fi}$ $\displaystyle=$
$\displaystyle-i\frac{\overline{u}(p_{f},s_{f})\gamma^{0}u(p_{i},s_{i})}{2V\sqrt{E_{f}E_{i}}}2\pi
H_{inel}(\Delta)\delta\big{(}E_{f}+\mathcal{E}(2s_{1/2})-E_{i}-\mathcal{E}(1s_{1/2})\big{)}$

where $\Delta=|p_{i}-p_{f}|$ and $\gamma^{0}$ is the Dirac matrix. Using the
standard technique of the QED, we find for the unpolarized DCS

$\displaystyle\frac{d\overline{\sigma}}{d\Omega_{f}}$ $\displaystyle=$
$\displaystyle\frac{|\mathbf{p}_{f}|}{|\mathbf{p}_{i}|}\frac{1}{(4\pi
c^{2})^{2}}\left(\frac{1}{2}\sum_{s_{i}s_{f}}|\overline{u}(p_{f},s_{f})\gamma^{0}u(p_{i},s_{i})|^{2}\right)\left|H_{inel}(\Delta)\right|^{2}$
(29)

##  3 Calculation of the integral part

The function $H_{inel}(\Delta)$ is found if one performs the various integrals
:

$\displaystyle
H_{inel}(\Delta)=\int_{0}^{+\infty}d\mathbf{r}_{1}e^{i\mathbf{\Delta}\mathbf{r}_{1}}I(\mathbf{r}_{1})$
(30)

###  3.1 Integral over $\mathbf{r}_{2}$

The quantity $I(\mathbf{r}_{1})$ is easily evaluated in the following way. We
first write the explicit form of $I(\mathbf{r}_{1})$ :

$\displaystyle
I(\mathbf{r}_{1})=\int_{0}^{+\infty}d\mathbf{r}_{2}\phi^{{\dagger}}_{2s}(\mathbf{r}_{2})\left[\frac{1}{r_{12}}-\frac{Z}{r_{1}}\right]\phi_{1s}(\mathbf{r}_{2})$
(31)

Next, we develop the quantity $r^{-1}_{12}$ in spherical harmonics as

$\displaystyle\frac{1}{\mathbf{r}_{12}}=4\pi\sum_{lm}\frac{Y_{lm}(\widehat{r}_{1})Y_{lm}^{*}(\widehat{r}_{2})}{2l+1}\frac{(\mathbf{r}_{<})^{l}}{(\mathbf{r}_{>})^{l+1}}$
(32)

where $r_{>}$ is the greater of $r_{1}$ and $r_{2}$, and $r_{<}$ the lesser of
them. The angular coordinates of the vectors $\mathbf{r}_{1}$ and
$\mathbf{r}_{2}$ are such that : $\widehat{r}_{1}=(\theta_{1},\varphi_{1})$
and $\widehat{r}_{2}=(\theta_{2},\varphi_{2})$. We use the well known integral
[7]

$\displaystyle\int_{x}^{+\infty}du\;u^{m}e^{-\alpha
u}=\frac{m!}{\alpha^{m+1}}e^{-\alpha
x}\sum_{\mu=0}^{m}\frac{\alpha^{\mu}x^{\mu}}{\mu!}\qquad\qquad Re(\alpha)>0$
(33)

then, after some analytic calculations, we get for $I(\mathbf{r}_{1})$ :

$\displaystyle
I(\mathbf{r}_{1})=\frac{6}{27}(\frac{1}{c^{2}}-4)+\frac{4}{27c^{2}}\frac{1}{\mathbf{r}_{1}}-\frac{4}{9}(1+\frac{1}{8c^{2}})\mathbf{r}_{1}$
(34)

###  3.2 Integral over $\mathbf{r}_{1}$

The integration over $\mathbf{r}_{1}$ gives rise to the following formula :

$\displaystyle
H_{inel}(\Delta)=\int_{0}^{+\infty}d\mathbf{r}_{1}e^{i\mathbf{\Delta}\mathbf{r}_{1}}I(\mathbf{r}_{1})=-\frac{4\pi}{\sqrt{2}}(I_{1}+I_{2}+I_{3})$
(35)

the angular integrals are performed by expanding the plane wave
$e^{i\mathbf{\Delta}\mathbf{r}_{1}}$ in spherical harmonics as :

$\displaystyle e^{i\mathbf{\Delta}\mathbf{r}_{1}}=\sum_{lm}4\pi
i^{l}j_{l}(\mathbf{\Delta}\mathbf{r}_{1})Y_{lm}(\widehat{\mathbf{\Delta}})Y_{lm}^{*}(\widehat{\mathbf{r}}_{1})$
(36)

with $\mathbf{\Delta}=\mathbf{p}_{i}-\mathbf{p}_{f}$ is the relativistic
momentum transfer and $\widehat{\mathbf{\Delta}}$ is the angular coordinates
of the vector $\mathbf{\Delta}$. Then, after some analytic computations, we
get for $I_{1}$, $I_{2}$ and $I_{3}$ the following result :

$\displaystyle I_{1}$ $\displaystyle=$
$\displaystyle\frac{4}{27c^{2}}\int_{0}^{+\infty}dr_{1}\;r_{1}e^{-\frac{3}{2}r_{1}}j_{0}(\Delta
r_{1})=\frac{4}{27c^{2}}\frac{1}{((3/2)^{2}+\mathbf{\Delta}^{2})}$
$\displaystyle I_{2}$ $\displaystyle=$
$\displaystyle\frac{6}{27}(\frac{1}{c^{2}}-4)\int_{0}^{+\infty}dr_{1}\;r_{1}^{2}e^{-\frac{3}{2}r_{1}}j_{0}(\Delta
r_{1})=\frac{2}{27}(\frac{1}{c^{2}}-4)\frac{3}{((3/2)^{2}+\mathbf{\Delta}^{2})^{2}}$
(37) $\displaystyle I_{3}$ $\displaystyle=$
$\displaystyle-\frac{4}{9}(1+\frac{1}{8c^{2}})\int_{0}^{+\infty}dr_{1}\;r_{1}^{3}e^{-\frac{3}{2}r_{1}}j_{0}(\Delta
r_{1})=\frac{8}{9}(1+\frac{1}{8c^{2}})\frac{\mathbf{\Delta}^{2}-27/4}{((3/2)^{2}+\mathbf{\Delta}^{2})^{3}}$

It is clear that the situation is different than in elastic collision [4],
since we have no singularity in the case ($\mathbf{\Delta}\to 0$)

Figure 1: Behavior of the probability density for radial Darwin wave function
compared with that of the Dirac wave function for small distances and for
increasing values of the atomic charge number.

##  4 Calculation of the spinorial part

The calculation is now reduced to the computation of traces of $\gamma$
matrices. This is routinely done using Reduce [8]. We consider the unpolarized
DCS. Therefore, the various polarization states have the same probability and
the actual calculated spinorial part is given by summing over the final
polarization $s_{f}$ and averaging aver the initial polariztion $s_{i}$.
Therfore, the spinorial part is given by :

$\displaystyle\frac{1}{2}\sum_{s_{i}s_{f}}|\overline{u}(p_{f},s_{f})\gamma^{0}u(p_{i},s_{i})|^{2}$
$\displaystyle=$
$\displaystyle\text{Tr}\left\\{\gamma^{0}(p\\!\\!\\!/_{i}c+c^{2})\gamma^{0}(p\\!\\!\\!/_{f}c+c^{2})\right\\}$
(38) $\displaystyle=$ $\displaystyle
2c^{2}[\frac{2E_{f}E_{i}}{c^{2}}-(p_{i}.p_{f})+c^{2}]$

We must, of course, recover the result in the nonrelativistic limit
($\gamma\longrightarrow 1$), situation of which the differential cross section
can simply given by :

$\displaystyle\frac{d\overline{\sigma}}{d\Omega_{f}}=\frac{|\mathbf{K}_{f}|}{|\mathbf{K}_{i}|}\frac{128}{\left(|\mathbf{\Delta_{nr}}|^{2}+\frac{9}{4}\right)^{6}}$
(39)

with $|\mathbf{\Delta_{nr}}|=|\mathbf{K}_{i}-\mathbf{K}_{f}|$ is the
nonrelativistic momentum transfer and the momentum vectors ($\mathbf{K}_{i}$,
$\mathbf{K}_{f}$) are related by the following formula :

$\displaystyle\mathbf{K}_{f}=(|\mathbf{K}_{i}|^{2}-3/4)^{1/2}$ (40)

Figure 2:  The long-dashed line represents the semi-relativistic DCS, the
solid line represents the corresponding non-relativistic DCS for a
relativistic parameter ($\gamma=1.5$) as functions of the scattering angle
$\theta$.

Figure 3:  The solid line represents the semi-relativistic DCS, the long-
dashed line represents the corresponding non-relativistic DCS for various
values of the relativistic parameter ($\gamma=1.5$, $\gamma=2$ and
$\gamma=2.5$) as functions of the scattering angle $\theta$.

##  5 Results and discussions

In presenting our results it is convenient to consider separately those
corresponding to non-relativistic regime (the relativistic parameter
$\gamma\simeq 1$) and those related to relativistic one (the relativistic
parameter $\gamma\simeq 2$). Before beginning the discussion of the obtained
results, it is worthwhile to recall the meaning of some abbreviation that will
appear throughout this section. The NRDCS stands for the nonrelativistic
differential cross section, where nonrelativistic plane wave are used to
describe the incident and scattered electrons. The SRDCS stands for the
semirelativistic differential cross section.
We begin our numerical work, by the study of the dependence of the probability
density for radial Darwin and Dirac wave functions, on the atomic charge
number $Z$.

Figure 4:  The solid line represents the semi-relativistic DCS, the long-
dashed line represents the corresponding non-relativistic DCS for a
relativistic parameter $\gamma=1.00053$ as functions of the scattering angle
$\theta$.

Figure 5:  The variation of the SRDCSs with respect to $\theta$, for various
kinetic energies.

As long as the condition $Z\alpha\ll 1$ is verified, the use of Darwin wave
function do not have any influence at all on the results at least in the first
order of perturbation theory. So, the semi-relativistic treatment when $Z$
increases may generate large errors but not in the case of this work. In this
paper, we can not have numerical instabilities since there are none. For the
sake of illustration, we give below the behavior of the probability density
for radial Darwin wave functions as well as that of the exact relativistic
Dirac wave functions for different values of $Z$. As you may see, even if it
is not noticeable on the figure 1, there are growing discrepancies for $Z=10$
and these become more pronounced when $Z=20$. The QED formulation shows that
there are relativistic and spin effects at the relativistic domain and the non
relativistic formulation is no longer valid.

Figure 6:  The variation of the differential $1s-2s$ cross section of
$e^{-}-H$ scattering at $200\;eV$. The dots are the observed values of J. F.
Wiliams (1981) ; the solid line represents the semi-relativistic approximation
and the long-dashed line corresponds to the non-relativistic DCS.

In the relativistic regime, the semirelativistic differential cross section
results obtained for the $1s\longrightarrow 2s$ transition in atomic hydrogen
by electron impact, are displayed in figures 2 and 3. In this regime, there
are no theoretical models and experimental data for comparison as in
nonrelativistic regime. In such a situation, it appears from figures 3 and 3
that in the limit of high electron kinetic energy, the effects of the
additional spin terms and the relativity begin to be noticeable and that the
non-relativistic formalism is no longer applicable. Also a pick in the
vicinity of $\theta_{f}=0^{\circ}$ is clearly observed.
The investigation in the nonrelativistic regime were conducted with $\gamma$
as a relativistic parameter and $\theta$ as a scattering angle. In atomic
units, the kinetic energy is related to $\gamma$ by the following relation :
$E_{k}=c^{2}(\gamma-1)$. Figure 4 shows the dependence of DCS, obtained in two
models (SRDCS, NRDCS), on scattering angle $\theta$. In this regime, it
appears clearly that there is no difference between these models. Figure 5
shows the variation of the SRDCS with $\theta$ for various energies. It also
shows approximatively in the interval [-5, 5], the SRDCS increases with
$\gamma$, but decreases elsewhere. Figure 6 presents the observed and
calculated angular dependence of $1s-2s$ differential cross section of
$e^{-}-H$ scattering at incident energie $200\;eV$. Results obtained in two
approaches semirelativistic and non-relativistic approximations are
indistinguishable and in good agreement with the experimental data provided by
J. F. Williams [9].

##  6 Conclusion

In this paper we have presented the results of a semirelativistic excitation
of atomic hydrogen by electronic impact. We have used the simple
semirelativistic Darwin wave function that allows to obtain analytical results
in an exact and closed form within the framework of the first Born
approximation. This model gives good results if the condition $Z/c\ll 1$ is
fulfilled. We have compared our results with previous nonrelativistic results
and have found that the agreement between the different theoretical approaches
is good in the nonrelativistic regime. We have also showed that the non-
relativistic treatment is no longer reliable for energies higher. We hope that
we will be able to compare our theoretical results with forthcoming
experimental data in the relativistic regime.

ACKNOWLEDGMENT

I would like to thank Professor N. BOURIMA for his help in maintaining the
text linguistically acceptable.

## References

  * [1] R. Kisielius, K.A. Berrington and P.H. Norrington J. Phys. B, 28, 2459-2471, (1995).
  * [2] N. Andersen and K. Bartschat, J. Phys. B, 35 4507-4525 (2002).
  * [3] Daniel Payne, Benjamin Krueger and Klaus Bartschat J. Phys. B, 38 3349-3357 (2005) .
  * [4] Y. Attaourti, B. Manaut and A. Makhoute, Phys. Rev. A 69, 063407 (2004).
  * [5] J. Eichler and W.E. Meyerhof, Relativistic Atomic Collisions, Academic Press, (1995).
  * [6] F.W. Jr Byron and C.J. Joachain, Phys. Rep. 179, 211, (1989).
  * [7] Gradstein, L S., Rizik, I.M. : Tables of Integrals, Sutures, Sets and Their Products. Moscow: Nauka. (1971).
  * [8] A. G. Grozin, Using REDUCE in High Energy Physics (Cambridge University, Cambridge, England, 1997).
  * [9] J. F. Williams, J. Phys. B 14, 1197 (1981).


Jean is two years older than Mark. Two years ago, Mark was 5 years older than
half Jan’s age. Today, Jan is 30. How old is Jean?

  38. 38.

Vince can staple 30 reports every 15 minutes. He was stapling reports from
8:00 AM until 11:00 PM. How many reports did he staple altogether?

  39. 39.

A toy was $40 in November. The price increased by 80% in December. The price
decreased by 50% in January. What was the price of the toy after it was
discounted in January?

  40. 40.

Amir eats 5 cookies. Cody eats three times as many cookies as Amir eats. How
many cookies do both of them eat together?

  41. 41.

For an online task she does, Susan earns $5 every 10 minutes. She works
between 8 a.m. and 11 a.m., pausing in between for half an hour. How much
money does she earn for the online task?

  42. 42.

Carrie was given 140 quarters and ten twenties by her aunt to use for lunch.
If she spent 3/5 of the twenties and all the quarters, calculate the total
amount of money she paid for the lunch.

  43. 43.

A football team played 22 games, winning 8 more games than they lost. How many
games did they win?

  44. 44.

The combined age of Peter, Paul and John is 100 years old. Paul is 10 years
older than John. Peter’s age is equal to the sum of Paul and John’s age. How
old is Peter?

  45. 45.

Mia and Emma are currently 16 years apart in age. Mia is 40 years old and
younger than Emma. What is the average of their ages?

  46. 46.

Jan has three times as many pets as Marcia. Marcia has two more pets than
Cindy, who has four pets. How many total pets do the three have?

  47. 47.

There is one set of twins and one set of triplets. One triplet is 7 years
younger than one twin. The combined ages of the set of twins and the set of
triplets is 44. How old is one of the twins?

  48. 48.

Four friends ordered four pizzas for a total cost of 64 dollars. Two of the
pizzas cost 30 dollars. The other two pizzas cost the same amount. How much
did each of the other two pizzas cost?

  49. 49.

Jerry is twice as old as he was 5 years ago. In three years, how old will
Jerry be?

  50. 50.

A bag has a 5% discount. The marked price is $140. How much will you pay after
the discount?

###  A.9 Selected Questions For Experiment 3 Repetition Trials

In this section we provide the 5 questions each from the CSQA, SST, GSM8K and
CoinFlip datasets that we used for repetition trials in Experiment 3.

####  A.9.1 SST (Original)

  1. 1.

Classify the following sentence as either positive or negative: “together the
movies establish Mr. Cantet as France’s foremost cinematic poet of the
workplace.”

  2. 2.

Classify the following sentence as either positive or negative: “this is a
movie full of grace and, ultimately, hope.”

  3. 3.

Classify the following sentence as either positive or negative: “his routine
is offensive, puerile and unimaginatively foul-mouthed if it was at least
funny.”

  4. 4.

Classify the following sentence as either positive or negative: “inhabit that
special annex of hell where adults behave like kids.”

  5. 5.

Classify the following sentence as either positive or negative: “plenty of
warmth to go around, with music and laughter and the love of family.”

####  A.9.2 CoinFlip (Original)

  1. 1.

A coin is heads up. Matthew does not flip the coin. Lynn does not flip the
coin. Is the coin still heads up?

  2. 2.

A coin is heads up. Sara does not flip the coin. Tony flips the coin. Is the
coin still heads up?

  3. 3.

A coin is tails up. Andrea flips the coin. Matt flips the coin. Is the coin
still tails up?

  4. 4.

A coin is heads up. Rupert flips the coin. Yoel does not flip the coin. Is the
coin still heads up?

  5. 5.

A coin is tails up. Thomas does not flip the coin. Fanny does not flip the
coin. Is the coin still tails up?

####  A.9.3 CSQA (Original)

  1. 1.

Stanley had a dream that was very vivid and scary. He had trouble telling it
from what?

    1. A. reality, B. imagination C. dreamworker, D. nightmare, E. awake.

  2. 2.

At the end of your meal what will a waiter do?

    1. A. serve food, B. eat, C. set table, D. serve meal, E. present bill.

  3. 3.

Where would there be many people sitting in chair and listening to religious
speech?

    1. A. auditorium, B. office, C. synagogue, D. confession, E. church.

  4. 4.

The person was looking up airline and hotel prices, what was he looking to do?

    1. A. control computer, B. separate things, C. go on vacation, D. cross street, E. go out.

  5. 5.

You’d add pepper and salt to what liquid meal if it’s bland?

    1. A. supermarket, B. water, C. cellars, D. soup, E. grocery store.

####  A.9.4 GSM8K (Original)

  1. 1.

In 10 years, Melanie will be 18 years old. In how many years will her age be
thrice her present age?

  2. 2.

James has 30 teeth. His dentist drills 4 of them and caps 7 more teeth than he
drills. What percentage of James’ teeth does the dentist fix?

  3. 3.

Tim grows 5 trees. Each year he collects 6 lemons from each tree. How many
lemons does he get in a decade?

  4. 4.

John fills a 6 foot by 4 foot pool that is 5 feet deep. It cost $.1 per cubic
foot to fill. How much does it cost to fill?

  5. 5.

Cody eats three times as many cookies as Amir eats. If Amir eats 5 cookies,
how many cookies do both of them eat together?

###  A.10 Hand-Annotated Relevant Tokens

####  A.10.1 Experiments 1 and 2

In this section, we provide lists of the tokens we hand-encoded as most
“relevant” to the final model output for the 50 questions each from the SST
(Original), CoinFlip (Original and Reworded), CSQA (Original), and GSM8K
(Original and Reworded) datasets that we used in Experiments 1 and 2.

Table 12: Hand-annotated relevant tokens for the 50 SST (Original) questions for Experiment 1. Question # | Relevant Tokens
---|---
1 | comedy, hussein, strike
2 | fest, scant, sc, ant, self
3 | fest, too, much
4 | every, body, everybody, manufactured, artificial
5 | much, rather, poking, genitals
6 | wonder, diverse, marvelously, marvel, twisted
7 | allows, benefit, full, vividly, beauty, power
8 | establish, foremost, cinematic, poet
9 | really, strong, good
10 | disturbed, beguiling, beg, iling, se, ren, ity, poise, po, ise, accessible
11 | never, coughed, fidgeted, romped, breaks
12 | tense, distressing, dist, ressing, suspense
13 | empty, fetish, violence, murder, casual, fun
14 | full, grace, hope
15 | pleasant, engaging, trying, best, falling, short, whole
16 | solid, ang, ished, eclips, everything, else, ever
17 | unique, carved
18 | game, ly, tries, huge, gap, creepy, clean, fi, endish
19 | tribute, passion, shines
20 | right, prom, adrenaline
21 | anomaly, well, challenging, actually, interesting
22 | jolly, fun, essence
23 | compelling, warm, vivid, moving
24 | attempts, grand, pret, entious, gr, isly
25 | dogged, winning, darling
26 | gritty, crisp, radiant, compassion, draws, effort, effortlessly
27 | bland, dentist, waiting
28 | what, relevant, first, place
29 | non, stop, art, ifice, tires, ome, tire, tiresome, fac, failing, surface, thin
30 | strong, themes, powerful, moving, base
31 | imagine, so, bad
32 | offensive, uer, ile, unimagin, atively, foul, least, funny
33 | powerful, young
34 | lacks, charm, novel
35 | str, addle, classic
36 | meaningless, vap, id, devoid, definitely
37 | offers, more, accurate, ever
38 | unab, ashed, spring, lives
39 | convinced, decent, doesn, magic
40 | all, pleasure, handsome, well, made
41 | hate, lacks, skill, regain, any
42 | suffers, awkward, mess
43 | hell, kids, special
44 | pleasantly, haunting, debut
45 | been, done, thousand, better, but
46 | deft, serious, dark, funny, humor
47 | plenty, warmth, music, laughter, love, family
48 | considerable, ransom, not
49 | merely, pret, entious
50 | more, enjoyable, over
Table 13: Hand-annotated relevant tokens for the 50 CoinFlip (Original) questions for Experiments 1 and 2. Question # | Relevant Tokens
---|---
1-50 | tails, heads, up, does, not, flip, flips
Table 14: Hand-annotated relevant tokens for the 50 CoinFlip (Reworded) questions for Experiment 2. Question # | Relevant Tokens
---|---
1-50 | tails, heads, up, does, did, not, flip, flips, flipping
Table 15: Hand-annotated relevant tokens for the 50 CSQA (Original) questions for Experiment 1. Question # | Relevant Tokens
---|---
1 | what, children, do, bored
2 | behind, what, small, door, canned, goods, in
3 | laid, hospital, remembering, good, massage, vacation, what
4 | maximize, customers, where, build, department, store
5 | Where, good, place, get, ball
6 | What, common, chemical, reaction, used, heat, source
7 | Where, put, dollar, hard, get, out, breaking
8 | restaurant, glass, milk, how, find, out, serve
9 | What, contain, no, more, 100, people
10 | army, see, world, fighting, saw, what, things
11 | where, children, play, game
12 | What, happen, driving, car, not, involve, pain
13 | what, place, find, air, breathed, few, people, recently
14 | what, happens, company, when, bankrupt
15 | Blood, isn, t, spilled, what, sport, doesn, t, use, hands
16 | dog, ran, front, window, bark, ed, presence, what
17 | Where, find, sign, people, lined, up, next
18 | felt, pay, bills, reason, actively, what
19 | made, first, violin, position, what
20 | Where, someone, keep, digital, file
21 | What, appliance, uses, water, soap
22 | buy, honey, ap, iary, where, go
23 | Where, someone, bring, att, ache, case
24 | examine, things, why, books, chapters
25 | family, playing, cards, joy, what
26 | beer, alcoholic, probation, Where, go
27 | What, country, capital, Amsterdam, has, Fort, is, bank
28 | What, building, has, glue, bottles
29 | king, meet, ambassador, where
30 | Where, kids, play, ball, concrete
31 | D, iving, cliff, cartoon, character, ends, comedic, what
32 | Jimmy, didn, t, like, going, party, guys, nothing, but, what
33 | Where, person, need, get, more, kids
34 | Where, special, f, icus, found
35 | apply, job, wants, knows, good, fit, experience, doesn, t, qualifications, asking, worried, what
36 | What, sign, not, be, living, soon
37 | Riding, bike, through, rough, terrain, dangerous, what
38 | What, dpcument, be, not, ob, t, use
39 | convenience, customers, things, doorstep, use, what
40 | What, great, non, -, specific, benefit, exercise
41 | Where, spoon, go, side, plate
42 | Where, note, indicate, melody
43 | what, years, playing, tennis, lead
44 | Where, going, using, parking, lot, near, roller, coaster
45 | What, virus, primarily, do, person
46 | Where, go, didn, t, feel, baking, cake
47 | Where, floors, clean, holy, purposes
48 | Where, bullet, projectile, found, war
49 | What, place, not, have, queen
50 | What, need, be, learn, hard, concepts
Table 16: Hand-annotated relevant tokens for the 50 GSM8K (Original) questions for Experiments 1 and 2. Question # | Relevant Tokens
---|---
1 | 10, 88, 000, combined
2 | 180, 304, two, one
3 | 5, 2, twice, 3, left
4 | 14, 8, 9, 5, hour, stopped
5 | 5, 2, 3, twice, wider
6 | 8, 12, 2, 3, total
7 | 400, 20, cost
8 | 200, 00, 2007, 21, 2010, %
9 | 10, 18, thr, ice
10 | 300, 20, 10, total
11 | 5, 8, 100, start
12 | 13, 82, 9
13 | 4, 20, 2, 10
14 | 20, %, 50, 30
15 | 600, 300, 30, %
16 | 60, 30, 10, more
17 | 200, 100, twice, more, together
18 | 40, 75, 5, 3, 1
19 | 100, 3, 4, day, two, weeks
20 | two, dozen, 36, 30
21 | 2, 1, three, 10
22 | 10, 2, 50, 30, %, left
23 | 30, 4, 7, more, percentage
24 | sum, 20, 10
25 | 3, 5, 7, total, more
26 | ten, 4, 40, more, fewer
27 | 3, 400, 50, total
28 | 3, 4, 43, 23
29 | 5, 6, decade, year
30 | 60, 5, 30, 8, farther
31 | 8, 3, 7, equally
32 | 1000, quarter, third
33 | 10, 2, 15, 4, pairs, total
34 | 0, 25, 16, 0, 2, 36
35 | 60, twice, together
36 | 6, 4, 5, 1
37 | two, 5, half, 30, older
38 | 30, 15, 8, 00, 11
39 | 40, 80, 50, increased, decreased, %
40 | 5, three, times, both, together
41 | 5, 10, 8, 11, half
42 | 140, ten, 3, 5, quarters, twenties
43 | 22, 8, lost, winning, win
44 | combined, 100, 10, equal
45 | 16, 40, average, younger
46 | three, two, four, times
47 | one, twins, triplets, 7, younger, twin, triplet, 44
48 | four, two, 64, 30, same
49 | twice, 5, old, three, years
50 | 5, %, 140, discount, price
Table 17: Hand-annotated relevant tokens for the 50 GSM8K (Reworded) questions for Experiment 2. Question # | Relevant Tokens
---|---
1 | 10, 88, 000, combined
2 | 180, 304, two, one
3 | 5, 2, twice, 3, left
4 | 14, 8, 9, 5, hour, stopped
5 | 5, 2, 3, twice, wider
6 | 8, 12, 2, 3, total
7 | 400, 20, cost
8 | 200, 00, 2007, 21, 2010, %
9 | 10, 18, thr, ice
10 | 300, 20, 10, total
11 | 5, 8, 100, start
12 | 13, 82, 9
13 | 4, 20, 2, 10
14 | 20, %, 50, 30
15 | 600, 300, 30, %
16 | 60, 30, 10, more
17 | 200, 100, twice, more, together
18 | 40, 75, 5, 3, 1
19 | 100, 3, 4, day, two, weeks
20 | two, dozen, 36, 30
21 | 2, 1, three, 10
22 | 10, 2, 50, 30, %, left
23 | 30, 4, 7, more, percentage
24 | sum, 20, 10
25 | 3, 5, 7, total, more
26 | ten, 4, 40, more, fewer
27 | 3, 400, 50, total
28 | 3, 4, 43, 23
29 | 5, 6, decade, year
30 | 60, 5, 30, 8, farther
31 | 8, 3, 7, equally
32 | 1000, quarter, third
33 | 10, 2, 15, 4, pairs, total
34 | 0, 25, 16, 0, 2, 36
35 | 60, twice, together
36 | 6, 4, 5, 1
37 | two, 5, half, 30, older
38 | 30, 15, 8, 00, 11
39 | 40, 80, 50, increased, decreased, %
40 | 5, three, times, both, together
41 | 5, 10, 8, 11, half
42 | 140, ten, 3, 5, quarters, twenties
43 | 22, 8, lost, winning, win
44 | combined, 100, 10, equal
45 | 16, 40, average, younger
46 | three, two, four, times
47 | one, twins, triplets, 7, younger, twin, triplet, 44
48 | four, two, 64, 30, same
49 | twice, 5, old, three, years
50 | 5, %, 140, discount, price

####  A.10.2 Experiment 3

In this section we provide lists of the tokens we hand-encoded as most
“relevant” to the final model output for the 5 questions from the SST
(Original), CoinFlip (Original), CSQA (Original) and GSM8K (Original) datasets
used in Experiment 3.

Table 18: Hand-annotated relevant tokens for the five selected SST (Original) questions for Experiment 3. Question # | Relevant Tokens
---|---
1 | cinematic, establish, forecast, poet
2 | full, ultimately, hope, grace
3 | unimagin, foul, least, offensive
4 | hell, kids, behave, adults
5 | laughter, family, love, warmth
Table 19: Hand-annotated relevant tokens for the five selected CoinFlip (Original) questions for Experiment 3. Question # | Relevant Tokens
---|---
1-5 | does, not, heads, flip, up, tails, flips
Table 20: Hand-annotated relevant tokens for the five selected CSQA (Original) questions for Experiment 3. Question # | Relevant Tokens
---|---
1 | trouble, scary, vivid, dream
2 | meal, end, do, waiter
3 | sitting, speech, people, religious
4 | prices, hotel, looking, airline
5 | liquid, salt, add, pepper
Table 21: Hand-annotated relevant tokens for the five selected GSM8K (Original) questions for Experiment 3. Question # | Relevant Tokens
---|---
1 | 18, old, 10, present, age, years
2 | caps, 7, 30, more, drills, 4
3 | decade, 5, 6, trees, le, mons
4 | cost, 5, 6, 1, 4, foot
5 | times, both, cookies, 5, together, three


11institutetext: Indian Institute of Information Technology, Allahabad, Uttar
Pradesh 211015, India 11email<EMAIL_ADDRESS>{pse2017002,
rsi2017502<EMAIL_ADDRESS>
# Hate speech detection using static BERT embeddings ††thanks: all authors
contributed equally.

Gaurav Rajput  Narinder Singh punn  Sanjay Kumar Sonbhadra  Sonali Agarwal

###### Abstract

With increasing popularity of social media platforms hate speech is emerging
as a major concern, where it expresses abusive speech that targets specific
group characteristics, such as gender, religion or ethnicity to spread
violence. Earlier people use to verbally deliver hate speeches but now with
the expansion of technology, some people are deliberately using social media
platforms to spread hate by posting, sharing, commenting, etc. Whether it is
Christchurch mosque shootings or hate crimes against Asians in west, it has
been observed that the convicts are very much influenced from hate text
present online. Even though AI systems are in place to flag such text but one
of the key challenges is to reduce the false positive rate (marking non hate
as hate), so that these systems can detect hate speech without undermining the
freedom of expression. In this paper, we use ETHOS hate speech detection
dataset and analyze the performance of hate speech detection classifier by
replacing or integrating the word embeddings (fastText (FT), GloVe (GV) or FT
+ GV) with static BERT embeddings (BE). With the extensive experimental trails
it is observed that the neural network performed better with static BE
compared to using FT, GV or FT + GV as word embeddings. In comparison to fine-
tuned BERT, one metric that significantly improved is specificity.

###### Keywords:

Hate speech detection BERT embeddings Word embeddings BERT.

##  1 Introduction

With growing access to internet and many people joining the social media
platforms, people tend to post online as per their desire and tag it as
freedom of speech. It is one of the major problems on social media that tend
to degrade the overall user’s experience. Facebook defines hate speech as a
direct attack against people on the basis of protected characteristics: race,
ethnicity, national origin, disability, religious affiliation, caste, sexual
orientation, sex, gender identity and serious disease [3], while for Twitter
hateful conduct includes language that dehumanizes others on the basis of
religion or caste [6]. In March 2020, Twitter expanded the rule to include
languages that dehumanizes on the basis of age, disability, or disease.
Furthermore, the hateful conduct policy was expanded to also include race,
ethnicity, or national origin [6]. Following this context, hate speech can be
defined as an abusive speech that targets specific group characteristics, such
as gender, religion, or ethnicity.

Considering the massive amount of text what people post on social media, it is
impossible to manually flag them as hate speech and remove them. Hence, it is
required to have automated ways using artificial intelligence (AI) to flag and
remove such content in real-time. While such automated AI systems are in place
on social media platform, but one of the key challenges is the separation of
hate speech from other instances of offensive language and other being higher
false positive (marking non-hate as hate) rates of such system. Higher false
positive rate means system will tag more non-hate content as hate content
which can undermine the right to speak freely.

Hate speech can be detected using state-of-the-art machine learning
classifiers such as logistic regression, SVM, decision trees, random forests,
etc. However, deep neural networks (DNNs) such as convolutional neural
networks (CNNs), long short-term memory networks (LSTMs) [15], bidirectional
long short-term memory networks (BiLSTMs) [26], etc. have outperformed the
former mentioned classifiers for hate speech detection [19]. Former
classifiers do not require any word embedding [7] to work with while the
latter ones i.e DNNs requires word embeddings such as GloVe (GV) [20],
fastText (FT) [16], Word2Vec [18], etc. Following this context, the present
research work focuses on the scope of improvement of the existing state-of-
the-art deep learning based classifiers by using static BERT [13] embeddings
(BE) with CNNs, BiLSTMs, LSTMs and gated recurrent unit (GRU) [11].

###  1.1 BERT

Bidirectional encoder representations from transformers (BERT) was developed
by Devlin et al. [13] in 2018. BERT is a transformer-based ML technique pre-
trained from unlabeled data that is taken from Wikipedia (language: English)
and BookCorpus. Transformer [28] model has two main parts: encoder and
decoder. BERT is created by stacking the encoders. Two major strategies that
BERT uses for training are masked language modelling (MLM) and next sentence
prediction (NSP). The MLM strategy and fine-tuning of BERT is pictorially
depicted in Fig 1. In MLM technique 15% of the words in a sentence are
selected randomly and masked. Based on the context of the other words (which
are not masked) the model tries to predict the masked word.

In NSP technique model is given pairs of sentences as input. The model learns
to predict if the second sentence in a selected pair is the subsequent
sentence in original document. During the training phase half of the inputs
are a pair in which second sentence is subsequent sentence to the first in the
original document while the rest half of the input pairs has a randomly
selected sentence as second sentence.

Figure 1: Pre-training and fine-tuning of BERT.

###  1.2 Attention in neural networks

While processing a sentence in natural language for any NLP task, all words
are not of equal importance, hence it is necessary to put more attention to
the important words of the sentence. The importance of words depends on the
context and is learned through training data. Bahdanau et al. [9] proposed the
attention mechanism for improving machine translation that uses seq-to-seq
model. It is done by aligning the decoder with the relevant input sentences
and implementing attention. Steps for applying attention mechanism are as
follows:

  1. 1

Produce the encoder hidden states.

  2. 2

Calculate alignment scores.

  3. 3

Soft-max the alignment scores.

  4. 4

Calculate the context vector.

  5. 5

Decode the output.

  6. 6

At each time step, based on the current state of decoder and input received by
decoder, an element of decoder’s output sequence is generated by decoder.
Besides that decoder also updates its own state for next time step. Steps 2-5
repeats itself for each time step of the decoder until the output length
exceeds a specified maximum length or end of sentence token is produced.

The rest of the paper is organised as follows: literature review in Section 2
which focuses on the related work and recent developments in this field,
Section 3 describes the proposed methodology. Section 4 covers the exhaustive
experimental trials followed by improved results in section 5, and lastly in
Section 6 the concluding remarks are presented.

##  2 Related work

The advancements in deep learning technology have widen spectrum of its
application tasks involving classification, segmentation, object detection,
etc., across various domains such as healthcare, image processing, natural
language processing, etc. [23, 21, 10, 22, 30]. With hate speech detection
being one of the major problems in the evergrowing social media platforms, it
has drawn keen interest of the research community to develop AI assisted
applications. Following this, Badjatiya et al. [8] proposed a deep learning
approach to perform hate speech detection in tweets. The approach was
validated on the dataset [29] that consists of 16,000 tweets, of which 1972
are marked as racist, 3383 as sexist and the remaining ones as neither. The
authors utilized convolutional neural networks, long short-term memory
networks and FastText. The word embeddings are initialized with either random
embeddings or GV [20] embeddings. The authors achieved promising results with
“LSTM + Random Embedding + GBDT” model. In this model, the tweet embeddings
were initialized to random vectors, LSTM was trained using back-propagation,
and then learned embeddings were used to train a GBDT classifier.

Rizos et al. [25] experimented by using short-text data augmentation technique
in deep learning for hate speech classification. For short-text data
augmentation they used substitution based augmentation (ThreshAug), word
position augmentation (PosAug) and neural generative augmentation (GenAug).
For performing experiments they used the dataset [12] which consists of around
24k samples, of which 5.77% samples are marked as hate, 77.43% samples are
marked as offensive and 16.80% samples as neither. The authors experimented
with multiple DNNs such as CNN, LSTM and GRU. In addition, fastText, GloVe and
Word2Vec were used as word embeddings. They achieved their best results by
using GloVe + CNN + LSTM + BestAug, where BestAug is combination of PosAug and
ThreshAug. Faris et al. [14] proposed a deep learning approach to detect hate
speech in Arabic language context. They created their dataset by scraping
tweets from twitter using an application programming interface (API) [1] and
performed standard dataset cleaning methods. The obtained dataset have 3696
samples of which 843 samples are labelled as hate and 791 samples as normal
while rest of the samples were labelled as neutral. Word2Vec and AraVec [27]
were used for feature representation and embedding dimension was kept to 100.
The authors achieved promising results using combination of CNN and LSTM with
AraVec.

Ranasinghe et al. [24] in hate speech and offensive content identification in
Indo-European languages (HASOC) shared task 2019 experimented with multiple
DNNs such as pooled GRU, stacked LSTM + attention, LSTM + GRU + attention, GRU
+ capsule using fastText as word embedding on the dataset having posts written
in 3 languages: German, English and code-mixed Hindi. Furthermore, they also
experimented with fine-tuned BERT [13] which outperformed every above
mentioned DNN for all 3 languages. In another work, Mollas et al. [19]
proposed ETHOS dataset to develop AI based hate speech detection framework
that have used FT [16], GV [20] and FT + GV as word embeddings with CNNs,
BiLSTMs and LSTMs. In contrast to other datasets which are based on tweets
scraped from Twitter, this new dataset is based on YouTube and Reddit
comments. A binary version of ETHOS dataset has 433 sentences containing hate
text and 565 sentences containing non-hate text. Besides, transfer learning
was used to fine-tune BERT model on the proposed dataset that outperformed the
above mentioned deep neural networks. The results of the aforementioned
experiments are shown in Table 1, where bold values represent the highest
value of metrics among all models [19].

Table 1: Performance of BERT (fine-tuned on binary ETHOS dataset) with various neural networks using FT, GV or FT + GV as word embedding [19] Model | F1 Score | Accuracy | Precision | Recall | Specificity
---|---|---|---|---|---
CNN + Attention + FT + GV | 74.41 | 75.15 | 74.92 | 74.35 | 80.35
CNN + LSTM + GV | 72.13 | 72.94 | 73.47 | 72.4 | 76.65
LSTM + FT + GV | 72.85 | 73.43 | 73.37 | 72.97 | 76.44
BiLSTM + FT + GV | 76.85 | 77.45 | 77.99 | 77.10 | 79.66
BiLSTM + Attention + FT | 76.80 | 77.34 | 77.76 | 77.00 | 79.63
BERT | 78.83 | 76.64 | 79.17 | 78.43 | 74.31

Ever since the researchers started using BERT [13] for natural language
processing tasks, it has been observed that a fine-tuned BERT usually
outperforms other state-of-the-art deep neural networks in same natural
language processing task. The same has been observed in the results of
experiment carried out by Mollas et al [19]. Motivated from this, the
experiments carried out in this paper aims to analyse the performance of fine-
tuned BERT with other deep learning models.

##  3 Proposed methodology

Following the state-of-the-art deep learning classification models, in the
proposed approach the impact of BERT based embeddings is analyzed. The hate
speech detection framework is designed by combining DNNs (CNN, LSTM, BiLSTM
and GRU) with static BERT embeddings to better extract the contextual
information. Initially, the static BERT embedding matrix is generated from
large corpus of dataset, representing embedding for each word and later, this
matrix is processed using DNN classifiers to identify the presence of hate.
The schematic representation of the proposed model is shown in Fig 2.

###  3.1 Static BERT embedding matrix

The embedding matrix contains the word embeddings for each word in dataset.
Each row in the embedding matrix contains word embedding for a unique word and
they are passed to the DNNs (by converting natural language sentences to
vectors) that accepts input in fixed dimensions, therefore the word embeddings
have to be static. Since BERT [13] gives contexualised embedding of each word
according to the usage of the word in sentence, thereby same word will have
different embeddings depending on the usage context unlike in other static
word embeddings where each word has unique static embedding irrespective of
the context in which it is used.

Initially, the raw BERT embeddings are generated using bert-embedding library
[2] to provide contextualized word embedding. An embedding dictionary (key-
value pair) is developed where key is the unique word and value is an array
containing contextualized embeddings of that unique word. Since same word can
be used in different context in different sentences, hence it will have
different word embeddings depending on the context. Every contextualized
embedding for a word are stored in the dictionary [5] by pushing the embedding
into the vector corresponding to the unique word. Furthermore, the static BE
of a word is obtained by taking mean of the vector containing the
contexualized BERT embeddings of that word. For example, a word ‘W’occurs 4
times in the dataset, then there will be 4 contexualized embeddings of ‘W’,
let it be $E_{1},E_{2},E_{3},E_{4}$. These 4 embeddings each of dimension
(768,) are stored in the array corresponding to the key ‘W’in the dictionary.
Later, mean of $E_{1},E_{2},E_{3},E_{4}$ is computed that represents the
static BERT [13] embedding of ‘W’. For words which are not in vocabulary, BERT
[13] splits them into subwords and generate their embeddings, then take the
average of embeddings of subwords to generate the embedding of the word which
was not in vocabulary. Finally, by using keras Tokenizer [17] and static BERT
embeddings we create the embedding matrix.

Figure 2: Block diagram of proposed model.

##  4 Experiments

###  4.1 Choice of dataset

Even though there are multiple datasets that are publicly available for hate
speech detection but we chose to use binary version of ETHOS dataset [19]
because it is the most recent dataset and the two classes (hate and non-hate)
present in it are almost balanced as compared to other datasets. For example,
Davidson dataset having around 24k samples (Hate speech: 5.77%, Offensive:
77.43% and 16.80% as Neither) [12] is highly imbalanced. ETHOS dataset address
all such issues of available datasets.

The Shannon entropy can be used as a measure of balance for datasets. On a
dataset of $n$ instances, if we have $k$ classes of size $c_{i}$ we can
compute entropy as follows:

$H\;=\;-\sum_{i\;=\;1}^{k}\frac{c_{i}}{n}\log\frac{c_{i}}{n}$ (1)

It is equal to zero if there is a single class. In other words, it tends to 0
when the dataset is very unbalanced and $log(k)$ when all the classes are
balanced and of the same size $n/k$. Therefore, we use the following measure
of balance (shown in Eq. 2) for a dataset [4]:

$Balance=\frac{H}{\log\;k}=\frac{-\sum_{i=1}^{k}\frac{c_{i}}{n}\log{\frac{c_{i}}{n}}}{\log\;k}$
(2)

Binary version of ETHOS dataset has 433 samples containing hate text and 565
samples containing non-hate text. For binary version of ETHOS dataset,
$Balance=0.986$ which is nearly equal to 1, indicating balance between
classes.

###  4.2 Neural network architectures and testing environment

The proposed approach is trained and validated on the binary version of ETHOS
dataset. For the purpose of comparison, the neural network architectures are
kept exactly same as described by the Mollas et al. [19]. From the number of
units in a neural network to the arrangement of layers in a neural network
everything is kept same so as to create the same training and testing
environment but change the word embeddings to static BERT embeddings.

To establish robust results, stratified k-fold validation technique with value
of $k=10$ is utilized. Furthermore, the training phase is assisted with
callbacks such as early stopping (stop the training if performance doesn’t
improve) to avoid the overfitting problem and model-checkpointing (saving the
best model). Finally, the trained model is evaluated using standard
classification performance metrics i.e. accuracy, precision, recall
(sensitivity), F1-score and specificity.

$Accuracy=\frac{TP\;+\;TN}{TP\;+\;TN\;+\;FP\;+\;FN}$ (3)

$Precision=\frac{TP\;}{TP\;+FP}$ (4)

$Recall=\frac{TP\;}{TP\;+FN}$ (5)

$F1-score=2\;\times\frac{Precision\;\times\;Recall}{Precision\;+\;Recall}$ (6)

$Specificity=\frac{TN\;}{TN\;+FP}$ (7)

Where, TP: True Positive, TN: True Negative, FP: False Positive, FN: False
Negative

##  5 Results and discussion

Table 1 represents the results of experiment carried out by Mollas et al. [19]
on binary version of ETHOS dataset, hence the DNNs uses only FT, GV or FT + GV
as word embeddings. It is evident from the Table 1 that BERT (fine-tuned on
binary ETHOS dataset) outperformed other models in all metrics except accuracy
and specificity, its specificity stands at 74.31% which indicates high false
positive hate speech classification.

Table 2: Comparative analysis of the performance of various DNNs with and
without static BERT embeddings (BE).

Model | F1-Score | Accuracy | Precision | Recall | Specificity
---|---|---|---|---|---
CNN + Attention + FT + GV | 74.41 | 75.15 | 74.92 | 74.35 | 80.35
CNN + Attention + static BE | 77.52 | 77.96 | 77.89 | 77.69 | 79.62
CNN + LSTM + GV | 72.13 | 72.94 | 73.47 | 72.4 | 76.65
CNN + LSTM + static BE | 76.04 | 76.66 | 77.20 | 76.18 | 79.43
LSTM + FT + GV | 72.85 | 73.43 | 73.37 | 72.97 | 76.44
LSTM + static BE | 79.08 | 79.36 | 79.38 | 79.37 | 79.49
BiLSTM + FT + GV | 76.85 | 77.45 | 77.99 | 77.10 | 79.66
BiLSTM + static BE | 79.71 | 80.15 | 80.37 | 79.76 | 83.03
BiLSTM + Attention + FT | 76.80 | 77.34 | 77.76 | 77.00 | 79.63
BiLSTM + Attention+static BE | 78.52 | 79.16 | 79.67 | 78.58 | 83.00
GRU + static BE | 77.91 | 78.36 | 78.59 | 78.18 | 79.47
BERT | 78.83 | 76.64 | 79.17 | 78.43 | 74.31

Bold model names represent static BERT embedding variants of the models
Bold values represent the highest value of any metric among all models

The Table 2 presents the obtained results on various DNNs, where bold model
names represent BERT variant of a DNN model and bold quantities represent the
highest values. It is observed that a deep neural network with static BERT
embeddings outperforms the same deep neural network which is using word
embedding as fastText, GloVe or fastText + GloVe in all metrics. For DNNs like
CNN using attention, LSTM, CNN + LSTM, BiLSTM and BiLSTM using attention, the
average (avg) increase in F1-score is 3.56%, accuracy is 3.39%, precision is
3.40%, recall is 3.55% and sensitivity is 2.37%. Hence, it is evident that
static BERT embeddings tend to provide better feature representation as
compared to fastText, GloVe or fastText + GloVe.

Furthermore, BiLSTM using static BERT embeddings (BiLSTM + static BE) performs
better in all metrics as compared to other DNNs under consideration. In the
results of experiments done by Mollas et al. [19], fine-tuned BERT
outperformed other models in every metric with specificity as 74.31%, which
increases to 83.03% using static BERT embeddings (BiLSTM + static BE), thereby
attaining a significant increase of 8.72%.

##  6 Conclusion

In this article, the impact of performance in deep learning based hate speech
detection using static BERT embeddings is analysed. With exhaustive
experimental trials on various deep neural networks it is observed that using
neural networks with static BERT embeddings can significantly increase the
performance of the hate speech detection models especially in terms of
specificity, indicating that model is excellent at correctly identifying non
hate speeches. Therefore, it flags lesser non hate speech as hate speech,
thereby protecting the freedom of speech. With such promising improvements in
the results, the same concept of integrating static BERT embedddings with
state-of-the-art models can further be extended to other natural language
processing based applications.

## References

  * [1] Application programming interface, https://en.wikipedia.org/wiki/API, [Online accessed 24 June, 2021]
  * [2] bert-embedding. https://pypi.org/project/bert-embedding/, [Online accessed 10 June, 2021]
  * [3] Community standards. https://www.facebook.com/communitystandards/hate_speech, [Online accessed 10 June, 2021]
  * [4] A general measure of data-set imbalance. https://stats.stackexchange.com/questions/239973/a-general-measure-of-data-set-imbalance, [Online accessed 10 June, 2021]
  * [5] Python dictionary, https://www.programiz.com/python-programming/dictionary, [Online accessed 24 June, 2021]
  * [6] Updating our rules against hateful conduct. https://blog.twitter.com/en_us/topics/company/2019/hatefulconductupdate.html, [Online accessed 10 June, 2021]
  * [7] Word embedding, https://en.wikipedia.org/wiki/Word_embedding, [Online accessed 24 June, 2021]
  * [8] Badjatiya, P., Gupta, S., Gupta, M., Varma, V.: Deep learning for hate speech detection in tweets. In: Proceedings of the 26th international conference on World Wide Web companion. pp. 759–760 (2017)
  * [9] Bahdanau, D., Cho, K., Bengio, Y.: Neural machine translation by jointly learning to align and translate. arXiv preprint arXiv:1409.0473 (2014)
  * [10] Batra, H., Punn, N.S., Sonbhadra, S.K., Agarwal, S.: Bert based sentiment analysis: A software engineering perspective. arXiv preprint arXiv:2106.02581 (2021)
  * [11] Cho, K., Van Merriënboer, B., Gulcehre, C., Bahdanau, D., Bougares, F., Schwenk, H., Bengio, Y.: Learning phrase representations using rnn encoder-decoder for statistical machine translation. arXiv preprint arXiv:1406.1078 (2014)
  * [12] Davidson, T., Warmsley, D., Macy, M., Weber, I.: Automated hate speech detection and the problem of offensive language. In: Proceedings of the International AAAI Conference on Web and Social Media. vol. 11 (2017)
  * [13] Devlin, J., Chang, M.W., Lee, K., Toutanova, K.: Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810.04805 (2018)
  * [14] Faris, H., Aljarah, I., Habib, M., Castillo, P.A.: Hate speech detection using word embedding and deep learning in the arabic language context. In: ICPRAM. pp. 453–460 (2020)
  * [15] Hochreiter, S., Schmidhuber, J.: Long short-term memory. Neural computation 9(8), 1735–1780 (1997)
  * [16] Joulin, A., Grave, E., Bojanowski, P., Douze, M., Jégou, H., Mikolov, T.: Fasttext. zip: Compressing text classification models. arXiv preprint arXiv:1612.03651 (2016)
  * [17] Keras-Team: keras-team/keras. https://github.com/keras-team/keras, [Online accessed 10 June, 2021]
  * [18] Mikolov, T., Sutskever, I., Chen, K., Corrado, G., Dean, J.: Distributed representations of words and phrases and their compositionality. arXiv preprint arXiv:1310.4546 (2013)
  * [19] Mollas, I., Chrysopoulou, Z., Karlos, S., Tsoumakas, G.: Ethos: an online hate speech detection dataset. arXiv preprint arXiv:2006.08328 (2020)
  * [20] Pennington, J., Socher, R., Manning, C.D.: Glove: Global vectors for word representation. In: Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP). pp. 1532–1543 (2014)
  * [21] Punn, N.S., Agarwal, S.: Inception u-net architecture for semantic segmentation to identify nuclei in microscopy cell images. ACM Transactions on Multimedia Computing, Communications, and Applications (TOMM) 16(1), 1–15 (2020)
  * [22] Punn, N.S., Agarwal, S.: Multi-modality encoded fusion with 3d inception u-net and decoder model for brain tumor segmentation. Multimedia Tools and Applications pp. 1–16 (2020)
  * [23] Punn, N.S., Agarwal, S.: Automated diagnosis of covid-19 with limited posteroanterior chest x-ray images using fine-tuned deep neural networks. Applied Intelligence 51(5), 2689–2702 (2021)
  * [24] Ranasinghe, T., Zampieri, M., Hettiarachchi, H.: Brums at hasoc 2019: Deep learning models for multilingual hate speech and offensive language identification. In: FIRE (Working Notes). pp. 199–207 (2019)
  * [25] Rizos, G., Hemker, K., Schuller, B.: Augment to prevent: short-text data augmentation in deep learning for hate-speech classification. In: Proceedings of the 28th ACM International Conference on Information and Knowledge Management. pp. 991–1000 (2019)
  * [26] Schuster, M., Paliwal, K.: Bidirectional recurrent neural networks. Signal Processing, IEEE Transactions on 45, 2673 – 2681 (12 1997). https://doi.org/10.1109/78.650093
  * [27] Soliman, A.B., Eissa, K., El-Beltagy, S.R.: Aravec: A set of arabic word embedding models for use in arabic nlp. Procedia Computer Science 117, 256–265 (2017)
  * [28] Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A.N., Kaiser, L., Polosukhin, I.: Attention is all you need. arXiv preprint arXiv:1706.03762 (2017)
  * [29] Waseem, Z., Hovy, D.: Hateful symbols or hateful people? predictive features for hate speech detection on twitter. In: Proceedings of the NAACL student research workshop. pp. 88–93 (2016)
  * [30] Zhang, T., Gao, C., Ma, L., Lyu, M., Kim, M.: An empirical study of common challenges in developing deep learning applications. In: 2019 IEEE 30th International Symposium on Software Reliability Engineering (ISSRE). pp. 104–115. IEEE (2019)