#  I Could’ve Asked That: Reformulating Unanswerable Questions

Wenting Zhao Ge Gao Claire Cardie Alexander M. Rush
Cornell University
<EMAIL_ADDRESS>
###### Abstract

When seeking information from unfamiliar documents, users frequently pose
questions that cannot be answered by the documents. While existing large
language models (LLMs) identify these unanswerable questions, they do not
assist users in reformulating their questions, thereby reducing their overall
utility. We curate CouldAsk, an evaluation benchmark composed of existing and
new datasets for document-grounded question answering, specifically designed
to study reformulating unanswerable questions. We evaluate state-of-the-art
open-source and proprietary LLMs on CouldAsk. The results demonstrate the
limited capabilities of these models in reformulating questions. Specifically,
GPT-4 and Llama2-7B successfully reformulate questions only 26% and 12% of the
time, respectively. Error analysis shows that 62% of the unsuccessful
reformulations stem from the models merely rephrasing the questions or even
generating identical questions. We publicly release the
benchmark111https://huggingface.co/datasets/wentingzhao/couldask and the code
to reproduce the experiments222https://github.com/wenting-zhao/couldask.

##  1 Introduction

Applying large language models (LLMs) to perform question answering (QA) over
documents, such as legal and medical texts, has become increasingly popular
Agrawal et al. (2022); Guha et al. (2023). However, users’ limited knowledge
of these documents often results in the formulation of unanswerable questions,
whose assumptions either conflict with or cannot be verified with the
information available in the documents. We will refer to these assumptions as
_presupposition errors_.333Kim et al. (2023) refer to these assumptions as
questionable assumptions. Gao et al. (2023) and Yu et al. (2023) found that
around 30% of information-seeking questions written by users include
presupposition errors.

Figure 1: An example of an LLM suggesting an alternative relevant question the
user could have asked whose answers can be found in the document, besides only
informing users with the presupposition errors.

Research in the field has primarily focused on the detection of unanswerable
questions (Rajpurkar et al., 2018; Tran et al., 2023; Hu et al., 2023) and
providing explanations for why such questions cannot be answered (Yu et al.,
2023; Kim et al., 2023). However, this goal is insufficient for fostering an
effective interaction between users and LLMs. Identifying unanswerable
questions only serves as a starting point in question reformulation; without
additional guidance or feedback on how to rephrase the question, users,
especially those unfamiliar with the content, might find themselves caught in
a repetitive cycle of formulating questions. In a large-scale industrial
experiment, Faustini et al. (2023) have shown that the practice of rewriting
unanswerable questions users ask virtual assistants significantly enhances the
experience for millions of users.

Issue |  Strategy | % |  Original question |  Revised question
---|---|---|---|---
Contradictory |  Correct | 17 |  What other foods are adulterated with turmeric? |  What other substances are commonly adulterated in turmeric?
|  |  |  Which major cities are located at great lakes? |  Which U.S. states have jurisdictions that extend into the Great Lakes?
Unverifiable |  Generalize | 20 |  When was the Twenty-third Amendment to the United States Constitution passed into law? |  Has the Twenty-third Amendment to the United States Constitution been proposed?
|  |  |  How many children does Jennifer Lawrence have? |  Is Jennifer Lawrence expecting her first child?
Unverifiable |  Nearest Match | 44 |  How many arms does Krishna have? |  How is Krishna typically depicted in terms of arms?
|  |  |  How many schools are in CPS? |  What kind of schools are included in CPS?
Unverifiable |  Specify | 19 |  While working at Edison, what inventions did Nikola Tesla make? |  What specific aspects of electrical engineering did Nikola Tesla work on and further develop while working at Edison?
|  |  How many children did Toni Morrison have? |  How many children did Toni Morrison have with Harold Morrison before their divorce?
Table 1: Strategies from a human user reformulating questions on 100 examples.

This work aims to improve the utility of QA systems by introducing a new task
that requires both detecting unanswerable questions and generating questions
closely related to the initial query and grounded in the document. Opting to
generate a relevant question rather than a summary of related information
emphasizes a user-centered approach. While producing a summary is more
document-focused, formulating a relevant question targets understanding and
predicting the user’s intent, aligning the interaction more closely with the
user’s specific needs and queries. We provide an example of how to suggest
such questions in Figure 1. Although generating relevant and grounded
questions conditioned on initial queries offers greater utility to users, it
remains a difficult task even for the best models in a few-shot setting.

We first characterize human-reformulated questions and describe several
different strategies for updating questions to remove presupposition errors.
Motivated by these strategies, we curate CouldAsk, an evaluation benchmark for
document-grounded QA that consists of a combination of existing and new
datasets to study question reformulation in the presence of presupposition
errors. We evaluate several prompting methods such as few-shot prompting and
chain-of-thought prompting, employing state-of-the-art open-source and
proprietary models. The results illustrate the limitations of existing models
and prompting techniques in accurately detecting unanswerable questions and
reformulating questions: the F1 scores for identifying unanswerable questions
range from 41.16% to 67.82%, and success rates for reformulating questions
range from 7.13% to 26.21%, depending on base models. Analysis shows that most
of the unsuccessful reformulation come from rephrasing or repeating the
original questions and that LLMs are worse at reformulating questions
necessitating global edits compared to those solely requiring local edits.

##  2 Related Work

Several datasets have been proposed to study unanswerable questions. Rajpurkar
et al. (2018) curate the first document-grounded QA dataset that features
unanswerable questions. More recently, Yu et al. (2023) and Kim et al. (2023)
have collected questions with presupposition errors from Google user queries
and Reddit posts, respectively.

How to identify unanswerable questions, especially with off-the-shelf LLMs,
has remained understudied. Kim et al. (2021) proposed to first extract
presuppositions from a question and then perform natural language inference
(NLI) to check for presupposition violations. However, this pipeline requires
supervision. In practice, supervision is often not available; Kim et al.
(2023) thus explore prompting large language models in the chain-of-thought
style to identify unanswerable questions. However, the results remain
unsatisfying; using GPT-3 only yields detection accuracy that is only slightly
better than random guesses.

Faustini et al. (2023) investigate unanswerable questions and their
reformulations in the domain of spoken QA, focusing on issues stemming from
disfluencies, grammatical errors, and awkward phrasing. We, however, study
unanswerable questions arising from presupposition errors, which require a
more profound semantic comprehension of both contexts and questions.

Unanswerable questions are closely related to ambiguous questions Min et al.
(2020). While there has been extensive research into reformulating ambiguous
questions Rao and Daumé III (2018); White et al. (2021); Pyatkin et al.
(2023); Majumder et al. (2021), the problem of reformulating unanswerable
questions receives little attention. Strategies for rephrasing ambiguous
questions often involve making questions more specific by mentioning precise
entities or events Min et al. (2020). In contrast, as we will show in Section
3, reformulating unanswerable questions necessitates a wide range of
strategies.

Finally, we discuss the connection between document-grounded QA and open-
domain QA Kim et al. (2023). Document-grounded QA is essentially open-domain
QA with the correct document retrieved. Reformulating questions based on the
identified document is a separate skill from retrieving the document.
Therefore, question reformulation is an interesting task in itself.

| Total | Unans% | Document Length | Question Length | # Question Entities | Source | Domain
---|---|---|---|---|---|---|---
SQuADv2 | 1000 | 50.70 | $143.83\pm\phantom{0}59.97$ | $11.21\pm 3.54$ | $2.29\pm 0.94$ | Human | Wikipedia
QA2 | 506 | 48.81 | $818.28\pm 684.61$ |  0$7.74\pm 1.39$ | $2.05\pm 0.57$ | Human | Mostly Wikipedia
BanditQA | 2070 | 35.56 | $261.09\pm 145.19$ | $\phantom{0}8.37\pm 2.43$ | $1.70\pm 0.72$ | Human | Wikipedia
BBC | 278 | 21.22 | $477.75\pm 289.41$ | $16.37\pm 3.49$ | $3.31\pm 1.04$ | GPT-4 | News
Reddit | 313 | 36.10 | $477.43\pm 307.18$ | $14.27\pm 2.75$ | $2.93\pm 0.78$ | GPT-4 | Social Media
Yelp | 165 | 30.91 | $387.70\pm 147.83$ | $15.27\pm 3.04$ | $3.04\pm 0.76$ | GPT-4 | Review
Table 2: An overview of CouldAsk. Unans% is the percentage of unanswerable
questions.

##  3 Task: Question Reformulation

To assist users with question reformulation when reading unfamiliar documents,
we define the following task. Given a document and a user question, the system
must determine if the question is unanswerable. Upon identifying the
unanswerable question, it must reformulate the question such that the new
question is answerable by the document while remaining relevant to the
original question.

As this task is challenging to formally define, we begin with a qualitative
study over a set of example reformulations by a human user, shown in Table 1.
Different strategies are applied for different presupposition errors in the
reformulation process. For handling presuppositions that are contradictory to
the documents, the human user corrects the presuppositions. When it comes to
presuppositions that are unverifiable given the documents, we observe three
strategies. The first strategy takes a step back by asking about a less
specific event than the event in the original question. The second strategy
seeks a “nearest match” question that the document can answer due to a flaw in
the original. The third strategy refines the original question by asking about
something more specific that can be verified by the document. While these
strategies are not exhaustive, they demonstrate the challenging nature of the
problem and the necessity for establishing sources of ground truth in the
document.

##  4 The CouldAsk Benchmark

Motivated by the need to reformulate questions both to rely on verified
information and to avoid contradictions, we develop an evaluation benchmark.
We consider two important challenges in constructing benchmarks for this task.
(1) The benchmark should cover a wide range of domains to cover different
types of presuppositions. (Existing QA datasets that study unanswerable
questions mostly rely on Wikipedia articles Rajpurkar et al. (2018); Gao et
al. (2023); Kim et al. (2023).) (2) The evaluation method should be capable of
fairly assessing equally good reformulated questions, considering the
subjective nature of question reformulation.

###  4.1 Datasets

Following the desiderata, we select three existing datasets – SQuADv2,
BanditQA Gao et al. (2023), and QA2 Kim et al. (2023) – and to cover a broader
range of domains, we create three new datasets in the domains of news, review,
and Reddit, where the questions are generated by models and verified by
crowdworkers. We summarize statistics for all datasets in Table 2.

Example |  Revised question | Ans | Rel
---|---|---|---
Question: When did Chick-fil-A open their first restaurant in Pennsylvania? Document: […] he registered the name Chick-fil-A, Inc. From 1964 to 1967, the sandwich was licensed to over fifty eateries, including Waffle House and the concession stands of the new Houston Astrodome. The Chick-Fil-A sandwich was withdrawn from sale at other restaurants when the first standalone location opened in 1967, in the food court of the Greenbriar Mall, in a suburb of Atlanta. Since 1997, the Atlanta-based company has been the title sponsor of the Peach Bowl, an annual college football bowl game played in Atlanta on New Year’s Eve. |  $\bullet$ Did the article mention the first Chick-fil-A restaurant in Pennsylvania? | ✓ | ✓
$\bullet$ Which Chick-fil-A mentioned in the article is the closest to Pennsylvania? | ✓ | ✓
$\bullet$When did Chick-fil-A open their first freestanding location? | ✓ | ✗
$\bullet$ How many eateries of Chick-fil-A are licensed from 1964 to 1967? | ✓ | ✗
|  $\bullet$ Where is the first Chick-fil-A restaurant in Pennsylvania? | ✗ | ✓
|  $\bullet$ When did Chick-fil-A open its first restaurant in a northern state, specifically in Pennsylvania? | ✗ | ✓
|  $\bullet$ When were chicken sandwiches invented at Chick-fil-A? | ✗ | ✗

Table 3: Different aspects of question reformulation. Ans indicates whether
the reformulated question can be answered by the document, and Rel indicates
whether the reformulated question is relevant to the original question.

#### BBC, Reddit, and Yelp.

We synthetically generate questions with a question generation model. We use
the documents from BBC news
articles444https://huggingface.co/datasets/SetFit/bbc-news, Reddit
pages555https://huggingface.co/datasets/reddit_tifu, and Yelp
reviews666https://huggingface.co/datasets/yelp_review_full, respectively. To
not artificially craft unanswerable questions, we instruct the question
generation model to produce questions normally and later identify the
unanswerable ones. To produce a dataset that is challenging for LLMs, we
additionally leverage a question checking model777GPT-4 is used for both
question generation model and question checking model.. We search for
questions that confuse the question checking model. Specifically, we sample
the question checking model five times to produce an answer for each of the
questions. We gather questions where the question checking model flags the
questions are unanswerable any of those five times. We then ask three
crowdworkers from Amazon Mechanical Turk (MTurk) to independently verify
whether the question is answerable or not888In particular, to annotate whether
a question is answerable, we instruct the crowdworkers to select a span from
the document to answer the question. If they cannot identify a span, the
question is deemed unanswerable. To reduce noise, we take the majority vote
from three crowdworkers. To further ensure a low noise level in annotations,
we remove the examples where answer spans annotated by different crowdworkers
are disjoint from each other.. The question generation model produces 9500,
9964, and 10000 QA pairs for the BBC, Reddit, and Yelp datasets, respectively.
We keep 278, 313, and 165 examples that have confused the question checking
model. Finally, the crowdworkers identify 21.22%, 36.10%, and 30.91% of the
questions are truly unanswerable. We thus construct examples that are both
challenging to LLMs and high-quality.

#### SQuADv2, QA2, and BanditQA.

We adapt these datasets to be used for document-grounded QA. Questions in
SQuADv2 are mechanistically formulated with the intention of being
unanswerable, whereas the other two datasets feature naturally occurring
unanswerable questions. QA2 is composed of natural Google search queries, and
BanditQA includes questions formulated by users during interactions with LLMs.
More information on the modifications we make to these datasets can be found
in Appendix A.

|  | SQuADv2 | QA2 | BanditQA | BBC | Reddit | Yelp | Average
---|---|---|---|---|---|---|---|---
GPT-3.5 | ZS | 31.86 | 37.61 | 50.58 |  09.09 | 24.46 | 19.35 | 28.83
ZS CoT | 26.49 | 39.52 | 44.74 | 14.08 | 19.40 | 13.33 | 26.26
FS | 35.75 | 43.26 | 67.34 |  00.00 | 19.12 | 16.67 | 30.35
FS CoT | 51.08 | 37.90 | 70.33 | 16.22 | 37.65 | 33.77 | 41.16
GPT-4 | ZS | 85.47 | 67.40 | 71.24 | 51.93 | 61.82 | 58.74 | 66.10
ZS CoT | 84.97 | 68.55 | 67.33 | 52.02 | 55.51 | 61.65 | 65.01
FS | 77.34 | 64.17 | 80.48 | 52.07 | 65.95 | 60.74 | 66.79
FS CoT | 76.11 | 64.09 | 80.85 | 53.93 | 71.48 | 60.43 | 67.82
Llama2 | ZS | 21.29 | 35.26 | 44.51 | 24.44 | 15.49 | 24.32 | 27.55
ZS CoT | 27.76 | 37.39 | 48.22 | 19.61 | 19.23 | 27.16 | 29.89
FS | 55.36 | 54.24 | 66.77 | 27.91 | 42.11 | 45.83 | 48.70
FS CoT | 35.44 | 35.65 | 58.53 | 25.45 | 35.87 | 34.09 | 37.51
Mistral | ZS | 38.30 | 30.43 | 46.61 | 30.23 | 26.14 | 17.39 | 31.52
ZS CoT | 31.87 | 26.5 | 47.39 | 29.27 | 21.48 | 21.92 | 29.74
FS | 41.98 | 34.13 | 47.45 | 38.83 | 42.74 | 40.38 | 40.92
FS CoT | 46.65 | 44.32 | 58.23 | 38.10 | 48.28 | 32.97 | 44.76
Zephyr | ZS | 63.73 | 55.37 | 67.61 | 45.31 | 38.04 | 32.50 | 50.43
ZS CoT | 65.42 | 50.36 | 68.27 | 39.72 | 34.07 | 39.53 | 49.56
FS | 67.29 | 63.06 | 67.67 | 42.86 | 50.00 | 30.23 | 53.52
FS CoT | 64.25 | 71.10 | 68.61 | 42.03 | 49.61 | 43.40 | 56.50
Table 4: Comparing F1 scores for unanswerable question detection with different prompting methods using both proprietary and open-source models on CouldAsk. The best method for each base model is italicized, and the best method across all base models is bolded. |  | SQuADv2 | QA2 | BanditQA | BBC | Reddit | Yelp | Average
---|---|---|---|---|---|---|---|---
GPT-3.5 | ZS |  03.55 |  06.88 |  05.71 |  01.69 |  04.42 |  09.80 |  05.34
ZS CoT |  03.55 |  03.64 |  04.35 |  01.69 |  02.65 |  03.92 |  03.30
FS |  03.35 |  08.91 |  06.25 |  00.00 |  00.88 |  05.88 |  04.21
FS CoT |  05.52 |  08.50 |  07.20 | 10.17 |  03.54 |  07.84 |  07.13
GPT-4 | ZS | 17.16 | 23.89 | 11.68 | 52.54 |  08.85 | 43.14 | 26.21
ZS CoT | 15.78 | 18.22 |  08.29 | 35.59 | 14.16 | 35.29 | 21.22
FS | 10.45 | 17.00 | 10.19 | 42.37 |  08.85 | 31.37 | 20.04
FS CoT |  09.86 | 17.81 | 10.60 | 44.07 |  07.96 | 17.65 | 17.99
Llama2 | ZS |  02.56 |  06.88 |  05.30 | 13.56 |  04.42 | 11.76 |  07.42
ZS CoT |  03.75 |  03.24 |  02.99 | 10.17 |  01.77 |  09.80 |  05.29
FS |  07.10 | 14.17 |  08.15 | 16.95 |  08.85 | 17.65 | 12.14
FS CoT |  03.16 |  04.45 |  05.84 | 13.56 |  03.54 |  05.88 |  06.07
Mistral | ZS |  01.58 |  02.02 |  04.35 | 11.86 |  01.77 |  01.96 |  03.92
ZS CoT |  02.96 |  01.21 |  04.08 |  06.78 |  00.88 |  07.84 |  03.96
FS |  03.35 |  04.05 |  03.67 | 22.03 |  06.19 | 11.76 |  08.51
FS CoT |  05.92 |  04.05 |  06.39 | 16.95 |  05.31 | 13.73 |  08.72
Zephyr | ZS |  07.89 | 12.15 |  07.61 | 30.51 |  04.42 |  09.80 | 12.06
ZS CoT |  08.09 |  07.69 |  07.34 | 20.34 |  06.19 |  07.84 |  09.58
FS |  05.33 | 15.38 |  07.07 | 13.56 |  04.42 |  07.84 |  08.93
FS CoT |  08.88 | 13.77 | 10.19 | 35.59 |  07.96 | 13.73 | 15.02
Table 5: Question Reformulation. Success rates using different prompting
methods with both proprietary and open-source models on CouldAsk. The best
method for each base model is italicized, and the best method across all base
models is bolded.

###  4.2 Evaluating Reformulation

To improve the utility of QA systems in responding to unanswerable questions,
the reformulated questions must be (1) answerable by the documents and (2)
relevant to the original questions posed by the users. As illustrated by the
examples in Table 4.1, a reformulation could be answerable but not relevant,
or relevant but not answerable. A successful reformulation must satisfy both
conditions. There are multiple equally good reformulations for each question.
For instance, when given the original question, it is hard to determine which
of the first two reformulations in Table 4.1 would be closer to the user’s
intent. As a result, we opt for a reference-free evaluation approach, where
the evaluation does not rely on gold reformulations.

Measuring the relatedness of two questions involves determining how closely
their topics, intents, and meanings are aligned. With these goals in mind, we
propose three reference-free relevance metrics: edit distance, entity overlap
ratio999We justify our choice of entity overlap ratio as a relevance metric
with human evaluation in Section 7., and cosine similarity between the
original question and the reformulation to indicate the level of relevance. We
consider the reformulation to be unanswerable and have zero relatedness for
the unanswerable questions that are not successfully detected by the system.
To automatically evaluate (1), we train a Llama2-7B model on CouldAsk to
classify whether the reformulation is answerable or not. The classifier
achieved 95% accuracy on a held-out validation set. We release the classifier
on Hugging Face . For (2), we calculate the Levenshtein edit distance, use
GPT-4 to tag entities for computing entity overlap ratios, and apply OpenAI
embedding models to produce question embeddings for computing cosine
similarities. Finally, a reformulation that is answerable but irrelevant, or
vice versa, is not yet helpful. To consolidate the evaluation into a single
unified score, using entity overlap ratios as an example, we assign a score of
1 to a reformulation if it is both answerable and has an entity overlap ratio
of more than 50%; otherwise, we assign a score of 0. We refer to this binary
score as _success rate_.

##  5 Experimental Setup

#### Models.

We test a range of instruction-finetuned LLMs. For proprietary models, we
consider GPT-3.5 (gpt-3.5-turbo-0125) and GPT-4 (gpt-4-0613). For open-source
models, we consider a list of 7-billion-parameter models:
Llama2101010huggingface.co/meta-llama/Llama-2-7b-chat-hf Touvron et al.
(2023), Mistral111111huggingface.co/mistralai/Mistral-7B-Instruct-v0.2 Jiang
et al. (2023), and Zephyr121212huggingface.co/HuggingFaceH4/zephyr-7b-beta
Tunstall et al. (2023).

#### Comparisons.

We consider several prompting approaches: zero-shot (ZS) and few-shot (FS)
prompting and ZS and FS chain-of-thought (CoT) prompting. We first prompt LLMs
to determine whether the input question cannot be answered by the provided
document. For ZS and FS prompting, we use the prompt provided by
SurgeAI131313SurgeAI prompt: “Answer the following from the above passage
alone, and if you can’t determine the answer based on the passage, say that
you don’t know the answer.”, which explicitly instructs the model to not
produce an answer if the answer cannot be determined from the document alone.
For ZS and FS CoT prompting, we expand the aforementioned prompt by asking the
model to think step by step to come up with a reason to explain and support
its decision. Only questions determined to be unanswerable proceed to the
question reformulation stage. In this stage, all methods are provided with
their previous turns where the models determine the questions are
unanswerable. ZS and FS prompting instruct the model to make minimum edits to
the original question to make it answerable. ZS and FS CoT prompting instruct
the model to think step by step to reason about the minimum edits they can
make.

Error Category | % |  Original question |  Revised question
---|---|---|---
Simply rephrasing / producing the same questions | 62 |  When was he born? |  When was Jay Chou born and raised in Taipei, Taiwan?
|  Which team won the most NFL Europe titles? |  Who was the team that won the most NFL Europe titles?
Producing questions by copying documents | 14 |  When did the Cubs play their first home game at Wrigley Field? |  When did the Cubs move to Wrigley Field?
|  what are the characteristics of the Classical Roman architecture? |  What are some of the characteristics of Classical Roman architecture that were adopted by Renaissance architects?
Producing irrelevant questions | 17 |  What is Snow Patrol’s most famous song? |  Who are some famous musicians that have expressed admiration for Snow Patrol?
|  which campus is the biggest in University of California? |  Which college in the University of California system is not controlled by the Regents or President?
Other | 11 |  How many arms does Krishna have? |  I apologize for the confusion. The passage does not mention how many arms Krishna has.
Table 6: Error analysis on 100 revised questions generated by different
models.

##  6 Results

#### Detecting Unanswerable Questions

Being able to detect unanswerable questions is a necessary precondition for
successful question reformulation. Table 4 presents the F1 scores for
unanswerable question detection using different prompting approaches with each
base model. Performance is often better for existing datasets than new ones,
which indicates our approach’s effectiveness in generating more challenging
questions. Among all models, GPT-4 performs best at identifying unanswerable
questions. Surprisingly, both Mistral and Zephyr are more accurate at
detecting unanswerable questions than GPT-3.5. Among all prompting techniques,
FS CoT consistently improves upon ZS, with a larger degree of improvement
observed in smaller models compared to larger ones.

#### Reformulating Questions

Table 5 presents success rates for question reformulation vary dramatically
from domain to domain. News (BBC) appears to be the least challenging domain,
with success rates ranging from 10.17 to 52.54 depending on base models.
Reddit is a challenging domain, with success rates ranging from 4.42 to 14.16.
The results on Wikipedia are mixed. While SQuADv2, QA2, and BanditQA are in
the Wikipedia domain, LLMs achieve the lowest success rates on BanditQA. We
hypothesize that user queries written during interaction require deeper
revision.

Among all base models, GPT-4 achieves the highest average success rate
(26.21), while GPT-3.5 has the lowest average success rate (7.13). Among all
open-source models, Zephyr has the best performance. When it comes to
prompting methods, there is not a clear winner. Different LLMs can be improved
with different prompting approaches. GPT-3.5, Mistral, and Zephyr benefit the
most from FS CoT prompting, GPT-4 from ZS, Llama2 from FS. We include
individual metrics for question reformulation in Appendix B.

##  7 Analysis

#### Qualitative analysis

We randomly sample and analyze 20 reformulated questions from each base model
(a total of 100 questions) that cannot be answered by the corresponding
documents. We summarize the results in Table 6. We identify three major types
of errors. The most frequent type is that the models simply rephrase or
generate the same questions. Most of the errors in this type are contributed
by open-source models such as Llama2.

Another type of error that occurs 14% of the time is that the models generate
a question by copying a document span that looks similar to the original
question. For example, given the original question about the characteristics
of the Classical Roman architecture, the model identifies a span that is
similar to the original question and generates a question based on this span.
However, the model does not plan thoroughly about whether the new question can
be answered or not.

For 17% of the time, the models propose questions that are irrelevant to the
original questions. For example, in the Snow Patrol question, the subject of
the reformulation has entirely changed from asking about the most famous song
to famous musicians. Finally, we group the remaining eleven errors in the
Other type, where there usually is not even a question produced.

Document:
In December 2007, Sport England published a survey which revealed that
residents of St Albans were the 10th most active in England in sports and
other fitness activities. 30.8% of the population participate at least 3 times
a week for 90 minutes. Question:
What is St Albans Sport?
ZS CoT for unanswerable question detection:
The article did not provide information on what St Albans Sport is, so I don’t
know. ZS CoT for question reformulation:
The article discusses the activity level of the residents of St Albans in
sports and fitness but does not detail a specific sport. Instead of asking
"What is St Albans Sport?" we could ask, "How often do residents of St Albans
participate in sports and fitness activities?" to get an answer from the given
passage.
ZS for question reformulation:
What is the level of participation in sports and other fitness activities in
St Albans?

Figure 2: Example outputs produced by GPT-4. Via prompting, the model detects
unanswerable questions then reformulates the questions with a second prompt.

#### Limited benefit from FS CoT on Question Reformulation.

We explore why FS CoT improves the detection of unanswerable questions but not
question reformulation by conducting a qualitative analysis of GPT-4 outputs
on a BanditQA example, as illustrated in Figure 2. It is relatively
straightforward to determine why a question is unanswerable — either the
document does not provide the necessary information or there is a
presupposition that conflicts with the document. However, question
reformulation demands compositional reasoning. The model needs to first decide
on a reformulation strategy and then plan the specific steps to achieve the
reformulation. The reformulated question generated by GPT-4 via FS CoT
prompting is closer to being answerable. However, the model misses a subtle
detail — the document only mentions the exercise habits of 30.8% of residents,
not the general population. Therefore, FS CoT alone, without further
methodological innovation, does not fully address the challenge of question
reformulation.

Figure 3: The relation between the percentage of reformulations answerable by
the documents and the type of minimum spans in the original questions. q span
are the examples where the minimum span is the full question, while short span
includes all other instances. q span
---
Original Q |  What medicine is made from Coca?
Reformulated Q |  What substance is derived from the Coca leaf?
short span
Original Q |  When was USB-C developed?
Reformulated Q |  When was USB developed?
Table 7: Examples of a question with the minimum span being the entire
question (q span) and a question where the minimum span is a noun (short
span).

#### Compositional Modifications vs. Answerability.

We hypothesize that it is more difficult to reformulate an unanswerable
question to be answerable when it requires compositional modifications, which
means making global edits to the question instead of making local edits.

To quantify edits required, we follow Lee et al. (2020) and annotate the
minimum span of a question to explain why the question cannot be answered by
the document. We use GPT-4 to annotate unanswerable questions in BanditQA,
QA2, and Yelp. We divide the questions into two categories. The first category
comprises questions whose minimum span is the entire question. We call these
_q span_. The second category covers questions that have a shorter minimum
span, typically a noun or a noun phrase. We call these _short span_. We
calculate how many reformulations are answerable, broken down by the type of
minimum span. We consider the reformulations generated by zero-shot prompting
with GPT-4, GPT-3.5, and Zephyr.

The results of this analysis are in Figure 3. Our findings consistently show
that fewer reformulations are answerable when the minimum span constitutes the
entire question compared to when the minimum span is shorter, with only one
exception in zero-shot prompting with Zephyr on Yelp.

We present examples for each span type in Table 7. When the minimum span is
the entire question, we cannot attribute the presupposition error to a smaller
segment of the question. As a result, the modification has to be applied to
the full question. For example, for the q-span example in Table 7, modifying
individual parts of the question cannot correct the presupposition error, and
therefore the model needs to make global changes. On the contrary, when the
minimum span is short, it only requires local edits. For the short-span
question in Table 7, replacing USB-C with USB is enough to correct the
question. Future efforts should be more devoted to the more challenging cases
to make progress on question reformulation.

| Edit Distance | Entity Overlap
---|---|---
Fleiss’ $\kappa$ | 40.96 | 93.99
Table 8: The correlation between the tested metrics and human-judged relevance
between two questions, evaluated using Fleiss’ $\kappa$.

#### Sufficiency of entity overlap ratios.

Our metric is for relevance is based on a minimum entity overlaps. To judge
the sufficiency of this metric, we compare it to human evaluation. As a
baseline we consider Levenshtein edit distance, a method to measure the
similarity between two questions, as a baseline metric. We have a human
annotator evaluate 200 pairs of reformulated questions produced by zero-shot
prompting with GPT-4 and GPT-3.5 on BanditQA. The question pairs are randomly
shuffled to ensure the annotator remains unaware of the model source of each
reformulation. The annotator then selects the more relevant question from each
pair, based on alignment with the original question’s intent. Subsequently, we
identify the question with a higher entity overlap ratio and the question with
a lower edit distance as the more relevant ones, respectively.

We calculate the Fleiss’ $\kappa$ score between human evaluations and each of
the metrics, with the results summarized in Table 8. Compared to edit
distance, the entity overlap ratio more accurately represents the relevance
between the original and reformulated questions (93.99 vs. 40.96). A Fleiss’
$\kappa$ score of 93.99 also suggests a near-perfect agreement between the
entity overlap ratio and human judgements. We hypothesize that the specific
semantic properties of the questions are more central than the surface form
represented by edit distance.

##  8 Conclusion

Users often ask unanswerable questions when they seek information from
unfamiliar documents. Existing LLMs identify these questions but do not aid
users in reformulating new questions, resulting in ineffective user-LLM
interactions. We introduce CouldAsk, a compiled set of grounded-document QA
datasets designed to study both unanswerable question detection and question
reformulation.

## Limitations

While our benchmark offers advantages over existing sources, we acknowledge
the following limitations. Questions in BBC, Reddit, and Yelp are generated by
GPT-4, and they may not accurately represent questions posed by humans.
Despite best efforts to ensure high-quality annotations, occasional human
errors are possible. Additionally, our benchmark only collects English
questions and thus lacks language diversity. Finally, regarding evaluation,
the way we currently measure success rates only focuses on mistakes made on
unanswerable questions. If an answerable question is detected to be
unanswerable, we do not evaluate question reformulation in such cases.

## Acknowledgments

This work was supported by NSF CAREER #2037519 and NSF #1901030. We also thank
Lillian Lee and the anonymous reviewers for their helpful feedback.

## References

  * Agrawal et al. (2022) Monica Agrawal, Stefan Hegselmann, Hunter Lang, Yoon Kim, and David Sontag. 2022.  Large language models are few-shot clinical information extractors.  In _Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing_ , pages 1998–2022, Abu Dhabi, United Arab Emirates. Association for Computational Linguistics.
  * Faustini et al. (2023) Pedro Faustini, Zhiyu Chen, Besnik Fetahu, Oleg Rokhlenko, and Shervin Malmasi. 2023.  Answering unanswered questions through semantic reformulations in spoken QA.  In _Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 5: Industry Track)_ , pages 729–743, Toronto, Canada. Association for Computational Linguistics.
  * Gao et al. (2023) Ge Gao, Hung-Ting Chen, Yoav Artzi, and Eunsol Choi. 2023.  Continually improving extractive QA via human feedback.  In _Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing_ , pages 406–423, Singapore. Association for Computational Linguistics.
  * Guha et al. (2023) Neel Guha, Julian Nyarko, Daniel E. Ho, Christopher Re, Adam Chilton, Aditya Narayana, Alex Chohlas-Wood, Austin Peters, Brandon Waldon, Daniel Rockmore, Diego Zambrano, Dmitry Talisman, Enam Hoque, Faiz Surani, Frank Fagan, Galit Sarfaty, Gregory M. Dickinson, Haggai Porat, Jason Hegland, Jessica Wu, Joe Nudell, Joel Niklaus, John J Nay, Jonathan H. Choi, Kevin Tobia, Margaret Hagan, Megan Ma, Michael Livermore, Nikon Rasumov-Rahe, Nils Holzenberger, Noam Kolt, Peter Henderson, Sean Rehaag, Sharad Goel, Shang Gao, Spencer Williams, Sunny Gandhi, Tom Zur, Varun Iyer, and Zehua Li. 2023.  Legalbench: A collaboratively built benchmark for measuring legal reasoning in large language models.  In _Thirty-seventh Conference on Neural Information Processing Systems Datasets and Benchmarks Track_.
  * Hu et al. (2023) Shengding Hu, Yifan Luo, Huadong Wang, Xingyi Cheng, Zhiyuan Liu, and Maosong Sun. 2023.  Won’t get fooled again: Answering questions with false premises.  In _Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 5626–5643, Toronto, Canada. Association for Computational Linguistics.
  * Jiang et al. (2023) Albert Q Jiang, Alexandre Sablayrolles, Arthur Mensch, Chris Bamford, Devendra Singh Chaplot, Diego de las Casas, Florian Bressand, Gianna Lengyel, Guillaume Lample, Lucile Saulnier, et al. 2023.  Mistral 7b.  _arXiv preprint arXiv:2310.06825_.
  * Kim et al. (2023) Najoung Kim, Phu Mon Htut, Samuel R. Bowman, and Jackson Petty. 2023.  (QA)2: Question answering with questionable assumptions.  In _Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 8466–8487, Toronto, Canada. Association for Computational Linguistics.
  * Kim et al. (2021) Najoung Kim, Ellie Pavlick, Burcu Karagol Ayan, and Deepak Ramachandran. 2021.  Which linguist invented the lightbulb? presupposition verification for question-answering.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pages 3932–3945, Online. Association for Computational Linguistics.
  * Lee et al. (2020) Gyeongbok Lee, Seung-won Hwang, and Hyunsouk Cho. 2020.  SQuAD2-CR: Semi-supervised annotation for cause and rationales for unanswerability in SQuAD 2.0.  In _Proceedings of the Twelfth Language Resources and Evaluation Conference_ , pages 5425–5432, Marseille, France. European Language Resources Association.
  * Majumder et al. (2021) Bodhisattwa Prasad Majumder, Sudha Rao, Michel Galley, and Julian McAuley. 2021.  Ask what’s missing and what’s useful: Improving clarification question generation using global knowledge.  In _Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 4300–4312, Online. Association for Computational Linguistics.
  * Min et al. (2020) Sewon Min, Julian Michael, Hannaneh Hajishirzi, and Luke Zettlemoyer. 2020.  AmbigQA: Answering ambiguous open-domain questions.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 5783–5797, Online. Association for Computational Linguistics.
  * Pyatkin et al. (2023) Valentina Pyatkin, Jena D. Hwang, Vivek Srikumar, Ximing Lu, Liwei Jiang, Yejin Choi, and Chandra Bhagavatula. 2023.  ClarifyDelphi: Reinforced clarification questions with defeasibility rewards for social and moral situations.  In _Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 11253–11271, Toronto, Canada. Association for Computational Linguistics.
  * Rajpurkar et al. (2018) Pranav Rajpurkar, Robin Jia, and Percy Liang. 2018.  Know what you don’t know: Unanswerable questions for squad.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)_ , pages 784–789.
  * Rao and Daumé III (2018) Sudha Rao and Hal Daumé III. 2018.  Learning to ask good questions: Ranking clarification questions using neural expected value of perfect information.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 2737–2746, Melbourne, Australia. Association for Computational Linguistics.
  * Touvron et al. (2023) Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. 2023.  Llama 2: Open foundation and fine-tuned chat models.  _arXiv preprint arXiv:2307.09288_.
  * Tran et al. (2023) Son Quoc Tran, Gia-Huy Do, Phong Nguyen-Thuan Do, Matt Kretchmar, and Xinya Du. 2023.  Agent: A novel pipeline for automatically creating unanswerable questions.  _arXiv preprint arXiv:2309.05103_.
  * Tunstall et al. (2023) Lewis Tunstall, Edward Beeching, Nathan Lambert, Nazneen Rajani, Kashif Rasul, Younes Belkada, Shengyi Huang, Leandro von Werra, Clémentine Fourrier, Nathan Habib, et al. 2023.  Zephyr: Direct distillation of lm alignment.  _arXiv preprint arXiv:2310.16944_.
  * White et al. (2021) Julia White, Gabriel Poesia, Robert Hawkins, Dorsa Sadigh, and Noah Goodman. 2021.  Open-domain clarification question generation without question examples.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_ , pages 563–570, Online and Punta Cana, Dominican Republic. Association for Computational Linguistics.
  * Yu et al. (2023) Xinyan Yu, Sewon Min, Luke Zettlemoyer, and Hannaneh Hajishirzi. 2023.  CREPE: Open-domain question answering with false presuppositions.  In _Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 10457–10480, Toronto, Canada. Association for Computational Linguistics.

| SQuADv2 | QA2 | BanditQA | BBC | Reddit | Yelp | Average
---|---|---|---|---|---|---|---
Prompting | 18.74 | 21.86 | 10.60 | 47.46 | 7.96 | 33.33 | 23.33
Explicit Prompting | 11.43 |  08.91 |  04.07 | 18.64 | 7.07 | 17.64 | 11.00
Rule-based |  04.50 |  02.43 |  01.22 | 11.86 | 0.88 |  03.90 |  04.13
Table 9: Comparing the standard zero-shot prompting method to various baselines to hack the proposed metric, success rates. |  | SQuADv2 | QA2 | BanditQA | BBC | Reddit | Yelp | Average
---|---|---|---|---|---|---|---|---
Answerability | Prompting | 28.01 | 36.84 | 36.84 | 71.19 | 13.27 | 47.06 | 36.58
Rule-based | 28.01 | 35.22 | 24.86 | 62.71 | 10.61 | 52.94 | 35.73
Entity Overlap Ratio | Prompting | 38.64 | 24.87 | 29.13 | 45.00 | 44.73 | 48.69 | 38.51
Rule-based | 21.36 | 13.60 | 13.15 | 23.50 | 15.55 | 21.41 | 18.10
Table 10: Analysis of individual metrics used to compute success rates.

##  Appendix A Dataset Details

We provide more details about the existing datasets we include in CouldAsk.

#### SQuADv2

is a collection of QA pairs from Wikipedia articles, including questions with
presupposition errors. Such questions are written by crowdworkers who are
instructed to craft questions that are plausible but have presuppositions that
cannot be verified by the associated articles. These annotators either modify
valid questions or create new questions based on entities or topics related to
the text, ensuring the questions appear relevant and deceivingly valid.

#### QA2

contains QA pairs from general web articles. QA2 sources questions from
Google’s autocompletion API. It calls the API on prefix strings – when, where,
which, how, what, why, who, whose – to complete the queries. Crowdworkers are
recruited to (1) search for relevant documents and (2) check whether these
questions contain presupposition errors. QA2 features naturally occurring
presupposition errors and diverse document sources. The original QA2 dataset
is open-domain QA and only provides annotations for relevant URLs. To obtain
the context, we scrape the text from their annotated URL and remove the
examples where the contexts are not clear.

#### BanditQA

investigate whether continual human feedback can improve extractive QA
systems; we repurpose the dataset to study naturally occurring presupposition
errors. During data collection, users are presented with Wikipedia passages,
and they are required to write questions about things they are curious to
know. In a later verification step, over 30% of these questions are identified
to have presupposition errors. BanditQA is closest to the setting of this
study – when users are unfamiliar with the documents, they come up with
presuppositions that cannot be grounded in the documents.

##  Appendix B More Analysis

#### Hacking success rates.

We explore the potential for our proposed metrics to be manipulated in order
to artificially achieve perfect scores. We consider two approaches. The first
approach directly prompts LLMs to produce an answerable question while leaving
all the entities unchanged. In the second approach, we test a rule-based
heuristic that has the following steps: (1) tag entities in the original
question via LLM prompting, (2) select the sentence in the document that has
the highest entity overlap ratio with the original question, and (3) replace
something in the select sentence to create a wh-question, again using LLM
prompting. The results, summarized in Table 9, indicate that our success rates
remain robust, even when faced with methods explicitly designed to exploit our
metric.

We seek to understand where performance degrades in a rule-based heuristic by
inspecting individual metrics used to compute success rates. We present the
results in Table 10. While using the rule-based heuristic leads to similar
answerability performance, the entity overlap ratio drops significantly. We
show further qualitative analysis of the error types in Figure 4.

Failure case 1: Not all entities present in the same sentence
Original unanswerable question: What are balance in an open system of
particles? Entities: balance, open system, particles Most-overlapped sentence
in the document: This means that in a closed system of particles, there are no
internal forces that are unbalanced. Reformulated Question: What does this
mean about internal forces in a closed system of particles? Note: The three
entities are mentioned in different sentences. Therefore, the most overlapped
sentence only has one overlapped entity. Although this question can be
answered, the reformulation is not successful due to the low entity overlap
ratio. Note that most of our questions have an average number of two to three
entities.
Failure case 2: Reformulated questions are still unanswerable
Original unanswerable question: What job requires no qualifications? Entities:
job, qualifications Most-overlapped sentence in the document: As in the House
of Commons, a number of qualifications apply to being an MSP. Reformulated
Question: What qualifications apply to being an MSP as in the House of
Commons? Note: Even though a part of the sentence was replaced with a what
question, this process does not necessarily make the reformulated question
become answerable. The article does not mention what specific qualifications,
and successful reformulations require a deeper understanding of the document
as a whole.

Figure 4: Qualitative analysis on the rule-based heuristic approach to hack
our proposed metric, success rates.

#### Individual Metrics in Question Reformulation

We present individual metrics for question reformulation. Table 13 presents
the answerability (top) and entity overlap ratios (bottom) achieved by each
method using each base model. We additionally report cosine similarities in
Table 14 and edit distance in Table 15.

#### Assessing the Accuracy of Entity Tagging Models through Human Evaluation

To determine the entity overlap ratio, we first utilize GPT-4 to identify
entities within both the original and revised questions. To ensure the
credibility of the tagged entities, we conduct a human evaluation on a set of
100 questions. The findings of this evaluation are shown in Table 11. This
analysis reveals that GPT-4 exhibits both high precision and recall in the
identification of entities, affirming its effectiveness for this task.

| Precision | Recall
---|---|---
GPT-4 | 99 | 94
Table 11: Performance of applying GPT-4 to tag entities. | BBC | Reddit | Yelp
---|---|---|---
Fleiss’ $\kappa$ | 65.07 | 59.94 | 58.76
Table 12: Inter-annotator agreement rates among three workers for annotating unanswerable questions. |  | SQuADv2 | QA2 | BanditQA | BBC | Reddit | Yelp | Average
---|---|---|---|---|---|---|---|---
|  | Answerability |
GPT-3.5 | ZS |  04.73 | 12.55 |  08.42 |  05.08 |  04.42 |  09.80 |  07.50
ZS CoT |  05.92 | 10.93 |  08.29 |  05.08 |  02.65 |  05.88 |  06.46
FS |  07.30 | 18.22 | 14.54 |  00.00 |  00.88 |  05.88 |  07.80
FS CoT |  09.07 | 16.19 | 15.35 | 10.17 |  03.54 | 11.76 | 11.02
GPT-4 | ZS | 26.82 | 36.84 | 22.96 | 72.88 |  08.85 | 58.82 | 37.86
ZS CoT | 27.22 | 34.82 | 19.16 | 66.10 | 14.16 | 52.94 | 35.73
FS | 21.10 | 34.01 | 25.41 | 66.10 |  08.85 | 47.06 | 33.76
FS CoT | 21.30 | 34.82 | 24.18 | 71.19 |  07.96 | 52.94 | 35.40
Llama2 | ZS |  04.73 | 12.55 |  08.15 | 18.64 |  04.42 | 11.76 | 10.05
ZS CoT |  05.13 |  05.67 |  05.30 | 13.56 |  01.77 |  09.80 |  06.87
FS | 13.41 | 25.51 | 12.36 | 28.81 | 10.62 | 23.53 | 19.04
FS CoT |  05.13 |  08.50 |  08.42 | 15.25 |  05.31 |  07.84 |  08.41
Mistral | ZS |  03.55 |  06.48 |  06.39 | 15.25 |  02.65 |  03.92 |  06.37
ZS CoT |  05.13 |  02.02 |  07.74 | 11.86 |  02.65 |  07.84 |  06.21
FS |  06.90 |  08.50 |  07.47 | 28.81 |  06.19 | 19.61 | 12.92
FS CoT | 10.85 | 10.12 |  09.92 | 23.73 |  005.31 | 19.61 | 13.26
Zephyr | ZS | 15.78 | 23.89 | 12.77 | 42.37 |  04.42 | 11.76 | 18.50
ZS CoT | 14.20 | 12.96 | 12.23 | 33.90 |  06.19 | 11.76 | 15.21
FS | 20.32 | 34.82 | 16.98 | 38.98 |  04.42 | 15.69 | 21.87
FS CoT | 15.38 | 25.91 | 15.49 | 38.98 |  07.96 | 21.57 | 20.88
|  | Entity Overlap Ratios |
GPT-3.5 | ZS | 10.44 | 10.56 | 19.82 |  02.37 | 11.28 |  08.50 | 10.50
ZS CoT |  07.27 |  05.94 | 11.39 |  01.81 |  07.82 |  03.27 |  06.25
FS |  06.75 | 10.32 | 23.38 |  00.00 |  05.68 |  09.15 |  09.21
FS CoT | 14.97 |  08.03 | 28.17 |  07.91 | 16.74 | 15.20 | 15.17
GPT-4 | ZS | 38.73 | 24.93 | 31.26 | 49.49 | 45.13 | 48.86 | 39.73
ZS CoT | 29.99 | 20.28 | 23.73 | 34.97 | 32.98 | 38.30 | 30.04
FS | 26.13 | 18.42 | 31.66 | 43.98 | 45.84 | 47.32 | 35.56
FS CoT | 24.85 | 18.76 | 33.93 | 41.27 | 48.27 | 39.51 | 34.43
Llama2 | ZS |  05.78 |  08.40 | 18.07 | 12.43 |  06.98 | 12.25 | 10.65
ZS CoT |  06.53 |  05.16 | 13.45 |  07.37 |  05.84 | 10.62 |  08.16
FS | 21.09 | 17.88 | 35.15 | 14.58 | 30.22 | 31.86 | 25.13
FS CoT |  08.16 |  07.42 | 17.53 | 12.74 | 10.34 | 12.42 | 11.43
Mistral | ZS |  06.85 |  04.93 | 10.73 | 10.88 |  07.67 |  04.41 |  07.58
ZS CoT |  06.27 |  02.63 | 11.38 |  06.10 |  04.57 |  09.31 |  06.71
FS |  08.88 |  05.74 | 12.99 | 19.07 | 26.55 | 26.63 | 16.64
FS CoT | 10.46 |  06.07 | 16.66 | 15.37 | 22.05 | 20.26 | 15.15
Zephyr | ZS | 21.25 | 14.24 | 32.94 | 26.50 | 17.92 | 16.01 | 21.48
ZS CoT | 17.13 | 11.57 | 23.01 | 19.58 | 14.90 | 17.32 | 17.25
FS | 12.19 | 14.88 | 28.60 | 12.43 | 18.07 | 12.81 | 16.50
FS CoT | 21.37 | 16.94 | 35.29 | 30.42 | 33.26 | 25.98 | 27.21
Table 13: Question reformulation quality broken down by answerability (top) and entity overlap ratios (bottom) on CouldAsk. The best method for each base model is highlighted with an underscore, and the best method across all base models is bolded. |  | SQuADv2 | QA2 | BanditQA | BBC | Reddit | Yelp | Average
---|---|---|---|---|---|---|---|---
GPT-3.5 | ZS | 14.33 | 18.98 | 26.24 |  04.94 | 13.55 | 10.74 | 14.80
ZS CoT |  07.27 | 11.18 | 14.30 |  03.60 |  07.52 |  03.97 |  07.97
FS |  06.75 | 20.46 | 33.78 |  00.00 |  08.66 |  09.47 | 13.19
FS CoT | 14.97 | 16.76 | 38.43 |  08.86 | 21.90 | 20.22 | 20.19
GPT-4 | ZS | 57.92 | 42.45 | 44.52 | 64.72 | 55.18 | 59.91 | 54.12
ZS CoT | 44.51 | 33.66 | 31.64 | 51.80 | 32.54 | 42.49 | 39.44
FS | 43.98 | 35.28 | 47.66 | 59.4 | 54.18 | 53.71 | 49.03
FS CoT | 42.31 | 34.43 | 48.84 | 60.27 | 59.93 | 52.49 | 49.71
Llama2 | ZS |  08.26 | 16.42 | 23.30 | 17.22 |  08.66 | 15.94 | 14.97
ZS CoT |  07.90 |  08.62 | 14.60 |  09.31 |  06.41 | 10.61 |  09.57
FS | 33.02 | 35.71 | 51.55 | 28.46 | 38.01 | 38.38 | 37.52
FS CoT |  09.78 | 11.18 | 19.66 | 13.01 | 11.10 | 14.16 | 13.15
Mistral | ZS | 10.62 | 10.12 | 15.42 | 16.88 | 10.71 |  08.19 | 11.99
ZS CoT |  07.55 |  05.20 | 12.60 |  08.36 |  05.63 |  08.64 |  08.00
FS | 14.34 | 12.71 | 19.56 | 28.50 | 36.13 | 32.55 | 23.97
FS CoT | 12.64 | 12.93 | 19.64 | 19.72 | 22.86 | 20.50 | 18.05
Zephyr | ZS | 31.48 | 27.49 | 42.97 | 38.23 | 22.54 | 20.85 | 30.59
ZS CoT | 21.60 | 16.43 | 26.66 | 26.55 | 16.45 | 19.63 | 21.22
FS | 27.89 | 32.76 | 39.19 | 25.91 | 26.50 | 16.05 | 28.05
FS CoT | 30.72 | 28.60 | 42.91 | 35.22 | 42.45 | 33.67 | 35.59
Table 14: Cosine similarity using different prompting methods with both proprietary and open-source models on CouldAsk. The best method for each base model is highlighted with an underscore, and the best method across all base models is bolded. |  | SQuADv2 | QA2 | BanditQA | BBC | Reddit | Yelp | Average
---|---|---|---|---|---|---|---|---
GPT-3.5 | ZS |  01.23 |  02.04 |  02.37 |  00.24 |  00.95 |  00.51 |  01.22
ZS CoT |  04.88 | 11.70 | 11.58 |  03.07 |  03.35 |  06.25 |  06.81
FS |  01.79 |  02.90 |  04.24 | - |  00.94 |  00.37 |  01.71
FS CoT |  03.12 |  02.77 |  05.57 |  01.22 |  02.66 |  02.20 |  02.92
GPT-4 | ZS |  04.09 |  04.80 |  05.63 |  06.63 |  05.69 |  06.47 |  05.55
ZS CoT | 13.64 | 16.77 | 16.72 | 15.92 | 18.76 | 22.27 | 17.35
FS |  04.18 |  04.53 |  06.31 |  06.46 |  07.21 |  07.78 |  06.08
FS CoT |  05.05 |  05.86 |  07.47 |  08.41 |  09.98 |  08.29 |  07.51
Llama2 | ZS |  02.24 |  04.87 |  05.40 |  01.47 |  00.82 |  01.02 |  02.64
ZS CoT |  06.61 | 13.05 | 15.10 |  07.08 |  04.70 |  09.33 |  09.31
FS |  02.53 |  03.19 |  02.66 |  01.54 |  02.13 |  02.37 |  02.40
FS CoT |  09.02 | 10.27 | 18.04 |  08.29 | 12.09 |  09.55 | 11.21
Mistral | ZS |  05.93 |  05.20 |  07.85 |  03.29 |  02.19 |  02.18 |  04.44
ZS CoT | 11.20 |  09.17 | 20.88 | 11.39 |  09.21 |  08.88 | 11.79
FS |  06.05 |  04.23 |  06.00 |  04.29 |  04.69 |  05.27 |  05.09
FS CoT | 16.05 | 17.85 | 25.98 | 20.17 | 24.45 | 15.49 | 20.00
Zephyr | ZS | 11.53 | 12.28 | 13.04 | 10.93 |  06.22 |  03.41 |  09.57
ZS CoT | 40.03 | 29.28 | 47.48 | 30.58 | 15.26 | 15.53 | 29.69
FS |  08.32 |  08.64 |  09.70 |  07.00 |  06.06 |  03.84 |  07.26
FS CoT | 14.95 | 25.63 | 22.88 | 16.14 | 13.13 |  09.90 | 17.11
Table 15: Edit distance using different prompting methods with both
proprietary and open-source models on CouldAsk. The best method for each base
model is highlighted with an underscore, and the best method across all base
models is bolded.

##  Appendix C More Annotation Details

#### Annotation Guidelines

We present annotation guideline for annotating unanswerable questions in
Figure 5. The crowdworkers are those who were identified to contribute high-
quality annotations from our previous annotation tasks. For every completed
HIT, we pay the crowdworker USD 0.5.

Figure 5: Annotation guideline for crowdworkers to annotate unanswerable
questions.

#### Annotation Agreement

We report inter-annotator agreement rates between crowdworkers in Table 12.
Specifically, we compute how often all three workers agree with each other.
The agreement rates on the three datasets are close to each other.


# Lyapunov Densities For Markov Processes: An Application To Quantum Systems
With Non-Demolition Measurements

Özkan Karabacak  Horia Cornean  Rafael Wisniewski

###### Abstract

Stochastic convergence of discrete time Markov processes has been analysed
based on a dual Lyapunov approach. Using some existing results on ergodic
theory of Markov processes, it has been shown that existence of a properly
subinvariant function (counterpart of the Lyapunov density in deterministic
systems) implies sweeping of a Markov process out of the sets where this
function is integrable. Such a function can be used as a certificate of
convergence in probability of a stochastic system. We apply this technique to
Markov processes induced by a quantum system with non-demolition measurement
and propose dual Lyapunov certificates to certify sweeping.

###### keywords:

Dual Lyapunov theory, sweeping of Markov processes, quantum non-demolition
measurements

††journal: Systems and Control Letters

[ozkan]organization=Kadir Has University, Department of Mechatronics
Engineering,addressline=Cibali Mah., city=İstanbul, postcode=34083,
country=Turkey

[horia]organization=Aalborg University, Department of Mathematical
Sciences,addressline=Skjernvej 4A, city=Aalborg, postcode=9220,
country=Denmark

[rafael]organization=Aalborg University, Department of Electronic
Systems,addressline=Fredrik Bajers Vej 7, city=Aalborg, postcode=9220,
country=Denmark

##  1 Introduction

Stability certificates are used for the analysis and control of both
deterministic and stochastic dynamical systems. The existence of Lyapunov
functions and dual Lyapunov functions (also called Lyapunov density) can imply
certain asymptotic behaviour for deterministic systems. On the other hand,
Lyapunov-type functions can also be employed for stochastic systems to certify
certain types of stochastic convergence (Kushner, 1967). More specifically,
Bielecki functions certify an asymptotic property called sweeping (Lasota and
Mackey, 1994) for Markov stochastic processes. On the other hand, the
existence of a subinvariant, absolutely continuous measure implies the so-
called Foguel alternative: either there exists an invariant density or the
system is sweeping. In this work, we show that the existence a properly
subinvariant absolutely continuous measure directly implies sweeping as it
prohibits the existence of an invariant density. This result, which can be
seen as a dual version of the Bielecki function theorem, is a consequence of
the literature on ergodic theory of Markov processes (Foguel, 1969; Lasota and
Mackey, 1994; Komorowski and Tyrcha, 1989) but is not stated and proven
elsewhere.

Our work is inspired by an alternative approach to Lyapunov theory for
deterministic systems, which is the so-called dual Lyapunov approach developed
by (Rantzer, 2001) and has found applications in control of nonlinear
autonomous systems (Prajna et al., 2004), safety and reachibility analysis
(Prajna and Rantzer, 2007; Kivilcim et al., 2019), stability certification of
switched systems (Karabacak et al., 2020) and certification of synchronization
of coupled oscillators (Kudeyt et al., 2022). Dual Lyapunov approach leverages
measurable functions (called Rantzer’s function or Lyapunov density) that are
Radon-Nikodym derivatives of absolutely continuous subinvariant measures
(called Lyapunov measure in (Vaidya et al., 2010)). It can be shown via
standard techniques from potential theory (Syski, 1973) that the existence of
a properly subinvariant measure, which is necessarily infinite under the
assumption that solutions exist globally in time, implies that almost all
solutions converge to the set near which the measure is infinite (Karabacak et
al., 2018).

Applications of the dual Lyapunov theory to stochastic systems appeared for
stochastic differential equations (Van Handel, 2006) and for discrete-time
maps with independent, identically distributed noise (Vaidya, 2015). However,
up to our knowledge, dual Lyapunov approach has not been applied to general
Markov processes, where dynamics is given by a linear operator (called Markov
operator) on the set of Lebesgue integrable functions (Foguel, 1969; Lasota
and Mackey, 1994).

It has been shown in (Foguel, 1966) that a Markov process is sweeping if it
has no invariant density but admits a subinvariant function. In (Komorowski
and Tyrcha, 1989), various extensions of this result have been obtained.
Komornik and Melichercik (1995) discuss that if the system is dissipative,
then the condition on the existence of a subinvariant function is redundant;
and they characterize the sweeping property based on the absence of an
invariant density and the existence of a particular property, which implies
that the system is dissipative and therefore a construction of a subinvariant
function is possible. In this work, to come up with an easily checkable
condition, we waive the condition on the absence of an invariant density
(which might be nontrivial to show as in (Tyrcha, 1988, theorem 4.2)) and show
that the existence of a properly subinvariant function implies the sweeping
property.

We apply our main result to a quantum system with non-demolition measurements.
Non-demolition measurements are represented by invertible transformations
providing information about the state without collapsing it onto certain
subspaces. This type of measurements have been utilized to stabilize a photon
box system via feedback control, leading to a Nobel prize (Haroche, 2013).
Stochastic convergence of this system has been analyzed in (Amini et al.,
2012, 2013), where stochastic Lyapunov functions (Kushner, 1967) were
employed. We show that the dual Lyapunov approach can also provide (not yet
new) results on stochastic convergence for the photon box system.

##  2 Sweeping Markov Operators

In this section, we prove that the existence of a properly subinvariant
function implies sweeping of the process from an admissible family of subsets
on which the function has finite integral. As an example, we show that using
such a subinvariant function sweeping can be shown more directly for the cell
size distribution in a cell cycle processes (Tyson and Hannsgen, 1986; Tyrcha,
1988; Komorowski and Tyrcha, 1989). Finally, we apply our main result to
iterative function systems where the probability of choice of the active
function depends on the current state (Barnsley et al., 1988). This will be
used, in the next section, to prove stochastic convergence of trajectories for
quantum systems involving non-demolition measurements.

###  2.1 Preliminaries: Hopf Decomposition, Subinvariant Functions and
Sweeping

If not stated otherwise, we follow the setting used by Foguel (1969); Lasota
and Mackey (1994); Komorowski and Tyrcha (1989), where all arguments hold up
to zero measure sets. Let $(X,\Sigma,m)$ be a $\sigma$-finite measure space.
For a measurable function $f:X\to X$, $\|f\|$ denotes the $L_{1}$-norm of $f$,
namely $\|f\|=\int|f|\ dm$. $L_{1}(X)$ and $L_{\infty}(X)$ denote the set of
measurable functions with a finite $L_{1}$-norm and the set of bounded
measurable functions, respectively, where two functions differing only on a
measure zero set are assumed to be identical. A linear operator
$\mathcal{P}:L_{1}(X)\to L_{1}(X)$ is a Markov operator if $\mathcal{P}$ is a
contraction ($\|\mathcal{P}f\|\leq\|f\|$) and positive ($f\geq
0\implies\mathcal{P}f\geq 0$). In this case, $(X,\Sigma,m,\mathcal{P})$ is
called a Markov process (Foguel, 1969). An equivalent probabilistic definition
of a Markov process is given via transition probabilities $P(x,A)$ defined for
all $x\in X$ and for all $A\in\Sigma$ such that the conditions

$\displaystyle 0\leq P(x,A)\leq 1,$ (1) $\displaystyle P(\cdot,A)\text{ is
measurable},$ (2) $\displaystyle A=\bigcup_{i}A_{i}\text{ for disjoint
}A_{i}\text{'s}\implies P(x,A)=\sum_{i}P(x,A_{i}),$ (3) $\displaystyle
m(A)=0\implies P(x,A)=0\text{ for almost all }x\in X$ (4)

are satisfied for each $A\in\Sigma$. The correspondence between these
equivalent definitions are given via

$P(x,A)=U1_{A}(x),$ (5)

where $1_{A}$ is the characteristic function of $A$ and $U:L_{\infty}(X)\to
L_{\infty}(X)$ is the adjoint operator of $\mathcal{P}$. Equivalently, the
Markov operator $\mathcal{P}$ satisfies

$\displaystyle\int_{A}(\mathcal{P}\rho)(x)m(dx)$
$\displaystyle=\int_{X}(\mathcal{P}\rho)(x)1_{A}(x)m(dx)$ (6)
$\displaystyle=\int_{X}\rho(x)P(x,A)m(dx),$ (7)

for all $A\in\Sigma$, where duality between $\mathcal{P}$ and $\mathcal{U}$ is
used in the second equality.

######  Definition 1 (Hopf decomposition (Foguel, 1969)).

Let $u\in L_{1}(X)$ and $u>0$. The set

$C:=\left\\{x\in
X:\,\sum_{k=0}^{\infty}\big{(}\mathcal{P}^{k}u\big{)}(x)=\infty\right\\}$

does not depend on $u$ and it is called the conservative part of $X$, while
$D=X\setminus C$ is called the dissipative part. $\mathcal{P}$ is said to be
dissipative if $X=D$ (up to a set of measure zero).

The following lemma characterizes the result of the infinite sum in Definition
1, when $u\geq 0$.

######  Lemma 1 (Foguel (1969, p.11)).

If $u\in L_{1}(X)$ and $u\geq 0$ then

$\sum_{k=0}^{\infty}\big{(}\mathcal{P}^{k}u\big{)}(x)\in\begin{dcases}\\{0,\infty\\}&\text{for
}x\in C\\\ [0,\infty)&\text{for }x\in D\end{dcases}$

The operator $\mathcal{P}$ can be extended to the set of all non-negative
measurable functions as

$\big{(}\mathcal{P}f\big{)}(x)=\lim_{k\to\infty}(\mathcal{P}f_{k})(x),$

where $\\{f_{k}\\}\subset L_{1}(X)$ is any sequence of non-negative measurable
functions pointwise converging monotonically to $f$ almost everywhere (Foguel,
1969, p.4). Note that $\mathcal{P}f$ may be equal to infinity on a set of
positive measure.

######  Lemma 2 (Foguel (1969, p.16)).

Let $u$ be a real, nonnegative, measurable function on $X$ such that
$\mathcal{P}u\leq u$ on $C$. Then $\mathcal{P}u=u$ on $C$.

A measurable function $f:X\to X$ is called

  * 1.

invariant if $\mathcal{P}f=f$

  * 2.

subinvariant if $\mathcal{P}f\leq f$

  * 3.

properly subinvariant if $\mathcal{P}f<f$

  * 4.

a density if $f\geq 0$ and $\|f\|=1$

In the following, we introduce the so-called sweeping property of Markov
operators and some other definitions from (Komorowski and Tyrcha, 1989):

######  Definition 2 (Sweeping operator).

A Markov operator $\mathcal{P}$ is called sweeping (with respect to a familly
$\mathcal{A}\subset\Sigma$) if

$\lim_{n\to\infty}\int_{A}\big{(}\mathcal{P}^{n}f\big{)}\,dm=0,\quad\forall
A\in\mathcal{A}\text{ and }f\in L_{1}(X).$ (8)

In particular, if $X\subset\mathbb{R}^{N}$ or $\mathbb{C}^{N}$ and the family
$\mathcal{A}$ consists of countably many open sets $A_{n},\ n=1,2,\dots$, then
we say that $\mathcal{P}$ is sweeping to

$\Lambda:=\bigcap_{A\in\mathcal{A}}A^{c}$ (9)

if $\Lambda$ is non-empty; otherwise, we say that $\mathcal{P}$ is sweeping to
infinity111Here, we consider the standard metric in $\mathbb{R}^{n}$ or
$\mathbb{C}^{n}$ and hence this argument and the definition of $\Lambda$ is
not up to measure zero sets..

######  Definition 3 (Admissible family).

A family $\mathcal{A}\subset\Sigma$ is called admissible if

  * 1.

$m(A)<\infty$ for $A\in\mathcal{A}$,

  * 2.

$A_{1},A_{2}\in\mathcal{A}$ implies $A_{1}\cup A_{2}\in\mathcal{A}$,

  * 3.

there exists a countable subfamily $\\{A_{n}\\}\subset\mathcal{A}$ such that
$\bigcup_{n}A_{n}=X$.222We take this equality in the same form as in the
literature where equality holds again up to measure zero sets. Hence, this
equality does not imply that $\Lambda$ defined in (9) is empty but it implies
that $\Lambda$ has measure zero.

######  Definition 4 (Locally integrable function).

A measurable function $f:X\to\mathbb{R}_{+}$ is called locally integrable with
respect to $\mathcal{A}$ if

$\int_{A}fdm<\infty,\quad\text{for all }A\in\mathcal{A}.$

###  2.2 Main Result: Dual Lyapunov Function for Sweeping of Markov Processes

We now show that existence of a properly subinvariant, positive function
implies sweeping of the Markov process. The following directly follows from
Lemma 2:

######  Lemma 3.

If a properly subinvariant, positive function $u$ exists then $\mathcal{P}$ is
dissipative.

###### Proof.

Recall that all the results in this section hold up to zero measure sets.
Lemma 2 implies that $\mathcal{P}u=u$ on $C$. Since $\mathcal{P}u<u$ (almost
everywhere), this implies $C$ is a zero measure set. In other words, $X=D$ (up
to a zero measure set). ∎

######  Definition 5 (Smoothing operator).

A Markov operator $\mathcal{P}$ is called smoothing (with respect to
$\mathcal{A}$) if for any given $A\in\mathcal{A}$, $f\in L_{1}(X)$ and
$\epsilon>0$ there is $\delta>0$ such that

$E\in\Sigma,\ E\subset A,\
m(E)\leq\delta\implies\int_{E}\big{(}\mathcal{P}^{n}f\big{)}\,dm\leq\epsilon,\quad\text{for
all }n=1,2,\dots$ (10)

The following is proven in (Komorowski and Tyrcha, 1989):

######  Lemma 4.

If a subinvariant, nonnegative function exists then $\mathcal{P}$ is
smoothing.

###### Proof.

See the proof of (Komorowski and Tyrcha, 1989, Corollary 2.2) ∎

A version of the so-called Foguel alternative given in (Komorowski and Tyrcha,
1989, Theorem 3.1) states that a Markov operator $\mathcal{P}$ induced by a
stochastic kernel is sweeping (with respect to an admissible family
$\mathcal{A}$) if there is no invariant density but there exists a
subinvariant, locally integrable (with respect to $\mathcal{A}$), positive
function. To obtain a similar result for arbitrary Markov operators, we use
the following relation between sweeping and dissipativeness:

######  Theorem 1 (Komorowski and Tyrcha (1989, Theorem 4.1)).

If a Markov operator $\mathcal{P}$ is dissipative; i.e., $X=D$, and smoothing
with respect to an admissible family $\mathcal{A}\subset\Sigma$ then
$\mathcal{P}$ is sweeping with respect to $\mathcal{A}$.

Based on the above definitions and results, we obtain the following
characterizations of sweeping via properly subinvariant functions:

######  Theorem 2.

Let $(X,\Sigma,m)$ be a $\sigma$-finite measure space. A Markov operator
$\mathcal{P}:X\to X$ is sweeping with respect to an admissible family
$\mathcal{A}\subset\Sigma$, if there exists a properly subinvariant, locally
integrable (with respect to $\mathcal{A}$), positive function $u$.

###### Proof.

By Lemma 3, $\mathcal{P}$ is dissipative, and by Lemma 4, it is also
smoothing. Hence Theorem 1 implies the result. ∎

Let us assume that $X=\mathbb{R}^{N}$ or $\mathbb{C}^{N}$,
$\|\mathcal{P}f\|=\|f\|$ for all $f\in L_{1}(X)$ and consider the implication
of sweeping when $\left(\bigcup_{A\in\mathcal{A}}A\right)^{\text{c}}$ is a
singleton, say $\\{\bar{\phi}\\}$. For a given $f\in L_{1}(X)$ with $\|f\|=1$,
define probability measures $\mu_{n}(V):=\left(\int_{V}\mathcal{P}^{n}f\
dm\right)$. If $\mathcal{P}$ is sweeping with respect to $\mathcal{A}$, then
$\lim_{n\to\infty}\mu_{n}(A)=\lim_{n\to\infty}\int_{A}\mathcal{P}^{n}f\ dm=0$
for any $A\in\mathcal{A}$. Hence, for a bounded continuous function $g$, we
have $\int gd\mu_{n}\to g(\bar{\phi})$. In other words, $\mu_{n}$ converges
weakly to the Dirac measure $\delta_{\bar{x}}$. Let $\Phi_{n}$ be a random
variable taking values on $X$ with respective distributions
$\mathcal{P}^{n}f$. Then, by (Çinlar, 2011, Remark 5.2.b), we can conclude
that $\Phi_{n}$ converges to $\bar{\Phi}=\bar{\phi}$ in probability:

######  Corollary 1.

Let $(X=\mathbb{R}^{N}\text{ or }\mathbb{C}^{N},\Sigma,m,\mathcal{P})$ be a
Markov process, $\|\mathcal{P}f\|=\|f\|$ for all $f\in L_{1}(X)$ and
$\Phi_{0}$ be a random variable defined on $X$ and taking values on $X$ with a
distribution that is absolutely continuous with respect to $m$ with Radon-
Nikodym derivative being $\rho_{0}\in L_{1}(X)$. Let
$\mathcal{A}\subset\Sigma$ be an admissible family such that
$\bigcap_{\\{A\in\mathcal{A}\\}}A^{\text{c}}$ is a singleton, say
$\\{\bar{\phi}\\}$. Then, the stochastic process $\\{\Phi_{n}\\}$ with a
sequence of distributions $\\{\mathcal{P}^{n}\rho_{0}\\}$ converges in
probability to the random variable $\bar{\Phi}\equiv\bar{\phi}$ if there
exists a positive, properly subinvariant, locally integrable (with respect to
$\mathcal{A}$) measurable function $u$.

The following example illustrates an application of Theorem 2 to a stochastic
process modeling the cell size dynamics in a cell cycle process.

######  Example 1.

We consider the dynamics of the cell size distribution proposed in (Tyson and
Hannsgen, 1986) as

$\rho_{n+1}(x)=\mathcal{P}\rho_{n}(x):=\int_{\sigma}^{\infty}K(x,y)\rho_{n}(y)\
dy,$ (11)

where $\rho_{n}$ is the distribution of cell sizes at birth for the $n$th
generation cells, $\sigma$ is the minimum size at birth and $K(x,y)$ is a
stochastic kernel given by

$K(x,y)=\begin{dcases}\frac{\alpha}{\sigma}\left(\frac{x}{\sigma}\right)^{-1-\alpha}&,\sigma\leq
y<1\\\
\frac{\alpha}{\sigma}\left(\frac{x}{\sigma}\right)^{-1-\alpha}y^{\alpha}&,1\leq
y<\frac{x}{\sigma}\\\ 0&,\frac{x}{\sigma}\leq y.\\\ \end{dcases}$ (12)

Here $\alpha$ is a positive parameter. For $\alpha\ln\sigma>-1$, it is known
that there is no invariant density (Tyrcha, 1988, Theorem 4.2) and that
$\bar{\rho}(x)=x^{-1+\beta}$ is invariant for some $\beta>0$ (Komorowski and
Tyrcha, 1989). Note that $\bar{\rho}(x)$ is locally integrable with respect to
the family of subsets $\\{[\sigma,a)\mid a>\sigma\\}$ which implies that the
system is sweeping to infinity if $\alpha\ln\sigma\geq-1$ (Komorowski and
Tyrcha, 1989). We now show that this can also be proven using directly Theorem
2 without the need to show the absence of an invariant density

$\displaystyle\mathcal{P}\bar{\rho}=\mathcal{P}(x^{-1+\beta})$
$\displaystyle=\frac{\alpha}{(\alpha+\beta)\sigma^{\beta}}\
x^{-1+\beta}+\alpha\frac{\alpha-\sigma^{\beta}(\alpha+\beta)}{\beta(\alpha+\beta)\sigma^{-\alpha}}\
x^{-1-\alpha}$ (13)

Hence, $\mathcal{P}(x^{-1+\beta})<x^{-1+\beta}$ if

$f(\beta):=\alpha-\sigma^{\beta}(\alpha+\beta)<0.$ (14)

Note that the first term in (13) is less than $x^{-1+\beta}$ whereas the
second term is negative. $f(0)=0$ and $f^{\prime}(0)=-\alpha\ln\sigma-1<0$
imply that for a sufficiently small positive $\beta$, (14) is satisfied and
$x^{-1+\beta}$ is properly subinvariant. Hence, Theorem 2 implies that the
system is sweeping to infinity.

###  2.3 An Extension of Frobenius-Perron Operators

A special class of Markov operators describing the dynamics of probabilities
under a measurable, nonsingular333S is nonsingular if $m(S^{-1}(A))=0$ for all
$A$ with $m(A)=0$, deterministic map $S:X\to X$ are Frobenius-Perron operators
(Lasota and Mackey, 1994). In this case, $P(x,A)=(U1_{A})(x)=1_{A}(S(x))$ and
the Markov operator $\mathcal{P}$ can be obtained using the Radon-Nikodym
derivative of the measure $\hat{\mu}_{\rho}(A)=\int_{S^{-1}(A)}\rho\ dm$ with
repect to the Lebesgue measure $m$ as

$\mathcal{P}\rho=\frac{d\hat{\mu}_{\rho}}{dm}.$ (15)

Equivalently, $\mathcal{P}$ satisfies

$\displaystyle\int_{A}(\mathcal{P}\rho)(x)m(dx)=\int_{S^{-1}(A)}\rho(x)m(dx)$
(16)

If $S$ is differentiable and invertible then Frobenius-Perron operator has the
explicit form (Lasota and Mackey, 1994, Corollary 3.2.1 and Remark 3.2.4)

$\mathcal{P}\rho(x)=\rho(S^{-1}(x))\cdot|\det DS^{-1}(x)|,$ (17)

where $D$ stands for the Jacobian.

Let us now consider an extension of the Frobenius-Perron operator to systems
where the transition probabilities are given via

$P(x,A)=\sum_{k=1}^{K}p_{k}(x)\cdot 1_{A}(S_{k}(x)),$ (18)

where $\sum_{k=1}^{K}p_{k}(x)=1$ for all $x\in X$ and $p_{k}(\cdot)$ is
measurable for all $k$. Such processes arise from the iterated function
systems where probability of choice of a function depends on the state
(Barnsley et al., 1988). This induces a stochastic process $\\{X_{n}\\}$ with
transition probabilities

$\displaystyle\text{Prob}[X_{n+1}\in A\mid X_{n}=x]$
$\displaystyle=\sum_{k=1}^{K}\text{Prob}[\kappa_{n}=k\mid
X_{n}=x]\cdot\text{Prob}[X_{n+1}\in A\mid\kappa_{n}=k,X_{n}=x]$
$\displaystyle=\sum_{k=1}^{K}p_{k}(x)\cdot 1_{A}(S_{k}(x)),$

where $\kappa_{n}$ is a discrete random variable (taking values in
$\\{1,\dots,K\\}$) dependent on $X_{n}$ via the transition kernel $p_{k}(x)$.
The corresponding Markov operator $\mathcal{P}$ satisfies

$\displaystyle\int_{A}(\mathcal{P}\rho)(x)m(dx)$
$\displaystyle=\int_{X}\rho(x)P(x,A)m(dx)$
$\displaystyle=\sum_{k=1}^{K}\int_{S_{k}^{-1}(A)}\rho(x)p_{k}(x)m(dx)=\sum_{k=1}^{K}\int_{X}(\mathcal{P}_{k}(\rho
p_{k}))(x)m(dx),$

where $\mathcal{P}_{k}$ is the Frobenius-Perron operator for the deterministic
map ${S}_{k}$. When $S_{k}$’s are differentiable and invertible, by (17), we
get

$\displaystyle\mathcal{P}\rho(x)=\sum_{k=1}^{K}p_{k}(S_{k}^{-1}(x))\rho(S_{k}^{-1}(x))\cdot|\det
DS_{k}^{-1}(x)|,$ (19)

##  3 Application To Quantum Systems With Non-Demolition Measurements

In this section, we show that Markov operators in the form of (19) arise in
the analysis of quantum systems with non-demolition measurements and hence
Lyapunov densities can be used to prove stochastic convergence of such
systems.

For a real or complex vector $\phi$, let $\|\phi\|$ denote its 2-norm. The set
of all possible states of an $N$ dimensional quantum system is the unit
complex sphere

$\mathcal{S}_{N}\subset\mathbb{C}^{N},\quad\mathcal{S}_{N}=\\{\phi\in\mathbb{C}^{N}:|\|\phi\|=1\\}.$

Consider a set of non-demolition measurement operators
${S}_{k}:\mathcal{S}_{N}\to\mathcal{S}_{N}$, $k=1,\dots,K$ defined by

${S}_{k}(\phi):=\frac{M_{k}\phi}{\|M_{k}\phi\|}$ (20)

such that $M_{k}$’s are positive definite, invertible matrices satisfying

$\sum_{k=1}^{K}M_{k}^{*}M_{k}=I.$ (21)

Note that

${S}_{k}^{-1}(\phi)=\frac{M_{k}^{-1}\phi}{\|M_{k}^{-1}\phi\|}.$ (22)

For a fixed time $n$, we introduce a random variable $\Phi_{n}$ taking values
in $\mathcal{S}_{N}$ and a random variable $\kappa_{n}$ taking values in
$\\{1,\dots,K\\}$ representing the outcome of the measurement at time $n$. The
probability of obtaining the outcome $\kappa_{n}=k$ is independent from $n$
and is given by

$p_{k}(\phi):=\text{Prob}\left(\kappa_{n}=k|\Phi_{n}=\phi\right)=\|M_{k}\phi\|^{2}.$
(23)

(21) ensures the unity of the sum of probabilities. The following discrete-
time Markov process arises:

$\Phi_{n+1}={S}_{\kappa_{n}}(\Phi_{n})$ (24)

Note that $\mathcal{S}_{N}$ can be identified with the $2N-1$ dimensional real
sphere $\mathbb{S}^{2N-1}$ through the map

$(x_{1}+iy_{1},\dots,x_{N}+iy_{N})\mapsto(x_{1},y_{1},\dots,x_{N},y_{N}),\quad\sum_{j=1}^{N}(x_{j}^{2}+y_{j}^{2})=1.$

Let us consider the Riemannian measure on $\mathcal{S}_{N}$ induced by
$\mathbb{S}^{2N-1}$ and let $L^{1}(\mathcal{S}_{N})$ denote the set of
Lebesgue integrable (with respect to the Riemannian measure) functions on
$\mathcal{S}_{N}$. By (19), the Frobenius-Perron operator
$\mathcal{P}:L^{1}(\mathcal{S}_{N})\to L^{1}(\mathcal{S}_{N})$ related to the
dynamics driven by (24) can be obtained as

$\displaystyle\mathcal{P}\rho(\phi)$
$\displaystyle=\sum_{k=1}^{K}p_{k}({S}_{k}^{-1}\phi)\cdot\rho({S}_{k}^{-1}\phi)\cdot\left|\det\left(D{S}_{k}^{-1}(\phi)\right)\right|$
(25)
$\displaystyle=\sum_{k=1}^{K}\frac{1}{\|M_{k}^{-1}\phi\|^{2}}\cdot\rho({S}_{k}^{-1}\phi)\cdot\left|\det\left(D{S}_{k}^{-1}(\phi)\right)\right|.$
(26)

We first calculate the determinant of the Jacobian of an operator of form (20)
on a real sphere:

######  Lemma 5.

Let ${S}:\mathbb{S}^{N-1}\to\mathbb{S}^{N-1}$ be defined by
${S}(\phi):=M\phi/\|M\phi\|$, where $\phi\in\mathbb{R}^{N}$ with $\|\phi\|=1$
and $M$ is an invertible $N\times N$ real matrix. Then

$|\det\left(D{S}(\phi)\right)|=\frac{|\det(M)|}{\|M\phi\|^{N}},$

where $DS(\phi)$ is the Jacobian acting on the tangent space at $\phi$ seen as
an element of $\mathbb{S}^{N-1}$.

###### Proof.

At the outset, we compute the differential $DF$. Let
$\psi:(-\epsilon,\epsilon)\to\mathbb{S}^{N-1}$ be a path such that
$\psi(0)=\phi$, and $\dot{\psi}(0)=v$. Consequently,

$\displaystyle DS(\phi)v$
$\displaystyle=\left.\frac{d}{dt}\right|_{t=0}S(\psi(t))=\frac{Mv}{\|M\phi\|}-\frac{M\phi}{2\|M\phi\|^{3}}\left(\phi^{T}M^{T}Mv+v^{T}M^{T}M\phi\right)$
$\displaystyle=\|M\phi\|^{-1}\left(Mv-S(\phi)^{T}S(\phi)Mv\right)=\|M\phi\|^{-1}\left(\mathrm{Id}-S(\phi)^{T}S(\phi)\right)Mv$

Hence,

$\displaystyle
DS(\phi)=\|M\phi\|^{-1}\left(\mathrm{Id}_{N}-S(\phi)S(\phi)^{T}\right)M.$ (27)

By direct computation, we conclude that $DF(\phi)\phi=0$; whereas its range is
orthogonal to $S(\phi)$ when $\phi\in\mathbb{S}^{N-1}$, since
$S(\phi)^{T}(\mathrm{Id}_{N}-S(\phi)S(\phi)^{T})=0$.

Define $U\equiv U(\phi)$ to be an orthogonal $N\times N$ matrix which sends
$S(\phi)$ into $\phi$, i.e., $US(\phi)=\phi$. If $\\{f_{j}\\}_{j=1}^{N-1}$
denotes an orthonormal basis of the subspace orthogonal to $S(\phi)$, then
$e_{j}=Uf_{j}$ is an orthonormal basis of the subspace orthogonal to $\phi$.
Let us compute the matrix of $UM$ in the basis $\\{\phi,e_{1},...,e_{N-1}\\}$.
We have

$a_{00}:=\phi^{T}\,UM\phi=S(\phi)^{T}M\phi=\|M\phi\|,$
$a_{j0}:=e_{j}^{T}UM\phi=f_{j}^{T}M\phi=\|M\phi\|f_{j}^{T}S(\phi)=0,\quad
1\leq j\leq N-1,$

and by (27)

$a_{jk}=e_{j}^{T}UMe_{k}=f_{j}^{T}Me_{k}=\|M\phi\|\,[DS(\phi)]_{jk},\quad
1\leq j,k\leq N-1.$

In the above, we have used
$\left(\mathrm{Id}_{N}-\ket{S(\phi)}\bra{S(\phi)}\right)f_{j}=f_{j}$.

Thus, in this basis $\\{\phi,e_{1},...,e_{N-1}\\}$, the matrix
$\|M\phi\|^{-1}\,UM$ looks like

$\begin{bmatrix}1&*&\dots&*\\\ 0&[DS(\phi)]_{11}&\dots&[DS(\phi)]_{1,N-1}\\\
.&.&.&.\\\ .&.&.&.\\\
0&[DS(\phi)]_{N-1,1}&\dots&[DS(\phi)]_{N-1,N-1}\end{bmatrix}$

where “$*$” corresponds to the entries which are irrelevant for the further
computation. This implies that the determinant of $DS(\phi)$ equals the
determinant of $\|M\phi\|^{-1}\,UM$. Hence,
$|\det(DS(\phi))|=|\det(\|M\phi\|^{-1}\,M)|=\frac{1}{\|M\phi\|^{N}}|\det(M)|$.
∎

The determinant of the Jacobian of an operator of form (20) on a unit complex
sphere is as follows:

######  Lemma 6.

Let ${S}:\mathcal{S}_{N}\to\mathcal{S}_{N}$ be defined by
${S}(\phi):=M\phi/\|M\phi\|$, where $\phi\in\mathbb{C}^{N}$ with $\|\phi\|=1$
and $M$ is an invertible matrix with complex entries. Then we have

$|\det\left(D{S}(\phi)\right)|=\frac{|\det(M)|^{2}}{\|M\phi\|^{2N}},$

where $DS(\phi)$ is the Jacobian acting on the tangent space at $\phi$ seen as
an element of $\mathbb{S}^{2N-1}$.

###### Proof.

Let $\phi=u+iv\in\mathcal{S}_{N}$ with $u,v\in\mathbb{R}^{N}$ such that
$\|\phi\|^{2}=\|u\|^{2}+\|v\|^{2}=1$. We write $M=M_{R}+iM_{I}$. As a
consequence, the real and complex part of $M\psi$ is

$\tilde{M}\begin{bmatrix}u\\\ v\end{bmatrix},\hbox{ with
}\tilde{M}=\begin{bmatrix}M_{R}&-M_{I}\\\ M_{I}&M_{R}\end{bmatrix}.$

We observe that $\|M\phi\|=\|\tilde{M}[u^{T},v^{T}]^{T}\|_{\mathbb{R}^{2N}}$
and compute the determinant of the block matrix $\tilde{M}$,

$\displaystyle\det(\tilde{M})=\det(M_{R}+iM_{I})\det(M_{R}-iM_{I})=\det(M)\overline{\det(M)}=|\det(M)|^{2}.$

Now we can apply Lemma 5, where $M$ is replaced by $\tilde{M}$, and $N$ by
$2N$. ∎

We can now obtain the Frobenius-Perron operator of a stochastic quantum system
driven by quantum nondemolition measurements in terms of the measurement
operators. The following directly follows from (22), (26) and Lemma 6.

######  Theorem 3.

The Frobenius-Perron operator of (24) is given by

$\mathcal{P}\rho(\phi)=\sum_{k=1}^{K}\frac{|\det(M_{k}^{-1})|^{2}}{\|M_{k}^{-1}\phi\|^{{2}N+2}}\cdot\
\rho\left(\frac{M_{k}^{-1}\phi}{\|M_{k}^{-1}\phi\|}\right).$ (28)

In the following example, we apply Theorem 2 to the Markov operator in Theorem
3:

######  Example 2.

We consider the quantum system studied by Amini et al. (2012), namely the
system (24) where $M_{k}=\text{diag}(m_{k}(1),\dots,m_{k}(N))$,
$m_{k}(i)\in(0,1)$, $\sum_{k=1}^{K}m_{k}(i)^{2}=1$ and $i_{1}\neq i_{2}$
implies that $m_{k}(i_{1})\neq m_{k}(i_{2})$ for all $k=1,\dots,K$ and
$i=1,\dots,N$. A Lyapunov function has been found for this system in (Amini et
al., 2012) showing almost sure convergence to the set of elementary vectors
(corresponding to Fock states) for almost all initial quantum states. Here, to
apply the dual Lyapunov method, we choose

$\rho(\phi)=\frac{1}{\prod_{i=1}^{N}{|\phi_{i}|^{2}}}.$ (29)

Then, applying Theorem 3, we get

$\displaystyle\mathcal{P}\rho(\phi)$ $\displaystyle=$
$\displaystyle\sum_{k=1}^{K}\frac{(\det(M_{k}^{-1}))^{2}}{\|M_{k}^{-1}\phi\|^{{2}N+2}}\cdot\rho\left(\frac{M_{k}^{-1}\phi}{\|M_{k}^{-1}\phi\|}\right)$
$\displaystyle=$
$\displaystyle\sum_{k=1}^{K}\frac{\prod_{i=1}^{N}{\left|\frac{1}{m_{k}(i)}\right|^{2}}}{\|M_{k}^{-1}\phi\|^{{2}N+2}}\cdot\frac{1}{\prod_{i=1}^{N}{\left|\frac{{\phi_{i}}/{m_{k}(i)}}{\|M_{k}^{-1}\phi\|}\right|^{2}}}$
$\displaystyle=$
$\displaystyle\left(\sum_{k=1}^{K}\frac{1}{\|M_{k}^{-1}\phi\|^{2}}\right)\cdot\frac{1}{\prod_{i=1}^{N}{|\phi_{i}|^{2}}}$
$\displaystyle<$
$\displaystyle\frac{1}{\prod_{i=1}^{N}{|\phi_{i}|^{2}}}=\rho(\phi),$

where the last line is proven in A. By Theorem 2, the system (24) is sweeping
to $\bigcup_{i}\\{\phi_{i}=0\\}$. We conjecture that, recursively applying the
same argument for each subspace of type $\phi_{i}=0$, one may reach to the
conclusion that $\phi$ converges in probability to the set of Fock states,
which correspond to computational basis in $\mathcal{S}_{N}$. However, we
could not rigorously prove this conjecture.

##  4 Conclusion

The dual Lyapunov approach has been extended to a Markov process defined by a
Markov operator and a sufficient condition for the sweeping property of a
Markov process has been obtained. The result has been applied to the dynamics
of cell size distributions in a cell cycle process and to the dynamics of a
quantum system driven by nondemolition measurements.

Unlike the standard Lyapunov techniques, such as Kushner’s invariance theorem
(see Theorem 6 in (Amini et al., 2012)), the dual method does not require a
calculation of the largest invariant set. Conversely, demonstrating the
existence of a Lyapunov density, particularly when the nonintegrability
condition is limited to the vicinity of the stochastic attractor, can present
significant challenges. Practical tools for certifying the asymptotic behavior
of Markov processes may be developed through computational methods designed to
construct Lyapunov densities.

## Acknowledgements

ÖK acknowledges support from Scientific and Technological Research Council of
Turkey, grant TÜBİTAK-1001 122E522. RW acknowledges support from Independent
Research Fund Denmark–Natural Sciences, for the profect entitled _Q-Safe:
Quantum-Probabilistic Safe Decision Algorithms_. HC acknowledges support from
Independent Research Fund Denmark–Natural Sciences, grant
DFF–10.46540/2032-00005B.

##  Appendix A A Lemma for the Proof of $\mathcal{P}\rho_{1}<\rho_{1}$ in
Example 2

######  Lemma 7.

Let $M_{k}=\text{diag}(m_{k}(1),\dots,m_{k}(N))$ for $k=1,\dots,K$ such that
$m_{k}(i)\in(0,1)$ and $\sum_{k=1}^{K}m_{k}(i)^{2}=1$. Then, for any nonzero
$\phi\in\mathbb{C}^{N}$,

$\sum_{k=1}^{K}\frac{\|\phi\|^{2}}{\|M_{k}^{-1}\phi\|^{2}}\leq 1,$

where equality is satisfied only when for each $k$, $m_{k}(s)$ is constant for
all $s$ satisfying $\phi_{s}\neq 0$.

###### Proof.

Note that multiplying $\phi$ by a scalar does not change the above expression.
Hence, without loss of generality, we assume that $\|\phi\|=1$. By Cauchy-
Schwarz inequality, we have

$1=\left(\sum_{i}|\phi_{i}|^{2}\right)^{2}\leq\left(\sum_{i}\left(\frac{|\phi_{i}|}{m_{k}(i)}\right)^{2}\right)\cdot\left(\sum_{i}\left(m_{k}(i)|\phi_{i}|\right)^{2}\right),$
(30)

where equality takes place only when $m_{k}(s)^{2}$ is constant for indices
$s$ satisfying $\phi_{s}\neq 0$ (this condition is automatically satisfied
when $\phi_{s}=0$ for all $s$ but one).

(30) implies that

$\frac{1}{\sum_{i}\frac{|\phi_{i}|^{2}}{m_{k}(i)^{2}}}\leq\sum_{i}m_{k}(i)^{2}|\phi_{i}|^{2},$
(31)

Hence, we have

$\sum_{k}\frac{1}{\sum_{i}\frac{|\phi_{i}|^{2}}{m_{k}(i)^{2}}}\leq\sum_{k}\sum_{i}m_{k}(i)^{2}|\phi_{k}|^{2}=\sum_{i}\sum_{k}m_{k}(i)^{2}|\phi_{i}|^{2}=\sum_{i}|\phi_{i}|^{2}=1,$

where equality takes place if, for each $k$, $m_{k}(s)^{2}$ is constant for
indices $s$ satisfying $\phi_{s}\neq 0$.

∎

## References

  * Amini et al. (2012) Amini, H., Mirrahimi, M., Rouchon, P., 2012.  Stabilization of a delayed quantum system: The photon box case-study.  IEEE Transactions on Automatic Control 57, 1918–1930.  doi:10.1109/TAC.2012.2195853.
  * Amini et al. (2013) Amini, H., Somaraju, R.A., Dotsenko, I., Sayrin, C., Mirrahimi, M., Rouchon, P., 2013\.  Feedback stabilization of discrete-time quantum systems subject to non-demolition measurements with imperfections and delays.  Automatica 49, 2683–2692.  doi:10.1016/j.automatica.2013.06.012.
  * Barnsley et al. (1988) Barnsley, M.F., Demko, S.G., Elton, J.H., Geronimo, J.S., 1988\.  Invariant measures for Markov processes arising from iterated function systems with place-dependent probabilities.  Annales de l’I.H.P. Probabilit\’es et statistiques 24, 367–394.  URL: http://www.numdam.org/conditions.
  * Çinlar (2011) Çinlar, E., 2011.  Probability and Stochastics. volume 261 of Graduate Texts in Mathematics.  Springer New York, New York, NY.  URL: http://link.springer.com/10.1007/978-0-387-87859-1, doi:10.1007/978-0-387-87859-1.
  * Foguel (1969) Foguel, S., 1969.  The Ergodic Theory of Markov Processes.  Van Nostrand Reinhold Co.
  * Foguel (1966) Foguel, S.R., 1966.  Limit theorems for Markov processes.  Transactions of the American Mathematical Society 121, 200–209.
  * Haroche (2013) Haroche, S., 2013.  Nobel Lecture: Controlling photons in a box and exploring the quantum to classical boundary.  Reviews of Modern Physics 85, 1083–1102.  doi:10.1103/RevModPhys.85.1083.
  * Karabacak et al. (2020) Karabacak, O., Kivilcim, A., Wisniewski, R., 2020.  Almost Global Stability of Nonlinear Switched Systems with Time-Dependent Switching.  IEEE Transactions on Automatic Control 65, 2969–2978.  doi:10.1109/TAC.2019.2927934.
  * Karabacak et al. (2018) Karabacak, O., Wisniewski, R., Leth, J., 2018.  On the almost global stability of invariant sets.  2018 European Control Conference, ECC 2018 , 1648–1653doi:10.23919/ECC.2018.8550488.
  * Kivilcim et al. (2019) Kivilcim, A., Karabacak, O., Wisniewski, R., 2019.  Safe reachability verification of nonlinear switched systems via a barrier density.  Proceedings of the IEEE Conference on Decision and Control 2019-Decem, 2368–2372.  doi:10.1109/CDC40024.2019.9029718.
  * Komornik and Melichercik (1995) Komornik, J., Melichercik, I., 1995\.  The Foguel Alternative For Integral Markov Operators, in: Dynamical Systems and Applications. WORLD SCIENTIFIC, pp. 441–452.  doi:10.1142/9789812796417{\\_}0027.
  * Komorowski and Tyrcha (1989) Komorowski, T., Tyrcha, J., 1989\.  Asymptotic Properties of Some Markov Operators.  Bull. Polish Acad. Sci. Math. 37, 221–228.
  * Kudeyt et al. (2022) Kudeyt, M., Kıvılcım, A., Ersöz, E.K., Karabacak, O., 2022\.  Certification of Almost Global Phase Synchronization of Coupled Oscillators URL: https://www.preprints.org/manuscript/202208.0422/v1, doi:10.20944/PREPRINTS202208.0422.V1.
  * Kushner (1967) Kushner, H.J., 1967.  Stochastic Stability and Control.  Academic Press Inc., New York.
  * Lasota and Mackey (1994) Lasota, A., Mackey, M.C., 1994\.  Chaos, Fractals and Noise.  2nd ed. ed., Springer-Verlag, New York.
  * Prajna et al. (2004) Prajna, S., Parrilo, P.A., Rantzer, A., 2004.  Nonlinear Control Synthesis by Convex Optimization.  IEEE Transactions on Automatic Control 49, 310–314.  doi:10.1109/TAC.2003.823000.
  * Prajna and Rantzer (2007) Prajna, S., Rantzer, A., 2007\.  Convex programs for temporal verification of nonlinear dynamical systems.  SIAM Journal on Control and Optimization 46, 999–1021.  doi:10.1137/050645178.
  * Rantzer (2001) Rantzer, A., 2001.  A dual to Lyapunov’s stability theorem.  Systems and Control Letters 42, 161–168.  doi:10.1016/S0167-6911(00)00087-6.
  * Syski (1973) Syski, R., 1973.  Potential theory for Markov chains.  Probabilistic Methods in Applied Mathematics 3, 213–276.
  * Tyrcha (1988) Tyrcha, J., 1988.  Asymptotic stability in a generalized probabilistic/deterministic model of the cell cycle.  J. Math. Biol 26, 465–475.
  * Tyson and Hannsgen (1986) Tyson, J.J., Hannsgen, K.B., 1986\.  Mathematical Biology Cell growth and division: a deterministic/probabilistic model of the cell cycle.  J. Math. Biology 23, 231–246.
  * Vaidya (2015) Vaidya, U., 2015.  Stochastic stability analysis of discrete-time system using Lyapunov measure.  Proceedings of the American Control Conference 2015-July, 4646–4651.  doi:10.1109/ACC.2015.7172061.
  * Vaidya et al. (2010) Vaidya, U., Mehta, P.G., Shanbhag, U.V., 2010.  Nonlinear stabilization via control lyapunov measure.  IEEE Transactions on Automatic Control 55, 1314–1328.  doi:10.1109/TAC.2010.2042226.
  * Van Handel (2006) Van Handel, R., 2006.  Almost global stochastic stability.  SIAM Journal on Control and Optimization 45, 1297–1313.  doi:10.1137/040618850.