# Twin Vertices in Fault-Tolerant Metric Sets and Fault-Tolerant Metric
Dimension of Multistage Interconnection Networks

S. Prabhu1 Corresponding author<EMAIL_ADDRESS>V. Manimozhi2 M.
Arulperumjothi3 Sandi Klavžar4,5,6

###### Abstract

A set of vertices $S\subseteq V(G)$ is a resolving set of a graph $G$ if for
each $x,y\in V(G)$ there is a vertex $u\in S$ such that $d(x,u)\neq d(y,u)$. A
resolving set $S$ is a fault-tolerant resolving set if $S\setminus\\{x\\}$ is
a resolving set for every $x\in S$. The fault-tolerant metric dimension (FTMD)
$\beta^{\prime}(G)$ of $G$ is the minimum cardinality of a fault-tolerant
resolving set. It is shown that each twin vertex of $G$ belongs to every
fault-tolerant resolving set of $G$. As a consequence,
$\beta^{\prime}(G)=n(G)$ iff each vertex of $G$ is a twin vertex, which
corrects a wrong characterization of graphs $G$ with $\beta^{\prime}(G)=n(G)$
from [Mathematics 7(1) (2019) 78]. This FTMD problem is reinvestigated for
Butterfly networks, Benes networks, and silicate networks. This extends
partial results from [IEEE Access 8 (2020) 145435–145445], and at the same
time, disproves related conjectures from the same paper.

1 Department of Mathematics, Rajalakshmi Engineering College (Autonomous),
Thandalam, Chennai 602105, India

2 Department of Mathematics, Panimalar Engineering College, Chennai, India
600123

3 Department of Mathematics, Saveetha Engineering College (Autonomous),
Chennai 602105, India

4 Faculty of Mathematics and Physics, University of Ljubljana, Slovenia

5 Faculty of Natural Sciences and Mathematics, University of Maribor, Slovenia

6 Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia

Keywords: metric dimension; fault-tolerant metric dimension; twin vertex;
Benes network; butterfly network, silicate network

Mathematics Subject Classification (2020): 05C12, 68M15

##  1 Introduction

Let $G=(V(G),E(G))$ be a connected graph. The number of edges of a shortest
$u,v$-path in $G$ is equal to the distance $d_{G}(u,v)$ (or simply $d(u,v)$
whenever $G$ is understood) between the vertices $u$ and $v$ of $G$. A finite
collection of vertices $S\subseteq V(G)$ is a resolving set of $G$ if for
every pair $a,b\in V(G)$ there is a $u\in S$ such that $d(a,u)\neq d(b,u)$.
The metric dimension $\beta(G)$ is the lowest cardinality of a resolving set
of $G$.

This problem was initially investigated in the 1970s [15, 39], and has been
extensively investigated afterwards. The topic was first surveyed in 2003 by
Chartrand and Zhang [8]. Very recently, a new excellent review on the metric
dimension and its applications was written by Tillquist, Frongillo, and
Lladser [41]. The survey includes $117$ references, we point here only to
applications of resolving sets to verification of networks [6], robot
navigation [23], and geometric routing protocols [27].

Chartrand and Zhang in [8] also suggested using the members of a resolving set
as sensors. Provided that, there will be a defective sensor leading to failure
to acknowledge the burgler in the network. The idea arose from the assumption
that a faulty sensor will not cause device failure because the remaining
sensors will still be able to deal with the invasion force. It was formally
introduced in [19]. A resolving set $F$ of a (connected) graph $G$ is a fault-
tolerant resolving set if $F\smallsetminus\\{u\\}$ is a resolving set of $G$
for each $u\in F$. In other words, $F\subseteq G$ is a fault-tolerant
resolving set if for every distinct $x,y\in V(G)$ there exist $u,v\in F$ such
that $d(u,x)\neq d(u,y)$ and $d(v,x)\neq d(v,y)$. The least positive integer
representing the cardinality of $F$ is $\beta^{\prime}(G)$. The fault-tolerant
metric dimension, like that of the metric dimension, has already been widely
investigated, cf. [1, 4, 21, 36, 37, 38].

In [11], Estrada-Moreno, Rodríguez-Velázquez, and Yero introduced and studied
the $k$-metric dimension, $k\geq 1$, as a common generalization of the metric
dimension (the case $k=1$) and the fault-tolerant metric dimension (the case
$k=2$). The concept was later investigated in several papers, cf. [2, 10, 12].
We also emphasize that in [5] the $k$-metric dimension was investigated on
general metric spaces, while the fractional $k$-metric dimension is the core
concept of [22]. In parallel to the survey [41], another excellent survey was
posted by Kuziak and Yero [25]. The latter survey focuses on variants of the
metric dimension, and in particular gives a thorough list on results on the
$k$-metric dimension with a special attention to the case $k=2$, that is, to
the fault-tolerant metric dimension.

In the next section, we observe that each twin vertex of $G$ is a member of a
fault-tolerant resolving set. As a consequence, we deduce that
$\beta^{\prime}(G)=n(G)$ iff each $v$ of $G$ is a twin. (Here and later,
$n(G)$ denotes the order of $G$.) This result corrects a characterization with
$\beta^{\prime}(G)=n(G)$ that was incorrect in [35]. In Section 3, we
determine the FTMD of Butterfly, Benes, and silicate networks. For each of
these networks, partial results were reported in [17]. Moreover, our results
disprove related conjectures from the same paper.

##  2 Twin vertices

The open neighborhood of a vertex $u\in V(G)$ is $N(u)=\\{v\in V(G):uv\in
E(G)\\}$, the closed neighborhood of $u$ is $N[u]=N(u)\cup\\{u\\}$. Different
vertices $u,v\in V(G)$ are twins if either $N[u]=N[v]$ or $N(u)=N(v)$. We
further say that $u$ is a twin vertex, if there exists $v\neq u$ such that $u$
and $v$ are twins. Note that if $N[u]=N[v]$, then $uv\in E(G)$, and if
$N(u)=N(v)$, then $uv\notin E(G)$. Twins are a very natural concept, hence no
wonder that they were differently named in the literature. For instance, many
authors say that $u$ and $v$ are true twins or adjacent twins when $N[u]=N[v]$
holds, and false twins or non-adjacent twins when $N(u)=N(v)$, cf. [3, 26].

The role of twins for the metric dimension has been clarified in [18]. For the
fault-tolerant metric dimension, we have the following observation.

###### Lemma 2.1

If $u$ is a twin vertex of a graph $G$, and $S$ is a fault-tolerant resolving
set of $G$, then $u\in S$. In particular, if $S$ is the set of twin vertices
of $G$, then $\beta^{\prime}(G)\geq|S|$.

Proof. Let $u$ be a twin vertex of $G$ and let $v\neq u$ be a vertex such that
$u$ and $v$ are twins. Let $S$ is a fault-tolerant resolving set of $G$. Since
$d(u,x)=d(v,x)$ for every $x\neq u,v$ (cf. [18, Lemma 2.3]), and since $S$ is
a resolving set, at least one of $u$ and $v$ belongs to $S$. If $u\in S$ there
is nothing to prove. Assume hence that $v\in S$. Since $S$ is a fault-tolerant
resolving set, the set $S\setminus\\{v\\}$ is a resolving set. If $u\notin S$,
then the twins $u$ and $v$ have the same distance to all the vertices of the
resolving set $S\setminus\\{v\\}$, a contradiction. $\square$

Lemma 2.1 will be very useful in our consideration of interconnection networks
in the next section. Before that, we point to a couple of errors from [35].

Chartrand, Eroh, Johnson, and Oellermann [7] proved that (i) $\beta(G)=n(G)-1$
iff $G$ is complete; and that (ii) if $n(G)\geq 4$, then
$\beta(G)=n(G)-2\Leftrightarrow$ $G$ belongs to one of the following graph
classes $K_{s}+\overline{K_{t}}$ $(s\geq 1,t\geq 2)$, $K_{s,t}$ $(s,t\geq 1)$,
and $K_{s}+(K_{1}\cup K_{t})$ $(s,t\geq 1)$. Parallel results to (i) and (ii)
were erroneously claimed in [35, Theorem 7] and [35, Theorem 8], respectively.
In particular, in the first of these results the authors claim that
$\beta^{\prime}(G)=n(G)\Leftrightarrow G$ is complete. The correct result
reads as follows.

###### Proposition 2.2

Let $G$ be a connected graph. Then $\beta^{\prime}(G)=n(G)$ if and only if
each vertex of $G$ is a twin vertex.

Proof. If each vertex of $G$ is a twin vertex, then $\beta^{\prime}(G)=n(G)$
by Lemma 2.1.

Conversely, suppose that $u\in V(G)$ is not a twin vertex. Then we claim that
$V(G)\setminus\\{u\\}$ is a fault-tolerant resolving set. To show it, we only
need to consider a pair of vertices $u$ and $x$, where $x$ is an arbitrary
vertex from $V(G)\setminus\\{u\\}$. Clearly, $0=d(x,x)<d(u,x)$. In addition,
since $u$ and $x$ are not twins, there exits a vertex $y$ adjacent to exactly
one of $u$ and $x$. Hence $d(u,y)\neq d(x,y)$. We conclude that if $G$
contains a vertex which is not a twin, then $\beta^{\prime}(G)<n(G)$.
$\square$

The graphs from Proposition 2.2 can be described as follows. Its vertex set
can be divided into disjoint parts of the order at least two, each part
containing vertices that are pairwise twins. Moreover, each of these parts
induces either a full graph or a null graph. Between each pair of these parts,
there are either all possible edges or none at all.

As mention in the introduction, the fault-tolerant metric dimension is just
the $2$-metric dimension, and the two results of this section were actually
already established in [11]. In particular, our Proposition 2.2 is [11,
Corollary 5]. We have nevertheless derived these results also here from the
following reasons. First, in this way we are self-sufficient. Second, the
arguments are fairly simple. And finally, [11, Corollary 5] is deduced from
[11, Proposition 4], where the latter result is stated in a slightly different
and more involved language.

##  3 Butterfly, Benes, and silicate networks

The illustration of a multistage interconnected model as graph has processors
as vertices and interconnections between processors as edges. The structural
features of interconnection networks were investigated in [24]. Here, we
determine the fault-tolerant metric dimension for two classes of such
networks—butterfly networks and Benes networks. These networks were presented
by Manuel et al. [29], and investigated from differents angles, see [29] for
their metric dimension, [20] for their degree-based topological indices, [34]
for their Wiener index, [33] for their Zagreb indices and polynomials, and
[30] for their crossing number.

For $r\geq 3$, the $r$ dimensional butterfly network $BF(r)$ is defined as
follows. Its vertices are pairs $[s,j]$, where $s$ runs over all $r$-bit
binary strings, and $j\in\\{0,1,\ldots,r\\}$. The vertices $[s,j]$ and
$[s^{\prime},j^{\prime}]$ are adjacent iff $|j-j^{\prime}|=1$, and either
$s=s^{\prime}$ or $s$ and $s^{\prime}$ differ precisely in the $j^{\rm th}$
bit. Note that the order and the size of $BF(r)$ are $2^{r}(r+1)$ and
$r2^{r+1}$, respectively. In the normal representation of $BF(r)$, the first
coordinate of the vertex is interpreted as the row of the vertex and its
second coordinate is a column called level of the vertex. See Fig. 1 where
$BF(3)$ is drawn.

Figure 1: Normal representation of $BF(3)$

In [17, Corollary 5.3] it was proved that $\beta^{\prime}(BF(r))\leq 4\cdot
2^{r}$ and conjectured [17, Conjecture 5.4] that the equality holds here, that
is, $\beta^{\prime}(BF(r))=4\cdot 2^{r}$. In our next result we determine
$\beta^{\prime}(BF(r))$ which disproves the conjecture.

###### Theorem 3.1

If $r\geq 3$, then $\beta^{\prime}(BF(r))=2^{r+1}$.

Proof. From the definition of $BF(r)$ we infer that the vertices $[i-1,0]$ and
$[i-1+2^{r-1},0]$ are twins for each $i\in[2^{r-1}]$. (We use the convention
$[n]=\\{1,\ldots,n\\}$.) Moreover, for each $i\in[2^{r-1}]$, the vertices
$[2i-2,r]$ and $[2i-1,r]$ are also twins. That is, each vertex from the first
and the last level of $BF(r)$ is a twin vertex. Hence $BF(r)$ contains (at
least) $2^{r+1}$ twin vertices, therefore $\beta^{\prime}(BF(r))\geq 2^{r+1}$
by Lemma 2.1.

To prove that $\beta^{\prime}(BF(r))\leq 2^{r+1}$, we are going to show that
the set $X$ consisting of the vertices from the first and the last level of
$BF(r)$ forms a fault-tolerant resolving set. For this sake, let $[s,i]$ and
$[t,j]$ be arbitrary vertices of $BF(r)$. We need to show that they are
distance distinguished by two vertices of $X$. If at least one of $[s,i]$ and
$[t,j]$ lies in $X$, then the conclusion is clear, hence we may assume in the
rest that $i,j\in[r-1]$. Suppose first that $i\neq j$ and assume w.l.g that
$i<j$. Then $d([s,i],[s,0])<d([t,j],[s,0])$ and
$d([t,j],[t,r])<d([s,i],[t,r])$. As $[s,0],[t,r]\in X$, we have required two
vertices in this case.

It remains to consider vertices $[s,i]$ and $[t,i]$, where $i\in[r-1]$ and
$s\neq t$. Let $s=s_{1}\ldots s_{r}$ and $t=t_{1}\ldots t_{r}$. The following
facts will be used in subsequent lines. If $x=x_{1}\ldots x_{r}$ and
$d([x,0],[s,i])=i$, then $x_{i+1}=s_{i+1},\ldots,x_{r}=s_{r}$. Similarly, if
$d([x,r],[s,i])=r-i$, then $x_{1}=s_{1},\ldots,x_{i}=s_{i}$. The binary labels
$s$ and $t$ are different, hence they differ in at least one coordinate.
Assume first that there exists an index $k>i$ such that $s_{k}\neq t_{k}$.
Then we infer that $d([s,0],[s,i])=i<d([s,0],[t,i])$ and that
$d([t,0],[t,i])=i<d([t,0],[s,i])$. Hence the vertices $[s,0],[t,0]\in X$
distinguish $[s,i]$ and $[t,j]$. In the second case we may thus assume that
$s_{i+1}=t_{i+1},\ldots,s_{r}=t_{r}$. Let $k$ be an index such that $s_{k}\neq
t_{k}$. By the case assumption, $k\leq i$. Consider now the vertices $[s,r]$
and $[t,r]$. Suppose that $d([s,r],[s,i])=r-i=d([s,r],[t,j])$. Then, by the
above fact, $t_{1}=s_{1},\ldots,t_{i}=s_{i}$. But this means that $t=s$, a
contradiction. It follows that $d([s,r],[s,i])=r-i<d([s,r],[t,i])$. Similarly
we obtain that $d([t,r],[t,i])=r-i<d([t,r],[s,i])$. Hence in this case the
vertices $[s,r]$ and $[t,r]$ from $X$ distinguish $[s,i]$ and $[t,j]$ and we
are done. $\square$

For $r\geq 3$, the $r$-dimensional Benes network $B(r)$ is defined similarly
as $BF(r)$. The vertices are again ordered pairs $[s,i]$, where $s$ runs over
all $r$-bit binary strings, but now $i\in\\{0,1,\ldots,2r\\}$. The edges in
$B(r)$ up to level $r$ are just as in $BF(r)$, while later on, the edges are
vertically reflected. The formal definition should be clear from Fig. 2, where
$B(3)$ is shown in its normal representation.

Figure 2:  $B(3)$ drawn in its normal representation

The order and the size of $B(r)$ are $2^{r}(2r+1)$ and $r2^{r+2}$,
respectively. In [17, Corollary 4.3] it was proved that
$\beta^{\prime}(B(r))\leq 13\cdot 2^{r-1}$ and conjectured [17, Conjecture
4.4] that the equality holds here, that is, $\beta^{\prime}(B(r))=13\cdot
2^{r-1}$. In our next result we determine $\beta^{\prime}(B(r))$ which
disproves the conjecture.

###### Theorem 3.2

If $r\geq 3$, then $\beta^{\prime}(B(r))=3\cdot 2^{r}$.

Proof. Following the arguments adopted in Theorem 3.1, we observe first that
each vertex from the first, the middle, and the last level of $B(r)$ is a twin
vertex. Hence $B(r)$ contains (at least) $3\cdot 2^{r}$ twins, therefore
$\beta^{\prime}(B(r))\geq 3\cdot 2^{r}$ by Lemma 2.1.

To prove that $\beta^{\prime}(B(r))\leq 3\cdot 2^{r}$, we claim that the set
$X$ consisting of the vertices from the first, the middle, and the last level
of $B(r)$ forms a fault-tolerant resolving set. To show it we take arbitrary
vertices $[s,i]$ and $[t,j]$ of $B(r)$. If at least one of them is in $X$,
then two vertices from $X$ clearly distinguish them. Hence we may assume
$i,j\in[2r-1]$. If $i\neq j$, where $i<j$, then
$d([s,i],[s,0])<d([t,j],[s,0])$ and $d([t,j],[t,2r])<d([s,i],[t,2r])$. Hence
it remains to consider vertices $[s,i]$ and $[t,i]$, where $i\in[2r-1]$ and
$s\neq t$. If $i\in[r-1]$, then we proceed analogously as in the proof of
Theorem 3.1, hence we omit the details. And if $i\in\\{r+1,\ldots,2r-1\\}$,
then by the vertical symmetry of $B(r)$ over the level $r$ (with respect to
the normal representation of $B(r)$) we get the required conclusion is an
analogous way. $\square$

For Benes and butterfly networks, it was also conjectured in [17, Conjecture
7.1] that the FTMD problem is polynomially solvable. Theorems 3.1 and 3.2
clearly confirm the conjecture.

The last networks we consider are the silicate networks $SL(n)$, $n>1$, which
can be defined as follows. Begin with the $n^{\rm th}$ member of the
circumcoronene homologous series $H_{n}$, which consists of the central
hexagon and $n-1$ layers of hexagons around it. (Metric-based resolvability of
these polycyclic aromatic hydrocarbons were very recently investigated in
detail in [1].) Then subdivide each edge of it, and finally append a $K_{4}$
around the original vertices of $H_{n}$, where for each outer vertex of
$H_{n}$ we need to add an additional vertex to accomplish $K_{4}$. The
construction should be clear from Fig. 3, where $SL(2)$ is drawn.

Figure 3: $SL(2)$ and its twins

More generally, the anionic substructure of silicates comprises (SiO4)
tetrahedra, which can crosslink by sharing common corners. Their primary
variety has been widely explored, starting from mineralogy and topography to
chemical, physical, and computer sciences. From a synthetic perspective, the
tetrahedron’s focal hub represents the silicon particle, while the corner ions
speak to the oxygen atoms, while the corner vertices represent oxygen atoms.
We get distinct silicate structures by arranging different ways of tetrahedra.
Papers [16, 28, 31] derive some topological features of the silicate networks.
This network family is a multi-stage interconnection network comparable to the
hexagonal [9] and honeycomb [40] networks used in computer science networks
[40]. This is achieved by suggesting an addressing scheme to the vertices of
the silicate networks as suggested for hexagonal in [13] and honeycomb [40].

The metric dimension of the silicate networks $SL(n)$ was determined in 2011
as follows.

###### Theorem 3.3

[32] If $n\geq 2$, then $\beta(SL(n))=6n$.

For the FTMD of silicate networks it was proved in [17, Proposition 6.4] that

$6n+1\leq\beta^{\prime}(SL(n))\leq 21n\,.$

In our last result, we give an exact formula for FTMD of silicate networks.

###### Theorem 3.4

If $n\geq 2$, then $\beta^{\prime}(SL(n))=12n$.

Proof. $SL(n)$ contains $6n$ pairs of twin vertices, as shown in Fig 3 for
$SL(2)$. Hence $SL(n)$ contains $12n$ twin vertices and thus
$\beta^{\prime}(SL(n))\geq 12n$ by Lemma 2.1. To prove the reverse inequality,
we claim that these $12n$ vertices form a fault-tolerant resolving set.
Instead of proving it directly, we recall from the proof of [32, Theorem 5]
that the set of boundary vertices (the $6n$ outermost vertices in the standard
drawing of $SL(n)$, cf. Fig. 3) of $SL(n)$ is a (minimum) resolving set of
$SL(n)$. But then it straightforwardly follows that these boundary $6n$
vertices, together with their respective twins, form a (minimum) fault-
tolerant resolving set. $\square$

## Acknowledgements

Sandi Klavžar acknowledges the financial support from the Slovenian Research
Agency (research core funding P1-0297, and projects N1-0095, J1-1693,
J1-2452).

## References

  * [1] M. Azeem, M.F. Nadeem, Metric-based resolvability of polycyclic aromatic hydrocarbons, European Physical J. Plus, 136 (2021) Paper 395.
  * [2] R.F. Bailey, I.G. Yero, Error-correcting codes from $k$-resolving sets, Discuss. Math. Graph Theory 39 (2019) 341–355.
  * [3] G.A. Barragán-Ramírez, A. Estrada-Moreno, Y. Ramírez-Cruz, J.A. Rodríguez-Velázquez, The local metric dimension of the lexicographic product of graphs, Bull. Malays. Math. Sci. Soc. 42 (2019) 2481–2496.
  * [4] M. Basak, L. Saha, G.K. Das, K. Tiwary, Fault-tolerant metric dimension of circulant graphs $C_{n}(1,2,3)$, Theoret. Comput. Sci. 817 (2020) 66–79.
  * [5] A.F. Beardon, J.A. Rodríguez-Velázquez, On the $k$-metric dimension of metric spaces, Ars Math. Contemp. 16 (2019) 25–38.
  * [6] Z. Beerliova, F. Eberhard, T. Erlebach, A. Hall, M. Hoffman, M. Mihalák, Network discovery and verification, IEEE J. Sel. Areas Commun. 24 (2006) 2168–2181.
  * [7] G. Chartrand, L. Eroh, M.A. Johnson, O. Oellermann, Resolvability in graphs and the metric dimension of a graph, Discrete Appl. Math. 105 (2000) 99–113.
  * [8] G. Chartrand, P. Zhang, The theory and applications of resolvability in graphs, a survey, Congr. Numer. 160 (2003) 47–68.
  * [9] M.-S. Chen, K.G. Shin, D.D. Kandlur, Addressing routing and broadcasting in hexagonal mesh multiprocessors, IEEE Trans. Comput. 39 (1990) 10–18.
  * [10] S.G. Corregidor, A. Martínez-Pérez, A note on $k$-metric dimensional graphs, Discrete Appl. Math. 289 (2021) 523–533.
  * [11] A. Estrada-Moreno, J.A. Rodríguez-Velázquez, I.G. Yero, The $k$-metric dimension of a graph, Appl. Math. Inf. Sci. 9 (2015) 2829–2840.
  * [12] A. Estrada-Moreno, I.G. Yero, J.A. Rodríguez-Velázquez, The $k$-metric dimension of the lexicographic product of graphs, Discrete Math. 339 (2016) 1924–1934.
  * [13] F. Garcia Nocetti, I. Stojmenović, J. Zhang, Addressing and routing in hexagonal networks with applications for tracking mobile users and connection rerouting in cellular networks, IEEE Trans. Parallel Distrib. Syst. 13 (2002) 963–971.
  * [14] X. Guo, M. Faheem, Z. Zahid, W. Nazeer, J. Li, Fault-tolerant resolvability in some classes of line graphs, Math. Probl. Eng. Sept. (2020) 1–8.
  * [15] F. Harary, R.A. Melter, On the metric dimension of a graph, Ars Combin. 2 (1976) 191–195.
  * [16] S. Hayat, M. Imran, Computation of topological indices of certain networks, Appl. Math. Comput. 240 (2014) 213–228.
  * [17] S. Hayat, A. Khan, M.Y.H. Malik, M. Imran, M. K. Siddiqui, Fault-tolerant metric dimension of interconnection networks, IEEE Access 8 (2020) Paper 1436872.
  * [18] C. Hernando, M. Mora, I.M. Pelayo, C. Seara, D.R. Wood, Extremal graph theory for metric dimension and diameter, Electron. J. Combin. 17 (2010) Paper 30.
  * [19] C. Hernando, M. Mora, P.J. Slater, D.R. Wood, Fault-tolerant metric dimension of graphs, Ramanujan Math. Society Lecture Notes 5, (2008) 81–85.
  * [20] M. Imran, S. Hayat, M.Y.H. Mailk, On topological indices of certain interconnection networks, Appl. Math. Comput. 244 (2014) 936–951.
  * [21] I. Javaid, M. Salman, M.A. Chaudhry, S. Shokat, Fault-tolerance in resolvability, Util. Math. 80 (2009) 263–275.
  * [22] C.X. Kang, I.G. Yero, E. Yi, The fractional $k$-metric dimension of graphs, Appl. Anal. Discrete Math. 13 (2019) 203–223.
  * [23] S. Khuller, B. Ragavachari, A. Rosenfield, Landmarks in graphs, Discrete Appl. Math. 70 (1996) 217–229.
  * [24] C.P. Kruskal, M. Snir, A unified theory of interconnection network structure, Theoret. Comput. Sci. 48 (1986) 75–94.
  * [25] D. Kuziak, I.G. Yero, Metric dimension related parameters in graphs: A survey on combinatorial, computational and applied results, arXiv:2107.04877 [math.CO] (10 Jul 2021).
  * [26] M.-S. Lin, Simple linear-time algorithms for counting independent sets in distance-hereditary graphs, Discrete Appl. Math. 239 (2018) 144–153.
  * [27] K. Liu, N. Abu-Ghazaleh, Virtual coordinate backtracking for void traversal in geographic routing, in: Ad-Hoc, Mobile, and Wireless Networks, Springer, Berlin, Heidelberg (2006) 46–59.
  * [28] J.-B. Liu, S. Wang, C. Wang, S. Hayat, Further results on computation of topological indices of certain networks, IET Control Theory Appl. 11 (2017) 2065–2071.
  * [29] P. Manuel, M.I. Abd-El-Barr, I. Rajasingh, B. Rajan, An efficient representation of Benes networks and its applications, J. Discrete Algorithms 6 (2008) 11–19.
  * [30] P. Manuel, B. Rajan, I. Rajasingh, P.V. Beulah, Improved bounds on the crossing number of butterfly network, Discrete Math. Theoret. Comput. Sci. 15 (2013) 87–94.
  * [31] P. Manuel, I. Rajasingh, Topological properties of silicate networks, 2009 5th IEEE GCC Conference & Exhibition, 2009, 1–5.
  * [32] P. Manuel, I. Rajasingh, Minimum metric dimension of silicate networks, Ars Combin. 98 (2011) 501–510.
  * [33] M. Numan, N. Naz, F. Uddin, New results on topological indices for Benes and butterfly networks, U.P.B. Sci. Bull. 82 (2020) 33–42.
  * [34] I. Rajasingh, P. Manuel, N. Parthiban, D. Azubha Jemilet, R. Sundara Rajan, Transmission in butterfly networks, Comput. J. 59 (2016) 1174–1179.
  * [35] H. Raza, S. Hayat, M. Imran, X.F. Pan, Fault-tolerant resolvability and external structures of graphs, Mathematics 7(1) (2019) Paper 78.
  * [36] H. Raza, S. Hayat, X.F. Pan, On the fault-tolerant metric dimension of certain interconnection networks, J. Appl. Math. Comput. 60 (2019) 517–535.
  * [37] M. Salman, I. Javaid, M.A. Chaudhry, Minimum fault-tolerant, local and strong metric dimension of graphs, Ars Combin. 138 (2018) 333–353.
  * [38] A. Simić, M. Bogdanović, Z. Maksimović, J. Milošević, Fault-tolerant metric dimension problem: a new integer linear programming formulation and exact formula for grid graphs, Kragujevac J. Math. 42 (2018) 495–503.
  * [39] P.J. Slater, Leaves of trees, Congr. Numer. 14 (1975) 549–559.
  * [40] I. Stojmenović, Honeycomb networks: Topological properties and communication algorithms, IEEE Trans. Parallel Distrib. Syst. 8 (1997) 1036–1042.
  * [41] R.C. Tillquist, R.M. Frongillo, M.E. Lladser, Getting the lay of the land in discrete space: A survey of metric dimension and its applications, arXiv:2104.07201v1 [math.CO] (15 Apr 2021).
  * [42] D. Vietz, E. Wanke, The fault-tolerant metric dimension of cographs, in: Fundamentals of Computation Theory, Springer, Cham, 2019, 350–364.


#  An hybrid deterministic-stochastic iterative procedure to solve the heat
equation

Fouad Maouche Laboratory of Applied Mathematics,Faculty of Exact Sciences,
University of Bejaia, Algeria. E-mail<EMAIL_ADDRESS>Laboratory
of Applied Mathematics  Faculty of Exact Sciences, University of Bejaia,
Algeria

###### Abstract

Our goal in this paper is to solve the 1-D heat equation by an hybrid
deterministic-stochastic iterative procedure . The deterministic side consists
in discretizing the equation by the Crank-Nicolson method and the stochastic
side consists of applying Robbins Monro procedure to solve the resulting
matrix system. The almost complete convergence and the rate of convergence of
our procedure are established.

Keywords: Robbins-Monro, heat equation, Crank-Nicolson, Almost complete
convergence.

Mathematics Subject Classification: 65N21, 65C50.

## Introduction

Consider the heat equation problem on an interval $I$ in $\mathbb{R}$,

(1) $\left\\{\begin{array}[]{c}\frac{{}^{\partial u(x,t)}}{\partial
t}-D\frac{{}^{\partial^{2}u(x,t)}}{\partial x^{2}}=0,\\\
u(x,0)=f(x).\end{array}\right.$

Many researchers have worked on the one dimensional heat conduction equation
using various numerical methods and finite difference methods are the mostly
used of all the numerical methods [12, 13]. Recently, O. Nikan et al [7]
proposed an efficient coupling of the Crank–Nicolson scheme and localized
meshless technique for viscoelastic wave model in fluid flow, C.Chen et al [1]
present a second-order accurate Crank-Nicolson scheme for the two-grid finite
elements for nonlinear Sobolev equations and M. Ran et al [10] proposed a
linearized Crank–Nicolson scheme for the nonlinear time space fractional
Schrödinger equations.

Many other authors proposed iterative methods to solve the heat conduction
equation. For example, Newell–Whitehead–Segel equations of fractional order
are solved by fractional variational iteration method in [9] and Landweber
iterative regularization method to identify the initial value problem of the
time-space fractional diffusion-wave equation was studied in [16].

Stochastic algorithms are part of modern techniques for numerical solution of
many practical problems : signal processing and adaptive control [2, 4],
inverse problems [6], communication and system identification [15, 5, 3].

Let $(\Omega,\digamma,P)$ be a probability space and assume that
$\inf\left\\{re\text{ }\lambda;\text{ }\lambda\in\sigma(A)\right\\}>0$ with
$\sigma(A)$ is a spectrum of a matrix $A.$

Our goal is to solve the heat equation $\left(\ref{a}\right)$ by a hybrid
iterative procedure (deterministic and stochastic). The deterministic side
consists in discretizing equation $\left(\ref{a}\right)$ by the Crank-Nicolson
method and the stochastic side consists of applying Robbins Monro procedure
[11], which uses the full forward model when the noise on the right hand side
is stochastic, to solve the resulting matrix system.

By Hoeffding exponential inequalities, the almost complete convergence and the
rate of convergence of the iterative procedure to solve the heat equation
$\left(\ref{a}\right)$ are established.

##  1 Methodology

The crank-Nicolson method combines the stability of an implicit method with
the accuracy of a second-order method in both space and time. Simply from the
average of the explicit and implicit FTCS schemes (left and right sides are
centred at time step $m+0.5$).

The following approximation expression holds

$\frac{{}^{\partial u(x,t)}}{\partial
t}-D\frac{{}^{\partial^{2}u(x,t)}}{\partial
x^{2}}\simeq\frac{u_{n,m+1}-u_{n,m}}{\Delta
t}-\frac{D}{2}\left(\frac{u_{n+1,m+1}-2u_{n,m+1}+u_{n-1,m+1}+u_{n+1,m}-2u_{n,m}+u_{n-1,m}}{\Delta
x^{2}}\right).$

The scheme can be written as follow

$au_{n-1,m}+(2-2a)u_{n,m}+au_{n+1,m}=-au_{n-1,m+1}+(2+2a)u_{n,m+1}-au_{n+1,m+1}.$

These equations holds for $1\leq n\leq N-1,$ and the boundary conditions
supply the two missing equations. The Crank-Nicolson method will be written in
the following matrix form

$\begin{pmatrix}-a&2+2a&-a&0&.&.&.\\\ 0&-a&2+2a&-a&.&.&.\\\ .&.&.&.&.&.&.\\\
.&.&.&.&.&.&.\\\ .&.&.&.&.&.&.\\\ .&.&.&.&2+2a&-a&0\\\
.&.&.&.&-a&2+2a&-a\end{pmatrix}\begin{pmatrix}u_{0,m+1}\\\ u_{1,m+1}\\\ .\\\
.\\\ .\\\ u_{N-1,m+1}\\\ u_{N,m+1}\end{pmatrix}=$

$\begin{pmatrix}a&2-2a&a&0&.&.&.\\\ 0&a&2-2a&a&.&.&.\\\ .&.&.&.&.&.&.\\\
.&.&.&.&.&.&.\\\ .&.&.&.&.&.&.\\\ .&.&.&.&2-2a&a&0\\\
.&.&.&.&a&2-2a&a\end{pmatrix}\begin{pmatrix}u_{0,m}\\\ u_{1,m}\\\ .\\\ .\\\
.\\\ u_{N-1,m}\\\ u_{N,m}\end{pmatrix}.$

The matricial equation above is a representation of $N-1$ equations with $N+1$
unknown, the matrices have $N-1$ rows and $N+1$columns and the two missing
equations come from the boundary conditions which we use to convert this
matricial equation into a system of equations involving a square matrix of the
form:

(2) $A_{m+1}u_{m+1}+r_{m+1}=B_{m}u_{m}+w_{m},$

with

$A_{m+1}=\begin{pmatrix}2+2a&-a&0&.&.&.&.\\\ -a&2+2a&.&.&.&.&.\\\
0&.&.&.&.&.&.\\\ .&.&.&.&.&.&.\\\ .&.&.&.&.&-a&.\\\ .&.&.&.&-a&2+2a&-a\\\
.&.&.&.&0&-a&2+2a\end{pmatrix},$

$B_{m}=\begin{pmatrix}2-2a&a&0&.&.&.&.\\\ a&2-2a&a&.&.&.&.\\\ 0&.&.&.&.&.&.\\\
.&.&.&.&.&.&.\\\ .&.&.&.&.&a&.\\\ .&.&.&.&a&2-2a&a\\\
.&.&.&.&0&a&2-2a\end{pmatrix},$

$u_{m+1}=\begin{pmatrix}u_{1,m+1}\\\ .\\\ .\\\ .\\\ u_{N-1,m+1}\end{pmatrix},$
$u_{m}=\begin{pmatrix}u_{1,m}\\\ .\\\ .\\\ .\\\ u_{N-1,m}\end{pmatrix},$
$r_{m+1}=\begin{pmatrix}-au_{0,m+1}\\\ 0\\\ .\\\ .\\\
-au_{N,m+1}\end{pmatrix}$ and $w_{m}=\begin{pmatrix}au_{0,m}\\\ 0\\\ .\\\ .\\\
a_{N,m}\end{pmatrix}.$

The equation $\left(\ref{ck1}\right)$ can be written in following form

(3) $A_{m+1}u_{m+1}=B_{m}u_{m}+w_{m}-r_{m+1}.$

The matrix inversion method to find the solution $u_{m+1}$ is very time
consuming and computationally inefficient. In this paper, we propose the
following iterative procedure to solve the equation $\left(\ref{ck2}\right).$

(4)
$\left\\{\begin{array}[]{c}X_{(k+1)}=X_{(k)}-\frac{1}{k}\left[A_{m+1}X_{(k)}-(B_{m}u_{m}+w_{m}-r_{m+1})-\xi_{(k)}\right],\text{
}k=1,2,...,\\\ X_{(0)}\in\mathbb{R}^{N-1}\end{array}\right.$

where $(X_{(k)})_{k\in\mathbb{N}^{\ast}}$ are vectors of $\mathbb{R}^{n}$and
$\left(\xi_{(k)}\right)_{k\in\mathbb{N}^{\ast}}$ is a sequence of bounded and
i.i.d random variables with values in $\mathbb{R}^{n}$ satisfying

(5) $\left\|\xi_{(k)}\right\|<b,\text{ }b\in\mathbb{R}$

##  2  Preliminary results

According to [6, lemma 1] and after successive iterations, the following
relation is obtained

(6)
$X_{(k+1)}-X_{(ex)}=\mathop{\displaystyle\prod}\limits_{i=1}^{k}(I-\frac{1}{i}A_{m+1})(X_{1}-X_{ex})+\sum_{i=1}^{k}\mathop{\displaystyle\prod}\limits_{j=i+1}^{k}(I-\frac{1}{j}A_{m+1})\frac{1}{i}\xi_{i}.$

Where, $X_{(ex)}$ is the exact solution and
$\mathop{\displaystyle\prod}\limits_{j=k+1}^{k}(I-\frac{1}{j}A_{m+1})=I$ for
$1\leq i,j\leq k,$ with $I$ is the unit matrix.

###### Lemma 1

Suppose that $\inf\left\\{re\text{ }\lambda;\text{
}\lambda\in\sigma(A_{m+1})\right\\}>0.$ The following expression holds.

(7) $\exists\gamma>0,\text{ }\exists p>0,\text{ }\forall\text{ }1\leq i\leq
k:\left\|\mathop{\displaystyle\prod}\limits_{j=i+1}^{k}(I-\frac{1}{j}A_{m+1})\right\|\leq\gamma\left(\frac{i+1}{k+1}\right)^{p}.$

Proof. Under the condition $\inf\left\\{re\text{ }\lambda;\text{
}\lambda\in\sigma(A_{m+1})\right\\}>0,$ H. Walk obtained the following result
[14, Lemma 3.b]

(8) $\exists\gamma>0,\text{ }\exists p>0,\text{ }\forall\text{ }1\leq i\leq
k:\left\|\mathop{\displaystyle\prod}\limits_{j=i+1}^{k}(I-\frac{1}{j}A_{m+1})\right\|\leq\gamma\left(\mathop{\displaystyle\prod}\limits_{j=i+1}^{k}\left(1-\frac{1}{j}\right)\right)^{p}.$

Then, taking into account that: $\ln\left(1+x\right)\leq x$, for $x>-1$, we
have

$p\ln\left(1-\frac{1}{j^{\theta}}\right)\leq-\frac{p}{j^{\theta}}$
$\sum_{j=i+1}^{k}\ln\left(1-\frac{1}{j^{\theta}}\right)^{p}\leq\sum_{j=i+1}^{k}-\frac{p}{j^{\theta}}=-p\sum_{j=i+1}^{k}\frac{1}{j^{\theta}}=-p\int\limits_{i+1}^{k+1}\frac{1}{x^{\theta}}dx.$

Then

$\sum_{j=i+1}^{k}\ln\left(1-\frac{1}{j^{\theta}}\right)^{p}\leq
p\ln(\frac{i+1}{k+1}).$

This implies that

$\exp\left(\sum_{j=i+1}^{k}\ln\left(1-\frac{1}{j^{\theta}}\right)^{p}\right)\leq\exp\left(\ln\left(\frac{i+1}{k+1}\right)^{p}\right).$

So,

(9)
$\gamma\left(\mathop{\displaystyle\prod}\limits_{j=i+1}^{k}\left(1-\frac{1}{j^{\theta}}\right)\right)^{p}\leq\gamma\left(\frac{i+1}{k+1}\right)^{p}.$

From $(\ref{gA})$ we deduce that

(10)
$\lim_{k\rightarrow\infty}\left\|\mathop{\displaystyle\prod}\limits_{j=1}^{k}(I-\frac{1}{j}A_{m+1})\right\|\leq\lim_{k\rightarrow\infty}\gamma\left(\mathop{\displaystyle\prod}\limits_{j=1}^{k}\left(1-\frac{1}{j^{\theta}}\right)\right)^{p}=0.$

###### Lemma 2

Under assumptions of Lemma 1, the following expression holds.

(11) $\exists\gamma>0,\text{ }\exists p>0,\text{ }\forall\text{ }1\leq i\leq
k:\sum_{i=1}^{k}\left\|\mathop{\displaystyle\prod}\limits_{j=i+1}^{k}(I-\frac{1}{j}A_{m+1})\frac{1}{i}\right\|^{2}\leq
C\frac{\gamma^{2}}{(k+1)^{2p}},$

with $C$ is a constant.

Proof. By virtue of the relation $(\ref{ee})$ one has

$\exists\gamma>0,\text{ }\exists p>0,\text{ }\forall\text{ }1\leq i\leq
k:\left\|\mathop{\displaystyle\prod}\limits_{j=i+1}^{k}(I-\frac{1}{j}A_{m+1})\frac{1}{i}\right\|^{2}\leq\gamma^{2}\frac{(i+1)^{2p}}{(k+1)^{2p}i^{2}}.$

Then

(12) $\exists\gamma>0,\text{ }\exists p>0,\text{ }\forall\text{ }1\leq i\leq
k:\sum_{i=1}^{k}\left\|\mathop{\displaystyle\prod}\limits_{j=i+1}^{k}(I-\frac{1}{j}A_{m+1})\frac{1}{i}\right\|^{2}\leq\frac{\gamma^{2}}{(k+1)^{2p}}\sum_{i=1}^{k}\frac{(i+1)^{2p}}{i^{2}}.$

By Kronecker’s lemma,
$\frac{\gamma^{2}}{(k+1)^{2p}}\sum_{i=1}^{k}\frac{(i+1)^{2p}}{i^{2}}$ tends to
$0$ when $k$ tends to infinity.
In fact, $\left(\frac{1}{i^{2}}\right)_{i\in\mathbb{N}^{\ast}}$ is a
convergent sequence and $\lim\limits_{i\rightarrow+\infty}(i+1)^{2p}=+\infty.$
So,

(13)
$\lim\limits_{i\rightarrow+\infty}\frac{1}{(k+1)^{2p}}\sum_{i=1}^{k}\frac{(i+1)^{2p}}{i^{2}}=0.$

From the relation $(\ref{kro})$ one deduces that: $\exists(N^{\ast}$
$\in\mathbb{N}^{\ast})$ such that

(14)
$\lim\limits_{k\rightarrow\infty}\frac{1}{\left(k+1\right)^{2p}}\sum_{i=N^{\ast}+1}^{k}\frac{(i+1)^{2p}}{i^{2}}=0.$

We have the following relationship

$\frac{1}{\left(k+1\right)^{2p}}\sum_{i=1}^{k}\frac{(i+1)^{2p}}{i^{2}}=\frac{1}{\left(k+1\right)^{2p}}\sum_{i=1}^{N^{\ast}}\frac{(i+1)^{2p}}{i^{2}}+\frac{1}{\left(k+1\right)^{{}^{2c}}}\sum_{i=N^{\ast}+1}^{k}\frac{(i+1)^{2p}}{i^{2}}$
$\leq\frac{1}{\left(k+1\right)^{2p}}\sum_{i=1}^{N^{\ast}}\frac{(i+1)^{2p}}{i^{2}}=\frac{C}{\left(k+1\right)^{2p}},$

with, $\sum_{i=1}^{N}\frac{(i+1)^{2ap}}{i^{2}}=C.$
Replacing in $(\ref{1})$ we find $(\ref{h'}).$

##  3 Exponential inequalities and convergence results

In this section, exponential inequalities of the Hoeffding type are
established. These allow us to establish the almost complete convergence and
the rate of convergence of the iterative procedure $\left(\ref{cA}\right)$ to
solve the heat equation $\left(\ref{a}\right).$

###### Definition 1

The sequence of random variables $\left(X_{(k)\text{
}}\right)_{k\in\mathbb{N}^{\ast}}$ converges almost completely (a.co) to a
random variable $X,$ when $k$ tends to infinity, if and only if:
$\forall\varepsilon>0,\sum_{k=1}^{+\infty}\mathbb{P}\left(\left\|X_{(k+1)}-X_{(ex)}\right\|>\varepsilon\right)<+\infty.$

###### Theorem 2

Let $A\in L(H).$Under the condition $\inf\left\\{re\text{ }\lambda;\text{
}\lambda\in\sigma(A)\right\\}>0$, the following exponential inequalities hold.

(15) $\mathbb{P}\left(\left\|X_{(k+1)}-X_{(ex)}\right\|>\varepsilon\right)\leq
2\exp\left(-\frac{(k+1)^{2p}\varepsilon^{2}}{\alpha}\right),\text{
}\alpha\in\mathbb{R}.$

Proof. By virtue of the relation $(\ref{e}),$ one has the following expression

$\mathbb{P}\left(\left\|X_{(k+1)}-X_{(ex)}\right\|>\varepsilon\right)=P\left(\left\|\mathop{\displaystyle\prod}\limits_{i=1}^{k}(I-\frac{1}{i}A_{m+1})(X_{(1)}-X_{(ex)})+\sum_{i=1}^{k}\mathop{\displaystyle\prod}\limits_{j=i+1}^{k}(I-\frac{1}{j}A_{m+1})\frac{1}{i}\xi_{i}\right\|>\varepsilon\right)$
$\leq\mathbb{P}\left(\left\|\sum_{i=1}^{k}\mathop{\displaystyle\prod}\limits_{j=i+1}^{k}(I-\frac{1}{j}A_{m+1})\frac{1}{i}\xi_{i}\right\|>\varepsilon-\left\|\mathop{\displaystyle\prod}\limits_{i=1}^{k}(I-\frac{1}{i}A_{m+1})(X_{(1)}-X_{(ex)})\right\|\right).$

The relation $(\ref{ine})$ proves that:

(16)
$\exists\varepsilon>0,\left\|\mathop{\displaystyle\prod}\limits_{i=1}^{k}(I-\frac{1}{i}A_{m+1})(X_{(1)}-X_{(ex)})\right\|\leq\frac{\varepsilon}{2}.$

Then,

$\mathbb{P}\left(\left\|X_{(k+1)}-X_{(ex)}\right\|>\varepsilon\right)\leq\mathbb{P}\left(\left\|\sum_{i=1}^{k}\mathop{\displaystyle\prod}\limits_{j=i+1}^{k}(I-\frac{1}{j}A_{m+1})\frac{1}{i}\xi_{i}\right\|>\varepsilon-\frac{\varepsilon}{2}\right)$
$\leq\mathbb{P}\left(\left\|\sum_{i=1}^{k}\mathop{\displaystyle\prod}\limits_{j=i+1}^{k}(I-\frac{1}{j}A_{m+1})\frac{1}{i}\xi_{i}\right\|>\frac{\varepsilon}{2}\right).$

We pose

(17)
$\eta_{i}=\mathop{\displaystyle\prod}\limits_{j=i+1}^{k}(I-\frac{1}{j}A_{m+1})\frac{1}{i}\xi_{i}.$

$\left(\eta_{i}\right)_{i\in\mathbb{N}^{\ast}}$ is a sequence of bounded and
i.i.d random variables in a Hilbert space such that

(18)
$\left\|\eta_{i}\right\|<\left\|\mathop{\displaystyle\prod}\limits_{j=i+1}^{k}(I-\frac{1}{j}A_{m+1})\right\|\frac{1}{i}b=d_{i}.$

Thus

(19)
$\mathbb{P}\left(\left\|X_{(k+1)}-X_{(ex)}\right\|>\varepsilon\right)\leq\mathbb{P}\left(\left\|\sum_{i=1}^{k}\eta_{i}\right\|>\frac{\varepsilon}{2}\right).$

We give the Pinelis-Hoeffding inequality for the sequence
$\left(\eta_{i}\right)_{i\in\mathbb{N}^{\ast}}$ such that
$\left\|\eta_{i}\right\|<d_{i}$ in a Hilbert space $H$ ( [8]).

(20)
$\mathbb{P}\left(\left\|\sum_{i=1}^{k}\eta_{i}\right\|>\varepsilon\right)\leq
2\exp\left(-\frac{\varepsilon^{2}}{2\sum_{i=1}^{k}d_{i}^{2}}\right).$

Then, we deduce from $(\ref{ntheta})$ and $(\ref{xx})$ the following relation.

(21)
$\mathbb{P}\left(\left\|\sum_{i=1}^{k}\eta_{i}\right\|>\frac{\varepsilon}{2}\right)\leq
2\exp\left(-\frac{\varepsilon^{2}}{8b^{2}\sum_{i=1}^{k}\left\|\mathop{\displaystyle\prod}\limits_{j=i+1}^{k}(I-\frac{1}{j}A_{m+1})\right\|^{2}(\frac{1}{i})^{2}}\right).$

Finally, by virtue of the relation $(\ref{1111})$ and $(\ref{h'})$ and from
the relation $(\ref{PIN})$, we obtain

$\mathbb{P}\left(\left\|X_{(k+1)}-X_{(ex)}\right\|>\varepsilon\right)\leq
2\exp\left(-\frac{\varepsilon^{2}}{\frac{8C\left(\gamma
b\right)^{2}}{(k+1)^{2p}}}\right).$

By putting $\alpha=8C\left(\gamma b\right)^{2}$ we will find $(\ref{n}).$

In the next corollary, we give the proof that the iterative procedure
$(\ref{cA})$ converges almost completely to the solution of the equation
$(\ref{a}).$

###### Corollary 1

Under the conditions of Theorem 1:

The recursive procedure $(\ref{cA})$ converges almost completely (a.co) to the
solution of the equation$\ (\ref{a}):$

(22) $\forall\varepsilon>0,\text{
}\sum_{k=1}^{+\infty}\mathbb{P}\left(\left\|X_{(k+1)}-X_{(ex)}\right\|>\varepsilon\right)<+\infty.$

Additionally,

(23) $\left\|X_{(k+1)}-X_{(ex)}\right\|=O(k^{-2p}),\text{ }p>\frac{1}{2}.$

Proof. 1) Let us pose

$v_{k}=2\exp\left(-\frac{(k+1)^{2p}\varepsilon^{2}}{\alpha}\right)\leq
2\exp\left(-\left(k+1\right)^{2p}\varepsilon^{2}\right),$

Applying Cauchy’s rule to the positive term series $v_{k}$ it follows that:
When $p>\frac{1}{2}$, $\sum_{k=1}^{+\infty}v_{k}$ is a convergent series.
This implies that

(24)
$\forall\varepsilon>0,\sum_{k=1}^{+\infty}\mathbb{P}\left(\left\|X_{(k+1)}-X_{(ex)}\right\|>\varepsilon\right)\leq\sum_{k=1}^{+\infty}2\exp\left(-\left(k+1\right)^{2p}\varepsilon^{2}\right)<+\infty.$

2) To obtain $(\ref{vcon}),$ it is sufficient to choose $A=\varepsilon k^{2p}$
in $(\ref{ici})$ to have

$\sum_{k=1}^{+\infty}P\left(\left\|X_{(k+1)}-X_{(ex)}\right\|>Ak^{-2p}\right)<+\infty.$

${\LARGE Acknowledgement:}$ We acknowledge support of ”Direction de la
Recherche Scientifique et du Développement Technologique
DGRSDT”.MESRS,Algeria.

## References

  * [1] Chen, C., Li, K., Chen, Y., & Huang, Y. 2019. Two-grid finite element methods combined with Crank-Nicolson scheme for nonlinear Sobolev equations. Advances in Computational Mathematics, 45(2), 611-630.
  * [2] Ding, F. 2013. Decomposition based fast least squares algorithm for output error systems. Signal Processing, 93(5), 1235-1242.
  * [3] Ding, J., Fan, C., & Lin, J. 2013. Auxiliary model based parameter estimation for dual-rate output error systems with colored noise. Applied Mathematical Modelling, 37(6), 4051-4058.
  * [4] Kushner, H. J. 2011. Numerical methods for controls for nonlinear stochastic systems with delays and jumps: Applications to admission control. Stochastics: An International Journal of Probability and Stochastic Processes, 83(03), 277-310.
  * [5] Liu, Y., Ding, F., & Shi, Y. 2014. An efficient hierarchical identification method for general dual-rate sampled-data systems. Automatica, 50(3), 962-970.
  * [6] Maouche, F., Dahmani, A., & Rahmania, N. 2017. A stochastic procedure to solve linear ill-posed problems. Communications in Statistics-Theory and Methods, 46(3), 1519-1531.
  * [7] Nikan, O., & Avazzadeh, Z. 2021. Coupling of the Crank–Nicolson scheme and localized meshless technique for viscoelastic wave model in fluid flow. Journal of Computational and Applied Mathematics, 398, 113695.
  * [8] Pinelis, I. 1992, January. An approach to inequalities for the distributions of infinite-dimensional martingales. In Probability in Banach Spaces, 8: Proceedings of the Eighth International Conference (pp. 128-134). Birkhauser Boston.
  * [9] Prakash, A., Goyal, M., & Gupta, S. (2019). Fractional variational iteration method for solving time-fractional Newell-Whitehead-Segel equation. Nonlinear Engineering, 8(1), 164-171.
  * [10] Ran, M., & Zhang, C. 2019. Linearized Crank–Nicolson scheme for the nonlinear time–space fractional Schrödinger equations. Journal of Computational and Applied Mathematics, 355, 218-231.
  * [11] Robbins, H., & Monro, S. 1951. A stochastic approximation method. The annals of mathematical statistics, 400-407.
  * [12] Sun, G., & Trueman, C. W. 2006. Efficient implementations of the Crank-Nicolson scheme for the finite-difference time-domain method. IEEE transactions on microwave theory and techniques, 54(5), 2275-2284.
  * [13] Sun, C., & Trueman, C. W. 2003). Unconditionally stable Crank-Nicolson scheme for solving two-dimensional Maxwell’s equations. Electronics Letters, 39(7), 595-597.
  * [14] Walk, H., & Zsido, L. 1989. Convergence of the Robbins-Monro method for linear problems in a Banach space. Journal of Mathematical Analysis and Applications, 139(1), 152-177.
  * [15] Wang, C., & Tang, T. 2014. Recursive least squares estimation algorithm applied to a class of linear-in-parameters output error moving average systems. Applied Mathematics Letters, 29, 36-41.
  * [16] Yang, F., Zhang, Y., & Li, X. X. 2020. Landweber iterative method for identifying the initial value problem of the time-space fractional diffusion-wave equation. Numerical Algorithms, 83(4), 1509-1530.