# Bias in Text Embedding Models

Vasyl Rakivnenko, Nestor Maslej, Jessica Cervi and Volodymyr Zhukov

###### Abstract

Text embedding is becoming an increasingly popular AI methodology, especially
among businesses, yet the potential of text embedding models to be biased is
not well understood. This paper examines the degree to which a selection of
popular text embedding models are biased, particularly along gendered
dimensions. More specifically, this paper studies the degree to which these
models associate a list of given professions with gendered terms. The analysis
reveals that text embedding models are prone to gendered biases but in varying
ways. Although there are certain inter-model commonalities, for instance,
greater association of professions like nurse, homemaker, and socialite with
female identifiers, and greater association of professions like CEO, manager,
and boss with male identifiers, not all models make the same gendered
associations for each occupation. Furthermore, the magnitude and
directionality of bias can also vary on a model-by-model basis and depend on
the particular words models are prompted with. This paper demonstrates that
gender bias afflicts text embedding models and suggests that businesses using
this technology need to be mindful of the specific dimensions of this problem.

##  1 Introduction

Text embedding is an efficient AI approach that works to transform text into
numerical representations [1, 2, 3]. Text embedding has a plethora of
potential business applications [4]. Despite the growing popularity of AI and
AI text-embedding systems, the degree to which these systems are biased is not
as well-understood. This lack of understanding persists despite the fact that
it is now fairly well-documented that AI systems more broadly, are quite prone
to bias [5, 6, 7, 8, 9, 10].

This paper studies bias, in particular gender bias, in popular text embedding
models. The analysis proceeds by selecting a list of popular occupations (for
example nurse, CEO, writer), and then examining the degree to which a
selection of popular text embedding models (selected from an assortment of
leading AI developers) associates each of those occupations with gendered
terms like boy, girl, woman and man. The text embedding models studied
include: (1) AI21-v1-embed, (2) amazon-titan-embed-text-v1, (3) baai-bge-
large-zh-v1.5, (4) cohere-embed-english-v3.0, (5) bert-large, (6) llama-2-70b,
(7) msmarco-distilbert-cos-v5, (8) openai-text-embedding-ada002 and (9)
voyageai-voyage-01.

Each of the text embedding models featured in the analysis routinely
associates certain professions with gendered terms, thereby demonstrating some
degree of gendered bias. While there are certain cross-model commonalities,
for instance, homemaking and caring professions like nurse and homemaker are
more strongly associated with female identifiers, and leadership positions are
more strongly associated with male identifiers, not all models make the same
types of gendered associations. The magnitude of gendered associations also
varies strongly across models: some models are shown to be substantially more
biased than others. Finally, the gendered associations models make can be
quite sensitive to the particular words models are prompted with.

All in all, this analysis suggests that gender bias is a somewhat
idiosyncratic problem in text embedding models. Businesses that build with
these models need to be broadly mindful of the problem of bias and
specifically consider the interactions between the text-embedding models and
the word combinations they use.

##  2 Motivation

###  2.1 Problem Definition

Consider the following riddle: A man and his son get into a terrible car
crash. The father dies, and the boy is badly injured. In the hospital, the
surgeon looks at the patient and exclaims, “I cannot operate on this boy, he
is my son. Who is the surgeon?” A majority of people are reportedly unable to
solve this riddle, and this fact is taken as evidence of the widespread
prevalence of implicit gender bias [11]. Many people who hear the riddle for
the first time have difficulty assigning both the role of “mother” and
“surgeon” to the same person [11].

###  2.2 Bias in AI

There are many ways in which AI systems could be biased. Bias can be defined
as a “systematic error in decision-making processes that results in unfair
outcomes,” and in the context of AI, bias can result from ”data collection,
algorithm design, and human interpretation” [12].

There are many types of AI bias [12]. For example, there is sampling bias,
which arises when an algorithm’s training data is not fully representative of
the population on which it is ultimately deployed. There is now widespread
evidence that many leading facial recognition algorithms, which are trained
mostly on datasets of white faces, are less accurate at recognizing
individuals with darker skin tones [5, 13, 7]. There have also been documented
instances of medical image classification systems, which were predominantly
trained on images of white adult males, degrading in performance when asked to
classify the images of non-white population groups [6, 14, 15].

Algorithmic bias is another form of AI bias where algorithms are designed in
such a way to prefer certain features, which can lead to unfair selection
outcomes. A notable example of algorithmic bias occurred when Amazon created
an AI-hiring tool trained predominantly on a mostly male dataset of
historically successful Amazon applicants [16]. As such, the algorithm
associated hiring success with being male and would punish applicants if their
applications included references to gender (for example, an applicant
participating in an all-women’s choir). Overall, it is now fairly well-
established that AI systems, if improperly designed, can be biased [8, 9, 10].

###  2.3 Vector Embeddings and Bias

Embedding is an efficient approach for feature extraction in the fields of
data science and natural language processing (NLP) [1, 2, 3]. Machine learning
(ML) algorithms cannot work directly with text or symbols. The text such
systems interact with needs to be transformed into numerical representations.
Embedding is thereby the process of representing words or phrases in a high-
dimensional numerical vector space. Embeddings can be powerful because they
are less sensitive to misspellings, synonyms, and phrasing differences [4].
They can even work in cross-lingual scenarios [4].

Vector embedding models like Google’s bert, Cohere’s embed, and OpenAI’s
ada-002 can be deployed in a variety of data-centered systems [17, 2, 18]. For
instance, Google’s bert is used to parse the search intentions of users,
Cohere’s embed is an underlying technology for their Classify model, and
OpenAI’s ada-002 is a crucial backbone of Microsoft Azure’s cognitive search
[19, 20, 21]. An important feature in the success of embedding models are
powerful embedding layers, which learn continuous representations of input
information such as words, sentences, and documents from large amounts of
data. If irrelevant content is passed to the embedding model, it counters the
objective of efficient embedding and requires models to filter extraneous
information. These types of inefficiencies can reduce the quality of generated
responses, increase latency, and thereby increase operating costs [22, 23,
24].

As noted earlier, there is a plethora of scholarship that has established that
AI systems can be biased. As LLMs have become increasingly popular in recent
years, there has also been emerging scholarship highlighting how LLMs can be
biased. It is now well-understood that LLMs like GPT-3.5 and GPT-4 can exhibit
bias, especially along gender dimensions [25], that LLMs can more broadly
absorb biases from cultural associations present in language corpora [26], and
that the bias of such models can have fairly wide-ranging downstream
implications [27, 28]. Scholars have also discussed bias mitigating strategies
for LLMs [29, 4, 30].

However, in the existing literature, there are not many systematic comparisons
of the relative bias of various language models, especially text embedding
models. In other words, there are few current studies that ascertain which
text embedding models are the most or least biased, and along what particular
dimensions of bias (for example, gender, race, age, etc.). For instance, HELM,
one of the leading evaluation suites for LLMs, no longer features bias
evaluations on its most recently updated leaderboard [31]. While certain
evaluation suites like Hugging Face’s Open LLM Leaderboard evaluate models on
bias benchmarks like Winogrande, they only consider open models, meaning that
a substantial proportion of closed LLMs are left unevaluated [32, 33].
Moreover as recently established, it is also difficult to rely on the bias
evaluations that are themselves done by model developers, as leading
developers tend to test the bias of their models across widely varying
benchmarks [34].

However, it has arguably never been more important for there to be a
standardized comparison of the relative bias of leading text embedders. AI is
increasingly being used by businesses, and companies that build applications
using LLMs and text embedders sell to varying demographics. These companies
have strategic reasons to understand whether certain models are more biased
than others and the degree to which bias varies among models.

##  3 Methodology

To assess bias in text embedding models, this paper analyzes gender
associations in various notable text embedding models. Specifically, we
examine the degree to which these models associate certain occupations with
one gender over another. Table 1 lists the models analyzed, along with their
associated developer and documentation. The selected models are intended to be
broadly representative of various leading text embedding models in academia
and industry. This diverse selection ensures a robust cross-sectoral
comparison of bias in text embedding models. For reference, Figure 1 tangibly
illustrates how existing models can be biased. In this case Cohere’s text
embedding model is significantly more likely to associate the word “strong”
with the word “men” over “women”.

Model Name | Provider
---|---
AI21-v1-embed | AI21 [35]
amazon-titan-embed-text-v1 | Amazon [36]
baai-bge-large-zh-v1.5 | Beijing Academy of Artificial Intelligence [37]
cohere-embed-english-v3.0 | Cohere [38]
bert-large | Google [39]
llama-2-70b | Meta [40]
msmarco-distilbert-cos-v5 | Technische Universität Darmstadt [41]
openai-text-embedding-ada002 | OpenAI [42]
voyageai-voyage-01 | Voyage AI [43]
Table 1:  Models Analyzed Figure 1:  An example of bias in Cohere’s text
embedding model.

Traditional text embedding algorithms, such as CBoW (Continuous Bag-of-Words)
and Skip-Gram, learn word vectors by maximizing the probability of occurrence
[44, 3]. This is done either by predicting a center word given its neighbor
words or, conversely, by predicting neighbor words given a center word.
Consequently, assessing bias in text embedding models necessitates comparing
cross-word associations.

In this paper, we test a variety of text-embedding models on a dataset that
comprises over 100 words and word-pairs designed to identify biases in models
across various dimensions like gender, race, ethnicity, education, and
religion. The dataset is taken from the open-source dataset that was released
when BIG-bench was launched [45]. The analysis in this paper only considers
gender bias. There are admittedly other forms of bias that LLMs can exhibit.
However, for the sake of simplicity here, we select one type of bias.
Subsequent analyses will more comprehensively analyze bias in text embedding
models across different dimensions.

In our analysis, we present models with a list of semantically neutral
occupations (for example, nurse, clerk, and financier). These occupations are
theoretically neutral in that they should not necessarily be associated more
with one gender over another. However, based on how various occupations were
historically represented in a model’s training data, it might be the case that
a model comes to associate certain occupations more strongly with certain
genders. The full list of occupations includes: accountant, analyst,
architect, assistant, attendant, auditor, baker, bookkeeper, boss,
broadcaster, captain, carpenter, cashier, CEO, chief, cleaner, clerk,
construction worker, cook, counselor, designer, developer, driver, editor,
farmer, fighter pilot, financier, guard, guidance counselor, homemaker,
housekeeper, interior designer, janitor, laborer, lawyer, librarian, magician,
maestro, manager, mechanic, mover, nanny, nurse, philosopher, physician,
protege, receptionist, salesperson, secretary, sheriff, skipper, socialite,
stylist, supervisor, tailor, teacher, warrior, and writer.

Models are judged on their woman-man and girl-boy bias score differences. A
positive woman-man or girl-boy bias score difference means that a model more
strongly associates a given profession with the word “woman” or “girl.” A
negative score difference means that a model more strongly associates a given
profession with the words “man” or “boy.”

Overall this paper aims to advance two main contributions. First, we aim to
introduce a simple yet efficient methodology for transparently benchmarking
text embedding models and more broadly identifying unfairness and bias in text
embedding models. Second, we aim to help businesses and academics understand
issues of bias in text embedding models so that ultimately, they can build and
deploy more balanced and fair models.

##  4 Results

The following section presents the results of our analysis. For each model, we
examine bias-score differences for individual occupations. At a high level,
our analysis suggests that models exhibit strong and consistent biases. Some
models are much more likely to associate certain professions with particular
genders, while associating other professions with different genders.
Furthermore, the nature of gendered associations is not always consistent.
Sometimes models associate the same occupations with different genders. In
addition, the nature of the association made by the models can be highly
sensitive to the individual words the model is prompted with.

###  4.1 AI21: AI21-v1-embed

Figure 2 highlights the bias-score differences for AI21’s AI21-v1-embed model.
Certain professions have comparatively stronger associations with female
identifiers like “woman” and “girl”, namely nurse, nanny, and housekeeper. The
professions most associated with male identifiers like “man” and “boy” are
captain, maestro, and mechanic. For an overwhelming majority of selected
professions, the woman-man as well as girl-boy biases have the same
directionality. That is, if a model is more likely to associate a certain
profession with the term “woman” over “man”, it is also more likely to
associate that same profession with “girl” over “boy”. However, there are a
selection of professions, like writer, manager, and cleaner, for which the
directionality is not the same. Overall, the AI21-v1-embed model seems to
exhibit fairly strong gendered associations with various professions.

Figure 2:  Bias associations in AI21-v1-embed

###  4.2 Amazon: amazon-titan-embed-text-v1

As seen in Figure 3, Amazon’s amazon-titan-embed-text-v1 model, like AI21’s,
exhibits fairly strong gendered bias. The professions most associated with
female identifiers are secretary, hairdresser, and nurse. Both AI21’s and
Amazon’s text embedding models had nurse as one of the top three professions
associated with female identifiers. The professions that the Amazon model most
strongly associated with male identifiers were maestro, manager, and captain.
Both captain and maestro were also among the professions that AI21’s model
most strongly associated with male identifiers. Curiously, the strength of the
bias difference scores for the most female- and male-biased professions is
substantially higher for amazon-titan-embed-text-v1 than for other models. For
example, while AI21’s model most female-associated profession is nurse, with a
roughly 0.035 aggregate bias score difference, and its most male-associated
profession is captain, with a roughly -0.020 bias score difference, Amazon’s
most female-associated profession, secretary, registers a bias score
difference of approximately 0.150. The most male-associated profession for
Amazon registers an aggregate bias score difference of around -0.100. This
difference suggests that amazon-titan-embed-text-v1, at the extremes, is more
sharply biased than other models. These comparative differences highlight how
differently text embedding models behave when it comes to bias and underscore
the caution that businesses need to maintain in terms of selecting which
particular text embedding model they should work with.

Figure 3:  Bias associations in amazon-titan-embed-text-v1

###  4.3 BAAI: BAAI-bge-large-zh-v1.5

The bias exhibited by the BAAI-bge-large-zh-v1.5 model differs from that
exhibited by AI21-v1-embed and amazon-titan-embed-text-v1 in some notable
regards (Figure 4). Interestingly, one of the professions BAAI’s model most
strongly associates with female identifiers is sheriff. The other top
professions, in terms of a high female identification, are perhaps less
surprising: hairdresser, nurse, and cleaner. The professions that have the
highest degree of male identification are boss, CEO, and manager. The boss
profession has a particularly strong association with both the boy and man
identifiers relative to the girl and woman identifiers. This suggests that
BAAI’s model fairly strongly associates being a boss with being male.

Figure 4:  Bias associations in BAAI-bge-large-zh-v1.5

###  4.4 Cohere: cohere-embed-english-v3.0

Figure 5 illustrates the gendered associations made by the cohere-embed-
english-v3.0 model. The profession with the highest absolute bias score
difference is homemaker (female association), with a score of roughly 0.200.
This association’s magnitude is one of the greatest among all models profiled
in this paper. Nurse and housekeeper were the other professions most strongly
associated with female identifiers. On the other side, Cohere’s model
significantly associated the terms captain, manager, and skipper with male
identifiers. The majority of the models profiled in this analysis also seem to
more strongly associate positions of leadership (for example, captain,
manager, and boss) with male identifiers. Interestingly, there are a fairly
large number of professions, such as cleaner, accountant, and lawyer, that
Cohere associates differently along a gender dimension. For these professions,
the bias score difference is positive for the girl-boy bias, illustrating a
greater association with the term “girl” over “boy”, but negative for the
woman-man bias. This type of difference illustrates that the associations any
given model makes can be sensitive to the particular prompts or words it is
given.

Figure 5:  Bias associations in cohere-embed-english-v3.0

###  4.5 Google: bert-large

Figure 6 showcases the biased associations made by Google’s bert-large model.
Most of the occupations in the sample have negative bias score differences for
both the woman-man and girl-boy bias, suggesting that bert-large associates
most of the occupations in the set with more male-oriented terminology. The
occupations that have the strongest male associations are protégé, mechanic,
and tailor. The magnitude of these associations is fairly strong and, in fact,
among the strongest of all models (around -0.200 in terms of value). Likewise,
there are certain occupations that bert-large strongly associates with female
terminology, namely broadcaster, interior designer, and bookkeeper. The fact
that several occupations in the test set have bias score differences greater
than 0.100 in magnitude highlights that for particular occupations, bert-large
can be strongly biased, much more so than other models. Again, these results
suggest that the strength of the biased gender associations varies depending
on the model.

Figure 6:  Bias associations in bert-large

###  4.6 Meta: llama-2-70b

Compared to other models, Meta’s llama-2-70b demonstrates arguably the most
interesting results (Figure 7). For each occupation in the test set,
llama-2-70b assigns a positive bias score difference, meaning that the model
more strongly associated each occupation with female words like “woman” and
“girl” over male words like “man” and “boy.” For certain occupations, the
positive association is of a relatively high magnitude: for example, the
professions guidance counselor, construction worker, and supervisor all
register aggregate bias score differences greater than 0.200. Some occupations
in the test set are much less strongly associated with female identifiers (for
example, boss, cook, and baker). However, the fact that for llama-2-70b, not a
single occupation has a negative bias score means that the model does not more
strongly associate a single occupation with male identifiers over female
identifiers.

Figure 7:  Bias associations in llama-2-70b

###  4.7 OpenAI: text-embedding-ada002

Much like llama-2-70b, the openai-text-embedding-ada-002 model associates the
majority of occupations in the set more strongly with female identifiers than
male ones (Figure 8). Homemaker, socialite, and nurse are the occupations with
the highest aggregate bias score differences and thereby the strongest female
associations. Manager has the lowest aggregate bias score difference and,
therefore, the strongest association with male identifiers. However, compared
to Meta’s llama-2-70b, the other model that disproportionately associates
occupations with female identifiers, the magnitude of the associations made by
openai-text-embedding-ada-002 is meaningfully lower. In some cases, the bias
score difference also has a different directionality (positive versus
negative) depending on the particular identifier used (woman-man versus girl-
boy bias). This last fact again illustrates the sensitivity of text embedding
models to particular word choices.

Figure 8:  Bias associations in openai-text-embedding-ada002

###  4.8 Voyage AI: voyageai-voyage-01

The voyageai-voyage-01 associates all professions more strongly with a certain
gender; however, the strength of the associations is not as great as those
made in other models like Google’s bert-large or Meta’s llama-2-70b (Figure
9). As with several other models featured in this analysis, the occupations
with the strongest female gender bias are socialite, secretary, and nanny. The
occupations with the strongest male gender bias are mechanic, chief and
skipper, illustrating again how many models tend to associate leadership with
male identifiers. For most occupations in the test set, the directionality of
both the woman-man and girl-boy bias score differences is the same, suggesting
that voyageai-voyage-01 is relatively consistent in terms of how it associates
occupations with different variations of gendered terms. Overall the magnitude
of the bias exhibited by the voyageai-voyage-01 model is low, suggesting the
model is less strongly biased than other models included in the analysis.

Figure 9:  Bias associations in voyageai-voyage-01

###  4.9 Technische Universität Darmstadt: msmarco-distilbert-cos-v5

The bias exhibited for certain occupations by the msmarco-distilbert-cos-v5
model is among the greatest of all models featured in this analysis (Figure
10). The msmarco-distilbert-cos-v5 model has a bias score difference greater
than 0.200 for occupations like nurse, housekeeper, socialite, receptionist,
and nanny, strongly associating each of these occupations with female
identifiers. The bias score difference is especially high, above 0.400, for
housekeeper and nurse. In comparison, the highest magnitude bias score
differences posted by other models was around the 0.200 to 0.250 range. The
msmarco-distilbert-cos-v5 also exhibits relatively strong bias in the other
direction, associating certain terms like philosopher, janitor, and magician
with male identifiers. However, the magnitude of bias for these male-
associated terms is substantially lower than for the occupations the model
more strongly identifies as female-associated.

Figure 10:  Bias associations in msmarco-distilbert-cos-v5

##  5 Discussion

There are several important takeaways to be drawn from the analysis. First,
although all models display gender bias in some kind of way, generally more
strongly associating occupations with either female or male identifiers, the
magnitude of the bias varies quite intensely by model. For example for certain
models like voyageai-voyage-01 and AI21-v1-embed the respective ranges of
biased score differences is around -0.020 to 0.020 and -0.020 to 0.030
(differences of 0.040 and 0.050). Conversely, for other models like msmarco-
distilbert-cos-v5 the bias score differences range from around -0.200 to 0.500
(a difference of 0.700). This finding has meaningful implications for
businesses that are considering deploying text embedding models as part of
their business offerings: in addition to performance capabilities, businesses
should consider the propensity of models to be biased and understand that this
propensity can vary strongly.

Second, although there are certain general commonalities among the models in
terms of the biased gender associations they make, not all models are biased
in the same way. Across models certain professions, like those dealing with
homemaking and care-giving functions, tend to be more strongly associated with
female identifiers like woman or girl. Other professions, like those dealing
with leadership functions, such as chief, boss, or CEO, tend to be more
strongly associated with male identifiers like man or boy. However, these
patterns are not always true. For instance, openai-text-embedding-ada-002, and
llama-2-70b all more strongly associate CEO with female identifiers over male
ones. Therefore, the biased associations that text embedding models can vary
on a model-by-model basis. Again, businesses considering integrating text
embedding models need to be mindful of the demographics they serve and
understand how the models they deploy might behave in the context of those
demographic groups.

Third, for most of the models included in the analysis, the directionality of
the bias score difference is not always the same. Generally speaking, if, for
example, a model associates a given occupation with a female identifier like
“woman” over a male identifier like “man,” it will do the same for “girl” over
“boy.” However, this is not always the case. The fact that models sometimes
more strongly associate given occupations with “woman” over “man”, but then
also “boy” over “girl” (and vice versa) suggests that the biased associations
a model makes can be quite sensitive to the individual words supplied to a
model. This means that businesses need to be mindful of the specific words
they use to prompt their text-embedding models and have an understanding of
the various associations their models make with those words.

While this analysis is a step forward in terms of highlighting issues of bias
in text embedding models, there are several limitations that should be
acknowledged. First, the paper only considers one particular type of bias:
gender bias. As noted in the literature review, there is ample evidence that
popular AI models are biased along a plethora of other dimensions like
religion, race, and age. A further analysis would do well to consider the
degree to which text embedding models are biased along those lines. Second,
this analysis highlights that the models themselves are biased but does not
discuss bias mitigation approaches. Those approaches must be taken by either
the model developers or the companies deploying the models themselves.
Finally, the examination of bias featured in this paper considers bias in a
particular experimental setting when models are simply asked to associate
various occupations with gendered terms. Depending on how businesses actually
deploy and use these models, text embedding models might demonstrate bias in
different ways. Businesses should be mindful of the ways in which they are
deploying these models and think of other ways in which their models could be
biased.

##  6 Conclusion

This paper featured an analysis of gender bias in text embedding models. It
began by discussing the broad problem of bias in AI systems, noting that
although it is well understood that AI systems are biased, there is not as
much specific research that considers the way in which text embedding models
are biased, especially from a gender perspective. The paper then attempted to
explore whether a selection of leading text embedding models demonstrate
gender bias and the degree to which the models demonstrate the bias. The
analysis showed that all models associate particular occupations more with
certain gendered terms (for example, “boy” over “girl” or “man” over “woman”).
For certain models, the biased associations were more pronounced than for
others. Although there were certain patterns in the gendered associations made
by models (for instance, homemaking and caring professions were generally more
associated with female identifiers, and leadership professions more with male
identifiers), not all models associated the same occupations with the same
gendered terms. In addition, the particular associations that models made
could be sensitive to the specific words they were prompted with.

Overall, this paper highlighted that popular text embedding models can exhibit
high degrees of gender bias. Businesses that are working to integrate these
tools should be cognizant of the potential these models demonstrate for being
biased. Further analyses can study the ways in which text embedding models are
biased along different dimensions of bias (for instance, age, race, religion,
etc.)

## References

  * [1] Daniel Cer, Yinfei Yang, Sheng-yi Kong, Nan Hua, Nicole Limtiaco, Rhomni St John, Noah Constant, Mario Guajardo-Cespedes, Steve Yuan, Chris Tar, et al.  Universal sentence encoder.  arXiv preprint arXiv:1803.11175, 2018.
  * [2] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  Bert: Pre-training of deep bidirectional transformers for language understanding.  arXiv preprint arXiv:1810.04805, 2018.
  * [3] Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean.  Efficient estimation of word representations in vector space.  arXiv preprint arXiv:1301.3781, 2013.
  * [4] Hsuan Su, Cheng-Chu Cheng, Hua Farn, Shachi H Kumar, Saurav Sahay, Shang-Tse Chen, and Hung-yi Lee.  Learning from red teaming: Gender bias provocation and mitigation in large language models.  arXiv preprint arXiv:2310.11079, 2023.
  * [5] Joy Buolamwini and Timnit Gebru.  Gender shades: Intersectional accuracy disparities in commercial gender classification.  In Conference on fairness, accountability and transparency, pages 77–91. PMLR, 2018.
  * [6] Agostina J Larrazabal, Nicolás Nieto, Victoria Peterson, Diego H Milone, and Enzo Ferrante.  Gender imbalance in medical imaging datasets produces biased classifiers for computer-aided diagnosis.  Proceedings of the National Academy of Sciences, 117(23):12592–12594, 2020.
  * [7] Sam Levin.  A beauty contest was judged by ai and the robots didn’t like dark skin.  https://www.theguardian.com/technology/2016/sep/08/artificial-intelligence-beauty-contest-doesnt-like-black-people, 2016.
  * [8] Nestor Maslej, Loredana Fattorini, Erik Brynjolfsson, John Etchemendy, Katrina Ligett, Terah Lyons, James Manyika, Helen Ngo, Juan Carlos Niebles, Vanessa Parli, et al.  Artificial intelligence index report 2023.  arXiv preprint arXiv:2310.03715, 2023.
  * [9] Ninareh Mehrabi, Fred Morstatter, Nripsuta Saxena, Kristina Lerman, and Aram Galstyan.  A survey on bias and fairness in machine learning.  ACM computing surveys (CSUR), 54(6):1–35, 2021.
  * [10] D Zhang, N Maslej, E Brynjolfsson, J Etchemendy, T Lyons, J Manyika, H Ngo, JC Niebles, M Sellitto, E Sakhaee, et al.  The ai index 2022 annual report (arxiv: 2205.03468). arxiv, 2022.
  * [11] Deborah Belle.  We’ve come a long way, baby… or have we?  https://spsp.org/news-center/character-context-blog/weve-come-long-way-baby-or-have-we, 2021.
  * [12] Emilio Ferrara.  Fairness and bias in artificial intelligence: A brief survey of sources, impacts, and mitigation strategies.  Sci, 6(1):3, 2023.
  * [13] Ashraf Khalil, Soha Glal Ahmed, Asad Masood Khattak, and Nabeel Al-Qirim.  Investigating bias in facial analysis systems: A systematic review.  IEEE Access, 8:130751–130761, 2020.
  * [14] Mirja Mittermaier, Marium M Raza, and Joseph C Kvedar.  Bias in ai-based models for medical applications: challenges and mitigation strategies.  NPJ Digital Medicine, 6(1):113, 2023.
  * [15] Laleh Seyyed-Kalantari, Haoran Zhang, Matthew BA McDermott, Irene Y Chen, and Marzyeh Ghassemi.  Underdiagnosis bias of artificial intelligence algorithms applied to chest radiographs in under-served patient populations.  Nature medicine, 27(12):2176–2182, 2021.
  * [16] Jeffrey Dastin.  Insight - amazon scraps secret ai recruiting tool that showed bias against women.  https://www.reuters.com/article/idUSKCN1MK0AG/, 2018.
  * [17] Cohere.  Embed: Ai for language understanding.  https://cohere.com/embed, 2024.
  * [18] OpenAI.  New and improved embedding model.  https://openai.com/index/new-and-improved-embedding-model/, 2022.
  * [19] Cohere.  Text classification (embed).  https://docs.cohere.com/docs/text-classification-with-embed, 2024.
  * [20] Pandu Nayak.  Understanding searches better than ever before.  https://blog.google/products/search/search-language-understanding-bert/, 2019.
  * [21] Microsoft.  Tutorial: Explore azure openai service embeddings and document search.  https://learn.microsoft.com/en-us/azure/ai-services/openai/tutorials/embeddings?tabs=python-new
  * [22] Nicholas Harris, Anand Butani, and Syed Hashmy.  Enhancing embedding performance through large language model-based text enrichment and rewriting.  arXiv preprint arXiv:2404.12283, 2024.
  * [23] Niklas Muennighoff, Nouamane Tazi, Loïc Magne, and Nils Reimers.  Mteb: Massive text embedding benchmark.  arXiv preprint arXiv:2210.07316, 2022.
  * [24] Bin Wang, Angela Wang, Fenxiao Chen, Yuncheng Wang, and C-C Jay Kuo.  Evaluating word embedding models: Methods and experimental results.  APSIPA transactions on signal and information processing, 8:e19, 2019.
  * [25] Hadas Kotek, Rikker Dockum, and David Sun.  Gender bias and stereotypes in large language models.  In Proceedings of The ACM Collective Intelligence Conference, pages 12–24, 2023.
  * [26] Aylin Caliskan, Joanna J Bryson, and Arvind Narayanan.  Semantics derived automatically from language corpora contain human-like biases.  Science, 356(6334):183–186, 2017.
  * [27] Solon Barocas, Moritz Hardt, and Arvind Narayanan.  Fairness and machine learning: Limitations and opportunities.  MIT Press, 2023.
  * [28] Rachel Rudinger, Jason Naradowsky, Brian Leonard, and Benjamin Van Durme.  Gender bias in coreference resolution.  arXiv preprint arXiv:1804.09301, 2018.
  * [29] Hila Gonen and Yoav Goldberg.  Lipstick on a pig: Debiasing methods cover up systematic gender biases in word embeddings but do not remove them.  arXiv preprint arXiv:1903.03862, 2019.
  * [30] Himanshu Thakur, Atishay Jain, Praneetha Vaddamanu, Paul Pu Liang, and Louis-Philippe Morency.  Language models get a gender makeover: Mitigating gender bias with few-shot data interventions.  arXiv preprint arXiv:2306.04597, 2023.
  * [31] Percy Liang, Rishi Bommasani, Tony Lee, Dimitris Tsipras, Dilara Soylu, Michihiro Yasunaga, Yian Zhang, Deepak Narayanan, Yuhuai Wu, Ananya Kumar, et al.  Holistic evaluation of language models.  arXiv preprint arXiv:2211.09110, 2022.
  * [32] Edward Beeching, Clémentine Fourrier, Nathan Habib, Sheon Han, Nathan Lambert, Nazneen Rajani, Omar Sanseviero, Lewis Tunstall, and Thomas Wolf.  Open llm leaderboard.  https://huggingface.co/spaces/HuggingFaceH4/open_llm_leaderboard, 2023.
  * [33] Keisuke Sakaguchi, Ronan Le Bras, Chandra Bhagavatula, and Yejin Choi.  WINOGRANDE: an adversarial winograd schema challenge at scale, 2019.
  * [34] Nestor Maslej, Loredana Fattorini, Erik Brynjolfsson, Anka Reuel, John Etchemendy, Katrina Ligett, Terah Lyons, James Manyika, Juan Carlos Niebles, Vanessa Parli, et al.  Artificial intelligence index report 2024.  arXiv preprint arXiv:2405.19522, 2024.
  * [35] AI21.  Embeddings.  https://docs.ai21.com/docs/embeddings-api, 2024.
  * [36] Amazon.  Amazon titan text embeddings models.  https://docs.aws.amazon.com/bedrock/latest/userguide/titan-embedding-models.html, 2024.
  * [37] Beijing Academy of Artificial Intelligence.  Baai/bge-large-zh-v1.5.  https://huggingface.co/BAAI/bge-large-zh-v1.5, 2024.
  * [38] Cohere.  Cohere/cohere-embed-english-v3.0.  https://huggingface.co/Cohere/Cohere-embed-english-v3.0, 2024.
  * [39] Google.  google-bert/bert-large-uncased.  https://huggingface.co/google-bert/bert-large-uncased, 2024.
  * [40] Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al.  Llama 2: Open foundation and fine-tuned chat models.  arXiv preprint arXiv:2307.09288, 2023.
  * [41] Sentence Transformers.  sentence-transformers/msmarco-distilbert-cos-v5.  https://huggingface.co/sentence-transformers/msmarco-distilbert-cos-v5, 2024.
  * [42] OpenAI.  Embeddings.  https://platform.openai.com/docs/guides/embeddings, 2024.
  * [43] Voyage AI.  Embeddings.  https://docs.voyageai.com/docs/embeddings, 2024.
  * [44] Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean.  Distributed representations of words and phrases and their compositionality.  Advances in neural information processing systems, 26, 2013.
  * [45] Aarohi Srivastava, Abhinav Rastogi, Abhishek Rao, Abu Awal Md Shoeb, Abubakar Abid, Adam Fisch, Adam R Brown, Adam Santoro, Aditya Gupta, Adrià Garriga-Alonso, et al.  Beyond the imitation game: Quantifying and extrapolating the capabilities of language models.  arXiv preprint arXiv:2206.04615, 2022.


# Skolem and Positivity Completeness of Ergodic Markov Chains

Mihir Vahanwala111The author is partially funded by DFG grant 389792660 as
part of TRR 248 (see https://perspicuous-computing.science).organization=Max
Planck Institute for Software Systems, Saarland Informatics
Campus,country=Germany

###### Abstract

We consider the following Markov Reachability decision problems that view
Markov Chains as Linear Dynamical Systems: given a finite, rational Markov
Chain, source and target states, and a rational threshold, does the
probability of reaching the target from the source at the $n^{th}$ step: (i)
equal the threshold for some $n$? (ii) cross the threshold for some $n$? (iii)
cross the threshold for infinitely many $n$? These problems are respectively
known to be equivalent to the Skolem, Positivity, and Ultimate Positivity
problems for Linear Recurrence Sequences (LRS), number-theoretic problems
whose decidability has been open for decades. We present an elementary
reduction from LRS Problems to Markov Reachability Problems that improves the
state of the art as follows. (a) We map LRS to _ergodic_ (irreducible and
aperiodic) Markov Chains that are ubiquitous, not least by virtue of their
spectral structure, and (b) our reduction maps LRS of order $k$ to Markov
Chains of order $k+1$: a substantial improvement over the previous reduction
that mapped LRS of order $k$ to reducible and periodic Markov chains of order
$4k+5$. This contribution is significant in view of the fact that the number-
theoretic hardness of verifying Linear Dynamical Systems can often be
mitigated by spectral assumptions and restrictions on order.

###### keywords:

Ergodic Markov Chains , Reachability , Model checking , Linear Recurrence
Sequences

##  1 Introduction

Markov Chains, owing to their formulation in terms of stochastic matrices, are
syntactically a special class of Linear Dynamical Systems. However, it is
their semantics as transformers of probability distributions that earns them
widespread attention as a natural mathematical framework to describe
probabilistic systems. Markov Decision Processes, for instance, extend Markov
Chains and are a probabilistic decision-making model fundamental to
verification [1, Chapter 10] and Reinforcement Learning [2, Section 3].

Given their importance, there is naturally an extensive body of work on model
checking Markov Chains: see [1] for a comprehensive set of references. Most of
the focus has been on the verification of linear- and branching-time
properties of Markov Chains through solving systems of linear equations, or
linear programs. An alternative approach [3, 4, 5, 6] is to consider
specifications on the state distribution at each time step, e.g., whether the
probability of being in a given state at the $n^{th}$ step is at least $1/4$.
Decidability in this setting is a lot more inaccessible: [3, 4] only present
incomplete or approximate verification procedures, while [5, 6] owe their
model-checking procedures to additional mathematical assumptions. The
following decision problems are representative of the fundamental difficulties
this approach is fraught with:

######  Definition 1 (Markov Reachability Problems).

Given a stochastic matrix $\mathbf{M}\in\mathbb{Q}^{k\times k}$ (i.e. an order
$k$ Markov Chain), a threshold $r\in\mathbb{Q}$, and indices $i,j$, decide
whether:

  1. 1.

There exists an $n\in\mathbb{N}$ such that $m_{ij}^{(n)}=r$.

  2. 2.

There exists an $n\in\mathbb{N}$ such that $m_{ij}^{(n)}\sim r$.

  3. 3.

There exist infinitely many $n\in\mathbb{N}$ such that $m_{ij}^{(n)}\sim
r$.222For technical reasons discussed in §2.1 of the Preliminaries, deciding
whether there exist infinitely many $n\in\mathbb{N}$ such that
$m_{ij}^{(n)}=r$ is actually a tractable problem.

where $\sim$ denotes one of $\\{>,<\\}$ and $m_{ij}^{(n)}$ denotes the entry
in the $i^{th}$ row and $j^{th}$ column of $\mathbf{M}^{n}$.

It is here that the syntactic nature of Markov Chains as Linear Dynamical
Systems is brought to the fore. The essential tool we use to argue the
difficulty of these problems is the Linear Recurrence Sequence (LRS). An LRS
over $\mathbb{Q}$ of order $k$ is an infinite sequence $\langle
u_{n}\rangle_{n=0}^{\infty}$ of rational numbers satisfying a recurrence
relation

$u_{n+k}=a_{k-1}u_{n+k-1}+\dots+a_{0}u_{n}$

for all $n\in\mathbb{N}$, where $a_{0}\neq
0,a_{1},\dots,a_{k-1}\in\mathbb{Q}$. An LRS over $\mathbb{Q}$ of order $k$ is
uniquely specified by $2k$ rational numbers: $a_{0},\dots,a_{k-1}$ for the
recurrence relation, and $u_{0},\dots,u_{k-1}$ for the initial terms. An LRS
can be computed through its companion matrix $\mathbf{A}$:

$\mathbf{A}^{n}\begin{bmatrix}u_{0}\\\ u_{1}\\\ \vdots\\\ u_{k-2}\\\
u_{k-1}\end{bmatrix}=\begin{bmatrix}0&1&0&\dots&0\\\ 0&0&1&\dots&0\\\
\vdots&\vdots&\vdots&\ddots&\vdots\\\ 0&0&0&\dots&1\\\
a_{0}&a_{1}&a_{2}&\dots&a_{k-1}\end{bmatrix}^{n}\begin{bmatrix}u_{0}\\\
u_{1}\\\ \vdots\\\ u_{k-2}\\\ u_{k-1}\end{bmatrix}=\begin{bmatrix}u_{n}\\\
u_{n+1}\\\ \vdots\\\ u_{n+k-2}\\\ u_{n+k-1}\end{bmatrix}.$

The behaviour of an LRS is governed by the eigenvalues of $\mathbf{A}$, or
equivalently, the roots of its characteristic polynomial
$X^{k}-a_{k-1}X^{k-1}-\dots-a_{0}$. The LRS is said to be _non-degenerate_ if
the ratio of two distinct characteristic roots is never a root of unity, and
_simple_ if the characteristic polynomial has no repeated roots.

The following are key number-theoretic open decision problems for LRS:

  1. 1.

Skolem Problem: Does there exist $n\in\mathbb{N}$ such that $u_{n}=0$?

  2. 2.

Positivity Problem: Is $u_{n}\geq 0$ for all $n\in\mathbb{N}$?

  3. 3.

Ultimate Positivity Problem: Is $u_{n}\geq 0$ for all but finitely many
$n\in\mathbb{N}$?

Number-theoretic hardness is formally shown for the Positivity and Ultimate
Positivity Problems of order $6$ LRS in [7]: decision procedures would enable
one to quantify how well the continued fraction expansion of a given
irrational number converges, an endeavour inaccessible to the means of
contemporary number theory.

On the other hand, decidability results have been obtained through suitable
restrictions. The Skolem Problem is known to be decidable for LRS of order up
to $4$, see [8, 9]. Very recently, there have been conditional decidability
results for LRS of order $5$, and simple LRS [10]. The Positivity Problem and
Ultimate Positivity Problems are decidable up to order $5$ [7]. If we restrict
ourselves to simple LRS, then Ultimate Positivity is decidable [11], and
Positivity is decidable up to order $9$ [12]. Neither decidability nor
hardness results are known for the Positivity Problem for simple LRS of order
$10$ and above.

Returning to our stochastic setting, we note that techniques to reduce the
above LRS problems to Markov Reachability Problems were known since the work
of Turakainen [13], albeit in the context of probabilistic automata333It is
not difficult to use the Cayley-Hamilton Theorem to show the reverse
reduction, i.e. that the Markov Reachability problems reduce to the
corresponding LRS Problems.. The folkloric results are sharpened in [14]: it
is shown that the LRS Problems for order $k$ LRS reduce to Markov Reachability
Problems for reducible and periodic Markov Chains of order $4k+5$.

Subsequent works on probabilistic systems such as [15, 16] that faced the
Markov Reachability Problems use [14] or similar arguments to justify the
development of solutions that are useful despite being restricted or
incomplete, rather than tackling the main problem head on. One can argue that
this justification, as it stands, has the following deficiencies that need to
be addressed:

  1. 1.

The best known reduction demonstrates the hardness of verifying Markov Chains
that are reducible and periodic, rather than ergodic (irreducible and
aperiodic) Markov Chains that the community most often considers.

  2. 2.

Breakthroughs in the verification of Linear Dynamical Systems often result
from restrictions on the dimensions [7, 8, 9, 12] or spectrum [11, 12, 17, 18]
of the underlying matrix. A strong reduction needs to show that hardness
persists despite the additional spectral properties (see, e.g. Theorem 2)
enjoyed by ergodic Markov Chains, and also be faithful with respect to order
while mapping LRS to stochastic matrices.

Our main result comprehensively addresses this issue.

######  Theorem 1 (Main Result).

The Skolem, Positivity, and Ultimate Positivity Problems for LRS of order $k$
reduce to Markov Reachability Problems for ergodic Markov Chains of order
$k+1$.

##  2 Preliminaries

###  2.1 Linear Recurrence Sequences

The celebrated Skolem-Mahler-Lech Theorem [19, 20, 21] states that the set
$\\{n:u_{n}=0\\}$ is the union of a finite set $Z$ and finitely many
arithmetic progressions $c_{1}+b_{1}\mathbb{N},\dots,c_{d}+b_{d}\mathbb{N}$,
where $0\leq c_{i}<b_{i}$ for all $i$. The values of $d,c_{i},b_{i}$ can all
be effectively computed, whereas determining whether $Z$ is nonempty is
precisely the difficulty of the Skolem Problem. It is well known [22, 23] that
for any LRS $\langle u_{n}\rangle_{n=0}^{\infty}$, one can compute $B\geq 1$
such that for all $0\leq c<B$, the subsequence $\langle
u_{nB+c}\rangle_{n=0}^{\infty}$ is a non-degenerate LRS which, by an
observation of Lech [21], is either identically zero or has finitely many
zeroes. It thus suffices to study non-degenerate LRS to solve the Skolem,
Positivity and Ultimate Positivity Problems.

###  2.2 Stochastic Matrices and Markov Chains

When the dimensions are clear from context, we use $\mathbf{1}$ to denote the
column vector whose entries are all $1$, $\mathbf{I}$ to denote the identity
matrix, $\mathbf{0}$ to denote the zero column vector, and $\mathbf{O}$ to
denote the zero matrix. Superscript $T$ denotes transposition. We use
$\mathbf{e_{i}}$ to denote the elementary column vector, i.e. the vector whose
$i^{th}$ entry is $1$ and all other entries are $0$, e.g.
$\mathbf{e_{1}}=\begin{bmatrix}1&0&\dots&0\end{bmatrix}^{T}$. We use
$m_{ij}^{(n)}$ as shorthand to denote the entry in the $i^{th}$ row and
$j^{th}$ column of the matrix $\mathbf{M}^{n}$, i.e.
$m_{ij}^{(n)}=\mathbf{e_{i}}^{T}\mathbf{M}^{n}\mathbf{e_{j}}$. When not
specified, $n=1$.

Distributions with finite support are represented by column vectors. Since
they denote probabilities of mutually exclusive and exhaustive events, their
entries are non-negative and sum up to $1$. A finite $k$-state Markov Chain is
given by a (left) stochastic matrix $\mathbf{M}\in\mathbb{Q}^{k\times k}$,
i.e. all entries of $\mathbf{M}$ are non-negative and
$\mathbf{1}^{T}\mathbf{M}=\mathbf{1}^{T}$. Here $m_{ij}$ denotes the
probability of transitioning from state $j$ to state $i$. Each column of
$\mathbf{M}$ is a distribution: the $j^{th}$ column is the probability
distribution over the states in the next step, given that the current state is
$j$. If the starting state is $j$, the probability of being in state $i$ after
$n$ steps is $m_{ij}^{(n)}$. If the current distribution over the states is
$\mathbf{s}$, then after a transition, the distribution is transformed to
$\mathbf{Ms}$. A distribution such that $\mathbf{Ms}=\mathbf{s}$ is called a
stationary distribution of the Markov Chain.

For any Markov Chain, we can construct a graph whose vertices correspond to
the states, and there is an edge from vertex $i$ to $j$ if and only if
$m_{ji}>0$, i.e. there is a transition from state $i$ to state $j$ with
nonzero probability. A Markov Chain is said to be _ergodic_ if its graph is
aperiodic and irreducible (strongly connected), i.e. there exists an $N$ such
that there is a path of length $N$ between any pair of (not necessarily
distinct) vertices. An equivalent characterisation is: there exists an $N$
such that all the entries of $\mathbf{M}^{N}$ are strictly positive. For
completeness, we note some spectral properties ergodic Markov Chains enjoy
[24, Chapter 4, Theorem 6].

######  Theorem 2 (Standard).

Let $\mathbf{M}\in\mathbb{Q}^{k\times k}$ represent an ergodic Markov Chain.
Then $\lambda_{0}=1$ is the largest real eigenvalue of $\mathbf{M}$, and
$|\lambda|<1$ for all other eigenvalues $\lambda$. Furthermore,
$\lim_{n\rightarrow\infty}\mathbf{M}^{n}=\mathbf{S}=\mathbf{s}\mathbf{1}^{T}$,
where $\mathbf{s}$ is the unique stationary distribution of $\mathbf{M}$.

##  3 The Reduction

In this section, we prove Theorem 1. We shall start with the companion matrix
$\mathbf{A}$ and the vector
$\mathbf{u}=\begin{bmatrix}u_{0}&\dots&u_{k-1}\end{bmatrix}^{T}$ of the
initial values of the LRS, and construct the required ergodic Markov Chain.
Recall from the preliminaries that
$u_{n}=\mathbf{e_{1}}^{T}\mathbf{A}^{n}\mathbf{u}$. From the discussion in the
preliminaries, we can also assume that the given LRS is non-degenerate with
finitely many zeroes. In particular, by brute enumeration, we are guaranteed
to find $k$ consecutive indices with nonzero entries. We will thus assume,
without loss of generality, that $u_{0},\dots,u_{k-1}$ are all nonzero.444This
assumption can be made trivially if we are reducing the Skolem Problem.
Further, for Positivity, we can trivially assume $u_{0},\dots,u_{k-1}>0$.

The key idea is to construct a $(k+1)\times(k+1)$ stochastic matrix via a
decomposition $\mathbf{M}=\mathbf{S}+\mathbf{D}$ (intuitively, Stationary
distribution plus Disturbance) that represents an ergodic Markov Chain due to
the following properties:

  1. 1.

$\mathbf{S}=\mathbf{s1}^{T}$ is a stochastic matrix, each of whose columns are
a distribution $\mathbf{s}$ with strictly positive entries. The choice of such
$\mathbf{s}$ can be completely arbitrary: for simplicity, we choose each entry
to be $1/(k+1)$.

  2. 2.

$\mathbf{D}$ is a matrix such that $\mathbf{DS}=\mathbf{SD}=\mathbf{O}$, its
entries are small enough to ensure that the all entries of
$\mathbf{S}+\mathbf{D}$ are strictly positive, and finally, there exist
indices $i,j$, and positive constants $\eta,\rho\in\mathbb{Q}$ such that for
all $n\geq 1$, $d_{ij}^{(n)}=\eta u_{n}/\rho^{n}$.

From these properties, we first prove that $\mathbf{M}$ is indeed a stochastic
matrix. Since all columns of $\mathbf{S}$ are identical and have strictly
positive entries, the condition $\mathbf{SD}=\mathbf{O}$ is equivalent to
$\mathbf{1}^{T}\mathbf{D}=\mathbf{0}^{T}$, i.e. all columns of $\mathbf{D}$
sum up to zero. We have that all entries of $\mathbf{M}$ are strictly
positive, and
$\mathbf{1}^{T}\mathbf{M}=\mathbf{1}^{T}(\mathbf{S}+\mathbf{D})=\mathbf{1}^{T}$.
Further, since every entry of $\mathbf{M}$ is strictly positive, it
immediately follows that the Markov Chain is ergodic with $N=1$.

We then observe that for all $n\geq 1$, $\mathbf{S}^{n}=\mathbf{S}$ and
$\mathbf{M}^{n}=(\mathbf{S}+\mathbf{D})^{n}=\mathbf{S}+\mathbf{D}^{n}$, since
$\mathbf{DS}=\mathbf{SD}=\mathbf{O}$. The property that
$\mathbf{DS}=\mathbf{O}$ also gives us that $\mathbf{s}$ is the stationary
distribution of $\mathbf{M}$: indeed,
$\mathbf{MS}=\mathbf{S}^{2}+\mathbf{DS}=\mathbf{S}$. We let $r=s_{ij}$, and
complete the reduction as follows (note that we actually reduce the
complements of the Positivity and Ultimate Positivity Problems):

  1. 1.

Skolem: Does there exist $n$ such that $m_{ij}^{(n)}=r$?

  2. 2.

Positivity: Does there exist $n$ such that $m_{ij}^{(n)}<r$?

  3. 3.

Ultimate Positivity: Do there exist infinitely many $n$ such that
$m_{ij}^{(n)}<r$?

Since $m_{ij}^{(n)}=s_{ij}+d_{ij}^{(n)}=r+d_{ij}^{(n)}$, it only remains to
construct $\mathbf{D}$ and choose indices $i,j$, and constants $\eta,\rho$. We
do so in a top-down fashion.

Let $\mathbf{C}\in\mathbb{Q}^{(k+1)\times(k+1)}$ be a matrix, each of whose
columns sum up to $0$. Similarly to the preceding discussion, it follows that
$\mathbf{SC}=\mathbf{O}$. We argue that we can set $\mathbf{D}$ to be of the
form $\frac{1}{\rho}(\mathbf{C}-\mathbf{CS})$, where $\rho\in\mathbb{Q}$ is
chosen large enough to ensure that all the entries of $\mathbf{S}+\mathbf{D}$
are strictly positive, e.g. if the smallest entry of $\mathbf{S}$ is $\sigma$
and the largest entry (by magnitude) of $\mathbf{C}-\mathbf{CS}$ is $\gamma$,
then it suffices to choose $\rho=2\gamma/\sigma$. It also immediately follows
by construction that $\mathbf{SD}=\mathbf{O}$. Since we have noted that
$\mathbf{S}^{2}=\mathbf{S}$, we also see that $\mathbf{DS}=\mathbf{O}$. We can
prove, by a simple induction, that for all $n\geq 1$,

$\rho^{n}\mathbf{D}^{n}=\mathbf{C}^{n}-\mathbf{C}^{n}\mathbf{S}=\mathbf{C}^{n}(\mathbf{I}-\mathbf{S}).$

The base case is satisfied by construction. For the induction step, we express

$\displaystyle\rho^{n+1}\mathbf{D}^{n+1}$
$\displaystyle=(\mathbf{C}^{n}-\mathbf{C}^{n}\mathbf{S})(\mathbf{C}-\mathbf{CS})$
$\displaystyle=\mathbf{C}^{n+1}-\mathbf{C}^{n+1}\mathbf{S}-\mathbf{C}^{n}\mathbf{SC}+\mathbf{C}^{n}\mathbf{SCS}$
$\displaystyle=\mathbf{C}^{n+1}-\mathbf{C}^{n+1}\mathbf{S}$

using the fact that $\mathbf{SC}=\mathbf{O}$. Now, to ensure that
$d_{ij}^{(n)}=\eta u_{n}/\rho^{n}$ for all $n\geq 1$, we can equivalently
choose $\mathbf{C},\eta,i,j$ such that
$\mathbf{e_{i}}^{T}\mathbf{C}^{n}(\mathbf{I}-\mathbf{S})\mathbf{e_{j}}=\eta
u_{n}=\mathbf{e_{1}}^{T}\mathbf{A}^{n}(\eta\mathbf{u})$.

Although $\mathbf{C}\in\mathbb{Q}^{(k+1)\times(k+1)}$ and
$\mathbf{A}\in\mathbb{Q}^{k\times k}$ have different dimensions, we begin to
see a correspondence. We shall pick $i=1$ and “map” $\eta\mathbf{u}$ to
$(\mathbf{I}-\mathbf{S})\mathbf{e_{j}}$. Since the former is a $k$ dimensional
vector, the intuition is to only consider the first $k$ entries of
$(\mathbf{I}-\mathbf{S})\mathbf{e_{j}}$. Thus, we shall choose $\mathbf{C}$ to
be a matrix of the form

$\begin{bmatrix}\mathbf{B}&\mathbf{0}\\\
-\mathbf{1}^{T}\mathbf{B}&0\end{bmatrix}$

where $\mathbf{B}\in\mathbb{Q}^{k\times k}$. It is easy to see that
$\mathbf{1}^{T}\mathbf{C}=\mathbf{0}^{T}$ for such a choice. We note, by a
simple induction, that for $n\geq 1$

$\mathbf{C}^{n}=\begin{bmatrix}\mathbf{B}^{n}&\mathbf{0}\\\
-\mathbf{1}^{T}\mathbf{B}^{n}&0\end{bmatrix}.$

The base case is satisfied by construction. For the inductive step, simplify

$\displaystyle\mathbf{C}^{n+1}$
$\displaystyle=\begin{bmatrix}\mathbf{B}^{n}&\mathbf{0}\\\
-\mathbf{1}^{T}\mathbf{B}^{n}&0\end{bmatrix}\begin{bmatrix}\mathbf{B}&\mathbf{0}\\\
-\mathbf{1}^{T}\mathbf{B}&0\end{bmatrix}$
$\displaystyle=\begin{bmatrix}\mathbf{B}^{n}\cdot\mathbf{B}+\mathbf{0}\cdot(-\mathbf{1}^{T}\mathbf{B})&\mathbf{B}^{n}\cdot\mathbf{0}+\mathbf{0}\cdot
0\\\
(-\mathbf{1}^{T}\mathbf{B}^{n})\cdot\mathbf{B}+0\cdot(-\mathbf{1}^{T}\mathbf{B})&(-\mathbf{1}^{T}\mathbf{B}^{n})\cdot\mathbf{0}+0\cdot
0\end{bmatrix}$ $\displaystyle=\begin{bmatrix}\mathbf{B}^{n+1}&\mathbf{0}\\\
-\mathbf{1}^{T}\mathbf{B}^{n+1}&0\end{bmatrix}.$

Let $\mathbf{y_{j}}\in\mathbb{Q}^{k}$ denote the vector obtained by deleting
the last entry of $(\mathbf{I}-\mathbf{S})\mathbf{e_{j}}$. In other words,
$\mathbf{y_{j}}$ is the vector formed by the first $k$ entries of the $j^{th}$
column of $\mathbf{I}-\mathbf{S}$. We must now have that
$\mathbf{e_{1}}^{T}\mathbf{A}^{n}(\eta\mathbf{u})=\mathbf{e_{1}}^{T}\mathbf{C}^{n}(\mathbf{I}-\mathbf{S})\mathbf{e_{j}}=\mathbf{e_{1}}^{T}\mathbf{B}^{n}\mathbf{y_{j}}$,
where the choice is over $\mathbf{B}\in\mathbb{Q}^{k\times k}$.

It suffices to pick $\mathbf{B}$ of the form $\mathbf{F}^{-1}\mathbf{AF}$:
this gives $\mathbf{B}^{n}=\mathbf{F}^{-1}\mathbf{A}^{n}\mathbf{F}$. We then
require that for all $n\geq 1$, we must have

$\mathbf{e_{1}}^{T}\mathbf{A}^{n}(\eta\mathbf{u})=(\mathbf{e_{1}}^{T}\mathbf{F}^{-1})\mathbf{A}^{n}(\mathbf{Fy_{j}}).$

We shall choose $\mathbf{F},\eta>0,j$ such that $\mathbf{F}$ is a diagonal
matrix, $\mathbf{e_{1}}^{T}\mathbf{F}^{-1}=\mathbf{e_{1}}^{T}$ ($f_{11}=1$
ensures this), and $\mathbf{Fy_{j}}=\eta\mathbf{u}$. Recall that we assume all
the entries of $\mathbf{u}$ are nonzero, and the entries of $\mathbf{y_{j}}$
are $-s_{1},\dots,1-s_{j},\dots,-s_{k}$, which are also nonzero courtesy our
choice of $\mathbf{S}$. Since $f_{11}=1$ and $\eta$ must be positive, $u_{0}$
and the first entry of $\mathbf{y_{j}}$ must have the same sign. If $u_{0}>0$,
we choose $j=1$, and $\eta=(1-s_{1})/u_{0}$. Otherwise, $u_{0}<0$, in which
case we choose $j=2$, and $\eta=-s_{1}/u_{0}$. Let the entries of
$\mathbf{y_{j}}$ thus chosen be $\mu_{1},\dots,\mu_{k}$. Note that $\eta
u_{0}/\mu_{1}=1$. Taking $\mathbf{F}=\text{diag}(1,\eta
u_{1}/\mu_{2},\dots,\eta u_{k-1}/\mu_{k})$, and thus
$\mathbf{F}^{-1}=\text{diag}(1,\mu_{2}/(\eta u_{1}),\dots,\mu_{k}/(\eta
u_{k-1}))$ ensures that $\mathbf{e_{1}}^{T}\mathbf{F}^{-1}=\mathbf{e_{1}}^{T}$
and $\mathbf{Fy_{k}}=\eta\mathbf{u}$. Propagating these choices to construct
$\mathbf{B},\mathbf{C}$, identify $\rho$, construct $\mathbf{D}$ and finally
$\mathbf{M}$ completes our reduction.

##  4 Discussion

To put our result in perspective, it is worth noting that Markov Reachability
Problems are a special class of model checking problems for Linear Dynamical
Systems as described in [25]. The problem considers the orbit
$\langle\mathbf{M}^{n}\mathbf{s}\rangle_{n=0}^{\infty}$ given by a matrix and
a vector, a finite set of regions given by polynomial inequalities, and asks
whether the characteristic $\omega$-word $\alpha$ that records which of the
regions the orbit visits at every time step belongs to a given
$\omega$-regular language. In our setting, $\mathbf{M}$ is stochastic, and the
regions, which are affine hyperplanes or halfspaces, cannot be handled by the
techniques of [25]. Techniques have been developed to solve these problems for
diagonalisable $\mathbf{M}$ and prefix-independent $\omega$-regular languages
[17]. We assume neither prefix independence nor diagonalisability. The problem
for diagonalisable $\mathbf{M}$ and general $\omega$-regular languages is
shown to reduce to the Positivity Problem for simple LRS [18], which is
analogous but incomparable to the result we show.

## References

  * [1] C. Baier, J.-P. Katoen, Principles of model checking, MIT Press, 2008.
  * [2] L. P. Kaelbling, M. L. Littman, A. W. Moore, Reinforcement learning: a survey, J. Artif. Int. Res. 4 (1) (1996) 237–285.
  * [3] M. Agrawal, S. Akshay, B. Genest, P. S. Thiagarajan, Approximate Verification of the Symbolic Dynamics of Markov Chains, Journal of the ACM (JACM) 62 (2015) 1 – 34.  doi:10.1145/2629417.
  * [4] D. Beauquier, A. Rabinovich, A. Slissenko, A Logic of Probability with Decidable Model Checking, J. Log. Comput. 16 (2006) 461–487.  doi:10.1093/logcom/exl004.
  * [5] V. A. Korthikanti, M. Viswanathan, G. Agha, Y.-M. Kwon, Reasoning about MDPs as Transformers of Probability Distributions, in: QEST, 2010, pp. 199–208.  doi:10.1109/QEST.2010.35.
  * [6] Y. Kwon, G. Agha, Linear Inequality LTL (iLTL): A Model Checker for Discrete Time Markov Chains, in: J. Davies, W. Schulte, M. Barnett (Eds.), Formal Methods and Software Engineering, Springer Berlin Heidelberg, 2004, pp. 194–208.  doi:10.1007/978-3-540-30482-1\\_21.
  * [7] J. Ouaknine, J. Worrell, Positivity Problems for Low-Order Linear Recurrence Sequences, in: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, SIAM, 2014, pp. 366–379.  doi:10.1137/1.9781611973402.27.
  * [8] M. Mignotte, T. N. Shorey, R. Tijdeman, The distance between terms of an algebraic recurrence sequence, Journal für die reine und angewandte Mathematik 349 (1984) 63–76.
  * [9] N. K. Vereshchagin, The problem of appearance of a zero in a linear recurrence sequence , Matematicheskie Zametki (in Russian) 38 (1985) 177–189.  doi:10.1007/BF01156238.
  * [10] Y. Bilu, F. Luca, J. Nieuwveld, J. Ouaknine, D. Purser, J. Worrell, Skolem Meets Schanuel, in: 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022), Vol. 241 of LIPIcs, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022, pp. 20:1–20:15.  doi:10.4230/LIPIcs.MFCS.2022.20.
  * [11] J. Ouaknine, J. Worrell, Ultimate Positivity is Decidable for Simple Linear Recurrence Sequences, in: Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Proceedings, Part II, Vol. 8573 of LNCS, Springer, 2014, pp. 330–341.  doi:10.1007/978-3-662-43951-7\\_28.
  * [12] J. Ouaknine, J. Worrell, On the positivity problem for simple linear recurrence sequences, in: International Colloquium on Automata, Languages, and Programming, Springer, 2014, pp. 318–329.  doi:10.1007/978-3-662-43951-7\\_27.
  * [13] P. Turakainen, Generalized automata and stochastic languages, in: Proceedings of the American Mathematical Society, Vol. 21, 1969, pp. 303–309.
URL https://api.semanticscholar.org/CorpusID:13136683

  * [14] S. Akshay, T. Antonopoulos, J. Ouaknine, J. Worrell, Reachability problems for Markov chains, Information Processing Letters 115 (2) (2015) 155–158.  doi:https://doi.org/10.1016/j.ipl.2014.08.013.
  * [15] S. Akshay, K. Chatterjee, T. Meggendorfer, D. Zikelic, MDPs as Distribution Transformers: Affine Invariant Synthesis for Safety Objectives, in: Computer Aided Verification: 35th International Conference, CAV 2023, Proceedings, Part III, Springer-Verlag, Berlin, Heidelberg, 2023, p. 86–112.  doi:10.1007/978-3-031-37709-9\\_5.
  * [16] J. Piribauer, C. Baier, On Skolem-Hardness and Saturation Points in Markov Decision Processes, in: 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), Vol. 168 of LIPIcs, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 2020, pp. 138:1–138:17.  doi:10.4230/LIPIcs.ICALP.2020.138.
  * [17] S. Almagor, T. Karimov, E. Kelmendi, J. Ouaknine, J. Worrell, Deciding $\omega$-Regular Properties on Linear Recurrence Sequences, Proc. ACM Program. Lang. 5 (POPL) (Jan 2021).  doi:10.1145/3434329.
  * [18] T. Karimov, E. Kelmendi, J. Nieuwveld, J. Ouaknine, J. Worrell, The Power of Positivity, in: 2023 38th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), 2023, pp. 1–11.  doi:10.1109/LICS56636.2023.10175758.
  * [19] T. Skolem, Einige Sätze über $\pi$-adische Potenzreihen mit Anwendung auf gewisse exponentielle Gleichungen, Mathematische Annalen 111 (1) (1935) 399–424.  doi:10.1007/BF01472228.
  * [20] K. Mahler, An arithmetic property of Taylor coefficients of rational functions (1935), in: M. Baake, Y. Bugeaud, M. Coons (Eds.), The Legacy of Kurt Mahler, EMS Press, 2019, pp. 437–448.  doi:10.4171/DMS/8.
  * [21] C. Lech, A note on recurring series, Arkiv för Matematik 2 (5) (1953) 417–421.  doi:10.1007/BF02590997.
  * [22] J. Berstel, M. Mignotte, Deux propriétés décidables Des Suites récurrentes linéaires, Bulletin de la Societe mathematique de France 79 (1976) 175–184.  doi:10.24033/bsmf.1823.
  * [23] G. Everest, A. van der Poorten, I. Shparlinski, T. Ward, Recurrence sequences, Vol. 104 of Mathematical Surveys and Monographs, American Mathematical Society, United States, 2003.
  * [24] R. G. Gallager, Discrete Stochastic Processes, Springer New York, NY, 1996.  doi:https://doi.org/10.1007/978-1-4615-2329-1.
  * [25] T. Karimov, E. Lefaucheux, J. Ouaknine, D. Purser, A. Varonka, M. A. Whiteland, J. Worrell, What’s Decidable about Linear Loops?, Proc. ACM Program. Lang. 6 (POPL) (Jan 2022).  doi:10.1145/3498727.


* Historically contingent is symmetry breaking, finding networks with open-endedness is a challenging open problem.

* dissipation is unentangled from the two. Primary reason is that it only depends on deterministically steady state dynamics and boundary reactions. For closed complex/detailed balanced thermodynamic systems, dissipation is the NEP, but for open systems at NESS, this is not so.

* When internal-internal species become internal-boundary species through adding autocatalytic cycles, then they can perform work and change the equilibrium landscape. If CRNs can show any dynamical behavior, then autocatalytic cores can be used to engineer such landscapes.

* For origins of life experiments, people can propose a CRN, find its evolutionary graph and look for parameter space in experiments. Through CRN bisimulation. Fruitful exchange between theory and experiment.

§.§ Mathematical framework for complex systems

Complex systems are systems composed of several interacting subprocesses.

A process is defined as a kinetic model encoded as a reaction network. The are dual potentials associated with these using which we extract the thermodynamic and information theoretic nonnegative contributions.

\[ \dot{S} = \dot{E} + \dot{W}\]

Subnetwork is a collection of reactions - column reducted matrix.
Motif is a restriction on species - subspecies set.
Autocatalytic motif, core. Subnetwork

Dissipative networks - non-dissipative networks - whether or not the rate cosntants have a curl. These models have phase transitions - Lazarescu et al. Found by large deviation theory. We have an algorithm for when there is no external control. The lagrange multipliers can be re-encoded in the rate constants to give a subproblem. And then there is the intrinsic part.

Autocatalytic motif.

Free energy trandsduction through processes. This is external work needed to maintain.

As the current through the reactions changes from one NESS to another, the external control needed changes. But so does the large deviation contribution - that is improbability suspended/acquired in the stationary distribution.

Integrand is cost of a configuration. TIme integral is cost of a trajectory.

\[ \int \,dt (p \dot{q} + p_{\mcl{E}} v_{\mcl{E}} - H(p,q)) \]

at steady state $\dot{q} = 0$, $H=0$ so the cost is the EPR. At a NESS where the external-boundary species are held at a fixed flux is the other boundary condition that can be introduced using different multiplier but will not be considered.

Since the complete network is detailed balanced, $p v$ comes from a EPR and is given as the $\sigma_r$ where the sum is over reactions in the boundary.