# Local Explanations for Clinical Search Engine results

Edeline Contempré<EMAIL_ADDRESS>0000-0002-1767-121X Vrije
Universiteit AmsterdamDe Boelelaan 1105Amsterdamthe Netherlands ,  Zoltán
Szlávik<EMAIL_ADDRESS>0000-0002-2781-3795 Vrije Universiteit AmsterdamDe
Boelelaan 1105Amsterdamthe Netherlands ,  Majid Mohammadi<EMAIL_ADDRESS>** Vrije Universiteit AmsterdamDe Boelelaan 1105Amsterdamthe Netherlands ,
Erick Velazquez<EMAIL_ADDRESS>Vrije Universiteit
AmsterdamDe Boelelaan 1105Amsterdamthe Netherlands ,  Annette ten Teije
<EMAIL_ADDRESS>Vrije Universiteit AmsterdamDe Boelelaan
1105Amsterdamthe Netherlands and  Ilaria Tiddi<EMAIL_ADDRESS>Vrije
Universiteit AmsterdamDe Boelelaan 1105Amsterdamthe Netherlands

(2021)

###### Abstract.

Health care professionals rely on treatment search engines to efficiently find
adequate clinical trials and early access programs for their patients.
However, doctors lose trust in the system if its underlying processes are
unclear and unexplained. In this paper, a model-agnostic explainable method is
developed to provide users with further information regarding the reasons why
a clinical trial is retrieved in response to a query. To accomplish this, the
engine generates features from clinical trials using by using a knowledge
graph, clinical trial data and additional medical resources. and a crowd-
sourcing methodology is used to determine their importance. Grounded on the
proposed methodology, the rationale behind retrieving the clinical trials is
explained in layman’s terms so that healthcare processionals can effortlessly
perceive them. In addition, we compute an explainability score for each of the
retrieved items, according to which the items can be ranked. The experiments
validated by medical professionals suggest that the proposed methodology
induces trust in targeted as well as in non-targeted users, and provide them
with reliable explanations and ranking of retrieved items.

Explainability, Search, Health care, Crowdsourcing, Treatment search

††copyright: acmcopyright††journalyear: 2021††conference: KCAP 2021; ;

##  1\. Introduction

When healthcare professionals (HCPs) use a treatment search engine to find
treatment options for their patients, they need to gain a certain trust in the
system. While accuracy, performance, and the design are essential for
accomplishing such trust, we may need to do more to reach a threshold where
HCPs trust the system enough to want to use it in critical scenarios, e.g.,
when a patient’s life may be at risk.

A search engine would typically provide a ranked list of the related items
with regards to a certain query. However, lack of explanations could lead to a
lack of trust from users as they would not understand the underlying logic of
retrieving an item in response to a query. In the medical domain, where the
pressure to make no mistakes is high,incorrectly attributing the cause of a
mistake could be fatal. As a result, without the ability to interpret the
model, HCPs’ trust in the model decreases and will, ultimately, not use the
model’s outputs (pu2006trust, ). In addition, due to compliance regulations,
most search engines in the medical domain provide unordered lists of related
items in response to a query, making it difficult for users to look into or
distinguish the most relevant items for their needs. As an instance, treatment
search engines such as clinicaltrials.gov do not offer relevance-based ranking
of documents, partly because ranking in-criteria treatment options may be
suspect to favoritism, which is highly prohibited for clinical trials
(Clinical58:online, ). In addition, for an efficient and thorough search, a
status/date/title-based ordering may not always be the most practical for end
users as they tend to scatter similar results from each other.

A potential solution to provide explanations is to use current explainable
methods. A class of such methods would provide global explanations only so
that we can evaluate the overall search engine as a whole, but cannot provide
proper explanations in response to each individual query (dam2018explainable,
). Another option is to use other methods for local explainability such as
LIME (das2020opportunities, ) and SHAP (lundberg2017unified, ) as these
explain how or why a specific result is provided. However, these methods are
designed for machine learning problems, such as classification and regression,
but not for explaining search engine results. When local explanations were
used to explain search results, these were either based on one feature from
the documents like word prominence (verma2019lirme, ), or not applicable to
the clinical trials since they are based on user reviews for each document
(catherine2017explainable, ) (which are unavailable for clinical trials).

Another major challenge is to provide HCPs with user-friendly, reliable, and
easy-to-understand explanations. A major drawback of current explainability
techniques, such as LIME (das2020opportunities, ), is that these techniques
tend to focus on aiding users with technical backgrounds to interpret the
system. HCPs are not universally expected to understand the detailed workings
of a complex retrieval model. Thus, HCPs require explanations that are high
level and intuitive, while they do not necessarily need to reflect the exact
inner workings of retrieval models. This opens up an opportunity in which
explanation models can be built in a way that they are not sensitive to minor
changes in the model of a search engine. For instance, with a treatment search
engine, we may offer a local explanation such as “the queried disease is
mentioned in the retrieved clinical trial’s title”, and as long as the
retrieval model relies on this as a feature, we are using a generic
explanation method, and we can develop the search engine and explanation
module fairly separately in practice.

In this paper, an explainability method is developed which provides tailored
explanations to medical practitioners for retrieved items. To that end,
meaningful features from clinical trials are extracted from different data
sources, and preferences of different users are elicited by utilizing a
crowdsourcing-based methodology. We then put forward a method to translate
preferences into importance level of features. Based on features’ importance
levels, tailored explanations are acquired for each specific query, according
to which we develop a sentence template in order to present them to users. In
addition, we introduce explainability scores, according to which we order
retrieved items. The results suggest that the use of local explainability on
clinical search engines promote HCPs trust, search experience, and result
ordering satisfaction.

##  2\. Related Work

The General Data Protection Rule (GDPR) requires (since 2016) all systems
collecting data to be transparent on how these use data. Researchers have
since then created surveys on explainability (zhang2018explainable, ;
dovsilovic2018explainable, ; adadi2018peeking, ), defined different types of
explainability (sheh2018defining, ), used explainability in a variety of
sectors. However, up to date, there is no definition of explainability in the
Oxford Dictionary111See
https://www.oxfordlearnersdictionaries.com/spellcheck/english/?q=explainability
(visited on 15/10/2020) (rosenfeld2019explainability, ). Researchers argue
about the definition of explainability, what shape explainability has, meaning
it is a monolithic concept.

To clarify our vision of explainability, we identified three main dimensions
of explainability that can be observed throughout researchers’ definitions:
audience, understanding, and transparency. Understanding refers to the user’s
ability to understand the model’s results. However, not all users can
interpret all models using explainability as models can be domain specific.
For example, users without knowledge in biology would struggle to understand
highly biological terms generated by a model’s explainability attempting to
diagnose a certain type of lung cancer. Likewise, explainable AI (XAI) could
use simple terms, leading to a lack of details for the doctor assessing the
diagnosis. The user is therefore required to have a certain amount of
knowledge to understand the explanation itself, making it crucial for
developers using explainability to target their audience
(rosenfeld2019explainability, ). Lastly, an explainable method should increase
the model’s transparency by making it more interpretable for its users, and
not try to generate seemingly arbitrary explanations that do not fit with how
the model works (dimanov2020you, ).

A type of audience are, for example, health care professionals (HCPs) as they
increasingly rely on artificial intelligence models to make concise decisions
such as diagnosing or providing treatment options. A further increase of the
use of AI occurs when the machine provides explanations as HCPs use these
elaborations as a means to justify their decisions. For example, if a model
suggests diagnosing a patient with lung cancer, the HCP would want a
justification to this decision/suggestion. Other HCPs have reported a need to
understand the cause of learned representations (holzinger2019causability, ).
Moreover, HCPs reported it will not cause major complications if the model is
not as accurate, but would always want to know its potential shortcomings.
Therefore, local explanations benefit HCPs to construct their conclusions.

Local explanations increase trust in HCPs. Although providing local
explanations about features is a straightforward solutions, these do not aid
all clinicians in all departments. HCPs working in the intensive care unit and
in the emergency department reported that local explanations were not useful.
The two departments have time as common denominator. HCPs in these departments
often lack time due to patients with a short prognosis that only have a few
hours to live if the HCP does not take action. Local explanations could,
therefore, not be useful to users lacking time.

Current state-of-the-art local explainability techniques do not use user-
friendly explanations. These current local explainability techniques are
either based on feature importance such as LIME (das2020opportunities, ) and
SHAP (lundberg2017unified, ), rule-based (verma2019lirme, ), saliency maps
(mundhenk2019efficient, ), prototypes (gee2019explaining, ) example based
(dave2020explainable, ), or on counterfactual explanations
(dave2020explainable, ). Up to date, feature importance (zhang2019sigir, ) and
rule-based techniques (verma2019lirme, ) were used on search engines, but do
not meet the criteria that these should be user friendly.

LIME is a type of local explainability method aiming to increase transparency
for specific decisions given by an opaque model. It explains single result by
letting users know why they are getting this specific result over another
(verma2019lirme, ). Although LIME offers one way to solve the black-box
problem, it has a few limitations. The first limitation of using LIME is that
it is most commonly used for linear or classification models
(arrieta2020explainable, ). This limits the degree to which the model can be
meaningfully applied to, and restricts itself to non-user-friendly
explanations. Consequently, this research does not use LIME methods, but
developed a local explainability method to order and generate user friendly
explanations.

##  3\. Explainable Search Engine

This section presents the proposed model that provides explanations for its
users, as well as how it orders a clinical search engine’s results. This
enables users to efficiently find potential relevant clinical trials while
understanding the underlying processes of the model. The proposed method also
generates local explainability scores for each clinical trial and uses these
scores to order the search engine’s results. Moreover, users are shown user-
friendly explanations providing descriptions of the features are available in
each clinical trial. The prerequisites of computing the explanations and
ordering is the engineering of features from different data sources.

Figure 1 shows the pipeline of steps conducted for the proposed methodology.
The search engine takes as input the user’s query, and returns an output with
explainability-based ordered results with explanations. Figure 1 shows that
the local explainability search engine combines resources with the HCP’s query
to engineer features. These features are, thereupon, attributed local
explainability scores which are used to order the list of clinical trials. In
addition, the engineered features’ outputs fill template sentences. These
explanations provide information to the user on how much of this clinical
trial can the search engine explain. In the following section, each module in
Figure 1 is discussed and explained in more detail.

Figure 1. Overview of the methods’ pipeline. Resources include the knowledge
graph, data from UMLS, clinical trials from CT.gov, and data from Pubmed.

###  3.1. Feature Engineering

Before engineering the features linked to clinical trials, we first present
the data sources according to which features for each clinical trial are
extracted.

Table 1 provides an overview of the data sources used in the proposed model.
First, we used data from UMLS (Unified Medical Language System) (umls, ),
which is an official medical database where all conditions, diseases,
infections, and more, are associated to Concept Unique Identifiers (CUIs).
Second, different clinical trial sources such as
clinicaltrials.gov222https://www.clinicaltrials.gov/ are used as it is the
biggest clinical trial repository. Third, the database comprises Pubmed
publications, as it saves medical papers. Lastly, it comprises data from the
company’s conditions graph (knowledge graph) where parent-child relations
between diseases are defined, terms are specified, as well as the
clarification of terms and their synonyms.

Table 1. Description of the data sources for the feature engineering. Data source |  Data
---|---
UMLS |  Concept Unique Identifiers, disease terms, and relations between these
clinicaltrials.gov |  Clinical trials’ detailed descriptions, summaries, phase, title, overall status, primary purpose
Pubmed |  Publications associated to clinical trials
Knowledge graph |  Parent-child relationships between diseases taken from UMLS, disease concepts (with the diseases’ preferred term and synonyms), language.

Table 1 shows the properties, from different data sources, that were used to
engineer features. The properties, by themselves, do not measure how
explainable a clinical trial is. Therefore, features were created using the
conditions graph, the UMLS and pubmed databases to assess how much of a
clinical trial the AI can explain. The engineered features are provided in
Table 2.

Table 2. Classification of features created for the local explainability based
search engine.

Feature output type/ Query dependency Query dependent Query independent Output
Binary query in title, preferred term in title clinical stage present, stage
is recruiting, overall status given 0 or 1 Numeric query in summary, preferred
term in summary, preferred term in summary, query in detailed description
number of publications Between 0 and infinity

To facilitate the explainability-based calculations, features were assigned to
various categories. Table 2 shows different classifications where the first
category is based on the user’s query: the feature is either query dependent
or query independent. For example, the feature query in title is a query
dependent feature as the feature depends on a match between a query and the
title of the clinical trial. So, if a clinical trial about breast cancer
mentions the condition in the title, the feature receives a score of 1. In
contrast, query independent features do not depend on the query as regardless
of what the query is, its score remains unchanged. For example, the feature
number of publications attributed to a clinical trial remains fixed,
regardless of user’s query. Second, Table 2 shows engineered features have two
distinct outputs which are either binary or numeric. Binary features assess
the presence of a feature in a study. Therefore, its output is either 0 or 1.
On the other hand, numeric features count the occurrence of a feature. Thus,
its outputs range between 0 and infinity.

###  3.2. Feature Importance Identification: A Crowdsourcing Approach

We created a statistical approach to determine the weights of our features,
and conducted a crowdsourcing task on Amazon Sagemaker as an alternative
method to collect data on feature importance. Compliance regulations prohibits
pharmaceutical companies to retain data on its users, especially when these
relate to drugs (Clinical58:online, ). However, previous research has shown
that crowdsourcees provided equal quality answers when conducting medical
labeling tasks compared to domain experts (dumitrache2013dr, ;
dumitrache2017crowdsourcing, ). Hence, in this experiment, 1116 responses were
collected from participants to determine users’ feature preferences and,
thereupon, use these to order and explain results returned by the clinical
search engine.

Features’ importance were measured using a cold start implicit strategy, where
we asked participants to rate explainability sentences. The rating consisted
of assessing sentences on a 5-point Likert-scale, from ”Not convincing at all”
to ”Very convincing”. Each sentence explained the prominence or availability
of a feature mentioned in Table 2. In addition, we changed the format of the
sentences to implicitly measure which sentence format was most preferred to
users in order to create user-friendly explanations. Therefore, when
participants were asked to rate how convincing an explanation was to continue
to read the clinical trial in further detail, we were implicitly measuring how
important a certain feature was for our users.

We hypothesized that search features are not equally preferred by users. In
addition, we hypothesized that the formulation of explanations were not
equally preferred. We tested three dimensions of sentence formulation: numeric
vs. non-numeric (using entities ‘3 times’ vs. ‘multiple times’ in an
explanatory sentences), action-oriented versus fact-driven formulations
(‘retrieved’ versus ‘clearly mentioned’), and disease specific versus non-
disease specific outputs (‘HIV’ versus ‘condition’).

####  3.2.1. Results

Table 3. Features’ means and standard deviations. Features |  Mean |  Std dev
---|---|---
Query in detailed description |  3.69 |  0.82
Query in summary |  3.53 |  0.91
Primary purpose availability |  3.53 |  0.84
Number of publications |  3.51 |  0.92
Stage availability |  3.44 |  0.99
Query in title |  3.15 |  0.93
Trial is recruiting |  3.13 |  1
Table 4. Results of feature labeling task. Note: the results in bold are
statistically significant under the assumption p <0.05.

Features Title Summary Description Publications Stage Recruiting Primary
purpose Title / / / / / / / Summary 0.007 / / / / / / Description 0.00002 0.51
/ / / / / Publications 0.02 0.61 0.35 / / / / Stage 0.038 0.67 0.15 0.88 / / /
Recruiting 0.81 0.006 0.00001 0.01 0.054 / / Primary purpose 0.012 0.82 0.42
0.82 0.43 0.006 /

The results suggest that, in response to feature importance, partial ordering
can be obtained via crowdsourcing tasks and statistical tests. The results in
Table 3 illustrate that the feature with the highest mean score (3.69, on a
5-point Likert scale) was Query in detailed description, whereas the two least
convincing features were Query in title, and Trial is recruiting (3.15, and
3.13, respectively). We determined the weights of our features using
$\chi^{2}$ tests. Table 4 provides the results of these chi-square tests
where, for example, the features Query in title and Query in summary were not
equally preferred (as the results reveal a p-value of 0.007).

Data obtained in response to feature importance shows that there is at least a
partial ordering that can be obtained via the crowdsourcing (based on
statistical tests). We determined the features’ weight, using $\chi^{2}$
tests, based on statistical values. If two features were, for example, not
statistically equally preferred, these two features would be attributed
different weights.

Table 5. Experiment results for entities. Note: the results in bold are
statistically significant under the assumption p <0.05.

Entity $\overline{x}$(1) $\overline{x}$(2) P-value (1) Non-numerical (2)
Numerical 3.7 3.34 0.01 (1) Clearly mentioned (2) Retrieved 3.65 3.33 0.036
(1) Specify disease (2) Not specify disease 3.4 3.48 0.44

When it comes to results for the three formulation dimensions (Table 5), when
performing $\chi^{2}$ tests, we found that:

  * •

Users prefer explanations without non-numerical sentences (e.g. sentences
mentioning that there are ’multiple’ articles linked to the clinical trial vs.
’2’).

  * •

Users prefer factual sentences (‘clearly mentioned’) compared to actions
related to the search procedure (‘retrieved’).

  * •

No preferences were found between specifying the condition in a sentence (e.g.
the condition ‘HIV’ was mentioned in the title) versus (‘the condition’).

###  3.3. Explainability Score: Ordering Retrieved Items

In this section, we use the importance of the extracted features to compute
the explainability score for each of the clinical trials and order them
accordingly. For doing so, features are first assigned a weight, which are
then used to calculate the explainability score, and ultimately the clinical
trials are ordered based on these scores.

Each clinical trial was attributed an explainability score based on its
features availability or occurrences. Certain scores were fixed, while others
depended on the user’s query. The former are defined as query independent
features, and the latter as query dependent features. As such, query dependent
and query independent features were separately calculated (Table 2 reports
which features belong to each category).

Although query dependent and query independent scores were separately
calculated, all explainability feature scores, shown as $e_{f}$, were
calculated in the same manner:

$e_{f}=w*f_{s}$

where the explainability score for each feature is determined by the weight
$w$ (which depends on if the feature is binary or numeric, and if it is high
or low importance), and the feature’s score $f_{s}$. Binary $f_{s}$ scores are
identically determined for all binary features. If the feature is present;
$f_{s}=1$, and if the feature is unavailable; $f_{s}=0$. However, numerical
features $f_{s}$ scores are calculated based on each feature’s occurrence.

As previously mentioned, the process to calculate the scores differ for query
dependent and query independent features. For query dependent features,
because all the terms related to one CUI refer to the same condition, all
$e_{f}$ scores related to one CUI were grouped per clinical trial:

$E_{dtc}=\sum e_{f_{dtc}}$

where the explainability scores $E$ for features belonging in the category
query dependent $d$ were calculated by grouping features’ score per CUI $c$
for each clinical trial $t$. On the other hand, features’ scores belonging to
the query independent category $i$ scores were calculated as:

$E_{it}=\sum e_{f_{it}}$

where all the $E_{i_{t}}$ scores are attributed to their respective studies,
and linked to all the study’s CUIs. Therefore, as long as the HCP queries a
condition related to the clinical trial, the $E_{i_{t}}$ score attributed to
that clinical trial will remain unchanged. Finally, this score will be summed
per CUI with its $E_{d_{t_{c}}}$, which will give us our final explainability
per clinical trial per CUI:

$E_{ct}=E_{it}+E_{dtc}$

where $E_{c_{t}}$ was used to order the clinical trials by conducting linear
feature ranking. Explainability scores $E_{c_{t}}$ range between 0 and 1,
where clinical trials with scores close to 1 reflect that the search engine
can explain more about these clinical trials compared to clinical trials with
a score close to 0. Hence, the clinical trials linked to a CUI (that is
queried by the user) with the highest XAI scores for that CUI appear higher in
the results’ list.

Therefore, the algorithm orders the clinical trials by their explainability
scores $ef$. To do so, the algorithm takes as input the HCP’s query condition.
The algorithm will then search for the query term in the database, and
identify the CUI associated to the condition. Secondly, the algorithm filters
all clinical trials to keep studies related to that CUI, therefore providing a
list of all articles related to the condition the HCP queried. Lastly, the
list will be ordered based on explainability scores $ef$, where the highest
explainable scores will receive the highest ordering position, and the lowest
explainability scores will receive the lowest position.

###  3.4. Retrieval Explanations

Having extracted the features and computed their importance, this section is
dedicated on how to explain the retrieved items in response to a query from
the user. The explanations must be in a way that the HCP can readily
understand them. For doing so, we develop a a template list of sentences, as
shown in Table 6. These sentences are simple, user-friendly, hierarchically
structured, short and straightforward, as well as they can explain the source
of information, and cover why a result was returned.

Table 6. Template sentences created for the explainability based search
engine.

Feature Template sentence Query in title The condition is mentioned in the
title Preferred term in title The preferred term of the condition is mentioned
in the title Query in summary The condition is mentioned in the summary
Preferred term in summary The preferred term of the condition is mentioned in
the summary Query in detailed description The condition is mentioned in the
detailed description Preferred term in detailed description The preferred term
of the condition is mentioned multiple times in the description Number of
publications The clinical trial has multiple publications Stage availability
The clinical trial’s stage is clearly mentioned Overall status availability
The clinical trial’s status is clearly mentioned Trial is recruiting The
clinical trial’s status is recruiting

Sentences were created in the following manner:

  1. (1)

A maximum of three sentences at a time are displayed. We assume that, given
the limited amount of time HCPs spend on the search engine, a maximum of three
sentences will be enough for the HCP to read.

  2. (2)

Sentences are only displayed if certain conditions are met. Given the limited
time this research has, thresholds are determined based on intuitive
knowledge. This allows users to only see relevant explanations.

  3. (3)

Sentences are ordered by feature preference. The ordering at which sentences
are displayed rely on the results of the experiment described in sub-section
3.2.1.

  4. (4)

The sentences are kept simple. To understand which formulation of sentences
users prefer, we researched entity preferences as described in sub-section
3.2.

##  4\. MODEL EVALUATION

We evaluated our model by comparing it to other simulated clinical search
engines based on users’ trust, search experience, and result ordering
satisfaction. Our hypotheses were that all search engines were equally
preferred in all three dimensions. We, therefore, simulated 5 different search
engines with different city names, where each engine queried either lyme
disease, breast cancer, or HIV:

  1. (1)

Amsterdam: Search engine with ordered results and with explainable sentences

  2. (2)

Berlin: Search engine with ordered results and without explainable sentences

  3. (3)

Copenhagen: Search engine without ordered results and with explainable
sentences

  4. (4)

Dublin: Search engine without ordered results and without explainable
sentences

  5. (5)

Edinburgh: Search engine with titles ordered by alphabetical order

The engines used data from myTomorrows333https://search.mytomorrows.com/public
in order to create scenarios as realistic as possible. The different query
concepts were queried in each search engine, for which the top 10 results were
extracted and put into the simulated environments to imitate the first page of
a search engine showing 10 results at a time.

###  4.1. Experiment setup

Participants were recruited using different social media platforms such as
Facebook, Linkedin, or recruited in the company itself. Participants received
a link to a questionnaire focusing on one of the query concepts (either lyme
disease, HIV, or invasive breast cancer). In each questionnaire, participants
were shown one by one the different simulated search engines related to the
query concept. The different search engines were shown in a random order.
Additionally, participants were asked to:

  * •

Assess if they trusted the search engine.

    * –

Question asked: When looking at the search engine, how much do you trust the
search engine?

    * –

Possible answers:

      1. (1)

I trust this search engine very much

      2. (2)

I trust this search engine

      3. (3)

My trust is neutral

      4. (4)

I do not trust this search engine

      5. (5)

I do not trust this search engine at all

  * •

Assess if they were satisfied with the ordering of the search engines’ results

    * –

Question asked: When looking at the search engine, are you satisfied with the
ordering of clinical trials?

    * –

Possible answers:

      1. (1)

I am very satisfied with the ordering

      2. (2)

I am satisfied with the ordering

      3. (3)

I feel neutral

      4. (4)

I am not satisfied with the ordering

      5. (5)

I am highly not satisfied with the ordering

  * •

Asses their search experience while using the search engine

    * –

Question asked: What is your search experience when using the search engine?

    * –

Possible answers:

      1. (1)

I have a great search experience

      2. (2)

I have a good search experience

      3. (3)

My search experience is neutral

      4. (4)

My search experience is not good

      5. (5)

My search experience is not good at all

In the end of the questionnaire, participants were asked to order the
different search engines by:

  * •

Trust: users had to order the search engines from most trustworthy to least
trustworthy.

  * •

Result ordering satisfaction: users were asked to order of search engines they
preferred from highest result ordering satisfaction to lowest result ordering
satisfaction.

  * •

Search experience: users were asked to order the search engines from best
search experience to least favourite search experience.

An example of one of the simulated search engines is shown in Figure 2.

Figure 2. Example of a simulated search engine.

In total, we created 9 questionnaires which were randomly allocated to 55
participants, among which 34 completed the experiment.

###  4.2. Results

Table 7. $\chi^{2}$ results of the comparison of all search engines to each
other.

| All participants | HCPs | Non-HCPs
---|---|---|---
Trust | 0.29 | 0.44 | 0.62
Search experience | 0.04$*$ | 0.09 | 0.37
Ordering | 0.31 | 0.40 | 0.48

Note: the results in bold italic with a * are statistically significant under
the assumption p <0.05. By all participants, we mean the combination of
results of HCPs and non-HCPs.

In the experiment, we asked participants to evaluate the different search
engines one by one and report their experience. We conducted the $\chi^{2}$
test to test our hypotheses that all search engines are equally preferred in
all three dimensions. Table 7 reports the $\chi^{2}$ test results, and shows
that when combining the responses of HCPs and non-HCPs, the null hypothesis
that all search engines have equal search experience is rejected as the test
returned a p-value of 0.04. This suggests that users have different search
experiences when, distinctively, facing the search engines. The three
following subsections investigate how all participants (HCPs and non-HCPs),
HCPs alone, and non-HCPs alone, evaluate the different search engines.

The results of the task asking participants to order the search engines from
most trusted to least trusted, and best to worst search experience, suggest
that users, both HCPs and non-HCPs, reported more trust and better search
experience while using the search engines using explainability sentences
(Amsterdam and Copenhagen) compared to search engines not explaining its
results (Berlin, Dublin and Edinburgh). The results displayed in Figure 3 and
Figure 4 demonstrate these preferences.

Figure 3. Results: order the search engines from most trusted to least
trusted.

Note: Results close to 1 indicate the most preferred search engines. On the
contrary, results close to 5 are the least preferred search engines.

Figure 4. Results of ordering task: order the search engines from best search
experience to worst search experience.

Note: Results close to 1 indicate the most preferred search engines. On the
contrary, results close to 5 are the least preferred search engines.

The results of the task asking participants to order the search engines from
best result ordering satisfaction to worst ordering satisfaction are reported
in in Figure LABEL:figure_results_order_ordering. Similar to the results for
search experience, search engines including explanations of results improve
ordering satisfaction (Amsterdam and Copenhagen). In addition, HCPs ranked
last the search engine with explainability based ordering without explanations
(Berlin). This further demonstrates that failing to explain how the results’
ordering works leads to reduced result ordering satisfaction.

##  5\. Discussion

When asked to report the preferred order of search engines, participants
consistently preferred in all three dimensions the search engines Amsterdam
and Copenhagen. The two search engines include explainability based sentences
and ordering, and explainability based sentences, respectively. However, we
noticed that search engine Berlin scored low, even last in the dimension of
ordering satisfaction with HCPs. This suggests that explainability based
ordering is preferred when explained with user-friendly sentences. This is in
line with research in (pu2006trust, ) as authors demonstrated that
explainability overall increases trust. A reason is that without
explainability sentences, users understand less the logic behind the model,
and therefore attribute lower scores to the search engine Berlin. This
reasoning is further emphasized by the significant difference in ordering
preference between Dublin and Edinburgh for non-HCPs, where these prefer
Edinburgh given that the logic of the search engine is straightforward, which
can increase user satisfaction.

HCPs’ results on user experience, trust and ordering satisfaction could be
influenced by their expertise. When assessing the different dimensions of the
search engines, HCPs could be looking for familiarity and, therefore, search
for clinical trials that are within their field of experience. For example,
radiologists would pursue clinical trials related to radiology, etc. In
addition, a common problem in the medical domain are discrepancies in patient
diagnosis between HCPs. Research has shown that subjective preferences
influence a diagnosis’ outcome (gierada2008lung, ), which could explain why
HCPs have high variety with their responses when diagnosing a patient. This
follows that subjective preferences could have influenced the results of the
evaluation of our explainability-based search engine.

Although the model is scalable and generalizable, the features created for
this use case are not transferable to other search engines. Features need to
adapt to other models’ use cases as most features created in this research are
specific to clinical trials. For exmple, a search engine returning a list of
travel destinations would not benefit from the feature ’the clinical trial is
recruiting’. Transferring the model as-it-is to another set of data would,
therefore, require adapting the method to the different use-case. In addition,
developers would need to collect data on feature preferences for their use-
case.

##  6\. Future work

This research aimed to measure the influence of explainability based search
engines on users’ trust, search experience and result ordering satisfaction.
Two experiments were conducted, where the first experiment was created to
order explainability based features based on importance. The results were
translated to weights for features to order the results returned by the search
engine. The second experiment evaluated the explainability based search engine
by measuring users’ experience with the engine. Overall, the results suggest
that search engines with explanations are more trusted, provide greater user
experience, and increased ordering satisfaction, compared to search engines
without explanations. In addition, users are satisfied with explainability
based ordering of results if these have explanations, where not explaining the
ordering of results decreases users’ trust, search experience and ordering
satisfaction. Thus, the results urge developers to explain search engine
results.

Recommended future work is to investigate if there is a need for different
explanations for HCPs compared to non-HCPs. HCPs could require more detailed
explanations such as additional information on sources such as UMLS and
Pubmed. On the contrary, non-HCPs would rather have less medical terms in
order to interpret the explanations. Therefore, investigate the different
needs of explanations depending on the users’ background would benefit
explainable research.

Although our model provides explainability sentences, these are not
personalized to the profile of the HCP. In order to make it more personal,
results could be ordered based on the HCP’s profile and preferences. To
achieve this, future work should collect data on user profiles, and use
machine learning to identify users’ personal preferences. Moreover, this could
be combined with knowledge graphs to create a relationship between clinical
trials and users’ profiles as shown in (catherine2017explainable, ), where
users were provided personal explanations using a knowledge graph based on
item reviews and user profile.

## References

  * (1) P. Pu and L. Chen, “Trust building with explanation interfaces,” in _Proceedings of the 11th international conference on Intelligent user interfaces_ , 2006, pp. 93–100.
  * (2) “Clinical trials guidance documents — fda,” https://www.fda.gov/regulatory-information/search-fda-guidance-documents/clinical-trials-guidance-documents, (Accessed on 09/14/2021).
  * (3) H. K. Dam, T. Tran, and A. Ghose, “Explainable software analytics,” in _Proceedings of the 40th International Conference on Software Engineering: New Ideas and Emerging Results_ , 2018, pp. 53–56.
  * (4) A. Das and P. Rad, “Opportunities and challenges in explainable artificial intelligence (xai): A survey,” _arXiv preprint arXiv:2006.11371_ , 2020.
  * (5) S. Lundberg and S.-I. Lee, “A unified approach to interpreting model predictions,” _arXiv preprint arXiv:1705.07874_ , 2017.
  * (6) M. Verma and D. Ganguly, “Lirme: locally interpretable ranking model explanation,” in _Proceedings of the 42nd International ACM SIGIR Conference on Research and Development in Information Retrieval_ , 2019, pp. 1281–1284.
  * (7) R. Catherine, K. Mazaitis, M. Eskenazi, and W. Cohen, “Explainable entity-based recommendations with knowledge graphs,” _arXiv preprint arXiv:1707.05254_ , 2017.
  * (8) Y. Zhang and X. Chen, “Explainable recommendation: A survey and new perspectives,” _arXiv preprint arXiv:1804.11192_ , 2018.
  * (9) F. K. Došilović, M. Brčić, and N. Hlupić, “Explainable artificial intelligence: A survey,” in _2018 41st International convention on information and communication technology, electronics and microelectronics (MIPRO)_. IEEE, 2018, pp. 0210–0215.
  * (10) A. Adadi and M. Berrada, “Peeking inside the black-box: A survey on explainable artificial intelligence (xai),” _IEEE Access_ , vol. 6, pp. 52 138–52 160, 2018.
  * (11) R. Sheh and I. Monteath, “Defining explainable ai for requirements analysis,” _KI-Künstliche Intelligenz_ , vol. 32, no. 4, pp. 261–266, 2018.
  * (12) A. Rosenfeld and A. Richardson, “Explainability in human–agent systems,” _Autonomous Agents and Multi-Agent Systems_ , vol. 33, no. 6, pp. 673–705, 2019.
  * (13) B. Dimanov, U. Bhatt, M. Jamnik, and A. Weller, “You shouldn’t trust me: Learning models which conceal unfairness from multiple explanation methods.” in _SafeAI@ AAAI_ , 2020, pp. 63–73.
  * (14) A. Holzinger, G. Langs, H. Denk, K. Zatloukal, and H. Müller, “Causability and explainability of artificial intelligence in medicine,” _Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery_ , vol. 9, no. 4, p. e1312, 2019.
  * (15) T. N. Mundhenk, B. Y. Chen, and G. Friedland, “Efficient saliency maps for explainable ai,” _arXiv preprint arXiv:1911.11293_ , 2019.
  * (16) A. H. Gee, D. Garcia-Olano, J. Ghosh, and D. Paydarfar, “Explaining deep classification of time-series data with learned prototypes,” _arXiv preprint arXiv:1904.08935_ , 2019.
  * (17) D. Dave, H. Naik, S. Singhal, and P. Patel, “Explainable ai meets healthcare: A study on heart disease dataset,” _arXiv preprint arXiv:2011.03195_ , 2020\.
  * (18) Y. Zhang, J. Mao, and Q. Ai, “Sigir 2019 tutorial on explainable recommendation and search,” in _Proceedings of the 42nd International ACM SIGIR Conference on Research and Development in Information Retrieval_ , 2019, pp. 1417–1418.
  * (19) A. B. Arrieta, N. Díaz-Rodríguez, J. Del Ser, A. Bennetot, S. Tabik, A. Barbado, S. García, S. Gil-López, D. Molina, R. Benjamins _et al._ , “Explainable artificial intelligence (xai): Concepts, taxonomies, opportunities and challenges toward responsible ai,” _Information Fusion_ , vol. 58, pp. 82–115, 2020.
  * (20) O. Bodenreider, “The unified medical language system (umls): integrating biomedical terminology,” _Nucleic acids research_ , vol. 32, no. suppl_1, pp. D267–D270, 2004.
  * (21) A. Dumitrache, L. Aroyo, C. Welty, R.-J. Sips, and A. Levas, “Dr. detective”: combining gamification techniques and crowdsourcing to create a gold standard in medical text,” in _Proceedings of the 1st International Conference on Crowdsourcing the Semantic Web_ , vol. 1030, 2013.
  * (22) A. Dumitrache, L. Aroyo, and C. Welty, “Crowdsourcing ground truth for medical relation extraction,” _arXiv preprint arXiv:1701.02185_ , 2017.
  * (23) D. S. Gierada, T. K. Pilgram, M. Ford, R. M. Fagerstrom, T. R. Church, H. Nath, K. Garg, and D. C. Strollo, “Lung cancer: interobserver agreement on interpretation of pulmonary findings at low-dose ct screening,” _Radiology_ , vol. 246, no. 1, pp. 265–272, 2008.


# Percolation with random one-dimensional reinforcements

A. Nascimento1,∗, R. Sanchis2,†, D. Ungaretti3,‡

###### Abstract

We study inhomogeneous Bernoulli bond percolation on the graph
$G\times\mathbb{Z}$, where $G$ is a connected quasi-transitive graph. The
inhomogeneity is introduced through a random region $R$ around the origin axis
$\\{0\\}\times\mathbb{Z}$, where each edge in $R$ is open with probability $q$
and all other edges are open with probability $p$. When the region $R$ is
defined by stacking or overlapping boxes with random radii centered along the
origin axis, we derive conditions on the moments of the radii, based on the
growth properties of $G$, so that for any subcritical $p$ and any $q<1$, the
non-percolative phase persists.

<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
1,2Universidade Federal de Minas Gerais
3Universidade Federal do Rio de Janeiro

Mathematics Subject Classification (2020): 60K35, 60K37.

Keywords— Inhomogenous percolation, random reinforcements.

##  1 Introduction

Percolation models the spread of a fluid through random medium and it has been
object of intensive study since it was introduced in 1957 by Broadbent and
Hammersley [4]. Classical models consider a homogeneous medium representing it
as a random graph where edges (or sites) are independently present with
probability $p$ or absent otherwise.

The fluid is regarded as the connected component, also called the open
cluster, of a fixed point that we call the origin of the graph. With the
development of many techniques in the 80’s, many questions about inhomogeneous
percolation were raised. That is, when some region $R$ of privileged flow is
considered in the medium. We now formalize these ideas and give concrete
examples of such inhomogeneous models and questions.

We say that a graph $G=(V,E)$ is quasi-transitive if there exists a finite set
of sites $V_{0}\subset V$ such that for every site $w\in V$, there exists
$x\in V_{0}$ and an automorphism $\tau$ of $G$ such that $\tau(y)=x$. In this
work we consider inhomogeneous Bernoulli bond percolation on the cartesian
product $G\times\mathbb{Z}$ where $G$ is an infinite connected quasi-
transitive graph and $\mathbb{Z}$ is the set of integers $\mathbb{Z}$. The
edges of $G\times\mathbb{Z}$ are pairs of nearest neighbour’s sites and this
graph is sometimes called the box product and denoted
$G\mathbin{\text{\scalebox{0.84}{$\square$}}}\mathbb{Z}$. That is, we consider
the graph

$G\times\mathbb{Z}=(V\times\mathbb{Z},E(G\times\mathbb{Z})),$ (1)

where $E(G\times\mathbb{Z})$ is given by the edges which make every layer
$V\times\\{n\\}$ a copy of $G$ and also by the edges connecting the sites
corresponding to the same site in $G$ on neighbour layers. More precisely, if
$\sim$ denotes the relation "is connected by an edge to", two sites
$(v_{1},v_{2}),(w_{1},w_{2})\in G\times\mathbb{Z}$ are connected by an edge
if, and only if,

$v_{1}=w_{1}\text{ and }v_{2}\sim w_{2}\qquad\text{ or }\qquad v_{1}\sim
w_{1}\text{ and }v_{2}=w_{2}.$

We distinguish a vertex in $G$ to be the origin of the graph and we call it
$0$ as usual. We also denote by $0$ the origin $(0,0)\in G\times\mathbb{Z}$.
The set $\\{0\\}\times\mathbb{Z}$ will be called the vertical line or vertical
axis along the origin of $G\times\mathbb{Z}$. We denote by
$B_{G}^{x}(r)\subset G$ the set of sites that are up to distance $r$ from $x$,
that is

$B_{G}^{x}(r)=\\{v\in G;d_{G}(x,v)\leq r\\}\subset G,$

where $d_{G}$ denotes the graph distance. For simplicity, we will also write
$B_{G}(r)=B_{G}^{0}(r)$. We denote the set of integers $[a,b]\cap\mathbb{Z}$
within some interval $[a,b]\subset\mathbb{R}$ simply as
$[a,b]\subset\mathbb{Z}$. We denote the box centered at $(x,a)\in
G\times\mathbb{Z}$ with radius $r$ by

$B^{x}(a,r)=B^{x}_{G}(r)\times[a-r,a+r]\subset G\times\mathbb{Z}$ (2)

and we denote for simplicity $B(a,r)=B^{0}(a,r)$.

We consider inhomogeneous independent percolation on the graph
$G\times\mathbb{Z}$. For a subset $R\subset G\times\mathbb{Z}$ let
$\mathbb{P}(\text{$e$ is open})=q$ for edges $e$ in $R$ and
$\mathbb{P}(\text{$e$ is open})=p$ otherwise. Let us denote the resulting
probability measure by $\mathbb{P}^{(R)}_{p,q}$ and its percolation
probability by $\theta^{(R)}(p,q)$, i.e., the probability that there is an
infinite open path starting from the origin of $G\times\mathbb{Z}$.

The hyphotesis of quasi-transitivity on $G$ is due to some essential
properties for our work that such graphs possess. The first one is that quasi-
transitive graphs cannot grow too fast. If $\Delta_{x}$ denotes the degree of
$x\in G$ and $\Delta_{G}=\max_{x\in V_{0}}\Delta_{x}$, then, for every $x\in
G$,

$|B_{G}^{x}(n)|\leq\Delta_{G}^{n}.$ (3)

The second one is that, as it was shown by Antunović, Vaselić (see [1]),
subcritical homogeneous percolation on quasi-transitive graphs always have a
sharp threshold, see also Beekenkamp, Hulshof [2] for inhomogeneous
percolation. Since $G$ is quasi-transitive, this implies that
$G\times\mathbb{Z}$ is also quasi-transitive, hence, for any
$p<p_{c}(G\times\mathbb{Z})$, there exists a constant $c=c(p)>0$ such that for
every $(x,a)\in G\times\mathbb{Z}$,

$\mathbb{P}_{p}((x,a)\longleftrightarrow\partial B^{x}(a,r))\leq e^{-c(p)r}.$
(4)

Our results depend solely on these two properties. While we could present our
findings in terms of these properties, we believe that the quasi-transitivity
setting is sufficiently general for our purposes.

One important class of problems in inhomogeneous percolation is to consider a
parameter $p$ such that $\theta(p)=\theta^{(R)}(p,p)=0$ and a supercritical
parameter $q$. We seek to understand the relation between the size and shape
of $R$ and how large $q$ must be to enter the percolating phase of
$\mathbb{P}^{(R)}(p,q)$.

Several positive results are present in the literature when one considers
random regions $R$. For instance, Duminil-Copin, Hilário, Kozma, Sidoravicius
[6] showed that for Brochette Percolation in the square lattice, that is, when
$R\subset\mathbb{Z}^{2}$ is given by the union of vertical lines chosen
independently at random, whenever $q>p_{c}(\mathbb{Z}^{2})$ we can choose
$p<p_{c}(\mathbb{Z}^{2})$ such that the origin percolates. See also [3],
[7],[8], [9] for related problems.

Our work is, though, reminiscent of the following results. In 1994, Madras,
Schinazi, and Schonmann [10] showed that for the case where
$G=\mathbb{Z}^{d-1}$ and $R=\\{0\\}\times\mathbb{Z}$ is a vertical line, the
critical point of the inhomogeneous model remains the same as in the
homogeneous case. Their work is actually for the Contact Process, but it
translates naturally for percolation. Later in that year, Zhang [12] showed
that for all $q<1$ we have

$\mathbb{P}_{1/2,q}^{\\{0\\}\times\mathbb{Z}}(0\longleftrightarrow\infty)=0,$

recalling the value of the critical point $p_{c}(\mathbb{Z}^{2})=1/2.$ In
other words, phase transition also remains continuous in $\mathbb{Z}^{2}$,
which is the case $d-1=2$ of a problem posed in [10]. In general, we can
define

$q\mapsto
p_{c}(q)=\sup\\{p\in[0,1]\,;\,\mathbb{P}_{p,q}^{(R)}(0\longleftrightarrow\infty)=0\\}.$
(5)

Proposition 1.4 of [10] shows, in particular, that $p_{c}(q)$ is a constant
curve for $q\in(0,1)$ in $\mathbb{Z}^{d}$ for all $d\geq 2$. In 2020, Szabó
and Valesin [11] studied this problem for a general graph $G$ and proved that,
for any finite subgraph $F\subset G$, $p_{c}(q)$ is continuous when $R$ is the
cylinder $F\times\mathbb{Z}$ in the cartesian product $G\times\mathbb{Z}$,
which they call a ladder graph, and they conjecture that the curve is
constant. Our results, in particular, imply that this is actually the case
when $G$ is quasi-transitive. Also in 2020, Lima and Sanna [5] generalized the
result of [11] by replacing $F\times\mathbb{Z}$ by a region $R$ given by the
union of an infinite number of well spaced cylinders with uniformly bounded
radii.

Our objective is to extend beyond the deterministic setting, where the region
$R$ is fixed, and investigate models with random thickness in the reinforced
one-dimensional region, preventing it from being confined to a deterministic
cylinder. We do that in two ways. Firstly, we consider the region $R$ to be
the union of boxes centered along the line $\\{0\\}\times\mathbb{Z}$ having
radii given by i.i.d. random variables, this is the Overlap Model defined in
Subsection 2.1. Then we consider the region $R$ given by stacked boxes with
i.i.d. radii also centered along the line $\\{0\\}\times\mathbb{Z}$, this is
the Stack Model defined in Subsection 2.2. In both cases we prove that, under
mild conditions on the expectation of the radii, for any
$p<p_{c}(G\times\mathbb{Z})$ and for any $q<1$, the resulting process remains,
for almost every environment, in the non-percolating phase.

##  2 Definition of the models and statement of the results

Consider a collection $\\{X_{n};n\in\mathbb{Z}\\}$ of iid random variables
supported on $\mathbb{N}=\\{1,2,3,\dots\\}$ in the probability space
$(\Xi,\mathcal{G},\nu)$, where $\Xi=\mathbb{N}^{\mathbb{Z}}$ and
$\mathcal{G}=\sigma(X_{n},n\in\mathbb{Z})$, with associated expectation
operator denoted by $E$. One might assume that the random variables $X_{n}$
are supported on $\mathbb{R}_{+}$, however, this assumption would not
introduce any new phenomena to our results. A configuration $\Lambda\in\Xi$
will be called an environment. We start with a classical result of de la Valée
Poussin on uniform integrability applied to a single function.

######  Lemma 1.

Let $X$ be a random variable supported on $\mathbb{N}$. If
$\mathbb{E}X<\infty$, then there exists a non-decreasing function
$f:\mathbb{R}\to[0,\infty)$ with $f(x)\nearrow\infty$ as $x\to\infty$, such
that

$\mathbb{E}[Xf(X)]<\infty.$

Moreover, if $g$ is the inverse function of $xf(x)$. Then, we have

$\lim_{n\rightarrow\infty}\frac{g(n)}{n}=0.$

###### Proof.

We prove only the last assertion, by contradiction. Suppose that there exists
some $\varepsilon>0$ and an increasing sequence $(n_{k})$ with
$g(n_{k})\geq\varepsilon n_{k}$. Then, applying $x\mapsto xf(x)$ we get

$n_{k}\geq\varepsilon n_{k}f(\varepsilon n_{k}),\ \forall k\quad\implies\quad
f(\varepsilon n_{k})\leq\frac{1}{\varepsilon},\ \forall k$

contradicting that $f(n)\nearrow\infty$. ∎

From now on, we focus on two possible models of random environments describing
one-dimensional reinforcements.

###  2.1 The Overlap Model

In this subsection we introduce formally the Overlap Model and we state the
main theorem. Let $G$ be a quasi-transitive graph and consider the cartesian
product $G\times\mathbb{Z}$ as defined in (1). In each site $(0,n)$ of the
vertical line $\\{0\\}\times\mathbb{Z}$, we place a box

$B_{n}=B(n,X_{n})$ (6)

with radius $X_{n}$ and we consider the improved region $R$ to be the union of
these boxes. More precisely, we define

$R=\bigcup_{n\in\mathbb{Z}}B_{n}.$ (7)

We let every edge $e\in R$ be open with probability $q$ and every edge
$e\notin R$ open with probability $p$. In Figure 1, we sketch an environment
for the Overlap Model for $G=\mathbb{Z}$. To let the drawing clear and to not
lose proportionality, we choose to draw only boxes with centers $10$ units
apart. The reader is invited to imagine the other boxes in between them.

$\mathbb{Z}$$G$$B_{0}$$B_{10}$$B_{20}$$B_{-10}$$B_{30}$ Figure 1: An
environment for the Overlap Model

The region $R=R(\Lambda)$ is well defined and we write simply
$\mathbb{P}^{(R(\Lambda))}_{p,q}=\mathbb{P}^{\Lambda}_{p,q}$ and
$\theta^{(R(\Lambda))}(p,q)=\theta^{\Lambda}(p,q)$. We call
$\mathbb{P}^{\Lambda}_{p,q}$ the quenched probability measure associated with
the environment $\Lambda$.

Our main result for this model is the following:

######  Theorem 1.

Let $G$ be a quasi-transitive graph and consider the Overlap Model defined by
iid random variables $\\{X_{n};n\in\mathbb{Z}\\}$ with common distribution $X$
in $G\times\mathbb{Z}$. For $0<p<p_{c}<q<1$, we have

$\theta^{\Lambda}(p,q)=0\quad\Lambda\text{-a.s. }\quad\iff\quad EX<\infty.$
(8)

######  Remark 1.

Considering environments with radii given by random variables such that $X\geq
r$ a.s., it is clear that any cylinder $F\times\mathbb{Z}$ is contained in the
region $R$ if $r$ is chosen properly. In this setting the Overlap Model
dominates the model where the improved region $R$ is a cylinder. In the
context of quasi-transitive graphs $G$, this proves the conjecture by Szabó
and Valesin [11] that the curve $p_{c}(q)$ defined in (5) is constant if the
improved region is a deterministic cylinder.

######  Remark 2.

In the Overlap Model as defined above, each edge in the enhanced region is
open with a fixed probabilily $q<1$ and one could suppose that this
probability increases depending on how many boxes the edge belongs to. As it
will be clear, our proof could be easily adapted to such case and the result
would be the same. This relates to the fact that almost surely, either every
edge belongs to a finite number of boxes or the boxes cover the whole space,
see Proposition 1.

###  2.2 The Stack Model

In this subsection we define formally the Stack Model and state the main
theorem.

To start the construction of the environment, place the box $B(0,X_{0})$ at
the origin of $G\times\mathbb{Z}$ and then stack succssivelly the remaining
boxes in both directions along $\\{0\\}\times\mathbb{Z}$. More precisely. Let
$Z(0)=0$ and, for $n\in\mathbb{Z}\setminus\\{0\\}$,

$Z(n)=\begin{cases}X_{0}+2\sum_{i=1}^{n-1}X_{i}+X_{n},\quad\quad\text{ if
}n\geq 1\\\ -X_{0}-2\sum_{i=1}^{-n-1}X_{-i}-X_{n},\text{ if
}n\leq-1\end{cases}$ (9)

be the center of the $n$-th box and set

$B_{n}=B(Z(n),X_{n}).$ (10)

The improved region $R$ is again given by

$R=\bigcup_{n\in\mathbb{Z}}B_{n}.$ (11)

$\mathbb{Z}$$G$$B_{0}$$B_{3}$ Figure 2: An environment for the Stack Model

As in the Overlap Model, the region $R=R(\Lambda)$ is well defined and we let
every edge $e\in R$ be open with probability $q$ and every edge $e\notin R$
open with probability $p$ (see Figure 2). For the sake of simplicity, we use
the same notation to denote the probability measure associated to the Stack
Model, that is $\mathbb{P}^{(R(\Lambda))}_{p,q}=\mathbb{P}^{\Lambda}_{p,q}$
and $\theta^{(R(\Lambda))}(p,q)=\theta^{\Lambda}(p,q)$.

In the Overlap Model, the arrangement of the center of the boxes produces more
density of boxes along a determined height, causing the region $R$ to be large
when the random variables $X_{n}$ are fixed. In the Stack Model, instead, at
every fixed height the sample of only one box will determine the thickness of
the improved region $R$. Moreover, we emphasize that in the Stack Model $R$
cannot ever be the whole space. Considering connectedness of $R$ preserved,
this is the most sparse way that the boxes can be arranged along
$\\{0\\}\times\mathbb{Z}$, being in a sense the extreme opposite of the
Overlap Model. For that reason, although we see no straightforward coupling so
that Overlap Model dominates Stack Model, the Stack Model produces sparser
improved regions, at an heuristic level. As an effect, a weaker hypothesis is
needed to prove essentially the same result.

######  Theorem 2.

Let $G$ be any quasi-transitive graph and consider the Stack Model in
$G\times\mathbb{Z}$. If $E\log|B_{G}(X)|<\infty$, then

$\theta^{\Lambda}(p,q)=0\quad\text{for $p\in[0,p_{c}),\;q\in[0,1)$}$

almost surely on $\Lambda$.

The condition $E\log|B_{G}(X)|<\infty$ in Theorem 2 expresses the exact
relationship between the distribution of $X$, the growth of the graph $G$ and
the exponential decay (4) that must be satisfied for the theorem to hold. In
fact, as we will see in Section 4, the $\log$ function appears in the
expression as a consequence of the exponential decay of $\theta_{n}(p)$.

By the fact that quasi-transitive graphs grow at most exponentially fast, see
(3), Theorem 2 guarantees, for any such graph, that there is no percolation in
the Stack Model whenever $EX<\infty$. But if the asymptotic behavior of
$|B_{G}(n)|$ is known to be lesser than exponential, we can give an explicit
condition on the moment of the radii for the theorem to hold. For example, if
$G=\mathbb{Z}^{d-1}$, then $G\times\mathbb{Z}=\mathbb{Z}^{d}$ and in this case
we know that there exists a constant $C_{d}>0$ such that $|B_{G}(n)|\leq
C_{d}n^{d}$, so it is sufficient to choose iid radii with $E\log X<\infty$ for
the theorem to hold in this case.

##  3 The Overlap Model: Proof of Theorem 1

Consider the Overlap Model with radii given by independent random variables
with common distribution $X$ of finite expectation. Take $f$ and $g$ as in
Lemma 1 and using the estimate from this lemma, we have

$\sum_{n\geq 1}\nu(X_{n}\geq g(n))=\sum_{n\geq 1}\nu(X_{n}f(X_{n})\geq
n)=\sum_{n\geq 1}\nu(Xf(X)\geq n)<\infty.$

By the Borel-Cantelli’s Lemma we can conclude that

$\nu(\liminf_{n}\\{X_{n}\leq g(n)\\})=1.$ (12)

Hence, although the region $R$ is random, all except finitely many boxes in
$R$ are almost surely contained in a deterministic cone, whose growth we can
estimate. It will be useful to find a deterministic $n_{0}$ such that all
boxes with center above $n_{0}$ are within some deterministic region with
positive probability.

To formalize these ideas, we start by defining the deterministic cones
properly.

######  Definition 1.

Given $n_{0}\in\mathbb{N}$, such that $g(n)<n/2$ for all $n\geq n_{0}$. The
upwards and the downwards cone are, respectively, the sets

$W^{+}=\bigcup_{n\geq
2n_{0}}B_{G}(g(n))\times\Bigl{[}\frac{n}{2},\infty\Bigr{)}\quad\text{and}\quad
W^{-}=\bigcup_{n\geq
2n_{0}}B_{G}(g(n))\times\Bigl{(}-\infty,-\frac{n}{2}\Bigr{]}.$

Recall the notation $B_{n}=B(n,X_{n})$. See (2) and (6).

######  Definition 2.

Given $n_{0}\in\mathbb{N}$ and $W^{+}$, $W^{-}$ as in Definition 1, we say
that $\Lambda$ is a good environment if it satisfies

  1. 1.

The boxes $B_{n}$ with $n\geq 2n_{0}$ are contained in $W^{+}$:
$\bigcup\limits_{n\geq 2n_{0}}B_{n}\subseteq W^{+}$;

  2. 2.

The boxes $B_{-n}$ with $n\geq 2n_{0}$ are contained in $W^{-}$:
$\bigcup\limits_{n\geq 2n_{0}}B_{-n}\subseteq W^{-}$;

  3. 3.

The boxes $B_{n}$ with $n\in(-2n_{0},2n_{0})$ have radius $X_{n}\leq
g(2n_{0})$.

We denote by $\mathcal{A}=\mathcal{A}(n_{0})$ the set of all good
environments.

We notice that in a good environment given by Definition 2 the random region
$R$ is covered by the deterministic region
$\bigl{(}B_{G}(g(2n_{0}))\times[-n_{0},n_{0}]\bigr{)}\cup W^{+}\cup W^{-}$.
Cones $W^{+}$ and $W^{-}$ are illustrated in Figure 3 below, where they are
decomposed into layers.

######  Lemma 2.

There exists $n_{0}$ such that the set of good environments $\mathcal{A}$ has
$\nu(\mathcal{A})>0.$

###### Proof.

First notice that the finite intersection of independent events

$\bigcap_{n=-2n_{0}+1}^{2n_{0}-1}\\{X_{n}\leq g(2n_{0})\\}$

has positive probability for all $n_{0}$ such that $g(2n_{0})\geq m$, where
$m$ is some constant depending on the distribution of $X$. By Lemma 1 we can
choose $n_{0}$ sufficiently large so that $g(n)\leq n/2$ for all $n\geq
n_{0}$. Fix $n_{0}$ with these properties. In order to show that

$\nu\Bigl{(}\bigcup_{n\geq 2n_{0}}B_{n}\subseteq W^{+}\Bigr{)}>0$

it is sufficient to show that with positive probability $B(n,X_{n})\subseteq
B(n,g(n))$ for all $n\geq 2n_{0}$. It follows from (12) that

$\nu\Bigl{(}\bigcap_{n\geq 2n_{0}}\\{X_{n}\leq g(n)\\}\Bigr{)}>0.$

By the same reasoning we also show that

$\nu\Bigl{(}\bigcap_{n\geq 2n_{0}}\\{X_{-n}\leq g(n)\\}\Bigr{)}>0.$

We conclude that $\nu(\mathcal{A})>0$, being the intersection of three
independent events of positive probability. ∎

Proceeding to the proof of the theorem, first we show that one of the
implications of the statement is trivial.

######  Proposition 1.

$EX=\infty$ if, and only if, $R=G\times\mathbb{Z}$ almost surely.

###### Proof.

We show that any fixed vertex $v$ will be covered by some ball. By translation
invariance in the $\mathbb{Z}$ direction, we can assume $v=(w,0)$ and denote
$r=d_{G}(w,0)$. Notice that a ball centered at $(0,n)$ with $n>r$ will cover
$v$ if its radius satisfies $X_{n}\geq n$. Since

$\sum_{n\geq r}\nu(X_{n}\geq n)=\infty\quad\text{is equivalent to}\quad
EX=\infty,$

and the events $\\{X_{n}\geq n\\}$ are independent, the result follows from
Borel-Cantelli’s lemma. ∎

This proves the first implication since when $R=G\times\mathbb{Z}$ we are in
the supercritical phase of homogeneous percolation whenever
$q>p_{c}(G\times\mathbb{Z})$.

###### Proof of Theorem 1..

We decompose $W^{+}$ and $W^{-}$ into layers $(L^{+}_{n};n\geq n_{0})$. Define

$L^{+}_{n}:=B_{G}(g(2n))\times\\{n\\}.$ (13)

Notice that $W^{+}=\bigcup_{n\geq n_{0}}L_{n}^{+}$. In fact, let $n\geq
n_{0}$, the radius of $L_{n}^{+}$ at $G\times\\{n\\}$ is $g(2n)$, which is
also the radius of $W^{+}$ at this height, because the cylinder in $W^{+}$
with the largest radius that has non empty intersection with $G\times\\{n\\}$
is $B_{G}(g(2n))\times[n,\infty)$.

It follows by quasi-transitivity of $G$ that $B_{G}(n)$ grows at most
exponentially fast with $n$. As a consequence, the number of sites in each
layer is

$|L^{+}_{n}|=|B_{G}(g(2n))|\leq e^{c_{G}g(2n)},$ (14)

where $c_{G}>0$ is some constant depending only on $G$. We define analogously
the quantities $L^{-}_{n}$ for $W^{-}$.

Let us estimate $\mathbb{P}_{p}(W^{+}\leftrightarrow W^{-})$. We have

$\mathbb{P}_{p}(W^{+}\leftrightarrow W^{-})\leq\sum_{n,m\geq
n_{0}/2}\mathbb{P}_{p}(L_{n}^{+}\leftrightarrow L_{m}^{-}).$

Notice that any $w^{+}\in L_{n}^{+}$ and $w^{-}\in L_{m}^{-}$ have vertical
distance $m+n$. Since $G$ is quasi-transitive, let $c=c(p)$ be as in
$\eqref{eq:expdecay}$.

Summing over all possible pairs, we have

$\mathbb{P}_{p}(L_{n}^{+}\leftrightarrow
L_{m}^{-})\leq|L_{n}^{+}||L_{m}^{-}|e^{-c(m+n)}\leq
e^{c_{G}(g(2n)+g(2m))}e^{-c(m+n)}.$

Summing for $n,m\geq n_{0}/2$ we obtain

$\mathbb{P}_{p}(W^{+}\leftrightarrow W^{-})\leq\sum_{n,m\geq
n_{0}/2}e^{c_{G}(g(2n)+g(2m))}e^{-c(m+n)}=\Bigl{(}\sum_{n\geq
n_{0}/2}e^{n(-c+c_{G}2\frac{g(2n)}{2n})}\Bigr{)}^{2}.$ (15)

$2n_{0}$$L_{n_{0}}^{+}$$L_{n_{0}+1}^{+}$$L_{n_{0}+2}^{+}$$L_{n_{0}}^{-}$$L_{n_{0}+1}^{-}$$L_{n_{0}+2}^{-}$
Figure 3: Cones and their layers

Recalling that by Lemma 1 we have $g(n)/n\rightarrow 0$, we conclude that the
sum of the series above is convergent and we can actually make it as close to
zero as we want by increasing $n_{0}$.

Now we proceed to transport this result to the measure
$\mathbb{P}_{p,q}^{\Lambda}$. Fix $n_{0}$ large enough so that

$\mathbb{P}_{p}(W^{+}\longleftrightarrow W^{-})\leq\frac{1}{2}.$

Let $B=B_{G}(g(2n_{0}))\times[-n_{0},n_{0}]$. Recall that for good
environments $\Lambda\in\mathcal{A}$, the region $R$ is a subset of $B\cup
W^{+}\cup W^{-}$. Let $D=\\{W^{+}\centernot\longleftrightarrow W^{-}\\}$ and
$F=\\{\text{every edge inside $B$ is closed}\\}.$ Notice that,

$\displaystyle\mathbb{P}_{p,q}^{\Lambda}(D^{c}\cap F)$
$\displaystyle=\mathbb{P}_{p,q}^{\Lambda}(\\{W^{+}\xleftrightarrow{B^{c}}W^{-}\\}\cap
F)$
$\displaystyle=\mathbb{P}_{p,q}^{\Lambda}(W^{+}\xleftrightarrow{B^{c}}W^{-})\mathbb{P}_{p,q}^{\Lambda}(F)$
$\displaystyle=\mathbb{P}_{p}(W^{+}\xleftrightarrow{B^{c}}W^{-})\mathbb{P}_{p,q}^{\Lambda}(F)$
$\displaystyle\leq\mathbb{P}_{p}(D^{c})\mathbb{P}_{p,q}^{\Lambda}(F).$

As a consequence, we have

$\mathbb{P}_{p,q}^{\Lambda}(D\cap
F)=\mathbb{P}_{p,q}^{\Lambda}(F)-\mathbb{P}_{p,q}^{\Lambda}(D^{c}\cap
F)\geq\mathbb{P}_{p,q}^{\Lambda}(F)\mathbb{P}_{p}(D).$ (16)

Let

$R^{+}=\bigcup_{n\geq n_{0}}B(n,X_{n})\quad\text{and}\quad
R^{-}=\bigcup_{n\geq n_{0}}B(-n,X_{-n}).$ (17)

Since $\Lambda\in\mathcal{A}$, we have that $R^{\pm}\subset W^{\pm}$. Using
this fact and (16), we get

$\displaystyle\mathbb{P}^{\Lambda}_{p,q}(R^{+}\nleftrightarrow R^{-})$
$\displaystyle\geq\mathbb{P}^{\Lambda}_{p,q}(D)\geq\mathbb{P}^{\Lambda}_{p,q}(D\cap
F)$ (18)
$\displaystyle\geq\mathbb{P}^{\Lambda}_{p,q}(F)\mathbb{P}_{p}(D)\geq\frac{1}{2}(1-q)^{c(G,n_{0})},$

where $c(G,n_{0})$ is is the number of edges in
$B_{G}(g(2n_{0}))\times[-n_{0},n_{0}]$.

Now, in order to use ergodic properties, we define the annealed law

$\mathbb{P}_{p,q}^{\nu}(\cdot)=\int_{\Xi}\mathbb{P}_{p,q}^{\Lambda}(\cdot)d\nu(\Lambda).$

The main idea is that when we show that an event has propability $1$ in the
annealed law, then it also has probability $1$ for $\nu$-almost all
environment $\Lambda$.

We have,

$\mathbb{P}_{p,q}^{\nu}(D)=\int_{\Xi}\mathbb{P}_{p,q}^{\Lambda}(D)d\nu(\Lambda)\geq\int_{\mathcal{A}}\mathbb{P}_{p,q}^{\Lambda}(D)d\nu(\Lambda)\geq\frac{1}{2}(1-q)^{c(G,n_{0})}\nu(\mathcal{A})>0.$

Now, let $\tau$ be the vertical translation and consider the event where there
exists $n$ such that $\tau^{n}(D)$ occurs. Clearly this event is invariant by
$\tau$. By ergodicity of the annealed measure with respect to vertical
translations, we conclude that there are infinitely many vertical
disconnections almost surely, and this implies that $\theta^{\Lambda}(p,q)=0$
$\nu$-almost surely. Indeed, in order for the cluster of the origin to be
infinite whenever $p<p_{c}(G\times\mathbb{Z})$, it has to have infinite
intersection with $R$. ∎

##  4 The Stack Model: Proof of Theorem 2

In this section we prove Theorem 2. We actually prove it in a slightly more
general setting. We choose a function $\varphi\geq 0$ such that
$\varphi\nearrow\infty$, $E\varphi(X)<\infty$ and we investigate what
additional properties it has to satisfy for the result to hold.

Let $\varphi\geq 0$ be any increasing function and suppose
$E\varphi(X)<\infty$. As $X$ is unbounded, the set
$\mathcal{L}=\\{m\in\mathbb{N}\,|\,\nu(m\leq X\leq 2m)>0\\}$ is infinite.

######  Lemma 3.

Let $L=\min\\{l\in\mathbb{N}\,|\,\nu(\varphi(X)\leq l)>0\\}$,
$l_{0}\in\mathcal{L}$ and consider the event

$A_{k}=\\{l_{0}\leq X_{k}\leq 2l_{0}\\}\cap\bigcap_{j\geq
1}\\{X_{k+j}\leq\varphi^{-1}(j+L)\\}\cap\bigcap_{j\geq
1}\\{X_{k-j}\leq\varphi^{-1}(j+L)\\}.$

Then, for every $k\in\mathbb{Z}$, $\nu(A_{k})>0.$ Moreover, $\nu(A_{k})$ is
constant as a function of $k$.

###### Proof.

As the sequence of random variables is iid, we have

$\displaystyle\nu(A_{k})=\nu(l_{0}\leq X\leq 2l_{0})\biggl{(}\prod_{j\geq
1}\nu(\varphi(X)\leq j+L)\biggr{)}^{2}$

which is positive since $E\varphi(X)<\infty$. Furthermore, the identity also
shows that $\nu(A_{k})$ does not depend on $k$. ∎

Recall from (10) that $B_{n}=B(Z(n),X_{n})$. For $k\in\mathbb{Z}$, it will
also be useful to define the subregions

$R^{+}_{k}=\bigcup_{n>k}B_{n}$ (19)

and

$R^{-}_{k}=\bigcup_{n<k}B_{n}.$ (20)

Notice that for any $k\in\mathbb{Z}$, $R=R^{+}_{k}\cup B_{k}\cup R^{-}_{k}$.
Now we proceed to define analogous structures as done for the Overlap Model in
Definition 1.

######  Definition 3.

For $k\in\mathbb{Z}$, we define the upwards cone $W^{+}_{k}$ and the downwards
cone $W^{-}_{k}$ as the sets

$W^{+}_{k}=\bigcup_{n\geq
0}B_{G}(\varphi^{-1}(n+L+1))\times[Z(k)+l_{0}+n,\infty)$

and

$W^{-}_{k}=\bigcup_{n\geq
0}B_{G}(\varphi^{-1}(n+L+1))\times(-\infty,Z(k)-l_{0}-n].$

######  Proposition 2.

Let $c=c(p)$ be as in (4). There exists $l_{0}$ large enough such that for an
environment $\Lambda\in A_{k}$, if

$\sum_{n\geq 1}|B_{G}(\varphi^{-1}(n+L))|e^{-cn}<\infty$ (21)

then, there exists a constant $c(G,l_{0})$ such that

$\mathbb{P}_{p,q}^{\Lambda}(R^{+}_{k}\nleftrightarrow
R^{-}_{k})\geq\frac{1}{2}(1-q)^{c(G,l_{0})}>0.$ (22)

###### Proof.

For any environment $\Lambda\in A_{k}$ we have $R^{+}_{k}\subset W^{+}_{k}$
and $R^{-}_{k}\subset W^{-}_{k}$ for all $k\geq 1$, so with the same flavor of
(15), for $\Lambda\in A_{k}$, we have

$\displaystyle\mathbb{P}_{p}(R^{+}_{k}\longleftrightarrow R^{-}_{k})$
$\displaystyle\leq\mathbb{P}_{p}(W^{+}_{k}\longleftrightarrow W^{-}_{k})$
$\displaystyle\leq e^{-2cl_{0}}\sum_{m,n\geq
1}{|B_{G}(\varphi^{-1}(n+L))||B_{G}(\varphi^{-1}(m+L))|}e^{-c(m+n)}$
$\displaystyle=e^{-2cl_{0}}\biggl{(}\sum_{n\geq
1}{|B_{G}(\varphi^{-1}(n+L))|}e^{-cn}\biggr{)}^{2}.$ (23)

Now, by hypothesis $\sum_{n\geq 1}{|B_{G}(\varphi^{-1}(n+L))|}e^{-cn}$ is
convergent, so we can make the probability of connection as low as we want
uniformly on $k$, by choosing $l_{0}$ large enough. In this stage, we follow
the same procedure of (18) in Theorem 1 with $\Lambda\in A_{k}$ and

$F=\\{\text{every edge of }B_{k}\text{ is closed}\\}$

to obtain

$\displaystyle\mathbb{P}_{p,q}^{\Lambda}(R^{+}_{k}\centernot\longleftrightarrow
R^{-}_{k})\geq\frac{1}{2}(1-q)^{c(G,l_{0})}>0$ (24)

where $c(G,l_{0})\geq 1$ is the number of edges in $B(0,2l_{0})$. ∎

The next proposition shows that the lower bound (22) in Proposition 2 holds
under the hypothesis of Theorem 2.

######  Proposition 3.

Let $X$ be a random variable such that $E\log|B_{G}(X)|<\infty$. Then, for all
$p<p_{c}(G\times\mathbb{Z})$, there exists an increasing function
$\varphi=\varphi_{p}$ such that $E\varphi(X)<\infty$ and

$\sum_{n\geq 1}|B_{G}(\varphi^{-1}(n+L))|e^{-cn}<\infty$

###### Proof.

Let $\alpha=c(p)/2$ and define $g(n)=|B_{G}(n)|$,
$\varphi(n)=\alpha^{-1}\log(g(n)).$ Then $E\varphi(X)<\infty$,
$\varphi^{-1}(n)=g^{-1}(e^{\alpha n})$ and

$\sum_{n\geq 1}|B_{G}(\varphi^{-1}(n+L))|e^{-cn}=e^{\alpha L}\sum_{n\geq
1}e^{-(c-\alpha)n}<\infty.\qed$

######  Remark 3.

There is a crucial difference on the dynamics of the models with respect to
the shift transformation regarding the existence or not of the first moment of
$X$, which is a key point for both proofs. In Theorem 2 we cannot always rely
on ergodicity in the same way as in Theorem 1 because the renewal process with
interarrival distribution given by the Law of $X$ has no stationary measure if
$EX=\infty$.

###### Proof of Theorem 2..

We start by defining a sequence of explorations on the boundaries of the
downward cones in order to verify the existence of infinitely many vertical
blockades for the origin’s cluster almost surely. Loosely speaking, we explore
the cluster of all sites in the downwards cone to see if any of them
intersects the corresponding upwards cone. That is, given $\omega\in\Omega$,
we choose an enumeration $(e_{k})_{k}$ of the edges of $G\times\mathbb{Z}$
and, for every $l\in\mathbb{N}$, define
$\mathcal{C}_{0}=\mathcal{C}_{0}(l)=W^{-}_{l}$,
$\mathcal{D}_{0}(l)=\emptyset$. Given a set of sites $S\in G\times\mathbb{Z}$,
the edge boundary of $S$ is the set $\partial S=\\{e=vw\,;\,v\in S,w\notin
S\\}.$

  1. 1.

Let $m_{1}$ be the smallest index $k$ such that
$e_{k}\in\partial\mathcal{C}_{0}$. We set $\mathcal{D}_{1}=\\{e_{m_{1}}\\}$
and if the edge $e_{m_{1}}=v_{m_{1}}w_{m_{1}}$ is open, with
$w_{m_{1}}\notin\mathcal{C}_{0}$, then we set
$\mathcal{C}_{1}=\mathcal{C}_{0}\cup\\{w_{m_{1}}\\}$, otherwise we set
$\mathcal{C}_{1}=\mathcal{C}_{0}$.

  2. 2.

For $n\geq 2$, we let $m_{n}$ be the smallest index $k$ such that
$e_{k}\in\partial\mathcal{C}_{n-1}\setminus\mathcal{D}_{n-1}$. We set
$\mathcal{D}_{n}=\mathcal{D}_{n-1}\cup\\{e_{m_{n}}\\}$ and

$\mathcal{C}_{n}=\begin{cases}\mathcal{C}_{n-1}\cup\\{w_{m_{n}}\\},\text{if
}e_{m_{n}}=v_{m_{n}}w_{m_{n}}\text{ is
open},\,w_{m_{n}}\notin\mathcal{C}_{n-1}\\\ \mathcal{C}_{n-1},\text{
otherwise}.\end{cases}$

  3. 3.

If $\mathcal{C}_{n}\cap W^{+}_{l}\neq\emptyset$ the exploration stops and we
say that the exploration failed and we define
$\mathcal{C}_{i}=\mathcal{C}_{n}$ for $i\geq n$. If the exploration does not
stop, then we say that the exploration succeeded.

Notice that by construction the exploration does not stop only in
configurations where there is no crossing $\partial
W_{l}^{-}\leftrightarrow\partial W_{l}^{+}$. The exploration of $\partial
W^{-}_{l}$ just defined is denoted by $\mathcal{E}_{l}$.

Since $(X_{n})_{n}$ is an iid sequence, it is ergodic with respect to the
shift transformation, thus

$\nu(A_{k}\;{i.o.})=1.$

In fact, by Birkhoff’s Ergodic Theorem,

$\lim_{n\rightarrow\infty}\frac{1}{n}\sum_{k=0}^{n-1}\mathds{1}_{A_{k}}=\nu(A_{0})>0$

$\nu$-almost surely.

In other words, the set
$\mathcal{N}(\Lambda)=\\{l\in\mathbb{N}\,|\,A_{l}\text{ occurs}\\}$ is
infinite almost surely. Let $n_{1}=n_{1}(\Lambda)=\min\mathcal{N}$ and
consider the exploration $\mathcal{E}_{n_{1}}$. Suppose the exploration failed
and for $m\geq 1$ let
$\mathcal{C}(W_{m}^{-})=\bigcup_{i=1}^{\infty}\mathcal{C}_{i}(m)$. In this
case, as the exploited region is finite, we can find a translation of $W^{-}$
that contains it. That is, we can choose the next index
$n_{2}=n_{2}(\omega,\Lambda)\in\mathcal{N}$ such that

$W^{-}_{n_{1}}\cup\mathcal{C}(W_{n_{1}}^{-})\subseteq W^{-}_{n_{2}},$

and perform independently the same exploration on $\partial W_{n_{2}}^{-}$.

More generally, the exploration $\mathcal{E}_{n_{k}}$ of the cluster of
$W^{-}_{n_{k}}$ is well defined for every $k$ and explored only a finite
number of edges, where $n_{k}=n_{k}(\omega,\Lambda)$ is the smallest index
such that

$W^{-}_{n_{k-1}}\cup\mathcal{C}(W_{n_{k-1}}^{-})\subseteq W^{-}_{n_{k}},$

and it is independent of the preceeding explorations.

Define
$\mathcal{F}_{k}=\sigma(\mathcal{E}_{n_{1}},\dots,\mathcal{E}_{n_{k}})$, the
smallest $\sigma$-álgebra that contains all the information of the first $k$
explorations and let $T^{+}$ denote the index of the first exploration to
succeed. That is

$T^{+}(\Lambda,\omega)=\min\\{k\geq 1;\;\mathcal{E}_{n_{k}}\text{
succeeded}\\}.$ (25)

Notice that, as $\mathcal{E}_{m}$ is independent of $\mathcal{F}_{m-1}$, we
have

$\displaystyle\mathbb{P}_{p,q}^{\Lambda}\left(T^{+}>m\right)$
$\displaystyle=\mathbb{E}\left[\mathbb{E}\left[\mathds{1}_{\bigcap_{k=1}^{m}\\{\mathcal{E}_{n_{k}}\text{
failed}\\}}\bigg{|}\mathcal{F}_{m-1}\right]\right]$ (26)
$\displaystyle=\mathbb{E}\left[\mathds{1}_{\bigcap_{k=1}^{m-1}\\{\mathcal{E}_{n_{k}}\text{
failed}\\}}\mathbb{E}\left[\mathds{1}_{\\{\mathcal{E}_{n_{m}}\text{
failed}\\}}\bigg{|}\mathcal{F}_{m-1}\right]\right]$
$\displaystyle=\mathbb{P}_{p,q}^{\Lambda}(\mathcal{E}\text{
failed})\mathbb{P}_{p,q}^{\Lambda}\left(T^{+}>m-1\right).$

Proceeding by induction, Proposition 2 and Proposition 3, we have that for
every $m\geq 1$,

$\mathbb{P}_{p,q}^{\Lambda}\left(T^{+}>m\right)=\prod_{k=1}^{m}\mathbb{P}_{p,q}^{\Lambda}(\mathcal{E}_{n_{k}}\text{
failed})\leq\left(\frac{1}{2}(1-q)^{c(G,l_{0})}\right)^{m}\leq\frac{1}{2^{m}},$

hence

$\mathbb{P}_{p,q}^{\Lambda}\left(T^{+}=\infty\right)=\mathbb{P}_{p,q}^{\Lambda}\left(\bigcap_{m=1}^{\infty}\\{T^{+}>m\\}\right)=\lim_{m\rightarrow\infty}\mathbb{P}_{p,q}^{\Lambda}\left(T^{+}>m\right)\leq\lim_{m\rightarrow\infty}2^{-m}=0.$

Until now, we are investigating whether the origin’s cluster is infinite by
exploring the boundary of cones such that the initial vertex of exploration is
on the positive side of the vertical axis. Analogously, one can define the
mirrored explorations $\mathcal{E}_{-k}$ of cones with initial vertex of
exploration on the negative side of the vertical axis, we call these downward
explorations. Notice that the downward explorations are exploring the
boundaries of the upward cones. Thus, we can also define the first index
$T^{-}$ such that a downward exploration succeeds. That is,

$T^{-}(\Lambda,\omega)=\min\\{k\geq 1;\;\mathcal{E}_{n_{-k}}\text{
succeeded}\\}.$ (27)

To prove the theorem it is sufficient to show that some exploration will
succeed almost surely on both upper and lower semispaces. That is, it is
sufficient to show that

$\mathbb{P}_{p,q}^{\Lambda}(T^{+}=\infty)=\mathbb{P}_{p,q}^{\Lambda}(T^{-}=\infty)=0.$

By symmetry we also have that
$\mathbb{P}_{p,q}^{\Lambda}\left(T^{-}=\infty\right)=0$ and the proof is,
thus, completed. ∎

##  5 Open Questions

We conclude this article mentioning some questions that we think would be
interesting to investigate further.

  1. 1.

The Stack Model results in a connected region. Alternatively, one could
consider boxes with random spacing between them and set the parameter $q=1$.
Our methods might be applicable in this scenario, and it would be interesting
to establish conditions on the radii and spacings necessary to achieve the
percolating phase.

  2. 2.

The models considered here are intrinsically one-dimensional, with the
reinforced region centered along a fixed line. Now, consider a graph $G$ where
the simple symmetric random walk is transient. An interesting question is what
occurs if the path of the random walk is reinforced or thickened by random
boxes around it.

  3. 3.

A natural question we are unable to tackle is what happens when $p$ is exactly
the critical point of $\mathbb{Z}^{2}$. The simplest problem is to prove that
the Zhang’s result can be extended to our setting. Perhaps the current
understanding of near-critical percolation on $\mathbb{Z}^{2}$ could be useful
in addressing this issue.

  4. 4.

The reinforced region in the Stack Model is never the entire graph. It would
be nice to check if our result is sharp for $\mathbb{Z}^{d}$. Does percolation
occur for large $q$ whenever $\mathbb{E}(\log(X))=\infty$?

Acknowledgments: The authors thank Augusto Teixeira for suggesting the
problem. A.N thanks CAPES, R.S was partially supported by CNPq, CAPES and by
FAPEMIG, grants APQ-00868-21 and RED-00133-21, D.U. thanks FAPERJ, grant
E-26/210.571/2023.

## References

  * [1] T. Antunovic and I. Veselic.  Sharpness of the phase transition and exponential decay of the subcritical cluster size for percolation on quasi-transitive graphs.  Journal of Statistical Physics, 130:983–1009, 2008.
  * [2] T. Beekenkamp and T. Hulshof.  Sharpness for inhomogeneous percolation on quasi-transitive graphs.  Statistics & Probability Letters, 152:28–34, 2019.
  * [3] M. Bramson, R. Durrett, and R. H. Schonmann.  The Contact Processes in a Random Environment.  The Annals of Probability, 19(3):960 – 983, 1991.
  * [4] S. Broadbent and J. M. Hammersley.  Percolation processes.  Mathematical Proceedings of the Cambridge Philosophical Society, 53:629 – 641, 1957.
  * [5] B. N. B. de Lima and H. C. Sanna.  A note on inhomogeneous percolation on ladder graphs.  Bulletin of the Brazilian Mathematical Society, New Series, 51(3):827–833, Nov. 2019.
  * [6] H. Duminil-Copin, M. R. Hilário, G. Kozma, and V. Sidoravicius.  Brochette percolation.  Israel Journal of Mathematics, 225(1):479–501, apr 2018.
  * [7] M. R. Hilário, M. Sá, R. Sanchis, and A. Teixeira.  Phase transition for percolation on a randomly stretched square lattice.  The Annals of Applied Probability, 33(4):3145–3168, august 2023\.
  * [8] C. Hoffman.  Phase transition in dependent percolation.  Communications in Mathematical Physics, 254:1–22, 02 2005.
  * [9] H. Kesten, V. Sidoravicius, and M. E. Vares.  Oriented percolation in a random environment.  Electronic Journal of Probability, 27:1 – 49, 2022.
  * [10] N. Madras, R. Schinazi, and R. H. Schonmann.  On the critical behavior of the contact process in deterministic inhomogeneous environments.  The Annals of Probability, 22(3):1140–1159, 1994.
  * [11] R. Szabo and D. Valesin.  Inhomogeneous percolation on ladder graphs.  Journal of theoretical probability, 33(2):992–1010, June 2020.
  * [12] Y. Zhang.  A note on inhomogeneous percolation.  The Annals of Probability, 22:803–819, 1994.