11institutetext: Department of Computing and Informatics, Bournemouth
University, United Kingdom 22institutetext: Department of Electronics and
Computer Science, University of Southampton, United Kingdom
22email<EMAIL_ADDRESS>
22email: {m.soorati<EMAIL_ADDRESS>
# Outlining the design space of eXplainable swarm (xSwarm): experts’
perspective

Mohammad Naiseh 11 Mohammad D. Soorati 22 Sarvapali Ramchurn 22

###### Abstract

In swarm robotics, agents interact through local roles to solve complex tasks
beyond an individual’s ability. Even though swarms are capable of carrying out
some operations without the need for human intervention, many safety-critical
applications still call for human operators to control and monitor the swarm.
There are novel challenges to effective Human-Swarm Interaction (HSI) that are
only beginning to be addressed. Explainability is one factor that can
facilitate effective and trustworthy HSI and improve the overall performance
of Human-Swarm team. Explainability was studied across various Human-AI
domains, such as Human-Robot Interaction and Human-Centered ML. However, it is
still ambiguous whether explanations studied in Human-AI literature would be
beneficial in Human-Swarm research and development. Furthermore, the
literature lacks foundational research on the prerequisites for explainability
requirements in swarm robotics, i.e., what kind of questions an explainable
swarm is expected to answer, and what types of explanations a swarm is
expected to generate. By surveying 26 swarm experts, we seek to answer these
questions and identify challenges experts faced to generate explanations in
Human-Swarm environments. Our work contributes insights into defining a new
area of research of eXplainable Swarm (xSwarm) which looks at how
explainability can be implemented and developed in swarm systems. This paper
opens the discussion on xSwarm and paves the way for more research in the
field.

###### Keywords:

Explainable AI, Swarm Robotics, Human-Swarm Interaction.

##  1 Introduction

Swarm robotics consists of multiple robots that interact with each other to
accomplish a collective task that is beyond individual ability, or can be
performed more effectively by a group of robots [11]. Swarm robotics promise
various implementations in many scenarios such as pollution control,
surveillance, package delivery and firefighting. Although swarms can perform
the task autonomously, human intervention is still crucial for safe and
effective deployment in real-world scenarios [1]. For example, swarm operators
may need to manage swarm tasks that might be beyond swarm capability or
intervene in cases of failures and errors. This intervention could be more
complex when it requires multiple humans to work together in a team to operate
remote swarms [10]. For instance, in a search and rescue scenario where the
swarm is responsible for searching and identifying casualties, the system may
consist of two operators: (a) an operator is tasked with scheduling clusters
of robots to search areas and (b) an analyst who is tasked with analysing
casualties images.

Human-Swarm Interaction (HSI) is an emerging field of research that studies
human factors and swarm robotics to better utilise both humans and swarm
capabilities in a Human-Swarm environment. An essential part of HSI is
communicating, to humans, the reasons behind swarms’ decisions and behaviour
[25]. As swarms become more advanced, explaining their behaviour (individual
and collective) is buried in increasingly complex communication between swarm
agents and underlying black-box machine learning models.

Explainable Artificial Intelligence (XAI) is a response to this direction of
re-search. XAI is a domain of research that is interested in making the
behaviour or the output of intelligent systems more intelligible to humans by
providing explanations [18]. While the concept of XAI is increasingly gaining
attention in several research domains, such as Agent Planning [3], Machine
Learning [22] and Motion Planning [6]. There is a clear gap in the literature
on integrating swarm robotics into the research and development of XAI.
Similar to XAI fields of research, we argue that eXplainable Swarm (xSwarm)
should address that an explanation is an answer to an unexpected event or a
failure of the system [18]. However, compared to different XAI domains, xSwarm
can be significantly different since the decision made by a swarm
significantly depends on the communication and collective contribution of its
agents [25]. Further, the explainability of swarms would require explaining
the emerging collective behaviour that is not necessary for the summation of
the individual robot behaviour [5].

Many studies discussed the need for XAI methods and models for Human-Swarm
environments to improve trust and maintain situational awareness, e.g., [20,
25, 1]. However, at the current stage of research, it is still vague what kind
of explanations a swarm system should be expected to generate and what
questions an explainable swarm is expected to answer. This paper seeks to
conceptualise the concept of xSwarm and introduce a new taxonomy of
explainability requirements for HSI. Our results can guide the requirements
elicitation for explanation methods and models for Human-Swarm teaming. These
insights contribute to operationalising the concept of xSwarm in reality and
can serve as a resource for researchers and developers interested in designing
explainable Human-Swarm interfaces.

In this paper, we limit our research to swarm robotics, i.e., this paper does
not address multi-robot systems that have explicit goals and their agents
execute both individual and group plans. We follow a similar approach proposed
in recent publications to outline explainability requirements in a given
problem [15, 6]. Our method uses open-text and scenario-based questionnaire
with domain experts, to elicit explainability considerations for swarm
systems. We foresee a lack of established understanding of the concept or
common technical knowledge given the early stage of xSwarm in industrial
practices. Therefore, we used a novel use-case developed in our recent work
[10] and supported with failure scenarios and explanations to ground our
investigation. Our data set was collected from on an online questionnaire with
26 swarm experts. In this paper, we make the following contributions:

  * •

We present xSwarm taxonomy that summarises the explainability space for swarm
robotics from swarm experts’ perspective.

  * •

We summarize current challenges faced by researchers and industry
practitioners to create xSwarm.

##  2 Background and related work

So far, the process of generating explanations for AI systems users has
received a lot of attention from multiple domains, including psychology [21],
artificial intelligence [16], social sciences [18] and law [4]. Furthermore,
regulatory requirements and increasing customer expectations for responsible
artificial intelligence raise new research questions on how to best design
meaningful and understandable explanations for a wide range of AI users [23].
To respond to this trend, many explainable AI (XAI) models and algorithms have
been proposed to explain black-box ML models [23], agent-path planning [3],
multi-agent path planning [2] and explainable scheduling [14]. These
explanations can range from local explanations that provide a rationale behind
a single decision to global explanations that provide explanations for the
overall AI logic [16].

Despite a growing interest in explainable AI, there is a limited number of
studies on how to incorporate explainability in swarm robotics. Only a few
attempts in the literature have discussed explainability in swarm robotics.
For instance, a scalable human-swarm interaction has been proposed to allow a
single human operator to monitor the state of the swarm and create tasks for
the swarm [11]. Their study with 100 participants showed that users have
different visualisation preferences for explanations to observe the state of
the swarm depending on the type of the given tasks. The explanation in this
study was limited to a visual representation of the swarm coverage using a
heatmap or individual points space that does not capture the wider space of
xSwarm. Another example is the work proposed in [20]. They proposed Human-
Agent EXplainability Architecture (HAEXA) to filter explanations generated by
swarm agents with the aim to reduce human cognitive load. Finally, Roundtree
et al. [25] discussed design challenges and recommendations for explainable
Human-Swarm interfaces, e.g., they described the delivery of explanations to
human operators in swarm systems as the main challenge due to human processing
limitations caused by a large number of individual robots in the swarm.
Although these studies provide steps toward the right direction for xSwarm, it
is still unclear whether explanations developed in other XAI domains would be
useful for Human-Swarm environments. Also, it is still undefined what kind of
questions a swarm system is expected to answer or what explanations from swarm
robotics would look like.

Meanwhile, recent papers were published in multiple domains to guide the
exploration of explainability requirements in a certain domain. Liao et al.
[15] created a list of prototypical user questions to guide the design of
human-centred explainable black-box ML. Similarly, Brandao et al. [6] proposed
a taxonomy of explanation types and objects for motion planning based on
interviewing motion planning experts and understanding their current work and
practice. Our work is driven by a similar approach for outlining xSwarm’s
design space. More particularly, in light of the growing interest in XAI, we
are interested in understanding what is required to create xSwarm and what are
the major practical challenges to developing xSwarm.

##  3 Background and related work

Ethical approval was acquired via the Ethics Committee of the School of
Electronics and Engineering from the University of Southampton [Reference No.
67669].

###  3.1 Participants

Thirty-two participants voluntarily accessed our online questionnaire.
Participants were approached through two main mailing lists: multi-
agent111Multi-agent systems — The Alan Turing Institute
https://www.turing.ac.uk/research/interest-groups/multi-agent-systems and TAS-
Hub222UKRI Trustworthy Autonomous Systems Hub (TAS-Hub):
https://www.tas.ac.uk/ mailing lists. Four participants were excluded because
they identified themselves to have less than one year of working in swarm
robotics. Two more participants were also excluded as they chose not to
complete the questionnaire, leaving us with twenty-six experts. 46.2% of our
participants were researchers, 7.7% were lecturers, 23.1% were PhD students,
and 22.9% with industrial roles. All experts had at least more than one year
of working in swarm robotics. 61.5% of participants had 1-5 years of
experience, 23.1% had 5-10 years, 7.7% with 10-15 years and 7.7% exceeded 15
years of experience in the field.

###  3.2 Study procedure and design

Due to the limited research in xSwarm, we chose to conduct an online
questionnaire as it allows us to scope an early investigation into outlining a
preliminary xSwarm taxonomy for future in-depth investigations. It also helps
us to gather a large number of experts’ feedback in a brief time compared with
other data collection methods such as interviews [17]. We designed our
questionnaire to include several elicitation probes to obtain representative
results and minimise cognitive heuristics and bias [19, 13] (Appendix A -
Table A.1). First, a draft questionnaire was developed by the first author.
Then, the draft was pilot tested with experts (researchers from the inside and
outside the research group) to assure that question formulation can achieve
the research goal and be understandable to study participants. The
questionnaire starts by asking participants to read the participant
information sheet. The information sheet outlines the motivation of the study,
compiles background material about the research goal and problem as well as
describes the questionnaire structure. Participants’ information sheet also
contains background material about explainable AI to minimise any availability
bias [19]. Then participants were directed toward the main questionnaire. The
questionnaire has four main sections. Table 1 provides a brief description of
the questionnaire structure and probe types used in each section.

Table 1: Questionnaire structure and elicitation probes

Questionnaire section |  Probe type |  Description
---|---|---
Swarm experience |  NA |  Demographic questions
Swarm failures |  Knowledge |  Participants’ knowledge about swarm failures, e.g., What are the main reasons for swarm failures? And What behaviour sparks your concern?
xSwarm scenario |  Situation assessment |  Participants’ assessment of a swarm failure or unexpected behaviour, e.g., What questions would you ask to debug this failure? Why do you think the swarm failed in this case?
xSwarm challenges |  Experience |  Participants’ previous experience in generating explanations from a swarm, e.g., What kind of challenges did you face when generating an explanation from a swarm?
|  Hypothetical |  Participant needs to develop eXplainable swarms, e.g., How would swarm developers be supported in integrating explainability??

Swarm experience. In this section, we asked participants to provide four
demographic factors related to their previous swarm experience -
_participants’ area of research or experience, current role, years of
experience in swarm robotics, and level of experience in swarm robotics_. We
excluded participants who had less than a year of experience or had identified
themselves with a low level of experience in the field.

xSwarm scenario. This section used an industrial-based use case for HSI, which
represents a real-world use case for HSI where explainability is a crucial
requirement [10]. The use case presented the following scenario: “ _A
hurricane has affected a settlement. Many were evacuated, but some did not
manage to escape and have been caught in debris and fallen structures. A UAV
(Unmanned Aerial Vehicle) swarm is being deployed to identify locations of
survivors, to evaluate their condition, and to advise on where unmanned ground
res-cue vehicles should be deployed to evacuate casualties._ ” A diagram for
the use case can be found in Appendix A – Figure A.1. First, we asked
participants to select when and what the swarm should explain its behaviour to
human operators during the task. Then, we provided two cases of swarm failures
or unexpected behaviour and asked participants to explain these cases. This is
a situation assessment probe to determine the bases for explanations during
failures or unexpected behaviour, rather than waiting for these incidents to
happen [13]. We also asked participants to provide what questions will they
ask to debug failures. Fig. 1.A and Figure 1.B show two scenarios of either a
failure on an expected behaviour during two main stages of the swarm task: (a)
Planning: a swarm has suddenly stopped while it is trying to reach its
destination, and (b) Searching: the swarm has failed to identify all the
casualties in the search area.

Figure 1: Scenarios of swarm failures or unexpected behaviour presented to
participants (A) swarm has suddenly stopped. (B) Swarm has failed to recognise
all possible casualties in the search area.

xSwarm challenges. The questions in this section aim to understand the
challenges faced by experts to generate explanations from swarm systems.
First, this section included open-end questions to reflect on participants’
experience in generating or obtaining explanations from swarm systems. We
asked questions such as _“What were the typical difficulties you encountered
while trying to extract explanations from swarm systems?”_. The section also
contained hypothetical questions to identify the key tools and techniques that
swarm developers should have to build xSwarm. We asked questions such as _“How
would swarm developers be better supported in integrating explainability?”_
and _“What kind of issues and considerations should developers have in mind
when developing xSwarms?”_.

###  3.3 Analysis

We followed the content analysis method [12]. Our data set included
participants’ answers to open-ended questions with themes extracted across
perspectives. The analysis was conducted by the first author. To increase the
trustworthiness of our qualitative analysis, we followed an iterative process
across the research team. This iterative procedure was implemented to check
and confirm that the taxonomy is reflected in the responses of the
participants. The authors met multiple times during each stage of the research
to ensure the accurate interpretation of each category and the supporting
evidence. These discussions and meetings resulted in the dividing, altering,
removing, or adding of categories to ensure that all responses and their
settings were adequately represented in the data.

##  4 Results

Our results are divided into two parts. We start by discussing the general
explanation categories emergent in participants’ answers, which outline the
design space of xSwarm. We then discuss the main challenges faced by our
experts to integrate explainability in swarm systems. Table 2. shows a sample
of participants’ answers. More examples can be found in Appendix A - Table
A.2.

Table 2: Explanation categories for swarm robotics. _Explain_ column refers to
participants’ explanations to swarm failures or unexpected behaviour- _Debug_
column presents participants’ questions to debug swarm failures or unexpected
behaviour - _Freq._ refers to the number of times this category appeared in
the data set.

Category |  Explain |  Debug
---|---|---
Consensus |  Detecting the missing casualty caused a conflict between the agents.
Agents were not able to agree on some features of the casualty.
Freq.= 24 |  How much of the swarm is consolidating the same view?
What is the agreement percentage between agents?
Freq.= 18
Path Planning |  Because the swarm initiative plan is to visit Location L which is a charging location.
Because swarm is trying to avoid obstacles
Freq.= 22 |  Is it a collision-free route?
Where is the swarm right now? [the probability distribution of possible robots
locations]
Freq.= 14
Communication |  Because the communication is limited between agents.
Environmental condition is limiting the connection between agents
Freq.= 19 |  What is the accuracy of information exchange between swarm agents?
What is the synchronisation status between swarm agents?
Freq.= 6
Scheduling |  Because this casualty should be detected by another cluster.
Because there are not enough agents to detect all casualties
Freq.= 14 |  Why there is x number of agents to search this area?
Why a cluster c1 is assigned to task t1?
Freq.= 8
Hardware |  Because the casualty is out of sensors coverage distance.
Because of low-quality input data from swarm sensors
Freq.= 16 |  What is the communication bandwidth between swarm robots.
What is the limitation of the swarm sensors?
Freq.= 5
Architecture and design |  Because robots have limited communication links per robot.
Because the swarm has not got enough training in such an environment.
Freq.= 5 |  What is the response threshold function?
How is the swarm size selected?
Freq.= 6

###  4.1 Explanation categories

####  4.1.1 Consensus.

A key distinction between swarms and multi-agent systems is that the swarm can
be seen as a single entity rather than multiple individual robots with
multiple goals and tasks. Swarm robotics is usually equipped with methods to
reach a consensus on the swarm decision, based on the accumulation and sharing
of information about features of the decision encountered by individual
robots. The most frequently asked questions by our participants were not only
regarding why the swarm has made a single decision but at a high level,
acquiring who and how many robots contributed to that decision. Our
participants frequently asked questions to check either the percentage of
individual robots who communicated the preferred decision, e.g., P18333For
anonymity, individual participants are referred to as Pn (e.g. P18) in this
chapter. mentioned: _“How many robots detected the casualties?”_ , and P26
described: _“Which features of the casualty did the robots agree on?”_.
Furthermore, when participants were asked to provide reasons for swarm
failures, they frequently answered that such a failure could be related to a
conflict between swarm agents. Participants enquired information to further
understand the opinion dynamics of the swarm. Opinion dynamics is a branch of
statistical physics that studies the process of agreement in large populations
of interacting agents [24]. Because of these dynamics, a population of agents
might progressively transition from a situation in which they may hold varying
opinions to one in which they all hold the same opinion. Participants were
interested in how the swarm opinion dynamics might change and evolve. For
instance, P20 reflected on the swarm searching for casualties task: _“What we
are also interested in is that What are the emerging decisions
(fragmentation), Is there a dominant decision, how dominant is this decision,
and how will this opinion evolve”._

####  4.1.2 Path Planning.

Participants frequently asked questions related to the path that the swarm is
going to follow and its related events. For instance, P2 mentioned that remote
human operators would frequently check what is the next state of the swarm.
Similarly, P20 added, _“automatic planning has not been fully adopted
especially in high-risk domains such this scenario, what the system usually
does to suggest the plan to the human operator to check that path”_. Further,
participants were not only interested to validate the swarm plan but also
asked questions related to the path planning algorithm to debug swarm
failures, e.g., P18 and P7 asked to debug a failure in Fig. 1.A: _“What
metrics does the swarm use to follow this route?”_ and _“Why did the swarm
follow this route, not another one?”_. A similar pattern appeared in
participants’ answers when they were asked to explain the unexpected behaviour
in Fig. 1.A Participants explained the unexpected behaviour based on path
planning events, P9 stated: _“Because the swarm agents are charging their
batteries according to the initial plan”_ , similarly P18 commented:
_“Probably the swarm has not stopped, it is just avoiding obstacles right
now”_. These results support the growing interest in Explainable Planning
(XAIP), as shown by many planning contributions such as Human-Aware Planning
and Model Reconciliation [9] and multi-agent path planning [2]. Such
explanations aim to answer human operators’ questions regarding the path for
several agents or clusters of agents to reach their targets [2], such that
paths can be taken simultaneously without the agents colliding. However, the
research on explainable swarm path-planning is still limited and requires
further attention.

####  4.1.3 Communication.

The collective decision-making process is the outcome of an emergent
phenomenon that follows localised interactions among agents yielding a global
information flow. As a consequence, to investigate the dynamics of collective
decision-making, participants went beyond debugging consensus between agents
and asked questions related to the communication between swarm agents, e.g.,
P7 pointed out the following question: _“What is the synchronisation status
between swarm agents?”._ Participants also brought up that swarm failure in
our examples could be critically related to a failure in ensuring the
appropriate flow of behavioural information among agents, both in terms of
information quantity and accuracy, e.g., P21 commented on the failure in Fig.
1.B: _“because the environmental condition is limiting the connection between
agents”_ and P18 added: _“Perhaps one of the casualties moved on / no longer
is, therefore state was not updated”_.

####  4.1.4 Scheduling-based.

Task scheduling in swarm robotics is a collective behaviour in which robots
distribute themselves over different tasks. The goal is to maximize the
performance of the swarm by letting the robots dynamically choose which task
to perform. Yet, in many applications, human operators are still required to
intervene in scheduling plan and adapt accordingly. In our questionnaire,
participants’ understanding of particular swarm failure was sometimes
associated with an initial task scheduling. Questions and explanations related
to task scheduling were mentioned in both scenarios. For instance, P2 and P21
explained casualty detection failure (Fig. 1.B) with the following
explanations, _“Because this casualty should be detected by another cluster”_
, and _“Because the initial scheduling plan did not allocate enough robots”_.
Interestingly, regardless the failure scenarios, our participants repeatedly
suggested questions with a pattern proposed by Miller [miller2018explanation]
which have a contrastive nature of explanation that are often implying why not
another scheduling plan is feasible. For instance, P19 asked the following
question: _“Why is a cluster c1 better than cluster c2 in performing task
t1?”_. Our data also showed a set of questions that require interactive
scheduling-based explanations, where the human operator can understand the
consequences of the scheduling plan. This pattern is pointed out by Wang et
al. [wang2014also] as what-if questions, P12 mentioned: _“What if cluster c1
were to do task t1 rather than task t2?”_.

####  4.1.5 Hardware.

Even though the quality and robustness of the hardware are increasing,
hardware failure is still quite common. Participants explained the failure of
the swarm with a link to a hardware problem. For instance, when the swarm was
not able to detect all the casualties in the area, P17 commented: _“because of
faulty in the sensors”_. Our participants also discussed that explanations of
hardware are necessary to give human operators actionable explanations to
either better utilise the swarm or to improve the swarm performance, e.g.,
send more swarm agents to the location. There was also a typical pattern among
participants’ feedback to explain swarm behaviour or failure based on its
hardware boundaries and limitation as well as environmental and training data
limitations. For instance, P11 explained unexpected behaviour in Figure 4.1:
_“Because some agents have limited speed capabilities, so they are waiting for
each other”_ , and similarly, P14 explained Figure 4.2 failure, _“the swarm
sensors have low image input”_.

####  4.1.6 Architecture and design.

Participants also found many reasons for swarm failures based on the swarm
architecture or design decisions of the system. This category did not appear
frequently in the data, and participants mentioned five explanations and six
questions. Participants recognised that potential failure or unexpected
behaviour can be related to initial design decisions made by the systems
engineers e.g., P12 answered: _“Because the swarm has not got enough training
in such an environment”_ and similarly, P22 commented: _“Because the
transition probability between states is fixed”_. Participants also took a
broader view of swarm explainability when they discussed questions that can be
answered through descriptive information about the swarm system design. For
instance, P1 and P4 asked: _“How is the swarm size selected?”_ , _“What is the
design method? is it behaviour-based or Automatic design?.”_ Currently, these
kinds of explanations are discussed in the XAI literature as an on-boarding
activity where human operators are introduced to the system design
architecture to understand its capability and limitation [8]. These global
properties of the system could help inform the interpretation of swarm
behaviour and predictions during critical decision-making scenarios.

###  4.2 Challenges faced by swarm experts

In this section, we discuss three main challenges participants faced when
designing or developing explanations for swarm robotics.

####  4.2.1 A trade-off between explainability and Human-Swarm performance.

Participants discussed that developing explainable swarms comes with a
critical analysis of performance-explainability trade-offs that swarm
developers have to face. Participants frequently pointed out that generating
explanations does not come without cost; they mentioned that this could be a
computational or performance cost, e.g., interruption to the human-swarm task.
P18 mentioned: _“asking the operator to read an explanation at an emergent
situation can be vital and the explanation might delay the reaction time and
distract the operator”_. These observations are consistent with earlier
research [22] that showed explanations can be ignored by human operators when
they are perceived as a task goal impediment. It has been shown that humans in
Human-AI systems focus to complete the task rather than trying to engage
cognitively with AI systems to understand their behaviour [7]. Such effect can
be even amplified in human-swarm environments where swarm operators might face
time constraints and multitasking as well as large numbers of agents to
monitor. In summary, participants argued that integrating explainability in
the Human-Swarm task is difficult – numerous design decisions require trade-
offs involving explainability, workload and usability.

####  4.2.2 Increasing the number of agents would increase the complexity of
explanation generation

The xSwarm challenge is significantly more difficult than other XAI areas
since a swarm’s decision is dependent on numerous parameters linked to
numerous agents [karga2019using]. Participants pointed out that there is a
scalability problem in swarm explainability, i.e., increasing the number of
agents in a swarm will exponentially increase the complexity of the
explanation generation. P12 mentioned: _“explainable swarm can have an extreme
cost when the swarm size is 100”_. Similarly, P2 added: _“some of the
technical reasons that led to the decision are relevant to a given user; as
the number of agents increases, the non-relevant information increases
exponentially”_. For these reasons, simplicity as a usability feature for
explanation can be essential in swarm environments. Simplicity states that
explanations generated by AI systems should be selective and succinct enough
to avoid overwhelming the explainee with unnecessary information [26]. In
response to this challenge, participants suggested that future swarm systems
shall include methods and tools to help summarise explanations generated by
swarm agents, e.g., P20 suggested: _“Human operators cannot deal with loads of
explanations, there should be some tools to provide a summary of the swarm
decision”_. In one relevant research, Mualla et al. [20] addressed this issue
and presented a novel explainable swarm architecture with a filtering feature
to filter explanations generated from swarm agents. They conduct a user
evaluation with three experimental groups: “No explanation: the swarm does not
present an explanation”, “Detailed explanation: the swarm presents
explanations generated by each agent” and “Filtered explanation, the swarm
presented a filtered explanation of each agent”. They showed that filtering
explanation was the most preferable option for participants and lead to more
trust and understanding of the swarm behaviour.

####  4.2.3 The soundness of swarm explanations is difficult to achieve

The soundness of an explanation measures how truthful an explanation is with
respect to the underlying system state [26]. Participants stated that they
faced difficulties to generate explanations that are sound and complete
because, in some contexts, information might be unavailable or outdated, P7
mentioned: _“A variety of technical factors like bandwidth limitations and
swarm size, an environmental condition factors associated with swarms diminish
the likelihood of having perfect communication, which negatively impacts
generating explanations that are complete and sound”_. To address this
challenge, participants suggested explanation generation tools in swarm
robotics shall take into consideration the validity of the available
information to generate an explanation for a swarm action. P16 mentioned:
_“swarm explanation algorithms should have metrics to measure the soundness of
their explanations before presenting it to operators”._ Participants also
suggested that outdated information about the swarm may result in an outdated
explanation which may degrade Human-Swarm performance and trust, P4 raised
this issue: _“Sometimes the swarm explanation might be not synchronised with
the current state of the swarm, in these cases, it might be better to avoid
showing this information to human operators”_. Previous empirical studies
discussed this issue and showed that erroneous actions taken by the human
operator to progress toward the overall goal will be amass if actions are
based on outdated swarm explanations or information [27]. Future xSwarm
research may need to consider discovering mitigation strategies to break the
error propagation cycle that may emerge from outdated explanations.

##  5 Conclusion

Although the research in eXplainable AI is gaining a lot of interest from
industry and academia, the research on explainability for swarm robotics is
still limited. In this paper, we presented results from an online
questionnaire with 26 swarm experts to outline the design space of eXplainable
Swarm (xSwarm). In particular, we presented a list of explanations generated
by swarm experts to explain swarm behaviours or failures and what kind of
questions do they ask to debug the swarm. Our work provides concrete taxonomy
of what xSwarm would look like from swarm experts’ perspective, serving as an
initial artefact to outline the design space of xSwarm. Our work suggests
opportunities for the HCI and swarms robotics communities, as well as industry
practitioners and academics, to work together to advance the field of xSwarm
through translational work and a shared knowledge repository that represent an
xSwarm design space. Finally, we cannot claim this is a complete analysis of
xSwarm design space. The results only reflect swarm experts’ views using an
online questionnaire. Future work could use our taxonomy as a study probe for
in-depth investigation with multiple stakeholders in swarm systems to further
enhance our taxonomy.

## Acknowledgments

This work was supported by the Engineering and Physical Sciences Research
Council (EP/V00784X/1).

## References

  * [1] Agrawal, A., Cleland-Huang, J.: Explaining autonomous decisions in swarms of human-on-the-loop small unmanned aerial systems. In: Proceedings of the AAAI Conference on Human Computation and Crowdsourcing. vol. 9, pp. 15–26 (2021)
  * [2] Almagor, S., Lahijanian, M.: Explainable multi agent path finding. In: AAMAS (2020)
  * [3] Anjomshoae, S., Najjar, A., Calvaresi, D., Främling, K.: Explainable agents and robots: Results from a systematic literature review. In: 18th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2019), Montreal, Canada, May 13–17, 2019. pp. 1078–1088. International Foundation for Autonomous Agents and Multiagent Systems (2019)
  * [4] Atkinson, K., Bench-Capon, T., Bollegala, D.: Explanation in ai and law: Past, present and future. Artificial Intelligence 289, 103387 (2020)
  * [5] Brambilla, M., Ferrante, E., Birattari, M., Dorigo, M.: Swarm robotics: a review from the swarm engineering perspective. Swarm Intelligence 7(1), 1–41 (2013)
  * [6] Brandao, M., Canal, G., Krivić, S., Luff, P., Coles, A.: How experts explain motion planner output: a preliminary user-study to inform the design of explainable planners. In: 2021 30th IEEE International Conference on Robot & Human Interactive Communication (RO-MAN). pp. 299–306. IEEE (2021)
  * [7] Buçinca, Z., Malaya, M.B., Gajos, K.Z.: To trust or to think: cognitive forcing functions can reduce overreliance on ai in ai-assisted decision-making. Proceedings of the ACM on Human-Computer Interaction 5(CSCW1), 1–21 (2021)
  * [8] Cai, C.J., Winter, S., Steiner, D., Wilcox, L., Terry, M.: ” hello ai”: uncovering the onboarding needs of medical practitioners for human-ai collaborative decision-making. Proceedings of the ACM on Human-computer Interaction 3(CSCW), 1–24 (2019)
  * [9] Chakraborti, T., Sreedharan, S., Zhang, Y., Kambhampati, S.: Plan explanations as model reconciliation: Moving beyond explanation as soliloquy. arXiv preprint arXiv:1701.08317 (2017)
  * [10] Clark, J.R., Naiseh, M., Fischer, J., Trigo, M.G., Parnell, K., Brito, M., Bodenmann, A., Ramchurn, S.D., Soorati, M.D.: Industry led use-case development for human-swarm operations. arXiv preprint arXiv:2207.09543 (2022)
  * [11] Divband Soorati, M., Clark, J., Ghofrani, J., Tarapore, D., Ramchurn, S.D.: Designing a user-centered interaction interface for human–swarm teaming. Drones 5(4), 131 (2021)
  * [12] Elo, S., Kyngäs, H.: The qualitative content analysis process. Journal of advanced nursing 62(1), 107–115 (2008)
  * [13] Klein, G.A., Calderwood, R., Macgregor, D.: Critical decision method for eliciting knowledge. IEEE Transactions on systems, man, and cybernetics 19(3), 462–472 (1989)
  * [14] Kraus, S., Azaria, A., Fiosina, J., Greve, M., Hazon, N., Kolbe, L., Lembcke, T.B., Muller, J.P., Schleibaum, S., Vollrath, M.: Ai for explaining decisions in multi-agent environments. In: Proceedings of the AAAI Conference on Artificial Intelligence. vol. 34, pp. 13534–13538 (2020)
  * [15] Liao, Q.V., Gruen, D., Miller, S.: Questioning the ai: informing design practices for explainable ai user experiences. In: Proceedings of the 2020 CHI Conference on Human Factors in Computing Systems. pp. 1–15 (2020)
  * [16] Lundberg, S.M., Erion, G., Chen, H., DeGrave, A., Prutkin, J.M., Nair, B., Katz, R., Himmelfarb, J., Bansal, N., Lee, S.I.: From local explanations to global understanding with explainable ai for trees. Nature machine intelligence 2(1), 56–67 (2020)
  * [17] McGuirk, P.M., O’Neill, P.: Using questionnaires in qualitative human geography (2016)
  * [18] Miller, T.: Explanation in artificial intelligence: Insights from the social sciences. Artificial intelligence 267, 1–38 (2019)
  * [19] Morgan, M.G.: Use (and abuse) of expert elicitation in support of decision making for public policy. Proceedings of the National academy of Sciences 111(20), 7176–7184 (2014)
  * [20] Mualla, Y., Tchappi, I., Kampik, T., Najjar, A., Calvaresi, D., Abbas-Turki, A., Galland, S., Nicolle, C.: The quest of parsimonious xai: A human-agent architecture for explanation formulation. Artificial Intelligence 302, 103573 (2022)
  * [21] Mueller, S.T., Hoffman, R.R., Clancey, W., Emrey, A., Klein, G.: Explanation in human-ai systems: A literature meta-review, synopsis of key ideas and publications, and bibliography for explainable ai. arXiv preprint arXiv:1902.01876 (2019)
  * [22] Naiseh, M., Cemiloglu, D., Al Thani, D., Jiang, N., Ali, R.: Explainable recommendations and calibrated trust: two systematic user errors. Computer 54(10), 28–37 (2021)
  * [23] Naiseh, M., Jiang, N., Ma, J., Ali, R.: Personalising explainable recommendations: literature and conceptualisation. In: World Conference on Information Systems and Technologies. pp. 518–533. Springer (2020)
  * [24] Poli, R., Kennedy, J., Blackwell, T.: Particle swarm optimization. Swarm intelligence 1(1), 33–57 (2007)
  * [25] Roundtree, K.A., Goodrich, M.A., Adams, J.A.: Transparency: Transitioning from human–machine systems to human-swarm systems. Journal of Cognitive Engineering and Decision Making 13(3), 171–195 (2019)
  * [26] Sokol, K., Flach, P.: Explainability fact sheets: a framework for systematic assessment of explainable approaches. In: Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency. pp. 56–67 (2020)
  * [27] Walker, P., Nunnally, S., Lewis, M., Kolling, A., Chakraborty, N., Sycara, K.: Neglect benevolence in human control of swarms in the presence of latency. In: 2012 IEEE International Conference on Systems, Man, and Cybernetics (SMC). pp. 3009–3014. IEEE (2012)


# On approximation of solutions of stochastic delay differential equations via
randomized Euler scheme

Paweł Przybyłowicz  AGH University of Krakow, Faculty of Applied Mathematics,
Al. A. Mickiewicza 30, 30-059 Kraków, Poland<EMAIL_ADDRESS>corresponding author ,  Yue Wu  Department of Mathematics and Statistics,
University of Strathclyde, Glasgow, UK<EMAIL_ADDRESS>and  Xinheng Xie
Department of Mathematics and Statistics, University of Strathclyde, Glasgow,
UK<EMAIL_ADDRESS>
###### Abstract.

We investigate existence, uniqueness and approximation of solutions to
stochastic delay differential equations (SDDEs) under Carathéodory-type drift
coefficients. Moreover, we also assume that both drift $f=f(t,x,z)$ and
diffusion $g=g(t,x,z)$ coefficient are Lipschitz continuous with respect to
the space variable $x$, but only Hölder continuous with respect to the delay
variable $z$. We provide a construction of randomized Euler scheme for
approximation of solutions of Carathéodory SDDEs, and investigate its upper
error bound. Finally, we report results of numerical experiments that confirm
our theoretical findings.

MSC (2020): 68Q25, 65C30, 60H10

###### Key words and phrases:

stochastic differential equations, constant delay, randomized Euler scheme,
Wiener process, Carathéodory-type conditions

##  1\. Introduction

In this paper, we investigate the efficiency of randomized numerical scheme
for simulating the stochastic delay differential equations (SDDEs) by
considering the SDDEs of the following form

(1.1)
$\begin{cases}\mathrm{d}X(t)=f(t,X(t),X(t-\tau))\,\mathrm{d}t+g(t,X(t),X(t-\tau))\,\mathrm{d}W(t)\\\
X(t)=x_{0},t\in[-\tau,0],\end{cases}$

with the constant time-lag $\tau\in(0,+\infty)$, fixed time horizon
$n\in\mathbb{N}$,
$f:[0,(n+1)\tau]\times\mathbb{R}^{d}\times\mathbb{R}^{d}\mapsto\mathbb{R}^{d}$,
$g:[0,(n+1)\tau]\times\mathbb{R}^{d}\times\mathbb{R}^{d}\mapsto\mathbb{R}^{d\times
m}$, and $x_{0}\in\mathbb{R}^{d}$. We assume that the drift coefficient
$f=f(t,x,z)$ is Borel measurable with respect to $t$, and (at least)
continuous with respect to $(x,z)$. Therefore, the Carathéodory type
conditions for $f$ are considered. For the diffusion coefficient $g(t,x,z)$ we
assume (at least) continuity with respect to all variables $(t,x,z)$.

Inspired by known Monte Carlo methods, randomized algorithms for approximation
of stochastic integrals and solutions of stochastic differential equations
(SDEs) have been recently considered in [5, 7, 12, 18, 15, 16, 20], to name
but a few. The idea is to wisely combine the probabilistic representation for
integrals with classical numerical schemes. A notable observation is that
compared to classical algorithms, their randomized counterparts may handle
irregular coefficients well, which relates to the flexible smoothness
requirement of Monte Carlo methods. Suitably chosen randomization might be
very helpful in order to handle time-irregularities in the right-hand side
functions both for ODEs ([1, 2, 6, 8, 9, 11]) and SDEs ([16, 15, 18, 12, 20,
19]). For instance, the classical Milstein method for non-autonomous SDEs
requires the drift term to be differentiable with respect to both temporal and
spatial variables in order to achieve an order of convergence one. Its
randomised version [12] can achieve the same order of convergence with only an
Lipschitz condition (resp. a Hölder continuity) on the drift wrt the spatial
variable (resp. the temporal variable).

Though SDEs can be regarded as a special case of stochastic delay differential
equations (SDDEs), the extention of the randomized numerical approaches from
SDEs to SDDEs is non-trivial. On the one hand, compared to SDEs, the
existence, uniqueness and $L^{p}$-Hölder regularity of the strong solution to
(1.1) is currently not known in the literature under conditions for $f$ and
$g$ considered in this paper. On the other hand, the time-delays may induce
instabilities in the basic SDDEs [14], and the presence of time-delays may
further influence the convergence speed [3]. Both aspects bring challenges.

In this article, we resolve these challenges one by one. For the study of the
exact solution to (1.1), instead of considering the SDDE over the entire
interval all at once, we follow a different way, known for CDDEs form in [6].
The entire time interval will be divided into multiple subintervals of the
length $\tau$ and the solution of the SDDE will be considered at each
subinterval separately. This will allow the SDDE to be converted into a
sequence of iterative SDEs with random coefficients and analyzed by induction,
where the delay term is treated as a random resource that has been given (see
(3.2)). The randomized Euler-Maruyama method is defined in the same manner,
i.e., iteratively. We keep the same grid for all the subintervals of length
$\tau$ so that the simulation obtained from the preceding subinterval will
directly be the delay input for the current subinterval. To assist the error
analysis, we introduce the auxiliary randomized Euler-Maruyama scheme. In the
case when $f$ or $g$ are Hölder contiuous with respect to $z$ we observe that
the numerical error accumulates over the subintervals. In particular, this may
suggest that this analysis is not valid for the infinite time horizon cases.

To summarise, the main contributions of the paper are as follows:

  * •

We show existence, uniqueness, and Hölder regularity of the strong solution to
(1.1) when both the drift $f(t,x,z)$ and diffusion $g(t,x,z)$ coefficients are
Borel measurable with respect to $t$, satisfy a global Lipschitz condition
with respect to $x$ andf global linear growth condition wrt $(x,z)$, but are
continuous with respect to the delay variable $z$ (see Theorem 3.1).

  * •

We perform rigorous error analysis of the randomized Euler scheme applied to
(1.1) when both drift coefficient $f(t,x,z)$ and diffusion coefficient
$g(t,x,z)$ satisfy a global Lipschitz condition with respect to $x$ and a
global Hölder condition with respect to $z$. Still, we assume that $f$ is only
Borel measurable with respect to $t$, but for $g$ we assume now that it is
also Hölder contiuous with respect to the time variable $t$. (Theorem 4.1).

  * •

We present an implementation of the randomized Euler-Maruyama method in Python
code and report results of numerical experiments that show stable error
behaviour as stated in Theorem 4.1.

The structure of the article is as follows. Basic notions, definitions
together with assumptions and the construction of the randomized Euler-
Maruyama scheme are given in Section 2. All Section 3 is devoted to the issue
of existence and uniqueness of strong solutions of the Carathéodory type SDDEs
(1.1). Section 4 contains proof of the main result of the paper (Theorem 3.1)
that states upper bounds on the error of the randomized Euler-Maruyama scheme.
In Section 5 we report results of numerical experiments with an exemplary
Python implementation.

##  2\. Preliminaries

Define $\mathbb{N}=\\{1,2,\ldots\\}$, $\mathbb{N}_{0}=\mathbb{N}\cup\\{0\\}$.
For an integer $k$, $[k]:=\\{1,\ldots,k\\}$ and $[k]_{0}:=\\{0\\}\cup[k]$. By
$|\cdot|$ we mean the Euclidean norm in $\mathbb{R}^{d}$ or the Frobenius norm
in $\mathbb{R}^{d\times m}$. We consider a complete probability space
$(\Omega,\Sigma,\mathbb{P})$. For a random variable
$X:\Omega\to\mathbb{R}^{d}$ we denote by
$\|X\|_{L^{p}(\Omega)}=(\mathbb{E}|X|^{p})^{1/p}$, where $p\in[2,+\infty)$. We
denote by $(\Sigma_{t})_{t\geq 0}$ a filtration, satisfying the usual
conditions, such that $W=(W(t))_{t\geq 0}$ is $m$-dimensional Wiener process
on $(\Omega,\Sigma,\mathbb{P})$ with respect to $(\Sigma_{t})_{t\geq 0}$. Let
$\Sigma_{\infty}=\sigma\Bigl{(}\bigcup_{t\geq 0}\Sigma_{t}\Bigr{)}$. For two
sub-$\sigma$-fields $\mathcal{A}$, $\mathcal{B}$ of $\Sigma$ we denote by
$\mathcal{A}\vee\mathcal{B}=\sigma(\mathcal{A}\cup\mathcal{B})$.

Let us fix the horizon parameter $n\in\mathbb{N}$. On the drift coefficient
$f:[0,(n+1)\tau]\times\mathbb{R}^{d}\times\mathbb{R}^{d}\mapsto\mathbb{R}^{d}$
we impose the following assumptions:

  1. (A1)

$f(t,\cdot,\cdot)\in C(\mathbb{R}^{d}\times\mathbb{R}^{d};\mathbb{R}^{d})$ for
all $t\in[0,(n+1)\tau]$,

  2. (A2)

$f(\cdot,x,z):[0,(n+1)\tau]\to\mathbb{R}^{d}$ is Borel measurable for all
$(x,z)\in\mathbb{R}^{d}\times\mathbb{R}^{d}$,

  3. (A3)

There exist $K_{f}\in(0,\infty)$ such that for all $t\in[0,(n+1)\tau]$,
$x,x_{1},x_{2},z\in\mathbb{R}^{d}$

(2.1) $\displaystyle\begin{split}&|f(t,x,z)|\leq K_{f}(1+|x|+|z|),\\\
&|f(t,x_{1},z)-f(t,x_{2},z)|\leq K_{f}|x_{1}-x_{2}|.\end{split}$

For the diffusion coefficient
$g:[0,(n+1)\tau]\times\mathbb{R}^{d}\times\mathbb{R}^{d}\mapsto\mathbb{R}^{d\times
m}$ we impose the following assumptions:

  1. (B1)

$g(t,\cdot,\cdot)\in C(\mathbb{R}^{d}\times\mathbb{R}^{d};\mathbb{R}^{d\times
m})$ for all $t\in[0,(n+1)\tau]$,

  2. (B2)

$g(\cdot,x,z):[0,(n+1)\tau]\to\mathbb{R}^{d\times m}$ is Borel measurable for
all $(x,z)\in\mathbb{R}^{d}\times\mathbb{R}^{d}$,

  3. (B3)

There exists $K_{g}\in(0,\infty)$ such that for all $t\in[0,(n+1)\tau]$,
$x,x_{1},x_{2},z\in\mathbb{R}^{d}$

(2.2) $\displaystyle\begin{split}&|g(t,x,z)|\leq K_{g}(1+|x|+|z|),\\\
&|g(t,x_{1},z)-g(t,x_{2},z)|\leq K_{g}|x_{1}-x_{2}|.\end{split}$

In Section 3 we show that, under the assumptions (A1)-(A3), (B1)-(B3), the
SDDE (1.1) has an unique strong solution. Next, in Section 4 we investigate
error of the randomized Euler scheme under slightly stronger assumptions than
(A1)-(A3), (B1)-(B3).

Symbol | Meaning
---|---
$\gamma_{k}^{j}$ | uniformly distributed sample from $[0,1]$ for $j\in\mathbb{N}_{0}$ and $k\in\mathbb{N}$
$t_{k}^{j}$ |  $t_{k}^{j}=j\tau+kh$ for $k\in[N]_{0}$ and $j\in[n]_{0}$
$\theta_{k+1}^{j}$ | $\theta_{k+1}^{j}=t_{k}^{j}+h\gamma_{k+1}^{j}$
$\delta_{k+1}^{j}$ | $\delta_{k+1}^{j}=kh+h\gamma_{k+1}^{j}$
Table 1. Notations.

The aforementioned randomized Euler scheme is defined as follows. Fix the
discretization parameter $N\in\mathbb{N}$ and set

$t_{k}^{j}=j\tau+kh,\quad k\in[N]_{0},\ j\in[n]_{0},$

where

(2.3) $h=\frac{\tau}{N}.$

Note that for each $j$ the sequence $\\{t^{j}_{k}\\}_{k=0}^{N}$ provides
uniform discretization of the subinterval $[j\tau,(j+1)\tau]$. Let
$\\{\gamma_{k}^{j}\\}_{j\in\mathbb{N}_{0},k\in\mathbb{N}}$ be an iid sequence
of random variables, defined on the complete probability space
$(\Omega,\Sigma,\mathbb{P})$, where every $\gamma_{k}^{j}$ is uniformly
distributed on $[0,1]$. We assume that the $\sigma$-fields
$\sigma(\\{\gamma_{k}^{j}\\}_{j\in\mathbb{N}_{0},k\in\mathbb{N}})$ and
$\Sigma_{\infty}$ are independent. Then $W=(W(t))_{t\geq 0}$ is also the
Wiener process with respect to the extended filtration

(2.4)
$\tilde{\Sigma}_{t}=\Sigma_{t}\vee\sigma(\\{\gamma_{k}^{j}\\}_{j\in\mathbb{N}_{0},k\in\mathbb{N}}),\quad
t\geq 0.$

We set $y_{0}^{-1}=\ldots=y^{-1}_{N}=x_{0}$ and then for $j=[n]_{0}$,
$k=[N-1]_{0}$ we take

(2.5) $\displaystyle y_{0}^{j}=y^{j-1}_{N},$ (2.6) $\displaystyle
y_{k+1}^{j}=y_{k}^{j}+h\cdot
f(\theta_{k+1}^{j},y_{k}^{j},y_{k}^{j-1})+g(t_{k}^{j},y_{k}^{j},y_{k}^{j-1})(W(t_{k+1}^{j})-W(t_{k}^{j})),$

where $\theta_{k+1}^{j}=t_{k}^{j}+h\gamma_{k+1}^{j}$. As the output we obtain
the sequence of $\mathbb{R}^{d}$-valued random vectors
$\\{y_{k}^{j}\\}_{k\in[N]_{0},j\in[n]_{0}}$ that provides a discrete
approximation of the values $\\{X(t_{k}^{j})\\}_{k\in[N]_{0},j\in[n]_{0}}$. By
induction we get that for all $j\in[n]_{0}$, $k\in[N]_{0}$

$\displaystyle\sigma(\\{y_{k}^{j}\\})\subset\sigma\Bigl{(}\\{\gamma_{1}^{0}\ldots,\gamma_{N}^{0},\ldots,\gamma_{1}^{j-1},\ldots,\gamma_{N}^{j-1},\gamma_{1}^{j},\ldots,\gamma_{k}^{j}\\}\Bigr{)}$
(2.7)
$\displaystyle\quad\quad\vee\sigma\Bigl{(}\\{W(t_{0}^{0}),\ldots,W(t_{N}^{0}),\ldots,W(t_{0}^{j}),\ldots,W(t_{k}^{j})\\}\Bigr{)}.$

As the horizon parameter $n$ is fixed, the randomized Euler scheme uses $O(N)$
evaluations of $f$ (with a constant in the ’$O$’ notation that depends on $n$
but not on $N$).

The aim is to establish upper bounds on the $L^{p}(\Omega)$-error

(2.8) $\Bigl{\|}\max\limits_{0\leq k\leq
N}|X(t_{k}^{j})-y_{k}^{j}|\Bigl{\|}_{L^{p}(\Omega)}$

for all $j=0,1,\ldots,n$.

##  3\. Properties of solutions to Carathéodory SDDEs

We take into account the semi-flow property holds for SDDE (1.1). Namely, we
define

(3.1) $\phi_{l}(t):=X(t+l\tau),\quad t\in[0,\tau],\quad l=-1,0,1,\ldots,n$

and, in particular, $\phi_{-1}(t)=x_{0}$ for $t\in[0,\tau]$. Using change of
variable formula for Lebesgue and Itô integrals we arrive at the following SDE
with random coefficients

(3.2)
$\begin{cases}\mathrm{d}\phi_{l}(t)=f_{l}\big{(}t,\phi_{l}(t)\big{)}\,\mathrm{d}t+g_{l}\big{(}t,\phi_{l}(t)\big{)}\,\mathrm{d}W_{l}(t),\quad
t\in[0,\tau],\\\ \phi_{l}(0)=\phi_{l-1}(\tau),\end{cases}$

where the random fields
$f_{l}:\mathbb{R}\times\mathbb{R}^{d}\times\Omega\to\mathbb{R}^{d}$ and
$g_{l}:\mathbb{R}\times\mathbb{R}^{d}\times\Omega\to\mathbb{R}^{d\times m}$
are defined follows

(3.3) $\displaystyle f_{l}(t,x):=f\big{(}t+l\tau,x,\phi_{l-1}(t)\big{)},$
(3.4) $\displaystyle g_{l}(t,x):=g\big{(}t+l\tau,x,\phi_{l-1}(t)\big{)},$

and $W_{l}(t):=W(t+l\tau)$, $t\in[0,\tau]$, $x\in\mathbb{R}^{d}$ 111We can
also take $W_{l}(t):=W(t+l\tau)-W(l\tau)$ \- in both cases $W_{l}$ is a Wiener
process with respect to the filtration $(\Sigma_{t}^{l})_{t\in[0,\tau]}$=
$(\Sigma_{t+l\tau})_{t\in[0,\tau]}$, see, for example, Theorem 100, page 67 in
[21].. We also set

(3.5) $\displaystyle\Sigma^{-1}_{t}:=\\{\emptyset,\Omega\\},$ (3.6)
$\displaystyle\Sigma^{j}_{t}:=\Sigma_{t+j\tau},$

for $t\in[0,\tau]$, $j\in[n]_{0}$. The solution $X$ of (1.1) can be written as

(3.7)
$X(t)=\sum\limits_{j=-1}^{n}\phi_{j}(t-j\tau)\cdot\mathbf{1}_{[j\tau,(j+1)\tau]}(t),\quad
t\in[-\tau,(n+1)\tau].$

We state $L^{p}$-boundedness and regularity of the solution $X$ in the
following Theorem 3.1. Similar result is given in Theorem 3.1. at pages
156-157 in [13], however, the $L^{p}$ estimates and $L^{p}$-Hölder regularity
of the solution is not studied there.

######  Theorem 3.1.

Let $n\in\mathbb{N}_{0}$, $\tau\in(0,+\infty)$, $x_{0}\in\mathbb{R}^{d}$ and
let $f,g$ satisfy the assumptions (A1)-(A3), (B1)-(B3). Then there exists a
unique strong solution $X=X(x_{0},f,g)$ to (1.1) such that for $j\in[n]_{0}$
we have

(3.8) $\mathbb{E}\Bigl{(}\sup\limits_{0\leq
t\leq\tau}|\phi_{j}(t)|^{p}\Bigr{)}\leq K_{j},$

where $K_{-1}:=|x_{0}|^{p}$, $K=\max\\{K_{f},K_{g}\\}$,

(3.9)
$K_{j}=C_{p}\Bigl{(}K_{j-1}+c_{p}\tau^{p/2}K^{p}(\tau^{p/2}+1)(1+K_{j-1})\Bigr{)}\exp\Bigl{(}C_{p}\tau^{p}K^{p}(1+K^{p})\Bigr{)},$

and for all $j\in[n]_{0}$, $t,s\in[0,\tau]$ it holds

(3.10) $\|\phi_{j}(t)-\phi_{j}(s)\|_{L^{p}(\Omega)}\leq
c_{p}K(\tau^{1/2}+1)(1+K_{j-1}^{1/p}+K_{j}^{1/p})|t-s|^{1/2}.$

###### Proof.

We proceed by induction. We start with the case when $j=0$ and consider the
following SDE

(3.11)
$\begin{cases}\mathrm{d}\phi_{0}(t)=f_{0}(t,\phi_{0}(t))\,\mathrm{d}t+g_{0}(t,\phi_{0}(t))\,\mathrm{d}W_{0}(t),&t\in[0,\tau],\\\
\phi_{0}(0)=x_{0},\end{cases}$

with $f_{0}(t,x)=f(t,x,\phi_{-1}(t))=f(t,x,x_{0})$,
$g_{0}(t,x)=f(t,x,\phi_{-1}(t))=g(t,x,x_{0})$. Moreover, by (2.1), (2.2) we
have for all $t\in[0,\tau]$, $x,y\in\mathbb{R}^{d}$ that

(3.12)
$\max\\{|f_{0}(t,x)|,|g_{0}(t,x)|\\}\leq\max\\{K_{f},K_{g}\\}(1+|x_{0}|+|x|),$

and

(3.13)
$\max\\{|f_{0}(t,x)-f_{0}(t,y)|,|g_{0}(t,x)-g_{0}(t,y)|\\}\leq\max\\{K_{f},K_{g}\\}|x-y|.$

Therefore, by Proposition 3.28, page 187 in [17] we have that there exists a
unique strong solution $\phi_{0}:[0,\tau]\times\Omega\to\mathbb{R}^{d}$ of
(3.11) that is adapted to $(\Sigma^{0}_{t})_{t\in[0,\tau]}$. By Remark 3.29,
page 188 in [17], the solution $\phi_{0}$ satisfies (3.8) with $j=0$ and

(3.14)
$K_{0}=C_{p}\Bigl{[}|x_{0}|^{p}+c_{p}\tau^{p/2}K^{p}(1+\tau^{p/2})(1+|x_{0}|^{p})\Bigr{]}\exp\Bigl{(}C_{p}\tau^{p}K^{p}(1+K^{p})\Bigr{)},$

with $K=\max\\{K_{f},K_{g}\\}$. In addition, $\phi_{0}$ satisfies (3.10) for
$j=0$.

Let us now assume that for some $j\in[n-1]_{0}$ there exists, adapted to
$(\Sigma^{j}_{t})_{t\in[0,\tau]}$, a unique strong solution
$\phi_{j}:[0,\tau]\times\Omega\to\mathbb{R}^{d}$ of

(3.15)
$\begin{cases}\mathrm{d}\phi_{j}(t)=f_{j}(t,\phi_{j}(t))\,\mathrm{d}t+g_{j}(t,\phi_{j}(t))\,\mathrm{d}W_{j}(t),&t\in[0,\tau],\\\
\phi_{j}(0)=\phi_{j-1}(\tau),\end{cases}$

that satisfies (3.8), (3.10), where $f_{j}(t,x)=f(t+j\tau,x,\phi_{j-1}(t))$,
$g_{j}(t,x)=g(t+j\tau,x,\phi_{j-1}(t))$. We consider the following SDE

(3.16)
$\begin{cases}\mathrm{d}\phi_{j+1}(t)=f_{j+1}(t,\phi_{j+1}(t))\,\mathrm{d}t+g_{j+1}(t,\phi_{j+1}(t))\,\mathrm{d}W_{j+1}(t),&t\in[0,\tau],\\\
\phi_{j+1}(0)=\phi_{j}({\tau}),\end{cases}$

with $f_{j+1}(t,x)=f(t+(j+1)\tau,x,\phi_{j}(t))$,
$g_{j+1}(t,x)=g(t+(j+1)\tau,x,\phi_{j}(t))$. Since the process $\phi_{j}$ is
adapted to $(\Sigma^{j}_{t})_{t\in[0,\tau]}$,
$\Sigma^{j}_{t}\subset\Sigma^{j+1}_{t}$ and has continuous trajectories, for
all $x\in\mathbb{R}^{d}$ the processes $(f_{j+1}(t,x))_{t\in[0,\tau]}$,
$(g_{j+1}(t,x))_{t\in[0,\tau]}$ are
$(\Sigma^{j+1}_{t})_{t\in[0,\tau]}$-progressively measurable. Moreover, by
(2.1), (2.2) for all $(t,x)\in[0,\tau]\times\mathbb{R}^{d}$

(3.17) $\max\\{|f_{j+1}(t,x)|,|g_{j+1}(t,x)|\\}\leq K(1+|\phi_{j}(t)|)+K|x|,$

and for all $t\in[0,\tau]$, $x,y\in\mathbb{R}^{d}$ it holds

(3.18) $\max\\{|f_{j+1}(t,x)-f_{j+1}(t,y)|,|g_{j+1}(t,x)-g_{j+1}(t,y)|\\}\leq
K|x-y|.$

Hence, by by Proposition 3.28, page 187 in [17] there exists a unique strong
solution solution $\phi_{j+1}:[0,\tau]\times\Omega\to\mathbb{R}^{d}$ of
(3.16). By the inductive assumption and Remark 3.29, page 188 in [17] we get
that

(3.19) $\displaystyle\mathbb{E}\Bigl{(}\sup\limits_{0\leq
t\leq\tau}|\phi_{j+1}(t)|^{p}\Bigr{)}$ $\displaystyle\leq
C_{p}\Biggl{(}\mathbb{E}|\phi_{j}(\tau)|^{p}+\mathbb{E}\Bigl{(}\int\limits_{0}^{\tau}K(1+|\phi_{j}(s)|)\,\mathrm{d}s\Bigr{)}^{p}+\mathbb{E}\Bigl{(}\int\limits_{0}^{\tau}K^{2}(1+|\phi_{j}(s)|)^{p/2}\,\mathrm{d}s\Bigr{)}^{p}\Biggr{)}$
$\displaystyle\qquad\times\exp\Bigl{(}C_{p}\tau^{p-1}\int\limits_{0}^{\tau}(K^{p}+K^{2p})\,\mathrm{d}s\Bigr{)}$
$\displaystyle\leq
C_{p}\Bigl{(}K_{j}+c_{p}\tau^{p/2}K^{p}(\tau^{p/2}+1)(1+K_{j})\Bigr{)}\exp\Bigl{(}C_{p}\tau^{p}K^{p}(1+K^{p})\Bigr{)}=K_{j+1},$

and therefore, by the Hölder and Burkholder inequalities, we get for
$s,t\in[0,\tau]$, $s<t$

$\displaystyle\mathbb{E}|\phi_{j+1}(t)-\phi_{j+1}(s)|^{p}\leq
C_{p}\Bigl{[}(t-s)^{p-1}\int\limits_{s}^{t}\mathbb{E}|f_{j+1}(u,\phi_{j+1}(u))|^{p}\,\mathrm{d}u$
(3.20)
$\displaystyle+\hat{C}_{p}(t-s)^{\frac{p-2}{2}}\int\limits_{s}^{t}\mathbb{E}|g_{j+1}(u,\phi_{j+1}(u))|^{p}\,\mathrm{d}u\Bigr{]}\leq\bar{K}_{j+1}(t-s)^{p/2},$

where $\bar{K}_{j+1}=c_{p}^{p}K^{p}(\tau^{p/2}+1)(1+K_{j}+K_{j+1})$. This ends
the inductive proof. ∎

##  4\. Error analysis for the randomized Euler algorithm

In this section we provide error analysis for randomized Euler scheme under
slightly stronger assumptions than those stated in Section 2. Namely, for the
drift coefficient we assume that instead of (A3) it satisfies what follows:

  * (A3’)

There exist $\alpha_{1}\in(0,1]$, $\bar{K}_{f},L_{f}\in(0,\infty)$ such that
for all $t\in[0,(n+1)\tau]$

(4.1) $|f(t,0,0)|\leq\bar{K}_{f},$

and for all $t\in[0,(n+1)\tau]$, $x_{1},x_{2},z_{1},z_{2}\in\mathbb{R}^{d}$

(4.2) $|f(t,x_{1},z_{1})-f(t,x_{2},z_{2})|\leq
L_{f}(|x_{1}-x_{2}|+|z_{1}-z_{2}|^{\alpha_{1}}).$

For the diffusion coefficient we impose the following assumption, that is
stronger than (B1), (B2), and (B3):

  * (B3’)

There exist $\alpha_{2},\varrho\in(0,1]$, $\bar{K}_{g},L_{g}\in(0,\infty)$
such that for all $t\in[0,(n+1)\tau]$, $x,z\in\mathbb{R}^{d}$

(4.3)
$|g(t_{1},x,z)-g(t_{2},x,z)|\leq\bar{K}_{g}(1+|x|+|z|)|t_{1}-t_{2}|^{\varrho},$

and for all $t\in[0,(n+1)\tau]$, $x_{1},x_{2},z_{1},z_{2}\in\mathbb{R}^{d}$

(4.4) $|g(t,x_{1},z_{1})-g(t,x_{2},z_{2})|\leq
L_{g}(|x_{1}-x_{2}|+|z_{1}-z_{2}|^{\alpha_{2}}).$

Note that for any $f$ that satisfies the assumption (A3’) it holds for all
$t\in[0,(n+1)\tau]$, $x,z\in\mathbb{R}^{d}$

(4.5) $|f(t,x,z)|\leq K_{f}(1+|x|+|z|),$

with $K_{f}=\bar{K}_{f}+L_{f}$, while for any $g$ satisfying (B3’) we have for
all $t\in[0,(n+1)\tau]$, $x,z\in\mathbb{R}^{d}$

(4.6) $|g(t,x,z)|\leq K_{g}(1+|x|+|z|),$

with $K_{g}=|g(0,0,0)|+L_{g}+\bar{K}_{g}((n+1)\tau)^{\varrho}$.

In order to perform error analysis, we define the auxiliary randomized Euler-
Maruyama scheme as follows:

(4.7) $\displaystyle\bar{y}_{0}^{0}=y^{0}_{0}=y^{-1}_{N}=x_{0},$ (4.8)
$\displaystyle\bar{y}_{k+1}^{0}=\bar{y}_{k}^{0}+h\cdot
f_{0}(\theta_{k+1}^{0},\bar{y}_{k}^{0})+g_{0}(t_{k}^{0},\bar{y}_{k}^{0})\Delta_{k}^{0}W,\
k=0,1,\ldots,N-1,$

and for $l=0,1,\ldots,n-1$

(4.9) $\displaystyle\bar{y}_{0}^{l+1}=y^{l+1}_{0}=y^{l}_{N},$ (4.10)
$\displaystyle\bar{y}_{k+1}^{l+1}=\bar{y}_{k}^{l+1}+h\cdot
f_{l+1}(\delta_{k+1}^{l+1},\bar{y}_{k}^{l+1})+g_{l+1}(t_{k}^{0},\bar{y}_{k}^{l+1})\Delta_{k}^{l+1}W,\
k=0,1,\ldots,N-1.$

where $\delta_{k+1}^{l+1}=kh+\gamma_{k+1}^{l+1}h$ and
$\Delta_{k}^{l+1}W:=W(t_{k+1}^{l+1})-W(t_{k}^{l+1})$ for $l=-1,0,\ldots,n-1$.

Note that $\delta_{k+1}^{l+1}$ is uniformly distributed in
$(t_{k}^{0},t_{k+1}^{0})$ and
$\theta_{k+1}^{l+1}=\delta_{k+1}^{l+1}+(l+1)\tau$ is uniformly distributed in
$(t_{k}^{l+1},t_{k+1}^{l+1})$. For $N\geq 2$ we have that $h\in(0,\tau)$,
which gives that $t_{k}^{l+1}>t_{k+1}^{l}$ and
$\Sigma_{t_{k+1}^{l}}\subset\Sigma_{t_{k}^{l+1}}$. This fact and Lemma 6.1
imply that for
$\phi_{l}(\delta_{k+1}^{l+1})=X(t_{k}^{l}+h\gamma_{k+1}^{l+1})$, where
$\phi_{l}$ is defined in (3.1), we have

(4.11)
$\sigma(\phi_{l}(\delta_{k+1}^{l+1}))\subset\sigma(\\{\gamma_{k+1}^{l+1}\\})\vee\Sigma_{t_{k+1}^{l}}\subset\sigma(\\{\gamma_{k+1}^{l+1}\\})\vee\Sigma_{t_{k}^{l+1}},$

and hence, $\phi_{l}(\delta_{k+1}^{l+1})$ is independent of
$\Delta_{k}^{l+1}W$. Moreover, it follows from (3.3), (4.10) that

$\displaystyle\bar{y}_{k+1}^{l+1}=\bar{y}_{k}^{l+1}+h\cdot
f(t_{k}^{l+1}+h\gamma_{k+1}^{l+1},\bar{y}_{k}^{l+1},\phi_{l}(\delta_{k+1}^{l+1}))$
(4.12)
$\displaystyle\quad\quad+g(t_{k}^{l+1},\bar{y}_{k}^{l+1},\phi_{l}(t_{k}^{l+1}))\cdot\Delta_{k}^{l+1}W.$

Hence, by (4), (4.11), and induction we get for $j\in[n]_{0}$ and
$k\in[N]_{0}$ that

(4.13)
$\sigma(\bar{y}_{k}^{j})\subset\Sigma_{t_{k}^{j}}\vee\sigma(\\{\gamma_{1}^{0}\ldots,\gamma_{N}^{0},\ldots,\gamma_{1}^{j-1},\ldots,\gamma_{N}^{j-1},\gamma_{1}^{j},\ldots,\gamma_{k}^{j}\\}).$

Therefore, $\bar{y}_{k}^{j}$ is measurable with respect to larger
$\sigma$-field than $y_{k}^{j}$ (see (2)). Note that $\bar{y}^{l}_{k}$ is not
implementable. However, we use $\bar{y}^{l}_{k}$ only in order to estimate the
error (2.8) of (implementable scheme) $y^{l}_{k}$.

######  Theorem 4.1.

Let $n\in\mathbb{N}_{0}$, $\tau\in(0,+\infty)$, $x_{0}\in\mathbb{R}^{d}$, and
let $f,g$ satisfy the assumptions (A1), (A2), (A3’) and (B1), (B2), (B3’) for
some $\varrho,\alpha_{1},\alpha_{2}\in(0,1]$. There exist
$C_{0},C_{1},\ldots,C_{n}\in(0,+\infty)$ such that for all
$N\geq\lceil\tau\rceil$ and $j=0,1,\ldots,n$ it holds

(4.14) $\Bigl{\|}\max\limits_{0\leq k\leq
N}|X(t_{k}^{j})-y_{k}^{j}|\Bigl{\|}_{L^{p}(\Omega)}\leq
C_{j}h^{\min\\{\varrho,\frac{1}{2}\\}\alpha^{j}},$

where $\alpha:=\min\\{\alpha_{1},\alpha_{2}\\}$, and, in particular, if
$\alpha=1$ then

(4.15) $\Bigl{\|}\max\limits_{0\leq k\leq
N}|X(t_{k}^{j})-y_{k}^{j}|\Bigl{\|}_{L^{p}(\Omega)}\leq
C_{j}h^{\min\\{\varrho,\frac{1}{2}\\}}.$

###### Proof.

We start with the initial-vale problem (3.2) with $l=0$. Since
$\bar{y}_{0}^{0}=y_{0}^{0}=x_{0}$, $f_{0}(t,x)=f(t,x,x_{0})$ and
$g_{0}(t,x)=g(t,x,x_{0})$, we have that $\bar{y}_{k}^{0}=y_{k}^{0}$ for all
$k=0,\ldots,N$. Moreover, by (A1), (A2), (A3’) and (B1), (B2), (B3’) we have
that $f_{0}$ and $g_{0}$ is Borel measurable, and for all
$t,t_{1},t_{2}\in[0,\tau]$ and $x,y\in\mathbb{R}^{d}$

$\displaystyle|f_{0}(t,x)|\leq K_{f}(1+|x_{0}|+|x|),$ (4.16)
$\displaystyle|f_{0}(t,x)-f_{0}(t,y)|\leq L_{f}|x-y|.$

and

$\displaystyle|g_{0}(t,x)|\leq K_{g}(1+|x_{0}|+|x|),$ (4.17)
$\displaystyle|g_{0}(t,x)-g_{0}(t,y)|\leq K_{g}|x-y|$
$\displaystyle|g_{0}(t_{1},x)-g_{0}(t_{2},x)|\leq\bar{K}_{g}(1+|x|+|x_{0}|)|t_{1}-t_{2}|^{\varrho}.$

Since for $l=0$ we deal with ordinary SDE, by Theorem 3.1 and by using
analogous arguments as in the proof of Proposition 1 in [15] we get

$\displaystyle\Bigl{\|}\max\limits_{0\leq k\leq
N}|\phi_{0}(t_{k}^{0})-y_{k}^{0}|\Bigl{\|}_{L^{p}(\Omega)}\leq
C_{0}h^{\min\\{\varrho,\frac{1}{2}\\}},$

where $C_{0}$ does not depend on $N$. Since $\phi_{0}(t_{k}^{0})=X(t_{k}^{0})$
we get (4.14) for $j=0$.

Let us now assume that there exists $l\in\\{0,1,\ldots,n-1\\}$ for which there
exists $C_{l}\in(0,+\infty)$ such that for all $N\geq\lceil\tau\rceil$

(4.18) $\Bigl{\|}\max\limits_{0\leq k\leq
N}|\phi_{l}(t_{k}^{0})-y_{k}^{l}|\Bigl{\|}_{L^{p}(\Omega)}\leq
C_{l}h^{\min\\{\varrho,\frac{1}{2}\\}\alpha^{l}}.$

We consider the initial-value problem (3.2) for $\phi_{l+1}$. By (A1), (A2),
(A3’) and (B1), (B2), (B3’) we have that $f_{l+1}$ and $g_{l+1}$ are Borel
measurable, and for all $t,t_{1},t_{2}\in[0,\tau]$, $x,y\in\mathbb{R}^{d}$

$\displaystyle|f_{l+1}(t,x)|\leq K_{f}(1+|x|+|\phi_{l}(t)|),$ (4.19)
$\displaystyle|f_{l+1}(t,x)-f_{l+1}(t,y)|\leq L_{f}|x-y|.$

and

$\displaystyle|g_{l+1}(t,x)|\leq K_{g}(1+|x|+|\phi_{l}(t)|),$ (4.20)
$\displaystyle|g_{l+1}(t,x)-g_{l+1}(t,y)|\leq L_{g}|x-y|$
$\displaystyle|g_{l+1}(t_{1},x)-g_{l+1}(t_{2},x)|\leq\bar{K}_{g}(1+|x|+|\phi_{l}(t_{1})|)|t_{1}-t_{2}|^{\varrho}$
$\displaystyle\quad\quad+L_{g}|\phi_{l}(t_{1})-\phi_{l}(t_{2})|^{\alpha_{2}}.$

The following error decomposition holds

(4.21) $\displaystyle\Bigl{\|}\max\limits_{0\leq k\leq
N}|\phi_{l+1}(t_{k}^{0})-y_{k}^{l+1}|\Bigl{\|}_{L^{p}(\Omega)}$
$\displaystyle\leq\Bigl{\|}\max\limits_{0\leq k\leq
N}|\phi_{l+1}(t_{k}^{0})-\bar{y}_{k}^{l+1}|\Bigl{\|}_{L^{p}(\Omega)}$
$\displaystyle\quad+\Bigl{\|}\max\limits_{0\leq k\leq
N}|\bar{y}_{k}^{l+1}-y_{k}^{l+1}|\Bigl{\|}_{L^{p}(\Omega)}.$

Firstly, we estimate $\displaystyle{\Bigl{\|}\max\limits_{0\leq k\leq
N}|\bar{y}_{k}^{l+1}-y_{k}^{l+1}|\Bigl{\|}_{L^{p}(\Omega)}}$. For $k\in[N]$ we
get

$\displaystyle\bar{y}^{l+1}_{k}-y^{l+1}_{k}$
$\displaystyle=\sum\limits_{j=1}^{k}(\bar{y}^{l+1}_{j}-\bar{y}^{l+1}_{j-1})-\sum\limits_{j=1}^{k}(y^{l+1}_{j}-y^{l+1}_{j-1})$
$\displaystyle=h\sum\limits_{j=1}^{k}\Bigl{(}f(\theta_{j}^{l+1},\bar{y}^{l+1}_{j-1},\phi_{l}(\delta_{j}^{l+1}))-f(\theta_{j}^{l+1},y^{l+1}_{j-1},y^{l}_{j-1})\Bigr{)}$
$\displaystyle\quad+\sum\limits_{j=1}^{k}\Bigl{(}g(t_{j-1}^{l+1},\bar{y}^{l+1}_{j-1},\phi_{l}(t_{j-1}^{0}))-g(t_{j-1}^{l+1},y^{l+1}_{j-1},y^{l}_{j-1})\Bigr{)}\Delta_{j-1}^{l+1}W,$

where $\Delta_{j-1}^{l+1}W=W(t_{j}^{l+1})-W(t_{j-1}^{l+1})$. This gives by the
assumption (4.3) that

$\displaystyle|\bar{y}^{l+1}_{k}-y^{l+1}_{k}|^{p}$ $\displaystyle\leq
C_{p}L_{f}^{p}\Big{(}h\sum\limits_{j=1}^{k}|\bar{y}^{l+1}_{j-1}-y^{l+1}_{j-1}|+h\sum\limits_{j=1}^{k}|\phi_{l}(\delta_{j}^{l+1})-y^{l}_{j-1}|^{\alpha_{1}}\Big{)}^{p}$
$\displaystyle\quad+C_{p}\Big{|}\sum\limits_{j=1}^{k}\Bigl{(}g(t_{j-1}^{l+1},\bar{y}^{l+1}_{j-1},\phi_{l}(t_{j-1}^{0}))-g(t_{j-1}^{l+1},y^{l+1}_{j-1},y^{l}_{j-1})\Bigr{)}\Delta_{j-1}^{l+1}W\Big{|}^{p}$

Let us denote by

(4.22)
$G_{j-1}^{l+1}=g(t_{j-1}^{l+1},\bar{y}^{l+1}_{j-1},\phi_{l}(t_{j-1}^{0}))-g(t_{j-1}^{l+1},y^{l+1}_{j-1},y^{l}_{j-1}).$

Hence, for $k\in[N]$ we get that

$\displaystyle\mathbb{E}\Bigl{[}\max\limits_{0\leq i\leq
k}|\bar{y}^{l+1}_{i}-y^{l+1}_{i}|^{p}\Bigr{]}\leq
L_{f}^{p}C_{p}\tau^{p-1}h\sum\limits_{j=1}^{k}\mathbb{E}\Bigl{[}\max\limits_{0\leq
i\leq j-1}|\bar{y}^{l+1}_{i}-y^{l+1}_{i}|^{p}\Bigr{]}$ (4.23)
$\displaystyle+C_{p}L_{f}^{p}\tau^{p-1}h\sum\limits_{j=1}^{k}\mathbb{E}\Bigl{[}|\phi_{l}(\delta_{j}^{l+1})-y_{j-1}^{l}|^{\alpha_{1}p}\Bigr{]}+C_{p}\mathbb{E}\Bigl{[}\max\limits_{1\leq
i\leq
k}\Bigl{|}\sum\limits_{j=1}^{i}G_{j-1}^{l+1}\cdot\Delta_{j-1}^{l+1}W\Bigl{|}^{p}\Bigr{]}$

Moreover

$\displaystyle\mathbb{E}[|\phi_{l}(\delta_{j}^{l+1})-y^{l}_{j-1}|^{\alpha_{1}p}]$
$\displaystyle\leq
C_{p}\mathbb{E}[|\phi_{l}(\delta_{j}^{l+1})-\phi_{l}(t_{j-1}^{0})|^{\alpha_{1}p}]+C_{p}\mathbb{E}\Bigl{[}\max\limits_{0\leq
k\leq N}|\phi_{l}(t_{k}^{0})-y_{k}^{l}|^{\alpha_{1}p}\Bigr{]}$

where by Theorem 3.1, Jensen inequality (applied to the concave function
$[0,+\infty)\ni x\to x^{\alpha_{1}}$), and (4.18) we have

(4.24)
$\mathbb{E}[|\phi_{l}(\delta_{j}^{l+1})-\phi_{l}(t_{j-1}^{0})|^{\alpha_{1}p}]\leq\Bigl{(}\mathbb{E}[|\phi_{l}(\delta_{j}^{l+1})-\phi_{l}(t_{j-1}^{0})|^{p}]\Bigr{)}^{\alpha_{1}}\leq\bar{K}^{\alpha_{1}}_{l}h^{\alpha_{1}p/2},$

and

(4.25) $\mathbb{E}\Bigl{[}\max\limits_{0\leq k\leq
N}|\phi_{l}(t_{k}^{0})-y_{k}^{l}|^{\alpha_{1}p}\Bigr{]}\leq\Biggl{(}\mathbb{E}\Bigl{[}\max\limits_{0\leq
k\leq N}|\phi_{l}(t_{k}^{0})-y_{k}^{l}|^{p}\Bigr{]}\Biggr{)}^{\alpha_{1}}.$

Now define for all $t\in[0,t_{N}^{l+1}]$ the following stochastic process

$\displaystyle M(t):=\int_{0}^{t}\sum\limits_{j=1}^{N}G_{j-1}^{l+1}\cdot{\bf
1}_{[t_{j-1}^{l+1},t_{j}^{l+1})}(s)\,\mathrm{d}W(s).$

Note that by (4.22), (2), and (4.13) we have that

(4.26)
$\sigma(G_{j-1}^{l+1})\subset\tilde{\Sigma}_{t_{j-1}^{l+1}}=\Sigma^{l+1}_{t_{j-1}^{0}}\vee\sigma(\\{\gamma_{k}^{j}\\}_{j\in\mathbb{N}_{0},k\in\mathbb{N}}),$

and, hence, $G_{j-1}^{l+1}$ is independent of $\Delta_{j-1}^{l+1}W$.
Therefore, the stochastic Itô integral above is well-defined. Moreover, the
quadratic variation of the martingale $M$ for $t\in[0,t_{N}^{l+1}]$ is as
follows

$\displaystyle\langle M\rangle(t)$
$\displaystyle=\int_{0}^{t}\sum\limits_{j=1}^{N}|G_{j-1}^{l+1}|^{2}\cdot{\bf
1}_{[t_{j-1}^{l+1},t_{j}^{l+1})}(s)\,\mathrm{d}s$

and then for $k\in[N]$

$\displaystyle\langle M\rangle(t_{k}^{l+1})$
$\displaystyle=h\sum\limits_{j=1}^{k}|G_{j-1}^{l+1}|^{2}.$

From Burkholder-Davis-Gundy inequality (see, for example, Corollary 2.9, page
82 in [17]), Jensen’s inequality and the assumption (4.4) on $g$, we have that

$\displaystyle\mathbb{E}\Bigl{[}\max\limits_{1\leq i\leq
k}\Bigl{|}\sum\limits_{j=1}^{i}G_{j-1}^{l+1}\cdot\Delta_{j-1}^{l+1}W\Bigl{|}^{p}\Bigr{]}=\mathbb{E}\Bigl{[}\max\limits_{1\leq
i\leq k}|M(t_{i}^{l+1})|^{p}\Bigr{]}\leq\mathbb{E}\Bigl{[}\sup\limits_{0\leq
t\leq t_{k}^{l+1}}|M(t)|^{p}\Bigr{]}$ $\displaystyle\leq
C_{p}\mathbb{E}\Bigl{(}\langle M\rangle(t_{k}^{l+1})\Bigr{)}^{p/2}\leq
C_{p}\tau^{\frac{p}{2}-1}h\sum\limits_{j=1}^{k}|G_{j-1}^{l+1}|^{p}$
$\displaystyle\leq\bar{C}_{p}\tau^{\frac{p}{2}-1}L_{g}^{p}h\sum\limits_{j=1}^{k}\mathbb{E}\Bigl{[}\max\limits_{0\leq
i\leq j-1}|\bar{y}^{l+1}_{i}-y^{l+1}_{i}|^{p}\Bigr{]}$ (4.27)
$\displaystyle\quad\quad+\bar{C}_{p}\tau^{\frac{p}{2}}L_{g}^{p}\Bigl{(}\mathbb{E}\Bigl{[}\max\limits_{0\leq
k\leq N}|\phi_{l}(t_{k}^{0})-y_{k}^{l}|^{p}\Bigr{]}\Bigr{)}^{\alpha_{2}}.$

Combining (4), (4.24), (4.25), (4) and using the fact that
$y_{0}^{l+1}=\bar{y}_{0}^{l+1}$ we arrive for $k\in[N]$ at

$\displaystyle\mathbb{E}\Bigl{[}\max\limits_{0\leq i\leq
k}|\bar{y}^{l+1}_{i}-y^{l+1}_{i}|^{p}\Bigr{]}\leq
c_{1}h\sum\limits_{j=1}^{k-1}\mathbb{E}\Bigl{[}\max\limits_{0\leq i\leq
j}|\bar{y}^{l+1}_{i}-y^{l+1}_{i}|^{p}\Bigr{]}+c_{2}h^{\alpha_{1}p/2}$ (4.28)
$\displaystyle+c_{3}\Biggl{(}\mathbb{E}\Bigl{[}\max\limits_{0\leq k\leq
N}|\phi_{l}(t_{k}^{0})-y_{k}^{l}|^{p}\Bigr{]}\Biggr{)}^{\alpha_{1}}+c_{4}\Biggl{(}\mathbb{E}\Bigl{[}\max\limits_{0\leq
k\leq N}|\phi_{l}(t_{k}^{0})-y_{k}^{l}|^{p}\Bigr{]}\Biggr{)}^{\alpha_{2}}.$

By the discrete version of Gronwall’s lemma (see, for example, Lemma 2.1. in
[11]) we get

$\displaystyle\mathbb{E}\Bigl{[}\max\limits_{0\leq k\leq
N}|\bar{y}^{l+1}_{k}-y^{l+1}_{k}|^{p}\Bigr{]}\leq
K_{1,l}e^{K_{2,l}\tau}\Biggl{[}h^{\alpha_{1}p/2}+\Biggl{(}\mathbb{E}\Bigl{[}\max\limits_{0\leq
k\leq N}|\phi_{l}(t_{k}^{0})-y_{k}^{l}|^{p}\Bigr{]}\Biggr{)}^{\alpha_{1}}$
(4.29) $\displaystyle\quad\quad+\Biggl{(}\mathbb{E}\Bigl{[}\max\limits_{0\leq
k\leq
N}|\phi_{l}(t_{k}^{0})-y_{k}^{l}|^{p}\Bigr{]}\Biggr{)}^{\alpha_{2}}\Biggr{]}.$

We now establish an upper bound on $\displaystyle{\Bigl{\|}\max\limits_{0\leq
i\leq N}|\phi_{l+1}(t_{i}^{0})-\bar{y}_{i}^{l+1}|\Bigl{\|}_{L^{p}(\Omega)}}$.
For $k\in[N]$ we have

$\displaystyle\phi_{l+1}(t_{k}^{0})-\bar{y}^{l+1}_{k}=\phi_{l+1}(0)-\bar{y}_{0}^{l+1}+(\phi_{l+1}(t_{k}^{0})-\phi_{l+1}(t_{0}^{0}))-(\bar{y}^{l+1}_{k}-\bar{y}^{l+1}_{0})$
$\displaystyle=(\phi_{l}(t_{N}^{0})-y_{N}^{l})+\sum\limits_{j=1}^{k}(\phi_{l+1}(t_{j}^{0})-\phi_{l+1}(t_{j-1}^{0}))-\sum\limits_{j=1}^{k}(\bar{y}^{l+1}_{j}-\bar{y}^{l+1}_{j-1})$
$\displaystyle=(\phi_{l}(t_{N}^{0})-y_{N}^{l})+\sum\limits_{j=1}^{k}\Biggl{(}\int\limits_{t_{j-1}^{0}}^{t_{j}^{0}}f_{l+1}(s,\phi_{l+1}(s))\,\mathrm{d}s-hf_{l+1}(\delta_{j}^{l+1},\bar{y}^{l+1}_{j-1})\Biggr{)}$
$\displaystyle\quad+\sum\limits_{j=1}^{k}\Biggl{(}\int\limits_{t_{j-1}^{0}}^{t_{j}^{0}}g_{l+1}(s,\phi_{l+1}(s))\,\mathrm{d}W_{l+1}(s)-g_{l+1}(t_{j-1}^{0},\bar{y}_{j-1}^{l+1})\Delta_{j-1}^{l+1}W\Biggr{)}$
(4.30)
$\displaystyle=(\phi_{l}(t_{N}^{0})-y_{N}^{l})+\sum\limits_{i=1}^{6}S^{k}_{i,l+1},$

where

$\displaystyle S^{k}_{1,l+1}$
$\displaystyle=\sum\limits_{j=1}^{k}\Biggl{(}\int\limits_{t_{j-1}^{0}}^{t_{j}^{0}}f_{l+1}(s,\phi_{l+1}(s))\,\mathrm{d}s-hf_{l+1}(\delta_{j}^{l+1},\phi_{l+1}(\delta_{j}^{l+1}))\Biggr{)},$
$\displaystyle S^{k}_{2,l+1}$
$\displaystyle=h\sum\limits_{j=1}^{k}\Bigl{(}f_{l+1}(\delta_{j}^{l+1},\phi_{l+1}(\delta_{j}^{l+1}))-f_{l+1}(\delta_{j}^{l+1},\phi_{l+1}(t_{j-1}^{0}))\Bigr{)},$
$\displaystyle S^{k}_{3,l+1}$
$\displaystyle=h\sum\limits_{j=1}^{k}\Bigl{(}f_{l+1}(\delta_{j}^{l+1},\phi_{l+1}(t_{j-1}^{0}))-f_{l+1}(\delta_{j}^{l+1},\bar{y}^{l+1}_{j-1})\Bigr{)},$
$\displaystyle S^{k}_{4,l+1}$
$\displaystyle=\int\limits_{0}^{t_{k}^{0}}\sum\limits_{j=1}^{N}\big{(}g_{l+1}(s,\phi_{l+1}(s))-g_{l+1}(t_{j-1}^{0},\phi_{l+1}(s))\big{)}\mathbf{1}_{[t_{j-1}^{0},t_{j}^{0})}(s)\,\mathrm{d}W_{l+1}(s),$
$\displaystyle S^{k}_{5,l+1}$
$\displaystyle=\int\limits_{0}^{t_{k}^{0}}\sum\limits_{j=1}^{N}\big{(}g_{l+1}(t_{j-1}^{0},\phi_{l+1}(s))-g_{l+1}(t_{j-1}^{0},\phi_{l+1}(t_{j-1}^{0}))\big{)}\mathbf{1}_{[t_{j-1}^{0},t_{j}^{0})}(s)\,\mathrm{d}W_{l+1}(s),$
$\displaystyle S^{k}_{6,l+1}$
$\displaystyle=\int\limits_{0}^{t_{k}^{0}}\sum\limits_{j=1}^{N}\big{(}g_{l+1}(t_{j-1}^{0},\phi_{l+1}(t_{j-1}^{0}))-g_{l+1}(t_{j-1}^{0},\bar{y}_{j-1}^{l+1})\big{)}\mathbf{1}_{[t_{j-1}^{0},t_{j}^{0})}(s)\,\mathrm{d}W_{l+1}(s).$

We have that

(4.31)
$S_{1,l+1}^{k}=\int\limits_{0}^{t_{k}^{0}}Y_{l+1}(s)\,\mathrm{d}s-h\sum\limits_{k=1}^{k}Y_{l+1}(\delta_{j}^{l+1}),$

where $\delta_{j}^{l+1}=t^{0}_{j-1}+h\gamma_{j}^{l+1}$,
$Y_{l+1}(t)=f_{l+1}(t,\phi_{l+1}(t))=f\big{(}t+(l+1)\tau,\phi_{l+1}(t),\phi_{l}(t)\big{)}$,
and $\sigma((Y(t))_{t\in[0,\tau]})\subset\Sigma_{\infty}$. Hence, the process
$Y$ is independent of the $\sigma$-field
$\sigma(\\{\gamma_{k}^{j}\\}_{j\in\mathbb{N}_{0},k\in\mathbb{N}})$. Moreover,
by Theorem 3.1 we arrive at

(4.32)
$\|f_{l+1}(\cdot,\phi_{l+1}(\cdot))\|_{L^{p}([0,\tau]\times\Omega;\mathbb{R}^{d})}\leq
T^{1/p}C_{p}K_{f}(1+K_{l}+K_{l+1})^{1/p}<+\infty.$

Therefore, by Theorem 4.1 in [12] we obtain

(4.33) $\Bigl{\|}\max\limits_{1\leq k\leq
N}|S^{k}_{1,l+1}|\Bigl{\|}_{L^{p}(\Omega)}\leq
2C_{p}\tau^{\frac{p-2}{2p}}(1+K_{l})(1+K_{l+1})h^{1/2}.$

By Jensen’s inequality we get

$\displaystyle\max\limits_{1\leq k\leq
N}|S^{k}_{2,l+1}|^{p}\leq\tau^{p-1}L_{f}^{p}h\sum\limits_{j=1}^{N}|\phi_{l+1}(\delta_{j}^{l+1})-\phi_{l+1}(t_{j-1}^{0})|^{p}.$

Thus, by Theorem 3.1

(4.34) $\displaystyle\Bigl{\|}\max\limits_{1\leq k\leq
N}|S^{k}_{2,l+1}|\Bigl{\|}_{L^{p}(\Omega)}$ $\displaystyle\leq L_{f}c_{p}\tau
K(\tau^{1/2}+1)(1+K_{l}^{1/p}+K_{l+1}^{1/p})h^{1/2}.$

Moreover,

(4.35) $\displaystyle\mathbb{E}\Bigl{[}\max\limits_{1\leq i\leq
k}|S^{i}_{3,l+1}|^{p}\Bigr{]}\leq
C_{p}L_{f}^{p}\tau^{p-1}h\mathbb{E}|\phi_{l}(t_{N}^{0})-y_{N}^{l}|^{p}$
$\displaystyle+C_{p}L_{f}^{p}\tau^{p-1}h\sum\limits_{j=1}^{k-1}\mathbb{E}\Bigl{[}\max\limits_{0\leq
i\leq j}|\phi_{l+1}(t_{i}^{0})-\bar{y}^{l+1}_{i}|^{p}\Bigr{]}.$

Regarding $S_{4,l+1}^{k}$ we shall apply Burkholder-Davis-Gundy inequality
(see Corollary 2.9, page 82 in [17]), Theorem 3.1 and (4) on $g_{l+1}$, and
get

(4.36) $\displaystyle\begin{split}&\mathbb{E}\Bigl{[}\max\limits_{1\leq k\leq
N}|S^{k}_{4,l+1}|^{p}\Bigr{]}\\\ &\leq
C_{p}\mathbb{E}\Bigg{(}\int\limits_{0}^{t_{N}^{0}}\sum\limits_{j=1}^{N}\big{|}g_{l+1}(s,\phi_{l+1}(s))-g_{l+1}(t_{j-1}^{0},\phi_{l+1}(s))\big{|}^{2}\mathbf{1}_{[t_{j-1}^{0},t_{j}^{0})}(s)\,\mathrm{d}s\Bigg{)}^{p/2}\\\
&=C_{p}\mathbb{E}\Bigg{(}\sum\limits_{j=1}^{N}\int\limits_{t_{j-1}^{0}}^{t_{j}^{0}}\big{|}g_{l+1}(s,\phi_{l+1}(s))-g_{l+1}(t_{j-1}^{0},\phi_{l+1}(s))\big{|}^{2}\,\mathrm{d}s\Bigg{)}^{p/2}\\\
&\leq
C_{p}N^{\frac{p}{2}-1}\sum\limits_{j=1}^{N}\mathbb{E}\Bigg{(}\int\limits_{t_{j-1}^{0}}^{t_{j}^{0}}\big{|}g_{l+1}(s,\phi_{l+1}(s))-g_{l+1}(t_{j-1}^{0},\phi_{l+1}(s))\big{|}^{2}\,\mathrm{d}s\Bigg{)}^{p/2}\\\
&\leq
C_{p}\tau^{\frac{p}{2}-1}\sum\limits_{j=1}^{N}\int\limits_{t_{j-1}^{0}}^{t_{j}^{0}}\mathbb{E}|g_{l+1}(s,\phi_{l+1}(s))-g_{l+1}(t_{j-1}^{0},\phi_{l+1}(s))|^{p}\,\mathrm{d}s\\\
&\leq\tilde{C}_{1,l}\sum\limits_{j=1}^{N}\int\limits_{t_{j-1}^{0}}^{t_{j}^{0}}|s-t_{j-1}^{0}|^{p\varrho}\cdot\mathbb{E}\big{(}1+|\phi_{l+1}(s)|+|\phi_{l}(s)|)^{p}\,\mathrm{d}s\\\
&\qquad+\tilde{C}_{2,l}\sum\limits_{j=1}^{N}\int\limits_{t_{j-1}^{0}}^{t_{j}^{0}}\mathbb{E}\big{|}\phi_{l}(s)-\phi_{l}(t_{j-1}^{0})\big{|}^{p\alpha_{2}}\,\mathrm{d}s\\\
&\leq\tilde{K}_{1,l}h^{p\varrho}+\tilde{C}_{2,l}\sum\limits_{j=1}^{N}\int\limits_{t_{j-1}^{0}}^{t_{j}^{0}}\Bigl{(}\mathbb{E}\big{|}\phi_{l}(s)-\phi_{l}(t_{j-1}^{0})\big{|}^{p}\Bigr{)}^{\alpha_{2}}\,\mathrm{d}s\\\
&\leq\tilde{K}_{1,l}h^{p\varrho}+\tilde{K}_{2,l}h^{p\alpha_{2}/2}\leq\tilde{K}_{3,l}h^{p\min\\{\varrho,\alpha_{2}/2\\}}.\end{split}$

Following the similar arguments as in Eqn.(4.36), and utilising Theorem 3.1
together with the Assumption (4) on $g_{l+1}$ we get

(4.37) $\displaystyle\begin{split}&\mathbb{E}\Bigl{[}\max\limits_{1\leq k\leq
N}|S^{k}_{5,l+1}|^{p}\Bigr{]}\\\ &\leq
C_{p}\mathbb{E}\Bigg{(}\int\limits_{0}^{t_{N}^{0}}\sum\limits_{j=1}^{N}\big{|}g_{l+1}(t_{j-1}^{0},\phi_{l+1}(s))-g_{l+1}(t_{j-1}^{0},\phi_{l+1}(t_{j-1}^{0}))\big{|}^{2}\mathbf{1}_{[t_{j-1}^{0},t_{j}^{0})}(s)\,\mathrm{d}s\Bigg{)}^{p/2}\\\
&\leq
C_{p}L_{g}^{p}\mathbb{E}\Bigg{(}\sum\limits_{j=1}^{N}\int\limits_{t_{j-1}^{0}}^{t_{j}^{0}}\big{|}\phi_{l+1}(s)-\phi_{l+1}(t_{j-1}^{0})\big{|}^{2}\,\mathrm{d}s\Bigg{)}^{p/2}\\\
&\leq
C_{p}L_{g}^{p}N^{\frac{p}{2}-1}\sum\limits_{j=1}^{N}\mathbb{E}\Bigg{(}\int\limits_{t_{j-1}^{0}}^{t_{j}^{0}}\big{|}\phi_{l+1}(s)-\phi_{l+1}(t_{j-1}^{0})\big{|}^{2}\,\mathrm{d}s\Bigg{)}^{p/2}\\\
&\leq
C_{p}L_{g}^{p}\tau^{\frac{p}{2}-1}\sum\limits_{j=1}^{N}\int\limits_{t_{j-1}^{0}}^{t_{j}^{0}}\mathbb{E}\big{[}\big{|}\phi_{l+1}(s)-\phi_{l+1}(t_{j-1}^{0})\big{|}^{p}\big{]}\,\mathrm{d}s\leq\tilde{K}_{4,l}h^{p/2}.\end{split}$

For the last term $S^{k}_{6,l+1}$ we use similar arguments as above and obtain

$\displaystyle\mathbb{E}\Bigl{[}\max\limits_{1\leq i\leq
k}|S^{i}_{6,l+1}|^{p}\Bigr{]}\leq
C_{p}L_{g}^{p/2}\tau^{p/2-1}h\mathbb{E}|\phi_{l}(t_{N}^{0})-y^{l}_{N}|^{p}$
$\displaystyle+C_{p}L_{g}^{p/2}\tau^{p/2-1}h\sum\limits_{j=1}^{k-1}\mathbb{E}\Bigl{[}\max\limits_{0\leq
i\leq j}\big{|}\phi_{l+1}(t_{i}^{0})-\bar{y}^{l+1}_{i}\big{|}^{p}\Bigr{]}.$

Hence, from (4.30) and (4.35) we have for $k\in\\{1,2,\ldots,N\\}$

$\displaystyle\mathbb{E}\Bigl{[}\max\limits_{0\leq i\leq
k}|\phi_{l+1}(t_{i}^{0})-\bar{y}^{l+1}_{i}|^{p}\Bigr{]}\leq
K_{1}\mathbb{E}|\phi_{l}(t_{N}^{0})-y_{N}^{l}|^{p}$
$\displaystyle+c_{p}\sum\limits_{m\in\\{1,2,4,5\\}}\mathbb{E}\Bigl{[}\max\limits_{1\leq
k\leq N}|S^{k}_{m,l+1}|^{p}\Bigr{]}$
$\displaystyle+K_{2}h\sum\limits_{j=1}^{k-1}\mathbb{E}\Bigl{[}\max\limits_{0\leq
i\leq j}\big{|}\phi_{l+1}(t_{i}^{0})-\bar{y}^{l+1}_{i}\big{|}^{p}\Bigr{]}.$

Now by using Gronwall’s lemma (see, Lemma 2.1 in [11]), (4.18), and (4.33) to
(4.37) we get for all $k\in[N]$

$\displaystyle\mathbb{E}\Bigl{[}\max\limits_{0\leq i\leq
k}|\phi_{l+1}(t_{i}^{0})-\bar{y}^{l+1}_{i}|^{p}\Bigr{]}\leq
K_{3}\Bigl{(}\mathbb{E}|\phi_{l}(t_{N}^{0})-y_{N}^{l}|^{p}$
$\displaystyle+\sum\limits_{m\in\\{1,2,4,5\\}}\mathbb{E}\Bigl{[}\max\limits_{1\leq
k\leq N}|S^{k}_{m,l+1}|^{p}\Bigr{]}\Bigl{)},$

which gives

(4.38) $\Bigl{\|}\max\limits_{0\leq i\leq
N}|\phi_{l+1}(t_{i}^{0})-\bar{y}_{i}^{l+1}|\Bigl{\|}^{p}_{L^{p}(\Omega)}\leq
K_{5,l}\Bigl{(}\mathbb{E}\Bigl{[}\max\limits_{0\leq k\leq
N}|\phi_{l}(t_{k}^{0})-y^{l}_{k}|^{p}\Bigr{]}+h^{p\min\\{\varrho,\alpha_{2}/2\\}}\Bigr{)}.$

Combining (4.21), (4), and (4.38) we obtain

$\displaystyle\Bigl{\|}\max\limits_{0\leq i\leq
N}|\phi_{l+1}(t_{i}^{0})-y_{i}^{l+1}|\Bigl{\|}_{L^{p}(\Omega)}\leq
K_{6,l}\Bigl{(}h^{\min\\{\varrho,\alpha_{1}/2,\alpha_{2}/2\\}}+\Bigl{\|}\max\limits_{0\leq
i\leq N}|\phi_{l}(t_{i}^{0})-y_{i}^{l}|\Bigl{\|}_{L^{p}(\Omega)}$ (4.39)
$\displaystyle\quad\quad+\Bigl{\|}\max\limits_{0\leq i\leq
N}|\phi_{l}(t_{i}^{0})-y_{i}^{l}|\Bigl{\|}^{\alpha_{1}}_{L^{p}(\Omega)}+\Bigl{\|}\max\limits_{0\leq
i\leq
N}|\phi_{l}(t_{i}^{0})-y_{i}^{l}|\Bigl{\|}^{\alpha_{2}}_{L^{p}(\Omega)}\Bigr{)},$

and therefore

(4.40) $\Bigl{\|}\max\limits_{0\leq i\leq
N}|\phi_{l+1}(t_{i}^{0})-y_{i}^{l+1}|\Bigl{\|}_{L^{p}(\Omega)}\leq
C_{l+1}h^{\min\\{\varrho,\frac{1}{2}\\}\alpha^{l+1}},$

which ends the inductive part of the proof. Finally,
$\phi_{l+1}(t_{i}^{0})=\phi_{l+1}(ih)=X(ih+(l+1)\tau)=X(t_{i}^{l+1})$ and the
proof of (4.14) is finished. ∎

######  Remark 4.2.

We briefly comment on optimality of the defined algorithm in the Information-
Based Complexity sense, see [10]. In the special case
$\alpha_{1}=\alpha_{2}=1$ we have the optimal bound
$\Theta(h^{\min\\{\varrho,1/2\\}})$, which follows from Proposition 5.1 in
[18].

##  5\. Numerical experiments

In order to illustrate our theoretical findings we perform several numerical
experiments. We chose the following exemplary right-hand side functions:

(5.1)
$f_{i}(t,x,z)=k_{i}(t)\Bigl{(}x+0.01|z|^{\alpha_{1}}+\sin(10x)\cdot\cos(100|z|^{\alpha_{1}})\Bigr{)},$

and the diffusion is either additive

(5.2) $g_{1}(t,x,z)=0.5|\cos(2^{5}\pi t)|,$

or multiplicative

(5.3)
$g_{2}(t,x,z)=k(t)\Bigl{(}x+0.01|z|^{\alpha_{2}}+\cos(10x)\cdot\cos(100|z|^{\alpha_{2}})\Bigr{)},$

where, $\alpha_{1},\alpha_{2}\in(0,1]$, $k_{1}$ is the following periodic
function

(5.4)
$k_{1}(t)=\sum_{j=0}^{n}\Bigl{(}(j+1)\tau-t\Bigr{)}^{-1/\gamma_{1}}\cdot\mathbf{1}_{[j\tau,(j+1)\tau]}(t),\quad\gamma_{1}>2,$

which belongs to $L^{p}([0,(n+1)\tau])$, $k_{2}$ is a step function satisfying

(5.5) $\displaystyle
k_{2}(t)=\sum_{j=0}^{n}0.1\cdot(j+1)\cdot\mathbf{1}_{[j\tau,(j+1)\tau]}(t),$

and $k$ is given by

(5.6) $k(t)=t^{\gamma_{2}},\quad\gamma_{2}\in(0,1],$

which is $\gamma_{2}$-Hölder continuous. Note that formally $f_{1}$ does not
satisfy our assumptions, however, we get numerical evidence that we probably
could extend result of Theorem 4.1 to the case when $L_{f},L_{g}$ are
integrable funtions.
We implement randomized Euler-Maruyama scheme (2.5)-(2.6) using Python
programming language. Moreover, since for the right-hand side functions (5.1)
plus (5.2) or (5.1) plus (5.3) we do not know the exact solution $X(t)$, we
approximate the mean square error (2.8) for each $0\leq j\leq n$ with

$\left\|\max_{0\leq i\leq
N}|\tilde{y}_{i}^{j}-y_{i}^{j}|\right\|_{L^{2}(\Omega)}\approx\left(\frac{1}{K}\sum_{k=1}^{K}\max_{0\leq
i\leq
N}|\tilde{y}_{i}^{j}(\omega_{k})-y_{i}^{j}(\omega_{k})|^{2}\right)^{\frac{1}{2}},$

where $K\in\mathbb{N}$, $\\{\omega_{k}\\}_{k=1}^{K}$ represents the $k$th
realisation from the complete probability space, $y_{i}^{j}$ is the output of
the randomized Euler-Maruyama scheme on the initial mesh
$t_{i}^{j}\mathrel{\mathop{:}}=j\tau+ih$ and
$h\mathrel{\mathop{:}}=\frac{\tau}{N}$ for $i=0,\ldots,N-1$, while
$\tilde{y}_{i}^{j}$ is the reference solution obtained also from the
randomized Euler-Maruyama scheme but on the refined mesh
$\tilde{t}_{i}^{j}\mathrel{\mathop{:}}=j\tau+i\tilde{h}$ and
$\tilde{h}\mathrel{\mathop{:}}=\frac{h}{m}=\frac{\tau}{mN}$ for
$i=0,\ldots,mN-1$. Note that $\\{\omega_{k}\\}_{k=1}^{K}$ is generated on the
refined mesh.

The implementation of the randomized Euler-Maruyama method method is
straightforward. To evaluate the solution at time point $t^{j}_{i}=ih+j\tau$
within the interval $[j\tau,(j+1)\tau]$, we need two steps:

Step (j1): First simulate $\gamma\sim\mathcal{U}(0,1)$ and set random time
point $t^{j}_{i-1}+\gamma h\in[t^{j}_{i-1},t^{j}_{i}]$.

Step (j2): Compute $y_{i}^{j}$ as defined in (2.5) and (2.6).

Listing 1 shows an implementation of method (2.5) and (2.6) in the case of a
1-dimensional Wiener process ($m=1$) in Python.

Listing 1: A sample implementation of (2.5) and (2.6) in Python

⬇

1import numpy as np

2

3def f(t,x,z):

4 return […]

5

6def g(t,x,z):

7 return […]

8

9

10def randEM_full(tau, X0, h, f,g,n_taus):

11

12 # input: delay lag tau, stepsize h, initials X0,

13 # drift and diffusion functions f and g

14 # number of intervals of length tau n_taus

15 # output:

16 # one trajectory of the randomized Euler-Maruyama method

17

18 ###to get numerical evaluation:

19

20 #number of steps within one interval with length tau

21 N=int(tau/stepsize)

22

23 #setting initial conditions

24 sol = np.zeros((N+ 1,n_tau+1))+X0

25

26 #for each interval [j*tau, (j+1)*tau]

27 for j in range(1, n_taus+1):

28

29 sol[0,j] = sol[-1,j-1]

30

31 # collect the grid points over [j*tau, (j+1)*tau]

32 grid = j* tau + h *np.arange(0, N)

33

34

35 for i in range(1,N+1):

36

37 # step (j1):

38 gamma=np.random.rand()

39 rand_time=grid[i-1]+gamma*h

40

41 # step (j2):

42 drift=h*f(rand_time, sol[i-1,j], sol[i-1,j-1])

43 diff=g(grid[i-1], sol[i-1,j], sol[i-1,j-1]) \

44 *np.sqrt(h)*np.random.normal()

45

46 sol[i,j] = sol[i-1,j]+drift+diff

47

48

49 return sol

######  Example 5.1 (Additive noise).

In the following numerical tests we use (5.1) with (5.4) and (5.2) (So in this
case we formally have $\alpha_{2}=1$.). We fix the number of experiments
$K=1000$ for each $N=2^{l}$, $l=5,\ldots,10$, and the reference solution is
computed with stepsize $2^{-17}$; also, the horizon parameter is $n=3$. We get
the following results for $\gamma_{1}=3$:
letting $\alpha_{1}=0.1$, the negative mean square error slopes are $0.65$,
$0.65$, and $0.62$. See Figure 1(a);
letting $\alpha_{1}=0.5$, the negative mean square error slopes are $0.65$,
$0.64$, and $0.62$. See Figure 1(b);
letting $\alpha_{1}=1$, the negative mean square error slopes are $0.63$,
$0.63$, and $0.58$. See Figure 1(c);
while, for $\gamma_{1}=5$:
letting $\alpha_{1}=0.1$, the negative mean square error slopes are $0.60$,
$0.63$, and $0.61$. See Figure 2(a);
letting $\alpha_{1}=0.5$, the negative mean square error slopes are $0.65$,
$0.65$, and $0.62$. See Figure 2(b);
letting $\alpha_{1}=1$, the negative mean square error slopes are $0.63$,
$0.63$ and $0.59$. See Figure 2(c).

(a) $\alpha=0.1$.

(b) $\alpha=0.5$.

(c) $\alpha=1$.

Figure 1. Mean square errors slope for $\gamma=3$ and values of
$\alpha=0.1,0.5,1$ for (5.1) plus (5.2).

(a) $\alpha_{1}=0.1$.

(b) $\alpha_{1}=0.5$.

(c) $\alpha_{1}=1$.

Figure 2. Mean square errors slope for $\gamma_{1}=5$ and values of
$\alpha_{1}=0.1,0.5,1$ for (5.1) plus (5.2).

All the figures show that the error of $[j\tau,(j+1)\tau]$ is worse that the
error of $[(j-1)\tau,j\tau]$ for $j\in\\{1,2\\}$ though the changes in the
order of convergence from $[(j-1)\tau,j\tau]$ to $[j\tau,(j+1)\tau]$ are not
significant.

######  Example 5.2 (Multiplicative noise).

In the following numerical tests we use (5.1) with (5.4) and (5.3). We fix the
number of experiments $K=1000$ for each $N=2^{l}$, $l=5,\ldots,10$, and the
reference solution is computed with stepsize $2^{-17}$; also, the horizon
parameter is $n=3$. We fix $\gamma_{1}=5$ and vary $\gamma_{2}$, $\alpha_{1}$
and $\alpha_{2}$.

We get the following results for $\gamma_{1}=5$ and $\gamma_{2}=0.1$:
letting $\alpha_{1}=0.1$ and $\alpha_{2}=0.1$, the negative mean square error
slopes are $0.23$, $0.13$, and $0.11$. See Figure 3(a);
letting $\alpha_{1}=0.1$ and $\alpha_{2}=1$, the negative mean square error
slopes are $0.23$, $0.15$, and $0.14$. See Figure 3(c);
letting $\alpha_{1}=1$ and $\alpha_{2}=0.1$, the negative mean square error
slopes are $0.23$, $0.14$, and $0.11$. See Figure 3(b);
letting $\alpha_{1}=0.5$ and $\alpha_{2}=0.5$, the negative mean square error
slopes are $0.30$, $0.18$, and $0.22$. See Figure 3(d);
while, for $\gamma_{1}=5$ and $\gamma_{2}=0.5$:
letting $\alpha_{1}=0.1$ and $\alpha_{2}=0.1$, the negative mean square error
slopes are $0.31$, $0.15$, and $0.17$. See Figure 4(c);
letting $\alpha_{1}=1$ and $\alpha_{2}=0.1$, the negative mean square error
slopes are $0.31$, $0.15$, and $0.17$. See Figure 4(b);
letting $\alpha_{1}=0.1$ and $\alpha_{2}=1$, the negative mean square error
slopes are $0.31$, $0.16$, and $0.23$. See Figure 4(c);
letting $\alpha_{1}=0.5$ and $\alpha_{2}=0.5$, the negative mean square error
slopes are $0.31$, $0.18$, and $0.25$. See Figure 4(d);
while, for $\gamma_{1}=5$ and $\gamma_{2}=1$:
letting $\alpha_{1}=0.1$ and $\alpha_{2}=0.1$, the negative mean square error
slopes are $0.31$, $0.28$, and $0.25$. See Figure 5(c);
letting $\alpha_{1}=1$ and $\alpha_{2}=0.1$, the negative mean square error
slopes are $0.31$, $0.27$, and $0.24$. See Figure 5(b);
letting $\alpha_{1}=0.1$ and $\alpha_{2}=1$, the negative mean square error
slopes are $0.31$, $0.25$, and $0.22$. See Figure 5(c);
letting $\alpha_{1}=0.5$ and $\alpha_{2}=0.5$, the negative mean square error
slopes are $0.31$, $0.18$, and $0.25$. See Figure 5(d).

(a) $\alpha_{1}=0.1$ and $\alpha_{2}=0.1$.

(b) $\alpha_{1}=1$ and $\alpha_{2}=0.1$.

(c) $\alpha_{1}=0.1$ and $\alpha_{2}=1$.

(d) $\alpha_{1}=0.5$ and $\alpha_{2}=0.5$.

Figure 3. Mean square errors slope for $\gamma_{1}=5$ and $\gamma_{2}=0.1$ and
values of $(\alpha_{1},\alpha_{2})=(0.1,0.1),(1,0.1),(0.1,1),(0.5,0.5)$ for
(5.1) plus (5.3).

(a) $\alpha_{1}=0.1$ and $\alpha_{2}=0.1$.

(b) $\alpha_{1}=1$ and $\alpha_{2}=0.1$.

(c) $\alpha_{1}=0.1$ and $\alpha_{2}=1$.

(d) $\alpha_{1}=0.5$ and $\alpha_{2}=0.5$.

Figure 4. Mean square errors slope for $\gamma_{1}=5$ and $\gamma_{2}=0.5$ and
values of $(\alpha_{1},\alpha_{2})=(0.1,0.1),(1,0.1),(0.1,1),(0.5,0.5)$ for
(5.1) plus (5.3).

(a) $\alpha_{1}=0.1$ and $\alpha_{2}=0.1$.

(b) $\alpha_{1}=1$ and $\alpha_{2}=0.1$.

(c) $\alpha_{1}=0.1$ and $\alpha_{2}=1$.

(d) $\alpha_{1}=0.5$ and $\alpha_{2}=0.5$.

Figure 5. Mean square errors slope for $\gamma_{1}=5$ and $\gamma_{2}=1$ and
values of $(\alpha_{1},\alpha_{2})=(0.1,0.1),(1,0.1),(0.1,1),(0.5,0.5)$ for
(5.1) plus (5.3).

It can be observed that for each fixed $(\alpha_{1},\alpha_{2})$ pair and for
each fixed $[j\tau,(j+1)\tau]$ interval, the order of convergence increases
with $\gamma_{2}$; for each fixed $\gamma_{2}$ and for each fixed
$[j\tau,(j+1)\tau]$ interval, the negative slops for
$(\alpha_{1},\alpha_{2})=(0.1,0.1),(1,0.1),(0.1,1)$ are almost the same, which
are slightly less than the negative slop of
$(\alpha_{1},\alpha_{2})=(0.5,0.5)$; for each fixed $(\alpha_{1},\alpha_{2})$
pair and for each fixed $\gamma_{2}$, the negative slope decreases with $j$.
All these observations coincide with Theorem 4.1.

######  Example 5.3 (Multiplicative noise).

In the following numerical tests we use (5.1) with (5.5) and (5.3). We fix the
number of experiments $K=1000$ for each $N=2^{l}$, $l=5,\ldots,10$, and the
reference solution is computed with stepsize $2^{-17}$; also, the horizon
parameter is $n=3$. We vary $\gamma_{2}$, $\alpha_{1}$, but allow the same
value of $\alpha_{2}$ as $\alpha_{1}$, ie, $\alpha_{1}=\alpha_{2}=\alpha$.

We get the following results for $\gamma_{2}=0.1$:
letting $\alpha=0.1$, the negative mean square error slopes are $0.34$,
$0.31$, and $0.25$. See Figure 6(a);
letting $\alpha=0.5$, the negative mean square error slopes are $0.35$,
$0.25$, and $0.23$. See Figure 6(b);
letting $\alpha=1$, the negative mean square error slopes are $0.35$, $0.23$,
and $0.23$. See Figure 6(c);
while, for $\gamma_{2}=0.5$:
letting $\alpha=0.1$, the negative mean square error slopes are $0.30$,
$0.27$, and $0.27$. See Figure 6(d);
letting $\alpha=0.5$, the negative mean square error slopes are $0.31$,
$0.27$, and $0.24$. See Figure 6(e);
letting $\alpha=1$, the negative mean square error slopes are $0.34$, $0.27$,
and $0.26$. See Figure 6(f);
while, for $\gamma_{2}=1$:
letting $\alpha=0.1$, the negative mean square error slopes are $0.29$,
$0.30$, and $0.23$. See Figure 6(g);
letting $\alpha=0.5$, the negative mean square error slopes are $0.32$,
$0.27$, and $0.25$. See Figure 6(h);
letting $\alpha=1$, the negative mean square error slopes are $0.35$, $0.30$,
and $0.28$. See Figure 6(i).

(a) $\gamma_{2}=0.1$, and $\alpha=0.1$.

(b) $\gamma_{2}=0.1$ and $\alpha=0.5$.

(c) $\gamma_{2}=0.1$ and $\alpha=1$.

(d) $\gamma_{2}=0.5$, and $\alpha=0.1$.

(e) $\gamma_{2}=0.5$ and $\alpha=0.5$.

(f) $\gamma_{2}=0.5$ and $\alpha=1$.

(g) $\gamma_{2}=1$ and $\alpha=0.1$.

(h) $\gamma_{2}=1$ and $\alpha=0.5$.

(i) $\gamma_{2}=1$ and $\alpha=1$.

Figure 6. Mean square errors slope for (5.1) with (5.5) plus (5.3) at
$\gamma_{2}=0.1,0.5,1$ and values of $\alpha_{1}=\alpha_{2}=\alpha=0.1,0.5,1$.

One can compare the results horizontally or vertically in Figure 6. For each
fixed $(\alpha_{1},\alpha_{2})$ pair and for each fixed $\gamma_{2}$, the
negative slope in general decreases with $j$. Horizontally, each fixed
$\gamma_{2}$ and for each fixed $[j\tau,(j+1)\tau]$ interval, the error
decreases significantly with increasing $\alpha_{1}$. Vertically, for each
fixed $(\alpha_{1},\alpha_{2})$ pair and for each fixed $[j\tau,(j+1)\tau]$
interval, the numerical error decreases with $\gamma$. All these observations
coincide with Theorem 4.1.

##  6\. Appendix

######  Lemma 6.1.

Let $Y=(Y(t))_{t\geq 0}$ is $(\Sigma_{t})_{t\geq 0}$-progressively measurable
stochastic process and let $\xi:\Omega\to[a,b]$, $-\infty<a<b<+\infty$, is a
random variable on $(\Omega,\Sigma,\mathbb{P})$. Then $Y(\xi)$ is
$\sigma(\xi)\vee\Sigma_{b}$-measurable.

###### Proof.

Since $Y$ is progressively measurable we have that the mapping
$[a,b]\times\Omega\ni(t,\omega)\to Y(t,\omega)\in\mathbb{R}^{d}$ is
$\mathcal{B}([a,b])\otimes\Sigma_{b}$-to-$\mathcal{B}(\mathbb{R}^{d})$
measurable. Let us define

(6.1) $\Omega\ni\omega\to H(\omega)=(\xi(\omega),\omega),$

and $\mathcal{F}_{0}=\\{B\times F\ |\ B\in\mathcal{B}([a,b]),\
F\in\Sigma_{b}\\}$. Note that
$\mathcal{B}([a,b])\otimes\Sigma_{b}=\sigma(\mathcal{F}_{0})$. Since for any
$B\times F\in\mathcal{F}_{0}$ we have that $H^{-1}(B\times F)=\xi^{-1}(B)\cap
F\in\sigma(\xi)\vee\Sigma_{b}$, we get by Proposition 2.3., page 6 in [4] that
the function $H$ is
$\sigma(\xi)\vee\Sigma_{b}$-to-$\mathcal{B}([a,b])\otimes\Sigma_{b}$
measurable. Since

(6.2) $\Omega\ni\omega\to Y(\xi(\omega),\omega)=(Y\circ
H)(\omega)\in\mathbb{R}^{d},$

we get for any $B\in\mathcal{B}(\mathbb{R}^{d})$ that $(Y\circ
H)^{-1}(B)=H^{-1}(Y^{-1}(B))\in\sigma(\xi)\vee\Sigma_{b}$. This implies the
thesis. ∎

## References

  * [1] T. Bochacik, M. Goćwin, P. M. Morkisz, and P. Przybyłowicz.  Randomized Runge-Kutta method–Stability and convergence under inexact information.  J. Complex., 65:101554, 2021.
  * [2] T. Bochacik and P. Przybyłowicz.  On the randomized Euler schemes for ODEs under inexact information.  Numerical Algorithms, 91:1205–1229, 2022.
  * [3] W. Cao, Z. Zhang, and G. E.M. Karniadakis.  Numerical methods for stochastic delay differential equations via the Wong–Zakai approximation.  SIAM J. Sci. Comput., 37(1):A295–A318, 2015.
  * [4] E. Cinlar.  Probability and Stochastics.  Springer Science & Business Media, 2011.
  * [5] T. Daun and S. Heinrich.  Complexity of Banach space valued and parametric stochastic Itô integration.  J. Complexity, 40:100–122, 2017.
  * [6] F. V. Difonzo, P. Przybyłowicz, and Y. Wu.  Existence, uniqueness and approximation of solutions to Carathéodory delay differential equations.  arXiv preprint arXiv:2204.02016, 2022.
  * [7] S. Heinrich.  Complexity of stochastic integration in Sobolev classes.  J. Math. Anal. Appl., 476:177–195, 2019.
  * [8] S. Heinrich and B. Milla.  The randomized complexity of initial value problems.  J. Complex., 24:77–88, 2008.
  * [9] A. Jentzen and A. Neuenkirch.  A random Euler scheme for Carathéodory differential equations.  Journal of Computational and Applied Mathematics, 224:346–359, 2009\.
  * [10] H. Woźniakowski J.F. Traub, G.W. Wasilkowski.  Information-Based Complexity.  Academic Press, New York, 1988.
  * [11] R. Kruse and Y. Wu.  Error analysis of randomized Runge-Kutta methods for differential equations with time-irregular coefficients.  Comput. Methods Appl. Math., 17:479–498, 2017.
  * [12] R. Kruse and Y. Wu.  A randomized Milstein method for stochastic differential equations with non-differentiable drift coefficients.  Discrete and Continuous Dynamical Systems - B, 24(8):3475–3502, 2019.
  * [13] X. Mao.  Stochastic Differential Equations and Applications, 2nd. ed. Woodhead Publishing, 2007.
  * [14] X. Mao and L. Shaikhet.  Delay-dependent stability criteria for stochastic differential delay equations with Markovian switching.  Stability and Control: Theory and Applications, 3(2):88–102, 2000\.
  * [15] P. M. Morkisz and P. Przybyłowicz.  Optimal pointwise approximation of SDE’s from inexact information.  J. Comp. Appl. Math., 324:85–100, 2017.
  * [16] P. M. Morkisz and P. Przybyłowicz.  Randomized derivative-free Milstein algorithm for efficient approximation of solutions of SDEs under noisy information.  J. Comp. Appl. Math., 383, 2021.  113112\.
  * [17] E. Pardoux and A. Rascanu.  Stochastic Differential Equations, Backward SDEs, Partial Differential Equations.  Stochastic Modelling and Applied Probability. Springer International Publishing Switzerland, 2014.
  * [18] P. Przybyłowicz and P. M. Morkisz.  Strong approximation of solutions of stochastic differential equations with time-irregular coefficients via randomized Euler algorithm.  Appl. Numer. Math., 2014.
  * [19] P. Przybyłowicz, V. Schwarz, and M. Szölgyenyi.  Randomized Milstein algorithm for approximation of solutions of jump-diffusion SDEs.  arXiv:2212.00411, 2022.
  * [20] P. Przybyłowicz, M. Sobieraj, and Ł. Stȩpień.  Efficient approximation of SDEs driven by countably dimensional Wiener process and Poisson random measure.  SIAM Journal on Numerical Analysis, 60(2):824–855, 2022.
  * [21] R. Situ.  Theory of Stochastic Differential Equations with Jumps and Applications: Mathematical and Analytical Techniques with Applications to Engineering.  Springer, Boston, 2005.