# Effect of expanding learning scope
on the evolution of cooperation in scale-free networks

Masaaki Inaba  Graduate School of Systems and Information Engineering,
University of Tsukuba, Tsukuba, Ibaraki 305-8573, Japan  Eizo Akiyama
Graduate School of Systems and Information Engineering, University of Tsukuba,
Tsukuba, Ibaraki 305-8573, Japan

###### Abstract

We study how expanding the scope for selecting game and learning (adaptation)
partners affects the evolution of cooperation in public goods games on scale-
free networks. We show the following three results. (i) Expanding the scope
for selecting game partners suppresses cooperation. (ii) Expanding the scope
for selecting learning partners promotes cooperation when cooperation
evolution is difficult. (iii) When cooperation is more likely to evolve,
slightly expanding the scope for selecting learning partners causes a
significant drop in the cooperation rate, but expanding the scope further
causes the cooperation rate to recover. Although (i) is explained by the hub-
centered mechanism, the well-known dynamic that promotes cooperation on scale-
free networks, (ii) and (iii) are caused by a completely different mechanism
that has heretofore been rarely mentioned.

PACS number: 89.75.Hc, 87.23.Kg, 87.23.Ge, 02.50.Le

##  I Introduction

There have been meaningful discussions [1, 2, 3] of mechanisms to promote
cooperation in social dilemma situations. Some of the major mechanisms are kin
selection, direct reciprocity, indirect reciprocity, network reciprocity, and
multilevel selection. Mechanisms other than network reciprocity often work
under the assumption of well-mixed populations (random interactions) that are
easy to model and analyze. However, interactions among agents in the real
world are rarely well-mixed, but rather resemble complex network structures
[4, 5, 6]. In the study of network reciprocity, the mechanism of evolving
cooperation has been studied using spatial structures such as circle graphs
and lattices [7, 8], but these spatial structures cannot represent the network
degree heterogeneity that is often observed in real-world human relationships.
Therefore, research on the evolution of cooperation in scale-free networks has
augmented in recent years, based on the heterogeneous characteristics of the
real world [9, 10, 11, 12, 13, 14, 15].

The basic dynamics of the evolution of cooperation in scale-free networks have
already been elucidated [9, 10, 12, 13]. The heterogeneity of the network
degree and the asymmetry of the cooperator and defector explain the dynamics.
Heterogeneity indicates a power-law distribution of the degree of each node in
a scale-free network; in other words, a node with many degrees gets more
degrees. The asymmetry between cooperators and defectors means that when
cooperators form a community, they enjoy high payoffs by cooperating with each
other, whereas when defectors form a community, there are no benefits. On a
scale-free network with these two characteristics, cooperators can stably
obtain higher payoffs than defectors by forming communities around nodes with
high degree. Therefore, the cooperation rate is much higher in scale-free
networks than in well-mixed populations or regular graphs, other conditions
being equal, simply because of the spatial structure. That is the basic
mechanism of network reciprocity on scale-free networks.

There are a number of studies [16, 17, 18, 19, 20, 21, 22, 23] that examine
the effects of spatial structure by incorporating other cooperation mechanisms
studied in well-mixed populations and regular networks into the study of
network reciprocity on scale-free networks. These studies are valuable because
they test certain cooperation mechanisms in a realistic setting. Our study
furthers this type of work by focusing on the scope of games and learning
(adaptation).

Prior works on network reciprocity essentially assume that interactions,
consisting of games and learning, only happen between neighboring agents in
the network (hop 1 in Fig.1). However, in the real world, we do not always
interact only with proximate agents. Depending on the type of activity, we may
interact not only with nearby agents, but also with distant agents (hop 2 and
above in Fig.1). This type of interaction with distant peers is known as ”weak
ties [24]” in empirical network analysis in sociology. Although there have
been several theoretical and experimental studies examining how the evolution
of cooperation is affected by the scope of interactions [25, 26, 27, 28],
there was insufficient focus on scale-free networks. We investigate the effect
of expanding the scope of interaction on the evolution of cooperation in
public goods games on scale-free networks.

Figure 1: Scope of game and learning.
Let the red node be a focal agent. We refer to a node whose shortest path
distance to the focal agent is less than or equal to x as an agent in the hop
x scope.

##  II Method

We simulate public goods games (PGG) that consider the scope of interactions
(games and learning) on a scale-free network with a multi-agent model based on
evolutionary game theory. PGG extends the prisoner’s dilemma game to multiple
players. PGG is a natural representation of social dilemmas and has been
adopted in many studies [29, 13, 30, 31, 32, 33].

The population structure is a static scale-free network generated by the
Barabási–Albert (BA) model [34], with $N=10^{3}$ nodes and the average degree
$k=4$. Each node in the network represents an agent, and an agent’s strategy
is either to cooperate (C) or to defect (D). Initially, we randomly assign C
or D with equal probability. A generation consists of a game and a learning
(adaptation), the games and learning for all agents are performed
synchronously.

The game entails the following steps. First, an agent is chosen as a focal
agent. Then, we randomly select $n-1$ agents whose shortest path distance from
the focal agent is within $hopG$ (game scope) as game partners. Including the
focal agent, the number of game partners is $n$. The number of agents with
strategy C among the n game partners is $n_{C}$. Of the game partners, the
agent with strategy C contributes cost $c=1$, while the agent with strategy D
pays no cost. The total contribution is multiplied by $b$ and divided equally
among all the game partners ($n$ players). Thus, the payoff for each C agent
is $\pi_{C}=\frac{n_{C}\times c\times b}{n}-c$, and the payoff for each D
agent is $\pi_{D}=\frac{n_{C}\times c\times b}{n}$. Each agent becomes the
focal agent once and repeats this process to accumulate payoffs. Note that the
payoffs accumulated by each agent during the game are reset to zero at the
beginning of each generation.

In the learning, as in the game, first, we assume that an agent is the focal
agent. Then, we randomly select $n-1$ agents whose shortest path distance from
the focal agent is within $hopL$ (learning scope) as the learning partners.
The agent with the highest payoff is chosen from among the learning partners,
and if its payoff is greater than the focal agent’s payoff, the focal agent
copies the agent’s strategy (C or D). If the payoffs are the same or lower,
the focal agent does not copy and does not change its strategy in the next
generation. In addition, the focal agent uses a random strategy in the next
generation according to a mutation rate $\mu$.

Figure 2: List of parameters.

##  III Result

###  III.1 Simulation result

In the heat maps in Fig.3, the horizontal axis is the scope for selecting
learning partners (learning scope, $hopL$) and the vertical axis is the scope
for selecting game partners (game scope, $hopG$). The numbers in each cell
represent the average population frequency of cooperators (cooperation rate)
in the total population between 800 and 1000 generations over 100 trials. We
observe that the cooperation rate almost converges in the first 200
generations. The heat map on the left corresponds to $b/c=2.0$ and the right
one corresponds to $b/c=3.0$. The setting on the right is more likely to
evolve cooperation than that on the left. The figures indicate the following
three results.

Figure 3: Population frequency of cooperators (%).
The x-axis ($hopL$) is the learning scope, the y-axis ($hopG$) is the game
scope and each cell indicates the average population frequency of cooperators
(%) in $800\sim 1000$ generations over 100 trials. The mutation rate ($\mu$)
is 1%.

(i) Expanding the game scope suppresses cooperation. The cooperation rate
converges to approximately $0.5\%$ when $hopG$ is greater than or equal to
two, under both settings $b/c=2.0$ and $3.0$.

(ii) Expanding the learning scope promotes cooperation when cooperation is
difficult to evolve. Under the adverse condition ($b/c=2.0$), the cooperation
rate is $0.9\%$ when $(hopG,hopL)=(1,1)$, indicating that almost no cooperator
survives. However, the cooperation rate is $16.8\%$ when $(hopG,hopL)=(1,5)$,
meaning that the cooperation rate improves as the learning scope ($hopL$)
expands. On a scale-free network, $hopL=5$ is approximately equivalent to a
well-mixed population, and the results do not change even if $hopL$ is
increased further.

(iii) If cooperation is more likely to evolve, slightly expanding the learning
scope causes a substantial drop in the cooperation rate, but expanding the
scope further recovers the cooperation rate. Under the advantageous condition
($b/c=3.0$), the cooperation rate is $88.6\%$ when $(hopG,hopL)=(1,1)$,
indicating that many cooperators survive. However, slightly expanding the
learning scope ($hopL=2$) drops the cooperation rate significantly to
$28.8\%$.Then, further expanding the learning scope ($hopL=5$) recovers the
cooperation rate to $58.8\%$.

We discuss the mechanisms that produce these results in the following
sections.

###  III.2 Why does expanding game scope decrease the cooperation rate?

As shown in Section III.1 (i), expanding game scope, regardless of $b/c$,
suppresses the evolution of cooperation. This phenomenon is particularly
evident when we observe that at $b/c=3.0$, where cooperation is relatively
easy to evolve, $88.6\%$ of the agents are C when $(hopG,hopL)=(1,1)$, while
there are only $0.5\%$ C agents when $(hopG,hopL)=$(2, 1)$.When$(hopG, hopL) =
$(1,1)$, the asymmetry between the cooperator and the defector is exploited to
form and expand groups of C agents around the hub. The asymmetry we are
referring to here is that C enjoys high payoffs if it forms a group around the
hub, while D gets no benefit from forming a group. Now, if we increase $hopG$
from one to two, thereby expanding game scope, D can invade C’s group and
free-ride more easily. As a result, C cannot form a robust group and is thus
conquered by D. Thus, the mechanism that promotes cooperation around the hub,
as researched in previous studies [9, 10, 12, 13], would be canceled when
$hopG$ is 2 or higher, thereby suppressing cooperation.

###  III.3 Why does expanding learning scope increase the cooperation rate?

Next, we examine why expanding the learning scope improves the cooperation
rate, as shown in Section III.1 (ii). We investigate this mechanism by
categorizing each agent according to its network degree and looking at the
cooperation rate, as shown in Fig.4. Regardless of whether b/c is 2.0 or 3.0,
when $hopL$ is one, the high-degree agents represented by the green line are
slightly more cooperative than the low-degree agents represented by the orange
line. However, when $hopL$ is set to five, the cooperation rate of low-degree
agents is higher than that of high-degree agents. In other words, when the
learning scope is narrow, high-degree agents lead the cooperative behavior,
but when the learning scope expands, this is reversed, and low-degree agents
appear to lead the cooperative behavior. This suggests that expanding the
learning scope promotes cooperation through a mechanism that is completely
different from the hub-based mechanism that was well documented in previous
studies [9, 10, 12, 13].

Figure 4: Population frequency of cooperators by network degree.
The agents are classified into three network degree categories (high:
$15\sim$, middle: $5\sim 14$, low: $\sim 4$). The transition of the frequency
of cooperators in each category is shown with the generation on the horizontal
axis. The three graphs in the upper row show $b/c=2.0$, the three graphs in
the lower row show $b/c=3.0$, the graph in the left column shows $hopL=1$, the
graph in the middle column shows $hopL=2$, and the graph in the right column
shows $hopL=5$. The number of trials is $100$, $hopG=1$, and $\mu=1\%$.

To examine this mechanism in more detail, we consider a mini-model as shown in
Fig.5 (d) and (e). This mini-model is an emphasized and deformed
representation of the relationship between high-degree agents and low-degree
agents in a scale-free network as a double star graph. In the initial status,
the agents in the left star are C and the agents in the right star are D. We
call the left side the cooperator’s village and the right side the defector’s
village. The three line charts in the Fig.5 (a), (b), and (c) show the results
of a 10 generation, $10^{4}$ trial simulation based on this mini-model with
the settings described in Section II: Method ($b/c=2.0$, $hopG=1$, $n=4$,
$\mu=0\%$).

First, we examine the transition in the cooperation rate of the total
population, which is the sum of the cooperator’s village and the defector’s
village (Fig.5 (a)). Compared with the gray line ($hopL=1$), the green line
($hopL=2$) is slightly higher, indicating that the phenomenon of increasing
cooperation with expanding learning scope is also reproduced in this mini-
model.

Next, we separate the total population (Fig.5 (a)) into the cooperator’s
village (Fig.5 (b)) and the defector’s village (Fig.5 (c)). In the
cooperator’s village, both gray lines (hopL = 1) maintain a 100% cooperation
rate from start to finish, whereas the green dense dashed line ($hopL=2$,
leaves) drops first, and then the green sparse dashed line (hopL = 2, hub)
drops to approximately $60\%$. In the defector’s village (Fig.5 (c)), for hubs
(sparse dashed lines), we see that there is no significant change in the
cooperation rate of about $60\%$ even when $hopL$ increases from one (gray
line) to two (green line). In contrast, for the leaves (dense dashed line),
when the $hopL$ is one (gray line), the cooperation rate is $0\%$, but when
$hopL$ increases to two (green line), the cooperation rate is approximately
$60\%$. Because there are more leaves than hubs, the $60\%$ improvement for
leaves has a greater overall impact.

Thus, expanding the learning scope lowers the cooperation rate in the
cooperator’s village and raises the cooperation rate in the defector’s
village. The effect of increasing the cooperation rate of the leaves in the
defector’s village is greater than the decrease in the cooperator’s village;
therefore, expanding the learning scope raises the cooperation rate as a
whole.

Figure 5: $hopL=1$ v.s. $hopL=2$ on mini-model ($b/c=2.0$, $hopG=1$)
This figure shows the results of 10 generations of the simulation shown in
”Section II: Method” using a mini-model with two star graphs connected
($10^{3}$ trials, $b=2.0$, $n=4$, $hopG=1$, $\mu=0\%$). The three line charts
((a), (b), (c)) show the transition of the frequency of cooperators in the
whole population, the cooperator’s village, and the defector’s village,
respectively, where the horizontal axis represents the generation. The color
of the line indicates the learning scope, where gray is $hopL=1$ and green is
$hopL=2$. The style of the lines represents the type of agent, with solid
lines representing the sum of hubs and leaves, sparse dashed lines
representing hubs, and dense dashed lines representing leaves. (d) and (e)
show how each agent changes from its initial status to the fifth generation,
comparing the case where $hopL=1$ with the case where $hopL=2$. The numbers in
the circles indicate the probability that the agent becomes C in the next
generation: the darker the blue, the higher the probability, and the darker
the red, the lower the probability.

This is further elucidated by examining the transition of the cooperation rate
by agent (Fig.5 (d) and (e)). Note that there is no significant difference in
the hubs when comparing $hopL=1$ with $hopL=2$ at generation 1, but there is a
significant change in the leaves. This is because at $hopL=1$, a leaf is only
affected by the hub of the village to which it is directly connected, while at
$hopL=2$, it is also affected by the hub of the other village. As a result,
the overall cooperation rate settles at about $60\%$. (See Supplemental
Information for the analytical solution for generation 1)

###  III.4 Why does expanding learning scope decrease the cooperation rate?

As Section III.1 (iii) shows, when $b/c=3.0$ and we change $(hopG,hopL)=(1,1)$
to $(1,2)$, the cooperation rate drops significantly. If, as III.3 shows,
expanding the learning scope promotes cooperation, then increasing $hopL$ from
one to two should increase the cooperation rate, but in fact it drops
significantly. We consider the mechanism that produces this phenomenon. As in
III.3, a mini-model deforming the relationship between hubs and leaves in a
scale-free network elucidates this mechanism. The conditions are the same as
in III.3 except that we increase b/c from 2.0 to 2.5. Note that if we increase
b/c to 3.0, the conditions become too favorable to cooperators and there is
little decrease in the cooperation rate; if we increase it to 2.25, the
cooperation rate does not converge in 10 generations.

Figure 6: $hopL=1$ v.s. $hopL=2$ on mini-model ($b/c=2.5$, $hopG=1$)
See Fig.5 for interpretation instructions; the difference is that we set $b/c$
to $2.5$ instead of $2.0$. The color scale is modified to emphasize the change
in the cooperation rate.

Examining the cooperation rate of the entire population (Fig.6 (a)), the green
line ($hopL=2$) is almost $20\%$ lower than the gray line ($hopL=1$) at
generation 10. The green lines for the cooperator’s village (Fig.6 (b)) and
the defector’s village (Fig.6 (c)) also converge to a similarly lower
cooperation rate of almost $20\%$ less than the gray lines. Recalling III.3,
when $b/c=2.0$, the cooperation rate decreased in the cooperator’s village and
increased in the defector’s village, and the overall cooperation rate of the
entire population increased. However, when $b/c=2.5$, the cooperation rate
decreases in both villages, and thus the cooperation rate of the entire
population decreases.

Next, we examine the transition diagram for each agent (Fig.6 (d) and (e)).
Comparing $hopL=1$ and $2$ at generation 1, there is no significant difference
in the probability of the hubs becoming C in the next generation, while the
probabilities of the leaves becoming C have changed significantly. This is
because when $hopL=1$, the leaves are only affected by the hub of the same
village, whereas when $hopL=2$, it is affected by the hub of another village.
As a result, the overall cooperation rate settles at over $80\%$. (See
Supplemental Information for an analytical solution for generation 1).

The mini-model is too small to reproduce the ”trough” where the cooperation
rate drops and then recovers, as seen in $(b/c,hopG,hopL)=(3,1,1-5)$ of Fig.3,
even if the learning scope is further expanded. However, two forces account
for this ”trough” phenomenon: the force that promotes cooperation by
clustering cooperators around hubs, and the force that promotes cooperation by
the expanding the learning scope. That is, when $(b/c,hopG,hopL)=(3,1,1)$ in
Fig.3, the hub force acts, and when $(b/c,hopG,hopL)=(3,1,5)$, the learning
scope force acts. These two forces cannot act at the same time because they
originate from conflicting mechanisms, as Fig.4 suggests. Hence, there is a
”trough” between $(b/c,hopG,hopL)=(3,1,1)$ and $(3,1,5)$, where neither of the
two forces is active when $(b/c,hopG,hopL)=(3,1,2)$ in Fig.3.

This brings us to the mechanism that produces the three results in Section
III.1. We describe this mechanism as follows. First, expanding both the game
and the learning scope precludes the hubs from promoting cooperation.
Expanding the game scope will only suppress the hub’s force, and nothing will
happen even if the scope continues to expand. In contrast, expanding the
learning scope suppresses the hub’s force at first, but then promotes
cooperative behavior through another mechanism led by the leaves rather than
the hubs. When the hub’s force cannot act from the outset ($b/c=2.0$), only
the promotion of cooperation by expanding the learning scope becomes apparent.
When the hub’s force can act ($b/c=3.0$), the model demonstrates both the
cancelation of the hub’s force and the promotion of cooperative behavior by
expanding the learning scope.

##  IV Conclusion

We studied the effect of expanding the scope of selecting game partners (game
scope) and learning partners (learning scope) in public goods games on scale-
free networks. We demonstrate the following three results. (i) Expanding game
scope suppresses cooperation. (ii) Under conditions limiting the evolution of
cooperation, expanding learning scope promotes cooperation. (iii) Under
conditions where cooperation is more likely to evolve, slightly expanding
learning scope causes a drop in the cooperation rate but expanding the
learning scope further causes the cooperation rate to recover. Previous
studies on the evolution of cooperation in scale-free networks do not consider
the scope of games and learning; our study is valuable in that it clarifies
these results and the mechanisms by which they occur. It is also important to
point out that these results are caused by a completely different mechanism
than the previously described promotion of cooperative behavior by hubs.

Future research should focus on further exploring some aspects of our study.
First, we consider that scale-free networks are realistic networks in the
sense that they are more realistic than well-mixed populations and regular
graphs; however, they are not always the best choice [35], and using other
network structures is an interesting direction. In addition, the network
structure used in our research amounts to a multiplex network, because
changing the scope of the game and learning represents different network
structures for the game and learning. In this sense, we expect that this
research relates to the accumulated research on multiplex networks [36, 37,
38, 39, 40]. Second, although our study reveals the existence of mechanisms by
which expanding the learning scope promotes and inhibits cooperation, our
future work will involve further theoretical and analytical studies to
identify and quantify the effects of specific parameters on the cooperation
rate. Further theoretical analysis of the relationship between scale-free
networks and mini-models is also important. Finally, this study shows the
theoretical potential of the highlighted mechanisms. The dynamics of this
mechanism in the real world must be verified and supported by research in
other fields such as behavioral ecology and evolutionary anthropology.

###### Acknowledgements.

We thank Irina Entin, M. Eng., from Edanz (https://jp.edanz.com/ac) for
editing a draft of this manuscript.

## References

  * [1] Martin A. Nowak.  Five Rules for the Evolution of Cooperation.  Science, 314(5805):1560–1563, dec 2006.
  * [2] David G. Rand and Martin A. Nowak.  Human cooperation.  Trends in Cognitive Sciences, 17(8):413–425, aug 2013.
  * [3] MICHAEL A. ZAGGL.  Eleven mechanisms for the evolution of cooperation.  Journal of Institutional Economics, 10(2):197–230, 2014.
  * [4] Kwang Il Goh, Eulsik Oh, Hawoong Jeong, Byungnam Kahng, and Doochul Kim.  Classification of scale-free networks.  Proceedings of the National Academy of Sciences of the United States of America, 99(20):12583–12588, oct 2002.
  * [5] Albert László Barabási.  Network Science.  Cambridge University Press, 1st editio edition, 2016.
  * [6] Linqing Liu, Mengyun Shen, and Chang Tan.  Scale free is not rare in international trade networks.  Scientific Reports 2021 11:1, 11(1):1–8, jun 2021.
  * [7] Martin A. Nowak and Robert M. May.  Evolutionary games and spatial chaos.  Nature, 359(6398), oct 1992.
  * [8] Carlos P. Roca, José A. Cuesta, and Angel Sánchez.  Effect of spatial structure on the evolution of cooperation.  Physical Review E, 80(4):046106, oct 2009.
  * [9] F. C. Santos and J. M. Pacheco.  Scale-Free Networks Provide a Unifying Framework for the Emergence of Cooperation.  Physical Review Letters, 95(9):098104, aug 2005.
  * [10] Hisashi Ohtsuki, Christoph Hauert, Erez Lieberman, and Martin A. Nowak.  A simple rule for the evolution of cooperation on graphs and social networks.  Nature, 441(7092):502–505, may 2006.
  * [11] Zhihai Rong, Xiang Li, and Xiaofan Wang.  Roles of mixing patterns in cooperation on a scale-free networked game.  Physical Review E - Statistical, Nonlinear, and Soft Matter Physics, 76(2):027101, aug 2007.
  * [12] F. C. Santos, J. M. Pacheco, and Tom Lenaerts.  Evolutionary dynamics of social dilemmas in structured heterogeneous populations.  Proceedings of the National Academy of Sciences of the United States of America, 103(9):3490, feb 2006.
  * [13] Francisco C. Santos, Marta D. Santos, and Jorge M. Pacheco.  Social diversity promotes the emergence of cooperation in public goods games.  Nature 2008 454:7201, 454(7201):213–216, jul 2008.
  * [14] Coren L. Apicella, Frank W. Marlowe, James H. Fowler, and Nicholas A. Christakis.  Social networks and cooperation in hunter-gatherers.  Nature 2012 481:7382, 481(7382):497–501, jan 2012.
  * [15] Benjamin Allen, Gabor Lippner, Yu-Ting Chen, Babak Fotouhi, Naghmeh Momeni, Shing-Tung Yau, and Martin A. Nowak.  Evolutionary dynamics on any population structure.  Nature, 544(7649):227–230, apr 2017.
  * [16] Samhar Mahmoud, Nathan Griffiths, Jeroen Keppens, and Michael Luck.  Norm Emergence through Dynamic Policy Adaptation in Scale Free Networks.  Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 7756 LNAI:123–140, 2012.
  * [17] Samhar Mahmoud, Nathan Griffiths, Jeroen Keppens, and Michael Luck.  Norm Emergence: Overcoming Hub Effects in Scale Free Networks.  Proceedings of the AAMAS 2012 Workshop on Coordination, Organizations, Institutions and Norms, pages 136–150, 2012.
  * [18] Shade T. Shutters.  Punishment Leads to Cooperative Behavior in Structured Societies.  Evolutionary Computation, 20(2):301–319, jun 2012.
  * [19] Lei Zhou, Aming Li, and Long Wang.  Evolution of cooperation on scale-free networks subject to error and attack.  New Journal of Physics, 11(3):033027, mar 2009.
  * [20] Boris Podobnik, Andrijana Musura Gabor, and Ivona Skreblin Kirbis.  Scale-free growth of human society based on cooperation and altruistic punishment.  Physica A: Statistical Mechanics and its Applications, 513:613–619, jan 2019.
  * [21] Ya Shan Chen, Hai Lin, and Chen Xu Wu.  Evolution of prisoner’s dilemma strategies on scale-free networks.  Physica A: Statistical Mechanics and its Applications, 385(1):379–384, nov 2007.
  * [22] Jorge Peña, Enea Pestelacci, André Berchtold, and Marco Tomassini.  Participation costs can suppress the evolution of upstream reciprocity.  Journal of Theoretical Biology, 273(1):197–206, mar 2011.
  * [23] Ana Peleteiro, Juan C Burguillo, and Siang Yew Chong.  Exploring Indirect Reciprocity in Complex Networks using Coalitions and Rewiring.  Proceedings of the 2014 international conference on Autonomous agents and multi-agent systems., pages 669–676, 2014.
  * [24] Mark S. Granovetter.  The strength of weak ties.  American journal of sociology, 1(1983):201–233, oct 1973.
  * [25] Tackseung Jun and Rajiv Sethi.  Neighborhood structure and the evolution of cooperation.  Journal of Evolutionary Economics, 17(5):623–646, jun 2007.
  * [26] Jung Kyoo Choi.  Play locally, learn globally: Group selection and structural basis of cooperation.  Journal of Bioeconomics, 10(3):239–257, sep 2008.
  * [27] Yanlong Zhang and Wolfram Elsner.  Social leverage, a core mechanism of cooperation. Locality, assortment, and network evolution.  Journal of Evolutionary Economics, 30(3):867–889, sep 2020.
  * [28] Isamu Okada, Hitoshi Yamamoto, Eizo Akiyama, and Fujio Toriumi.  Cooperation in spatial public good games depends on the locality effects of game, adaptation, and punishment.  Scientific Reports, 11(1):1–7, dec 2021.
  * [29] Elinor Ostrom.  Governing the Commons: The Evolution of Institutions for Collective Action.  Cambridge University Press, Cambridge, UK., 1990.
  * [30] Xian Bin Cao, Wen Bo Du, and Zhi Hai Rong.  The evolutionary public goods game on scale-free networks with heterogeneous investment.  Physica A: Statistical Mechanics and its Applications, 389(6):1273–1280, mar 2010.
  * [31] Zhen Wang, Attila Szolnoki, and Matja Perc.  Percolation threshold determines the optimal population density for public cooperation.  Physical Review E - Statistical, Nonlinear, and Soft Matter Physics, 85(3):037101, mar 2012.
  * [32] Xinyang Deng, Zhipeng Zhang, Yong Deng, Qi Liu, and Shuhua Chang.  Self-adaptive win-stay-lose-shift reference selection mechanism promotes cooperation on a square lattice.  Applied Mathematics and Computation, 284:322–331, jul 2016.
  * [33] Maja Duh, Marko Gosak, and Matjaž Perc.  Mixing protocols in the public goods game.  Physical Review E, 102(3):032310, sep 2020.
  * [34] Albert László Barabási and Réka Albert.  Emergence of scaling in random networks.  Science, 286(5439):509–512, oct 1999.
  * [35] Anna D. Broido and Aaron Clauset.  Scale-free networks are rare.  Nature Communications 2019 10:1, 10(1):1–10, mar 2019.
  * [36] Jesús Gómez-Gardeñes, Irene Reinares, Alex Arenas, and Luis Mario Floría.  Evolution of Cooperation in Multiplex Networks.  Scientific Reports, 2(1):1–6, dec 2012.
  * [37] Zhen Wang, Lin Wang, Attila Szolnoki, and Matjaz Perc.  Evolutionary games on multilayer networks: A colloquium.  apr 2015.
  * [38] María Pereda.  Evolution of cooperation under social pressure in multiplex networks.  Physical Review E, 94(3):032314, sep 2016.
  * [39] Federico Battiston, Matjaž Perc, and Vito Latora.  Determinants of public cooperation in multiplex networks.  New Journal of Physics, 19(7):073017, jul 2017.
  * [40] James M. Allen, Anne C. Skeldon, and Rebecca B. Hoyle.  Social influence preserves cooperative strategies in the conditional cooperator public goods game on a multiplex network.  Physical Review E, 98(6):062305, dec 2018.


# Quantization dimension for inhomogeneous bi-Lipschitz IFS

Amit Priyadarshi  Department of Mathematics, Indian Institute of Technology
Delhi, New Delhi, India 110016<EMAIL_ADDRESS>,  Mrinal K.
Roychowdhury  School of Mathematical and Statistical Sciences, University of
Texas Rio Grande Valley, 1201 West University Drive, Edinburg, TX 78539-2999,
USA<EMAIL_ADDRESS>and  Manuj Verma  Department of
Mathematics, Indian Institute of Technology Delhi, New Delhi, India 110016
<EMAIL_ADDRESS>
###### Abstract.

Let $\nu$ be a Borel probability measure on a $d$-dimensional Euclidean space
$\mathbb{R}^{d}$, $d\geq 1$, with a compact support, and let
$(p_{0},p_{1},p_{2},\ldots,p_{N})$ be a probability vector with $p_{j}>0$ for
$1\leq j\leq N$. Let $\\{S_{j}:1\leq j\leq N\\}$ be a set of contractive
mappings on $\mathbb{R}^{d}$. Then, a Borel probability measure $\mu$ on
$\mathbb{R}^{d}$ such that $\mu=\sum_{j=1}^{N}p_{j}\mu\circ
S_{j}^{-1}+p_{0}\nu$ is called an inhomogeneous measure, also known as a
condensation measure on $\mathbb{R}^{d}$. For a given $r\in(0,+\infty)$, the
quantization dimension of order $r$, if it exists, denoted by $D_{r}(\mu)$, of
a Borel probability measure $\mu$ on $\mathbb{R}^{d}$ represents the speed at
which the $n$th quantization error of order $r$ approaches to zero as the
number of elements $n$ in an optimal set of $n$-means for $\mu$ tends to
infinity. In this paper, we investigate the quantization dimension for such a
condensation measure.

###### Key words and phrases:

Quantization error, quantization dimension, Iterated function system,
Probability measure

###### 1991 Mathematics Subject Classification:

Primary 37A50; Secondary 28A80, 94A34

##  1\. Introduction

Quantization is a process of discretization, in other words, to represent a
continuous or a large set of values by a set with smaller number of values. It
has broad application in signal processing and data compression. For a
detailed survey on the subject and a comprehensive list of references to the
literature one is referred to [1, 3, 4, 5, 7, 8, 9, 10, 11, 12, 13, 20, 21].

Given a Borel probability measure $P$ on $\mathbb{R}^{d}$, a number
$r\in(0,+\infty)$ and a natural number $n\in\mathbb{N}$, the $n$th
quantization error of order $r$ for $P$, is defined by

$V_{n,r}:=V_{n,r}(P)=\text{inf}\\{\int
d(x,\alpha)^{r}dP(x):\alpha\subset\mathbb{R}^{d},\,\text{card}(\alpha)\leq
n\\},$ (1)

where $d(x,\alpha)$ denotes the distance from the point $x$ to the set
$\alpha$ with respect to a given norm $\|\cdot\|$ on $\mathbb{R}^{d}$. The
numbers

$\underline{D}_{r}(P):=\liminf_{n\to\infty}\frac{r\log n}{-\log
V_{n,r}(P)}\text{ and }\overline{D}_{r}(P):=\limsup_{n\to\infty}\frac{r\log
n}{-\log V_{n,r}(P)}$ (2)

are called the lower and the upper quantization dimensions of $P$ of order
$r$, respectively. If $\underline{D}_{r}(P)=\overline{D}_{r}(P)$, the common
value is called the quantization dimension of $P$ of order $r$ and is denoted
by $D_{r}(P)$. Quantization dimension measures the speed at which the
specified measure of the error goes to zero as $n$ tends to infinity. For any
$\kappa>0$, the numbers $\liminf_{n}n^{\frac{r}{\kappa}}V_{n,r}(P)$ and
$\limsup_{n}n^{\frac{r}{\kappa}}V_{n,r}(P)$ are called the
$\kappa$-dimensional lower and upper quantization coefficients for $P$,
respectively. If the $\kappa$-dimensional lower and upper quantization
coefficients are finite and positive, then $\kappa$ equals the quantization
dimension $D_{r}(P)$.

Let $\mathcal{F}=\\{\mathbb{R}^{d};S_{1},S_{2},\ldots,S_{N}\\}$ be a family of
contractive iterated function system (IFS) such that for all
$x,y\in\mathbb{R}^{d}$, we have

$s_{i}d(x,y)\leq d(S_{i}(x),S_{i}(y))\leq c_{i}d(x,y),$

where $0<s_{i}\leq c_{i}<1$ and $i\in\\{1,2,\ldots,N\\}.$ Let
$\mathcal{G}=\\{\mathbb{R}^{d};g_{1},g_{2},\ldots,g_{M}\\}$ be another IFS
such that

$d(g_{i}(x),g_{i}(y))\leq r_{i}d(x,y),$

where $0<r_{i}<1$ and $i\in\\{1,2,\ldots,M\\}.$ Let $K_{\phi}$ and $C$ be the
attractor of the IFS $\mathcal{F}$ and $\mathcal{G}$, respectively, that is,

$K_{\emptyset}=\bigcup_{i=1}^{N}S_{i}(K_{\emptyset}),\quad
C=\bigcup_{i=1}^{M}g_{i}(C).$

Let $(t_{1},t_{2},\ldots,t_{M})$ be a probability vector. Then, there exists a
unique invariant measure $\nu$ supported on $C$ such that

$\nu=\sum_{i=1}^{M}t_{i}\nu\circ g_{i}^{-1}.$

Let $(p_{0},p_{1},p_{2},\ldots,p_{N})$ be a probability vector. Then, there
exists a unique Borel probability measure $\mu$ and a compact set $K$ such
that

$\mu=p_{0}\nu+\sum_{i=1}^{N}p_{i}\mu\circ S_{i}^{-1},\quad
K=\bigcup_{i=1}^{N}S_{i}(K)\bigcup C.$

We call $(\\{S_{i}\\}_{i=1}^{N},(p_{i})_{i=0}^{N},\nu)$ a condensation system.
The measure $\mu$ is called the attracting measure or the condensation measure
for $({S_{i}}_{i=1}^{N},(p_{i})_{i=0}^{N},\nu)$, and the set $K$, which is the
support of the measure $\mu,$ is called the attractor of the system (see [3,
14]). Such a measure is also termed as an inhomogeneous measure. We say that
the condensation system satisfies the strong separation condition (SSC) if
$S_{1}(K),S_{2}(K),\ldots,S_{N}(K)~{}~{}\text{and}~{}~{}C$ are pairwise
disjoint. An IFS $\mathcal{F}=\\{\mathbb{R}^{d};S_{1},S_{2},\ldots,S_{N}\\}$
satisfies the open set condition (OSC) if there exists a bounded nonempty open
set $U\subset\mathbb{R}^{d}$ such that $\cup_{j=1}^{N}S_{j}(U)\subseteq U$ and
$S_{i}(U)\cap S_{j}(U)=\emptyset$ for all $1\leq i\neq j\leq N$. Furthermore,
$\mathcal{F}$ satisfies the strong open set condition (SOSC) if $U$ can be
chosen such that $U\cap K_{\emptyset}\neq\emptyset$, where $\emptyset$ is the
empty set and $K_{\emptyset}$ is the attractor of $\mathcal{F}$. Notice that
in the case of an iterated function system consisting of a finite number of
mappings on the Euclidean space, the open set condition implies the strong
open set condition (see [16, 18]), and it is not true for an iterated function
system with infinitely many mappings (see [19]).

In this paper, we state and prove the following theorem which is the main
result of the paper.

######  Theorem 1.1.

Let $r\in(0,\infty)$, and let $\mu$ be the condensation measure associated
with the condensation system $(\\{S_{i}\\}_{i=1}^{N},(p_{i})_{i=0}^{N},\nu)$.
Assume that the condensation system
$(\\{S_{i}\\}_{i=1}^{N},(p_{i})_{i=0}^{N},\nu)$ satisfies the strong
separation condition. Then,

$\max\\{k_{r},\underline{D}_{r}(\nu)\\}\leq\underline{D}_{r}(\mu),$

where $k_{r}$ is uniquely determined by
$\sum_{i=1}^{N}(p_{i}s_{i}^{r})^{\frac{k_{r}}{r+k_{r}}}=1.$ Furthermore, if
the IFS $\mathcal{G}$ satisfies the strong open set condition, then

$\max\\{k_{r},\underline{D}_{r}(\nu)\\}\leq\underline{D}_{r}(\mu)\leq\overline{D}_{r}(\mu)\leq\max\\{l_{r},d_{r}\\},$

where $l_{r}$ and $d_{r}$ are given by
$\sum_{i=1}^{N}(p_{i}c_{i}^{r})^{\frac{l_{r}}{r+l_{r}}}=1$ and
$\sum_{i=1}^{M}(t_{i}r_{i}^{r})^{\frac{d_{r}}{r+d_{r}}}=1$, respectively.

######  Remark 1.2.

In the above theorem, if we consider the mappings $S_{i}$ and $g_{i}$ as
similarity mappings, i.e.,

$d(S_{i}(x),S_{i}(y))=s_{i}d(x,y),\quad d(g_{j}(x),g_{j}(y))=r_{j}d(x,y)$

for all $i\in\\{1,2,\cdots,N\\}$ and $j\in\\{1,2,\ldots,M\\},$ then the
quantization dimension of the condensation measure $\mu$ exists, and

$D_{r}(\mu)=\max\\{k_{r},D_{r}(\nu)\\},$

where $k_{r}$ and $D_{r}(\nu)$ are given by
$\sum_{i=1}^{N}(p_{i}s_{i}^{r})^{\frac{k_{r}}{r+k_{r}}}=1$ and
$\sum_{i=1}^{M}(t_{i}r_{i}^{r})^{\frac{D_{r}(\nu)}{r+D_{r}(\nu)}}=1$,
respectively.

######  Remark 1.3.

In [24], Zhu estimated the quantization dimension of the condensation measure
$\mu$ corresponding to the condensation system
$(\\{f_{i}\\}_{i=1}^{N},(p_{i})_{i=0}^{N},\nu)$ with an inhomogeneous open set
condition, where each $f_{i}$ is a similarity map and the measure $\nu$ is an
invariant measure corresponding to some self-similar IFS satisfying the open
set condition. For determining the upper and the lower bound, the author used
the separation condition on the condensation system as well as the separation
condition on the self-similar IFS associated with the measure $\nu$. On the
other hand, in Theorem 1.1, we note that for determining the lower bound, we
only take separation condition on the condensation system
$(\\{S_{i}\\}_{i=1}^{N},(p_{i})_{i=0}^{N},\nu)$ and the measure $\nu$ is any
probability measure, and in obtaining the upper bound, we consider the the
condensation system with strong separation condition and the measure $\nu$
corresponding to some IFS with strong open set condition.

######  Remark 1.4.

In [22], Zhu determined the quantization dimension of the condensation measure
$\mu$ corresponding to the condensation system
$(\\{f_{i}\\}_{i=1}^{N},(p_{i})_{i=0}^{N},\nu)$ with the strong separation
condition, where $f_{i}$’s are similarity mappings and the measure $\nu$ is a
self similar measure corresponding to the IFS
$\\{\mathbb{R}^{d};f_{1},f_{2},\ldots,f_{N}\\}$ with a probability vector
$(t_{1},t_{2},\ldots,t_{N}).$ By taking the same conditions as in [22],
Roychowdhury [17] estimated the quantization dimension of the condensation
measure $\mu$ and related the upper bound of the quantization dimension with
the temperature function of the thermodynamic formalism that arises in the
multifractal analysis of $\mu.$ However, in Theorem 1.1, we consider more
general condensation system $(\\{S_{i}\\}_{i=1}^{N},(p_{i})_{i=0}^{N},\nu)$
with the strong separation condition by taking the maps $S_{i}$’s as bi-
Lipschitz and the measure $\nu$ as the invariant measure corresponding to some
IFS. Thus, Theorem 1.1 provides the quantization dimension of the condensation
measure in a more general setting.

##  2\. Preliminaries

Define $I:=\\{1,2,\ldots,N\\}$ and let $I^{n}=\\{w=w_{1}w_{2}w_{3}\cdots
w_{n}:w_{i}\in I~{}~{}\forall~{}~{}i\in\\{1,2,\ldots,n\\}\\}.$ Let
$I^{*}=\cup_{n\in\mathbb{N}\cup\\{0\\}}I^{n}$, where $I^{0}$ denotes the set
consisting of the empty sequence $\emptyset$. Thus, $I^{\ast}$ denotes the set
of all finite sequences of symbols belonging to $I$ including the empty
sequence $\emptyset$. Notice that if $\omega\in I^{\ast}$, then $\omega\in
I^{n}$ for some $n\in\mathbb{N}\cup\\{0\\}$. Such an $n$ is called the length
of the word $\omega$ and is denoted by $|\omega|$. Notice that the length of
the empty sequence is zero. Let $\Omega$ denote the set of all infinite
sequences of symbols from the set $I.$ For $w=w_{1}w_{2}\cdots w_{n}\in I^{n}$
with $n\geq 1$, we define

$S_{w}=S_{w_{1}}\circ S_{w_{2}}\circ\cdots
S_{w_{n}},~{}~{}p_{w}=\prod_{i=1}^{n}p_{w_{i}},~{}~{}s_{w}=\prod_{i=1}^{n}s_{w_{i}},~{}~{}c_{w}=\prod_{i=1}^{n}c_{w_{i}}~{}\text{and}~{}w^{-}=w_{1}w_{2}\cdots
w_{n-1}.$

For the empty sequence $\emptyset$, we write

$S_{\emptyset}=Id_{\mathbb{R}^{d}},\,p_{\emptyset}=1,\,\text{ and
}s_{\emptyset}=c_{\emptyset}=1,$

where $Id_{\mathbb{R}^{d}}$ is the identity mapping on $\mathbb{R}^{d}$. For
$n\geq 1$, by iterating, we obtain

$K=\bigg{(}\bigcup_{w\in
I^{n}}S_{w}(K)\bigg{)}\cup\bigg{(}\bigcup_{m=0}^{n-1}\bigcup_{w\in
I^{m}}S_{w}(C)\bigg{)},~{}\text{and}~{}\mu=\sum_{w\in I^{n}}p_{w}\mu\circ
S_{w}^{-1}+p_{0}\sum_{m=0}^{n-1}\sum_{w\in I^{m}}p_{w}\nu\circ S_{w}^{-1}.$

For any $w\in I^{*}$ such that $|w|\geq n$, we denote $w|_{n}=w_{1}w_{2}\cdots
w_{n}.$ We define an ordering on $I^{*}$ as follows

$w\prec\sigma~{}~{}\text{if and only
if}~{}~{}|w|\leq|\sigma|,~{}~{}\sigma|_{|w|}=w,$

where $\sigma,w\in I^{*}.$ For any $\sigma,w\in I^{*}$, we say that $\sigma$
and $w$ are incomparable if neither $\sigma\prec w$ nor $w\prec\sigma$. On the
other hand, if $\omega\prec\sigma$, we say that $\sigma$ is an extension of
$\omega$. For $w\in I^{*}$, we define

$\Xi_{w}(m)=\\{\sigma\in
I^{|w|+m}:w\prec\sigma\\}\quad\text{and}\quad\Xi_{w}^{*}=\cup_{m\in\mathbb{N}}\Xi_{w}(m),$

where $m\geq 1.$

Define $J:=\\{1,2,\ldots,M\\}.$ We define $J^{*}$ and $J^{n}$ in a similar way
as we define $I^{*}$ and $I^{n}.$

We call $\Gamma\subset I^{*}$ a finite maximal antichain if $\Gamma$ is a
finite set such that every sequence in $\Omega$ is an extension of some
element in $\Gamma$, but no element of $\Gamma$ is an extension of another
element in $\Gamma.$ Let $\Gamma$ be a finite maximal antichain. Set

$l_{\Gamma}=\min\\{|\omega|:\omega\in\Gamma\\}\quad\text{and}\quad
M_{\Gamma}=\max\\{|\omega|:\omega\in\Gamma\\}.$

For $w\in I^{l_{\Gamma}}$, we define

$\Delta_{\Gamma}(w)=\\{\sigma\in
I^{*}:w\leq\sigma,~{}~{}\Xi_{\sigma}^{*}\cap\Gamma\neq\emptyset\\},\quad\Delta_{\Gamma}^{*}=\cup_{w\in
I^{l_{\Gamma}}}\Delta_{\Gamma}(w).$

######  Lemma 2.1.

(see [24]) Let $\Gamma$ be a finite maximal antichain. Then,

$K=\bigg{(}\bigcup_{w\in\Gamma}S_{w}(K)\bigg{)}\cup\bigg{(}\bigcup_{w\in\Delta_{\Gamma}^{*}}S_{w}(C)\bigg{)}\cup\bigg{(}\bigcup_{n=0}^{l_{\Gamma}-1}\bigcup_{w\in
I^{n}}S_{w}(C)\bigg{)}.$

For a given Borel probability measure $P$ on $\mathbb{R}^{d}$, a positive real
number $r$ and a natural number $n$, let $V_{n,r}$ denote the $n$th
quantization error of order $r$ as defined in equation (1). If the infimum in
(1) is attained for some $A\subset\mathbb{R}^{d}$, then $A$ is called an
$n$-_optimal set_ for the measure $P$ of order $r$. The existence of
$n$-optimal set is guaranteed if $P$ has a compact support (see [6]). The
lower quantization dimension $\underline{D}_{r}$ and the upper quantization
dimension $\overline{D}_{r}$ are as defined in equation (2). We recall the
following important proposition which will be needed to prove our main
results.

######  Proposition 2.2.

(see [6])

  1. (1)

If $0\leq t_{1}<\overline{D}_{r}<t_{2},$ then

$\limsup_{n\to\infty}nV_{n,r}^{\frac{t_{1}}{r}}=\infty~{}~{}~{}\text{and}~{}~{}~{}\lim_{n\to\infty}nV_{n,r}^{\frac{t_{2}}{r}}=0.$

  2. (2)

If $0\leq t_{1}<\underline{D}_{r}<t_{2},$ then

$\liminf_{n\to\infty}nV_{n,r}^{\frac{t_{2}}{r}}=0~{}~{}~{}\text{and}~{}~{}~{}\lim_{n\to\infty}nV_{n,r}^{\frac{t_{1}}{r}}=\infty.$

##  3\. Main results

To prove Theorem 1.1, which gives the main results of the paper, we state and
prove some lemmas and propositions.

######  Lemma 3.1.

Let $r\in(0,\infty)$, and let $\mu$ be the condensation measure associated
with the condensation system $(\\{S_{i}\\}_{i=1}^{N},(p_{i})_{i=0}^{N},\nu)$.
Then,

$\underline{D}_{r}(\nu)\leq\underline{D}_{r}(\mu)\quad\text{and}\quad\overline{D}_{r}(\nu)\leq\overline{D}_{r}(\mu).$

###### Proof.

Let $A$ be an $n$-optimal set for the Borel probability measure $\mu$ of order
$r$. Then, we have

$V_{n,r}(\mu)=\int d(x,A)^{r}d\mu(x).$

Since $\mu=p_{0}\nu+\sum_{i=1}^{N}p_{i}\mu\circ S_{i}^{-1}$, we obtain
$\mu\geq p_{0}\nu.$ Then,

$\displaystyle V_{n,r}(\mu)\geq p_{0}\int d(x,A)^{r}d\nu(x)\geq
p_{0}V_{n,r}(\nu).$

In the above, taking logarithm, and then dividing both side by $\log
V_{n,r}(\mu)\log V_{n,r}(\nu)$, we get

$\frac{1}{\log V_{n,r}(\mu)}\leq\frac{-\log p_{0}}{\log V_{n,r}(\mu)\log
V_{n,r}(\nu)}+\frac{1}{\log V_{n,r}(\nu)},$

which implies that

$\bigg{(}1-\frac{\log p_{0}}{\log V_{n,r}(\mu)}\bigg{)}\frac{r\log n}{-\log
V_{n,r}(\nu)}\leq\frac{r\log n}{-\log V_{n,r}(\mu)}.$

By [6, Lemma 6.1], we have $\lim_{n\to\infty}V_{n,r}(\mu)\to 0.$ Hence, by
taking liminf and limsup on both sides of the above inequality, we get our
required result. ∎

In the following lemma, we only assume that the condensation system
$(\\{S_{i}\\}_{i=1}^{N},(p_{i})_{i=0}^{N},\nu)$ satisfies the strong
separation condition without assuming any condition on the probability measure
$\nu.$

######  Proposition 3.2.

Assume that the condensation system
$(\\{S_{i}\\}_{i=1}^{N},(p_{i})_{i=0}^{N},\nu)$ satisfies the strong
separation condition. Let $\mu$ be the inhomogeneous measure associated with
$(\\{S_{i}\\}_{i=1}^{N},(p_{i})_{i=0}^{N},\nu)$. Then for any $r>0$, we have

$\liminf_{n\to\infty}nV_{n,r}^{\frac{k_{r}}{r}}(\mu)>0,$

where $k_{r}$ is uniquely determined by
$\sum_{i=1}^{N}(p_{i}s_{i}^{r})^{\frac{k_{r}}{r+k_{r}}}=1.$

###### Proof.

Let $r\in(0,\infty)$. We define a map $\phi:[0,\infty)\to[0,\infty)$ by

$\phi(t)=\sum_{i=1}^{N}(p_{i}s_{i}^{r})^{t}.$

The map $\phi$ is strictly decreasing and continuous. Moreover, $\phi(0)=N>1$
and $\phi(1)=\sum_{i=1}^{N}(p_{i}s_{i}^{r})<\sum_{1}^{N}p_{i}=1.$ Thus, there
exists a unique $\tilde{t_{r}}\in(0,1)$ such that
$\sum_{i=1}^{N}(p_{i}s_{i}^{r})^{\tilde{t_{r}}}=1.$ By the uniqueness of
$\tilde{t_{r}}$, there is a unique $k_{r}\in(0,\infty)$ such that

$\sum_{i=1}^{N}(p_{i}s_{i}^{r})^{\frac{k_{r}}{r+k_{r}}}=1.$

Since the condensation system $(\\{S_{i}\\}_{i=1}^{N},(p_{i})_{i=0}^{N},\nu)$
satisfies the strong separation condition,
$S_{1}(K),S_{2}(K),\ldots,S_{N}(K)~{}\text{and}~{}C$ are pairwise disjoint
sets. Write

$\delta=\min\\{d(S_{i}(K),S_{j}(K)):1\leq i\neq j\leq N\\}>0.$

Let $A_{n}$ be an $n$-optimal set for the Borel probability measure $\mu$ of
order $r$. Set $\delta_{n}=\sup_{x\in K}d(x,A_{n})$. Then,
$\lim_{n\to\infty}\delta_{n}=0$ (see [6, Lemma 6.1, Lemma 13.8]). This implies
that there exists $n_{0}\in\mathbb{N}$ such that
$\delta_{n}\leq\frac{\delta}{3}$ for all $n\geq n_{0}.$ Set $A_{n_{i}}=\\{a\in
A_{n}:d(a,S_{i}(K))\leq\delta_{n}\\}.$ It is easy to see that
$A_{n_{i}}\neq\emptyset$ and $A_{n_{i}}\cap A_{n_{j}}=\emptyset$ for $1\leq
i\neq j\leq N.$ Let $k_{i}(n)=\text{card}(A_{n_{i}}).$ Thus, we have
$\sum_{i=1}^{N}k_{i}(n)\leq n.$ Also, $k_{i}(n)\leq n-1$ for each $1\leq i\leq
N.$ Since $A_{n}$ is an $n$-optimal set for the Borel probability measure
$\mu$ of order $r$, we have

$\displaystyle V_{n,r}(\mu)$ $\displaystyle=\int d(x,A_{n})^{r}d\mu(x)$
$\displaystyle\geq\sum_{i=1}^{N}\int_{S_{i}(K)}d(x,A_{n})^{r}d\mu(x)$
$\displaystyle=\sum_{i=1}^{N}\int_{S_{i}(K)}d(x,A_{n_{i}})^{r}d\mu(x)$
$\displaystyle\geq\sum_{i=1}^{N}p_{i}\int_{S_{i}(K)}d(x,A_{n_{i}})^{r}d(\mu\circ
S_{i}^{-1})(x)$
$\displaystyle\geq\sum_{i=1}^{N}p_{i}s_{i}^{r}\int_{K}d(x,S_{i}^{-1}(A_{n_{i}}))^{r}d(\mu)(x)$
$\displaystyle\geq\sum_{i=1}^{N}p_{i}s_{i}^{r}V_{k_{i}(n),r}(\mu).$

Define $M_{0}=\min\\{n^{\frac{r}{k_{r}}}V_{n,r}(\mu):n<n_{0}\\}.$ Clearly,
$M_{0}>0$ and $M_{0}\leq n^{\frac{r}{k_{r}}}V_{n,r}(\mu)$ for all $n<n_{0}$.
Now our claim is that $M_{0}\leq n^{\frac{r}{k_{r}}}V_{n,r}(\mu)$ for all
$n\in\mathbb{N}.$ We prove our claim by induction on $n\in\mathbb{N}.$ Let us
assume that $M_{0}\leq{\eta}^{\frac{r}{k_{r}}}V_{\eta,r}(\mu)$ for all
$\eta<n$ and $n\geq n_{0}.$ Thus, we have

$V_{n,r}(\mu)\geq\sum_{i=1}^{N}p_{i}s_{i}^{r}V_{k_{i}(n),r}(\mu)\geq
M_{0}\sum_{i=1}^{N}p_{i}s_{i}^{r}{k_{i}(n)}^{\frac{-r}{k_{r}}}.$

Hence, by the generalized Hölder’s inequality, we get

$\sum_{i=1}^{N}p_{i}s_{i}^{r}{k_{i}(n)}^{\frac{-r}{k_{r}}}\geq\bigg{(}\sum_{i=1}^{N}(p_{i}s_{i}^{r})^{\frac{k_{r}}{r+k_{r}}}\bigg{)}^{1+\frac{r}{k_{r}}}\cdot\bigg{(}\sum_{i=1}^{N}k_{i}(n)\bigg{)}^{\frac{-r}{k_{r}}}.$

Using the facts that
$\sum_{i=1}^{N}(p_{i}s_{i}^{r})^{\frac{k_{r}}{r+k_{r}}}=1$ and
$\sum_{i=1}^{N}k_{i}(n)\leq n$, we get $V_{n,r}(\mu)\geq
M_{0}n^{\frac{-r}{k_{r}}}$, that is, $M_{0}\leq
n^{\frac{r}{k_{r}}}V_{n,r}(\mu).$ Thus, by induction, we obtain that
$M_{0}\leq n^{\frac{r}{k_{r}}}V_{n,r}(\mu)$ holds for all $n\in\mathbb{N}.$
This implies that

$\liminf_{n\to\infty}nV_{n,r}^{\frac{k_{r}}{r}}(\mu)\geq
M_{0}^{\frac{k_{r}}{r}}>0.$

Thus, the proof is done. ∎

Motivated by [24], we fix some notations in the following paragraph.

First, we define a finite maximal antichain on $I^{*}$ as follows

$\Gamma_{n}^{r}=\\{w\in I^{*}:p_{w}c_{w}^{r}<\xi_{r}^{n}\leq
p_{w^{-}}c_{w^{-}}^{r}\\}$

where $n\geq 1$ and $\xi_{r}=\min\\{\min\limits_{1\leq j\leq
M}t_{j}r_{j}^{r},\min\limits_{1\leq j\leq N}p_{j}c_{j}^{r}\\}.$ Let
$|\Gamma_{n}^{r}|$ denote the cardinality of the set $\Gamma_{n}^{r}.$ We
write

$\Phi_{n}^{r}=\bigcup_{m=0}^{l_{\Gamma_{n}^{r}}-1}I^{m}\cup\Delta_{\Gamma_{n}^{r}}^{*}$

for all $n\geq 1.$ By the definition of $\Phi_{n}^{r}$, one can easily see
that for any $w\in\Phi_{n}^{r}$, we have $p_{w}c_{w}^{r}\geq\xi_{r}^{n}.$
Thus, for any $w\in\Phi_{n}^{r},$ we define a finite maximal antichain on
$J^{*}$ as follows

$\Gamma_{n}^{r}(w)=\\{\sigma\in
J^{*}:p_{w}c_{w}^{r}t_{\sigma}r_{\sigma}^{r}<\xi_{r}^{n}\leq
p_{w}c_{w}^{r}t_{\sigma^{-}}r_{\sigma^{-}}^{r}\\}.$

Let $|\Gamma_{n}^{r}(w)|$ be the cardinality of $\Gamma_{n}^{r}(w)$ for each
$w\in\Phi_{n}^{r}.$ We define

$\displaystyle\phi_{n,r}:=|\Gamma_{n}^{r}|+\sum_{w\in\Phi_{n}^{r}}|\Gamma_{n}^{r}(w)|.$
(3)

######  Lemma 3.3.

For each $n\geq 1$, we have

$K=\bigg{(}\bigcup_{w\in\Gamma_{n}^{r}}S_{w}(K)\bigg{)}\cup\bigg{(}\bigcup_{w\in\Phi_{n}^{r}}\bigcup_{\sigma\in\Gamma_{n}^{r}(w)}S_{w}(g_{\sigma}(C))\bigg{)}.$

###### Proof.

By Lemma 2.1, we have

$K=\bigg{(}\bigcup_{w\in\Gamma_{n}^{r}}S_{w}(K)\bigg{)}\cup\bigg{(}\bigcup_{w\in\Delta_{\Gamma_{n}^{r}}^{*}}S_{w}(C)\bigg{)}\cup\bigg{(}\bigcup_{m=0}^{l_{\Gamma_{n}^{r}}-1}\bigcup_{w\in
I^{m}}S_{w}(C)\bigg{)}.$

Since for each $w\in\Phi_{n}^{r}$, $\Gamma_{n}^{r}(w)$ is a finite maximal
antichain in $J^{*}$, we obtian

$C=\bigcup_{\sigma\in\Gamma_{n}^{r}(w)}g_{\sigma}(C).$

Using the definition of $\Phi_{n}^{r}$ and the above relations, we get

$K=\bigg{(}\bigcup_{w\in\Gamma_{n}^{r}}S_{w}(K)\bigg{)}\cup\bigg{(}\bigcup_{w\in\Phi_{n}^{r}}\bigcup_{\sigma\in\Gamma_{n}^{r}(w)}S_{w}(g_{\sigma}(C))\bigg{)}.$

∎

######  Lemma 3.4.

Assume that the condensation system
$(\\{S_{i}\\}_{i=1}^{N},(p_{i})_{i=0}^{N},\nu)$ satisfies the strong
separation condition and the IFS $\mathcal{G}$ satisfies the strong open set
condition. Let $\mu$ be the inhomogeneous measure associated with
$(\\{S_{i}\\}_{i=1}^{N},(p_{i})_{i=0}^{N},\nu)$. Then, we have

$V_{\phi_{n,r},r}(\mu)\leq
C^{*}\bigg{(}\sum_{w\in\Gamma_{n}^{r}}p_{w}c_{w}^{r}+\sum_{w\in\Phi_{n}^{r}}\sum_{\sigma\in\Gamma_{n}^{r}(w)}p_{w}c_{w}^{r}t_{\sigma}r_{\sigma}^{r}\bigg{)},$

where $C^{*}=\max\\{({\text{diam}(K)})^{r},({\text{diam}(C)})^{r}\\}$ and
$\phi_{n,r}$ is given by equation (3).

###### Proof.

First, we define a set $A$ such that $\text{card}(A)\leq\phi_{n,r}.$ For each
$w\in\Gamma_{n}^{r},$ we choose an element $a_{w}\in S_{w}(K)$ and for each
$w\in\Phi_{n}^{r}$, we choose an element $a_{w,\sigma}\in
S_{w}(g_{\sigma}(C))$ such that $\sigma\in\Gamma_{n}^{r}(w).$ We collect all
such type of elements and form a set $A$. Clearly,
$\text{card}(A)\leq\phi_{n,r}.$ Thus, by Lemma 3.3, we have

$\displaystyle V_{\phi_{n,r},r}(\mu)$
$\displaystyle\leq\int_{K}d(x,A)^{r}d\mu(x)$
$\displaystyle\leq\sum_{w\in\Gamma_{n}^{r}}\int_{S_{w}(K)}d(x,A)^{r}d\mu(x)+\sum_{w\in\Phi_{n}^{r}}\sum_{\sigma\in\Gamma_{n}^{r}(w)}\int_{S_{w}(g_{\sigma}(C))}d(x,A)^{r}d\mu(x)$
$\displaystyle\leq\sum_{w\in\Gamma_{n}^{r}}\int_{S_{w}(K)}d(x,a_{w})^{r}d\mu(x)+\sum_{w\in\Phi_{n}^{r}}\sum_{\sigma\in\Gamma_{n}^{r}(w)}\int_{S_{w}(g_{\sigma}(C))}d(x,a_{w,\sigma})^{r}d\mu(x)$
$\displaystyle\leq\sum_{w\in\Gamma_{n}^{r}}(\text{diam}(S_{w}(K)))^{r}\mu(S_{w}(K))+\sum_{w\in\Phi_{n}^{r}}\sum_{\sigma\in\Gamma_{n}^{r}(w)}(\text{diam}(S_{w}(g_{\sigma}(C))))^{r}\mu(S_{w}(g_{\sigma}(C)))$
$\displaystyle\leq\sum_{w\in\Gamma_{n}^{r}}c_{w}^{r}({\text{diam}(K)})^{r}\mu(S_{w}(K))+\sum_{w\in\Phi_{n}^{r}}\sum_{\sigma\in\Gamma_{n}^{r}(w)}c_{w}^{r}r_{\sigma}^{r}({\text{diam}(C)})^{r}\mu(S_{w}(g_{\sigma}(C))).$

Writing $C^{*}=\max\\{({\text{diam}(K)})^{r},({\text{diam}(C)})^{r}\\}$, we
get

$V_{\phi_{n,r},r}(\mu)\leq
C^{*}\bigg{(}\sum_{w\in\Gamma_{n}^{r}}c_{w}^{r}\mu(S_{w}(K))+\sum_{w\in\Phi_{n}^{r}}\sum_{\sigma\in\Gamma_{n}^{r}(w)}c_{w}^{r}r_{\sigma}^{r}\mu(S_{w}(g_{\sigma}(C)))\bigg{)}$
(4)

Now, we determine the values of $\mu(S_{w}(K))$ and $\mu(S_{w}(g_{\sigma}(C))$
for $w\in\Gamma_{n}^{r}$ and $\sigma\in\Gamma_{n}^{r}(w)$. Let
$w\in\Gamma_{n}^{r}$ and $|w|=n_{1}$. Since $\mu=\sum_{\tau\in
I^{n_{1}}}p_{\tau}\mu\circ
S_{\tau}^{-1}+p_{0}\sum_{m=0}^{n_{1}-1}\sum_{\tau\in I^{m}}p_{\tau}\nu\circ
S_{\tau}^{-1}$, and the condensation system satisfies the strong separation
condition, we have

$\displaystyle\mu(S_{w}(K))$ $\displaystyle=\sum_{\tau\in
I^{n_{1}}}p_{\tau}\mu\circ
S_{\tau}^{-1}(S_{w}(K))+p_{0}\sum_{m=0}^{n_{1}-1}\sum_{\tau\in
I^{m}}p_{\tau}\nu\circ S_{\tau}^{-1}(S_{w}(K))$
$\displaystyle=p_{w}\mu(S_{w}^{-1}(S_{w}(K)))+p_{0}\sum_{m=0}^{n_{1}-1}\sum_{\tau\in
I^{m}}p_{\tau}\nu\circ S_{\tau}^{-1}(S_{w}(K))$
$\displaystyle=p_{w}\mu(K)+p_{0}\sum_{m=0}^{n_{1}-1}\sum_{\begin{subarray}{c}\tau\in
I^{m}\\\ \tau\leq w\end{subarray}}p_{\tau}\nu\circ S_{\tau}^{-1}(S_{w}(K)).$

Since $\tau\in I^{m}$ and $\tau\leq w$, we write $w=\tau w_{\tau}$ for some
$w_{\tau}\in I^{*}$. Then, using $\mu(K)=1$, we have

$\displaystyle\mu(S_{w}(K))$
$\displaystyle=p_{w}+p_{0}\sum_{m=0}^{n_{1}-1}\sum_{\begin{subarray}{c}\tau\in
I^{m}\\\ \tau\leq w\end{subarray}}p_{\tau}\nu(S_{\tau}^{-1}(S_{\tau
w_{\tau}}(K)))$
$\displaystyle=p_{w}+p_{0}\sum_{m=0}^{n_{1}-1}\sum_{\begin{subarray}{c}\tau\in
I^{m}\\\ \tau\leq w\end{subarray}}p_{\tau}\nu(S_{w_{\tau}}(K)\cap C).$

Since the condensation system satisfies the strong separation condition, we
have $S_{w_{\tau}}(K)\cap C=\emptyset$. Thus, we get

$\mu(S_{w}(K))=p_{w}.$ (5)

Since the IFS $J$ satisfies the strong open set condition, we have
$\nu(g_{\sigma}(C))=t_{\sigma}$ for all $\sigma\in J^{*}$ (see [2, 15]).

$\displaystyle\mu(S_{w}(g_{\sigma}(C)))$ $\displaystyle=\sum_{\tau\in
I^{n_{1}}}p_{\tau}\mu\circ
S_{\tau}^{-1}(S_{w}(g_{\sigma}(C)))+p_{0}\sum_{m=0}^{n_{1}-1}\sum_{\tau\in
I^{m}}p_{\tau}\nu\circ S_{\tau}^{-1}(S_{w}(g_{\sigma}(C)))$
$\displaystyle=p_{w}\mu(S_{w}^{-1}(S_{w}(g_{\sigma}(C))))+p_{0}\sum_{m=0}^{n_{1}-1}\sum_{\begin{subarray}{c}\tau\in
I^{m}\\\ \tau\leq w\end{subarray}}p_{\tau}\nu\circ
S_{\tau}^{-1}(S_{w}(g_{\sigma}(C)))$ $\displaystyle=p_{w}\mu(g_{\sigma}(C))+0$
$\displaystyle=p_{w}\bigg{(}p_{0}\nu(g_{\sigma}(C))+\sum_{i=1}^{N}p_{i}\mu\circ
S_{i}^{-1}(g_{\sigma}(C))\bigg{)}.$

Since the condensation system satisfies the strong separation condition, we
obtain

$\mu(S_{w}(g_{\sigma}(C)))=p_{w}p_{0}\nu(g_{\sigma}(C))=p_{w}p_{0}t_{\sigma}\leq
p_{w}t_{\sigma}.$ (6)

By using (5) and (6) in the inequality (4), we get the required result. ∎

######  Proposition 3.5.

Assume that the condensation system
$(\\{S_{i}\\}_{i=1}^{N},(p_{i})_{i=0}^{N},\nu)$ satisfies the strong
separation condition and the IFS $\mathcal{G}$ satisfies the strong open set
condition. Let $\mu$ be the inhomogeneous measure associated with
$(\\{S_{i}\\}_{i=1}^{N},(p_{i})_{i=0}^{N},\nu)$. Then,

$\limsup_{n\to\infty}nV_{n,r}^{\frac{t}{r}}(\mu)<\infty,$

for all $t>\max\\{l_{r},d_{r}\\},$ where $l_{r}$ and $d_{r}$ are given by
$\sum_{i=1}^{N}(p_{i}c_{i}^{r})^{\frac{l_{r}}{r+l_{r}}}=1$ and
$\sum_{i=1}^{M}(t_{i}r_{i}^{r})^{\frac{d_{r}}{r+d_{r}}}=1$, respectively.

###### Proof.

By Lemma 3.4 and using the definition of $\Gamma_{n}^{r}$ and
$\Gamma_{n}^{r}(w)$, we have

$\displaystyle V_{\phi_{n,r},r}(\mu)$ $\displaystyle\leq
C^{*}\bigg{(}\sum_{w\in\Gamma_{n}^{r}}p_{w}c_{w}^{r}+\sum_{w\in\Phi_{n}^{r}}\sum_{\sigma\in\Gamma_{n}^{r}(w)}p_{w}c_{w}^{r}t_{\sigma}r_{\sigma}^{r}\bigg{)}$
$\displaystyle\leq C^{*}\xi_{r}^{n}\phi_{n,r}.$

Now, we determine the bound of $\phi_{n,r}$. Suppose the values of $l_{r}$ and
$d_{r}$ are uniquely determined by
$\sum_{i=1}^{N}(p_{i}c_{i}^{r})^{\frac{l_{r}}{r+l_{r}}}=1$ and
$\sum_{i=1}^{M}(t_{i}r_{i}^{r})^{\frac{d_{r}}{r+d_{r}}}=1$, respectively.
Since $\Gamma_{n}^{r}$ is a finite maximal antichain in $I^{*}$ and for each
$w\in\Phi_{n}^{r}$, $\Gamma_{n}^{r}(w)$ is a finite maximal antichain in
$J^{*}$, we have

$\sum_{w\in\Gamma_{n}^{r}}(p_{w}c_{w}^{r})^{\frac{l_{r}}{r+l_{r}}}=1\quad\text{and}\quad\sum_{\sigma\in\Gamma_{n}^{r}(w)}(t_{\sigma}r_{\sigma}^{r})^{\frac{d_{r}}{r+d_{r}}}=1.$

Let $t>\max\\{l_{r},d_{r}\\}.$ Then, we have

$\sum_{w\in\Gamma_{n}^{r}}(p_{w}c_{w}^{r})^{\frac{t}{r+t}}<1\quad\text{and}\quad\sum_{\sigma\in\Gamma_{n}^{r}(w)}(t_{\sigma}r_{\sigma}^{r})^{\frac{t}{r+t}}<1.$

By the definitions of $\phi_{n,r}$, $\Gamma_{n}^{r}$ and $\Gamma_{n}^{r}(w)$
for each $w\in\Phi_{n}^{r}$, we obtain

$\displaystyle\phi_{n,r}\xi_{r}^{\frac{(n+1)t}{r+t}}$
$\displaystyle\leq\sum_{w\in\Gamma_{n}^{r}}(p_{w}c_{w}^{r})^{\frac{t}{r+t}}+\sum_{w\in\Phi_{n}^{r}}\sum_{\sigma\in\Gamma_{n}^{r}(w)}(p_{w}c_{w}^{r}t_{\sigma}r_{\sigma}^{r})^{\frac{t}{r+t}}$
$\displaystyle<1+\sum_{w\in\Phi_{n}^{r}}(p_{w}c_{w}^{r})^{\frac{t}{r+t}}\sum_{\sigma\in\Gamma_{n}^{r}(w)}(t_{\sigma}r_{\sigma}^{r})^{\frac{t}{r+t}}$
$\displaystyle<1+\sum_{w\in\Phi_{n}^{r}}(p_{w}c_{w}^{r})^{\frac{t}{r+t}}.$

Since
$\Phi_{n}^{r}=\bigcup_{m=0}^{l_{\Gamma_{n}^{r}}-1}I^{m}\cup\Delta_{\Gamma_{n}^{r}}^{*}$
and
$\Delta_{\Gamma_{n}^{r}}^{*}\subset\bigcup_{m=l_{\Gamma_{n}^{r}}}^{M_{\Gamma_{n}^{r}}}I^{m}$,
we have

$\displaystyle\phi_{n,r}\xi_{r}^{\frac{(n+1)t}{r+t}}$
$\displaystyle<1+\sum_{m=0}^{l_{\Gamma_{n}^{r}}-1}\sum_{w\in
I^{m}}(p_{w}c_{w}^{r})^{\frac{t}{r+t}}+\sum_{m=l_{\Gamma_{n}^{r}}}^{M_{\Gamma_{n}^{r}}}\sum_{w\in
I^{m}}(p_{w}c_{w}^{r})^{\frac{t}{r+t}}$
$\displaystyle=1+\sum_{m=0}^{M_{\Gamma_{n}^{r}}}\sum_{w\in
I^{m}}(p_{w}c_{w}^{r})^{\frac{t}{r+t}}$
$\displaystyle=1+\sum_{m=0}^{M_{\Gamma_{n}^{r}}}\bigg{(}\sum_{i=1}^{N}(p_{i}c_{i}^{r})^{\frac{t}{r+t}}\bigg{)}^{m}$
$\displaystyle<\frac{2}{1-\sum_{i=1}^{N}(p_{i}c_{i}^{r})^{\frac{t}{r+t}}}.$

Thus, by the previous inequalities, we obtain

$\displaystyle\phi_{n,r}V_{\phi_{n,r},r}^{\frac{t}{r}}(\mu)$
$\displaystyle\leq{(C^{*})}^{\frac{t}{r}}\xi_{r}^{\frac{nt}{r}}\phi_{n,r}^{\frac{t+r}{r}}$
$\displaystyle\leq{(C^{*})}^{\frac{t}{r}}\xi_{r}^{\frac{-t}{r}}\bigg{(}\frac{2}{1-\sum_{i=1}^{N}(p_{i}c_{i}^{r})^{\frac{t}{r+t}}}\bigg{)}^{\frac{t+r}{r}}.$

This implies that
$\limsup_{n\to\infty}\phi_{n,r}V_{\phi_{n,r},r}^{\frac{t}{r}}<\infty$ for all
$t>\max\\{l_{r},d_{r}\\}$. By using [23, Theorem 2.4], we obtain

$\limsup_{n\to\infty}nV_{n,r}^{\frac{t}{r}}(\mu)<\infty\quad\forall\quad
t>\max\\{l_{r},d_{r}\\}.$

This completes the proof.

∎

### Proof of Theorem 1.1

Let $\mu$ be the condensation measure associated with the condensation system
$(\\{S_{i}\\}_{i=1}^{N},(p_{i})_{i=0}^{N},\nu)$. Assume that the condensation
system $(\\{S_{i}\\}_{i=1}^{N},(p_{i})_{i=0}^{N},\nu)$ satisfies the strong
separation condition. Then, by Lemma 3.1, Proposition 3.2 and $(2)$ of
Proposition 2.2, we obtain

$\max\\{k_{r},\underline{D}_{r}(\nu)\\}\leq\underline{D}_{r}(\mu),$

where $k_{r}$ is uniquely determined by
$\sum_{i=1}^{N}(p_{i}s_{i}^{r})^{\frac{k_{r}}{r+k_{r}}}=1.$ Furthermore, if
the IFS $\mathcal{G}$ satisfies the strong open set condition, then, by
Proposition 3.5 and $(1)$ of Proposition 2.2, we get

$\overline{D}_{r}(\mu)\leq\max\\{l_{r},d_{r}\\},$

where $l_{r}$ and $d_{r}$ are given by
$\sum_{i=1}^{N}(p_{i}c_{i}^{r})^{\frac{l_{r}}{r+l_{r}}}=1$ and
$\sum_{i=1}^{M}(t_{i}r_{i}^{r})^{\frac{d_{r}}{r+d_{r}}}=1$, respectively.

∎

######  Remark 3.6.

Let $\mu$ be the condensation measure for a condensation system
$(\\{S_{i}\\}_{i=1}^{N},(p_{i})_{i=0}^{N},\nu)$, where $\nu$ is any Borel
probability measure supported on any compact set $C$. Then, by Lemma 3.1 and
Proposition 3.2, the lower bound obtained in Theorem 1.1 is still valid in
this more general setting. The assumption that the measure $\nu$ is the
invariant measure corresponding to some IFS is needed only for the upper bound
of the quantization dimension.

## References

  * [1] E. F. Abaya and G. L. Wise, _On the existence of optimal quantizers_ , IEEE Trans. Inform. Theory 28 (1982), no. 6, 937–946.
  * [2] C. Bandt, M. Barnsley, M. Hegland and A. Vince, _Old wine in fractal bottles I: Orthogonal expansions on self-referential spaces via fractal transformations_ , Chaos Solitons Fractals 91 (2016), 478–489.
  * [3] J. A. Bucklew, _Two results on the asymptotic performance of quantizers_ , IEEE Trans. Inform. Theory 30 (1984), no. 2, 341–348.
  * [4] J. A. Bucklew and G. L. Wise, _Multidimensional asymptotic quantization theory with $r$th power distortion measures_, IEEE Trans. Inform. Theory 28 (1982), no. 2, 239–247.
  * [5] A. Gersho and R. M. Gray, _Vector Quantization and Signal Compression_ , Kluwer Academic Publishers, Boston, 1991.
  * [6] S. Graf and H. Luschgy, _Foundations of Quantization for Probability Distributions_ , Lecture Notes in Mathematics 1730, Springer, Berlin, 2000.
  * [7] S. Graf and H. Luschgy, _Asymptotics of the Quantization Errors for Self-Similar Probabilities_ , Real Anal. Exchange 26 (2000), no. 2, 795–810.
  * [8] S. Graf and H. Luschgy, _The quantization dimension of self-similar probabilities_ , Math. Nachr. 241 (2002), 103–109.
  * [9] S. Graf and H. Luschgy, _Quantization for probability measures with respect to the geometric mean error_ , Math. Proc. Cambridge Philos. Soc. 136 (2004), no. 3, 687–717.
  * [10] R. M. Gray, J. C. Kieffer and Y. Linde, _Locally optimal block quantizer design_ , Inform. and Control 45 (1980), no. 2, 178–198.
  * [11] R. Gray and D. Neuhoff, _Quantization_ , IEEE. Trans. Inform Theory, 44 (1998), 2325–2383.
  * [12] P. M. Gruber, _Optimum quantization and its applications_ , Adv. Math. 186 (2004), no. 2, 456–497.
  * [13] A. György and T. Linder, _On the structure of optimal entropy-constrained scalar quantizers_ , IEEE Trans. Inform. Theory 48 (2002), no.2, 416–427.
  * [14] A. Lasota, _A variational principle for fractal dimensions_ , Nonlinear Anal. 64 (2006), no. 3, 618–628.
  * [15] M. Morán, _Dynamical boundary of a self-similar set_ , Fund. Math. 160 (1999), no. 1, 1–14.
  * [16] Y. Peres, M. Rams, K. Simon and B. Solomyak, _Equivalence of positive Hausdorff measure and the open set condition for self-conformal sets_ , Proc. Amer. Math. Soc. 129 (2001), no. 9, 2689–2699.
  * [17] M. K. Roychowdhury, _Quantization dimension estimate of inhomogeneous self-similar measures_ , Bull. Pol. Acad. Sci. Math. 61 (2013), no. 1, 35–45.
  * [18] A. Schief, _Separation properties for self-similar sets_ , Proc. Amer. Math. Soc. 122 (1994), no. 1, 111–115.
  * [19] T. Szarek and S. L. Wedrychowicz, _The OSC does not imply the SOSC for infinite iterated function systems_ , Proc. Amer. Math. Soc. 133 (2005), no. 2, 437–440.
  * [20] P. L. Zador, _Development and evaluation of procedures for quantizing multivariate distributions_ , Thesis (Ph.D.)–Stanford University, 1964.
  * [21] P. L. Zador, _Asymptotic quantization error of continuous signals and the quantization dimension_ , IEEE Trans. Inform. Theory 28 (1982), no. 2, 139–149.
  * [22] S. Zhu, _Quantization dimension for condensation systems_ , Math. Z. 259 (2008), no. 1, 33–43.
  * [23] S. Zhu, _On the upper and lower quantization coefficient for probability measures on multiscale Moran sets_ , Chaos Solitons Fractals 45 (2012), no. 11, 1437–1443.
  * [24] S. Zhu, _The quantization for in-homogeneous self-similar measures with in-homogeneous open set condition_ , Internat. J. Math. 26 (2015), no. 5, 1550030, 23 pp.


# Characterisation and Simulation of stitched CMOS Strip Sensors

Naomi Davis11footnotemark: 1<EMAIL_ADDRESS>Jan-Hendrik Arling  Marta
Baselga  Leena Diehl  Jochen Dingfelder  Ingrid-Maria Gregor  Marc Hauser
Fabian Hügging  Tomasz Hemperek  Karl Jakobs  Michael Karagounis  Roland
Koppenhöfer  Kevin Kröninger  Fabian Lex  Ulrich Parzefall  Arturo Rodriguez
Birkan Sari  Niels Sorgenfrei  Simon Spannagel  Dennis Sperlich  Tianyang Wang
Jens Weingarten  Iveta Zatocilova

###### Abstract

In high-energy physics, there is a need to investigate alternative silicon
sensor concepts that offer cost-efficient, large-area coverage. Sensors based
on CMOS imaging technology present such a silicon sensor concept for tracking
detectors.

The CMOS Strips project investigates passive CMOS strip sensors fabricated by
LFoundry in a $150\text{\,}\mathrm{nm}$ technology. By employing the technique
of stitching, two different strip sensor formats have been realised. The
sensor performance is characterised based on measurements at the DESY II Test
Beam Facility. The sensor response was simulated utilising Monte Carlo methods
and electric fields provided by TCAD device simulations.

This study shows that employing the stitching technique does not affect the
hit detection efficiency. A first look at the electric field within the sensor
and its impact on generated charge carriers is being discussed.

###### keywords:

CMOS , Silicon strip sensors , Stitching , Test Beam

††journal: Nuclear Instruments and Methods in Physics Research A

[DESY]organization=Deutsches Elektronen Synchrotron DESY,
addressline=Notkestr. 85, postcode=22607 Hamburg, country=Germany

[Freiburg]organization=Physikalisches Institut, University of Freiburg,
addressline=Hermann-Herder-Straße 3, postcode=79104 Freiburg, country=Germany

[Bonn]organization=Physikalisches Institut, University of Bonn,
addressline=Nussallee 12, postcode=53115 Bonn, country=Germany

[TU_Dortmund]organization=Physik E4, TU Dortmund, addressline=Otto-Hahn-
Strasse 4a, postcode=44227 Dortmund, country=Germany

[FH_Dortmund]organization=Fachhochschule Dortmund, addressline=Sonnenstraße
96, postcode=44139 Dortmund, country=Germany

[CERN]organization=CERN, addressline=Esplanade des Particules 1, postcode=1211
Meyrin, country=Switzerland

[Littlefuse]organization=Littlefuse, addressline=Edisonstraße 15,
postcode=68623 Lampertheim, country=Germany

[Dectris]organization=DECTRIS AG, addressline=Täfernweg 1, postcode=5405
Baden, country=Switzerland

##  1 Introduction

Particle tracking detectors in high-energy physics primarily rely on silicon
sensors as tracking devices. With the active area of tracking detectors
constantly increasing, the high-energy physics community faces a challenge in
scaling production volumes and managing costs to cover large-area detectors
with high-resolution, radiation-hard silicon sensors. Based on this challenge,
sensors for particle tracking are only produced by a few foundries, creating
the risk of a single-vendor scenario.

This study aims to tackle this challenge by exploring strip sensors based on
CMOS imaging technology. As CMOS imaging technology is widely used for
industrial and commercial silicon sensor production, it can offer access to
fast- and large-scale production by various vendors. In addition, one can
profit from the larger wafer size available in commercial processes.

On the other hand, the maximum reticle size in the order of
$\mathcal{O}($1\text{\,}{\mathrm{cm}}^{2}$)$ in industrial sensor production
poses a remaining challenge for fabricating different sensor formats to
achieve large-area coverage in tracking detectors. To circumvent this issue, a
sensor is divided into individual parts matching the maximum reticle size,
which are illuminated separately on the wafer with a slight overlap. This
technique is referred to as stitching [1] in CMOS circuit production.

##  2 CMOS Strip Sensors

The CMOS Strips project is investigating stitched, passive CMOS strip sensors
fabricated by LFoundry [2] in a $150\text{\,}\mathrm{n}\mathrm{m}$ technology.
The sensors are produced on a p-type, $8$-inch, Float-Zone wafer with a
resistivity between $3\text{\,}\mathrm{k\SIUnitSymbolOhm}$ and
$5\text{\,}\mathrm{k\SIUnitSymbolOhm}$. In addition, the wafer underwent an
additional production step at IZM Berlin, where it was thinned down to a
thickness of $150\pm 10.\text{\,}\mathrm{\SIUnitSymbolMicro m}$ from the
backside and a laser-annealed p+ layer with a closing metallisation layer was
implemented as backside implant. The stitching technique enables the
realisation of a long ($4.1\text{\,}\mathrm{cm}$) and a short
($2.1\text{\,}\mathrm{cm}$) strip sensor format.

The strip implant design varies in doping concentration and width to study
various electric field configurations. Figure 1 depicts the Regular and the
two Low Dose design layouts. For the Regular design, the strip implant
consists of a highly doped n+ layer with a lesser doped n-implant (Nwell)
below and has a width of $18\text{\,}\mathrm{\SIUnitSymbolMicro m}$. The Low
Dose designs have a reduced width of $10\text{\,}\mathrm{\SIUnitSymbolMicro
m}$ for both the highly doped n+ layer and the lesser doped n-implant.
Additionally, these designs are extended by low-doped n-implants (Low-dose N)
on each side that reach a total width of
$30\text{\,}\mathrm{\SIUnitSymbolMicro m}$ and
$55\text{\,}\mathrm{\SIUnitSymbolMicro m}$, respectively. P-stop implants on
either side electrically isolate the strip implants from each other. Each
sensor comprises $40$ strips of the Regular design and $40$ strips of the Low
Dose designs, split into Low Dose $30$ and Low Dose $55$, as depicted in
Figure 2, with a $75.5\text{\,}\mathrm{\SIUnitSymbolMicro m}$ pitch. Figure 2
also shows where the stitching lines occur along the sensor length, indicated
by blue dashed lines.

In order to evaluate the performance of the different sensor layouts, the
sensors are characterised in a test beam environment concerning their hit
detection efficiency. In addition, a first simulation of the charge carrier
propagation within the sensor is discussed.

(a) Regular design

(b) Low Dose design

Figure 1: Schematic layout of the Regular (top) and Low Dose $30$/$55$
(bottom) strip implant designs [3]. Figure 2: Microscopic picture of a long
($4.1\text{\,}\mathrm{cm}$), passive CMOS strip sensor with the different
strip implant designs denoted. The blue dashed lines indicate stitching lines
across the sensor [3].

##  3 Experimental Methods

###  3.1 Test Beam Measurements

The present study is based on data acquired in test beam campaigns at the DESY
II Test Beam Facility [4]. The facility provides an electron beam with an
user-adjustable electron energy from $1\text{\,}\mathrm{GeV}$ to
$6\text{\,}\mathrm{GeV}$ and offers the ADENIUM [5] beam telescope as a
reference for reconstructing particle trajectories through the Device Under
Test (DUT). The ADENIUM telescope comprises six ALPIDE [6] pixel sensor planes
arranged perpendicularly. The strip sensor under investigation is placed in
the middle of the telescope with three telescope planes upstream and
downstream of the electron beam. Two scintillators, in coincidence, provide
trigger signals.

In this study, two different test beam campaigns are being presented. The
first test beam campaign was conducted in May 2022 with a
$3.4\text{\,}\mathrm{GeV}$ electron beam directed onto an unirradiated strip
sensor of the short format. The second campaign in March 2023 featured a
$4.2\text{\,}\mathrm{GeV}$ electron beam directed onto a neutron-irradiated
strip sensor of the long format. The irradiation was performed with
$23\text{\,}\mathrm{MeV}$ reactor neutrons at Ljubljana to a fluence of
$3\text{\times}{10}^{14}\text{\,}\mathrm{n}_{\text{eq}}\mathrm{/}\mathrm{c}\mathrm{m}\mathrm{{}^{2}}$.
The DUT is placed in a styrofoam box that is flushed with nitrogen and can be
cooled to $-45\text{\,}\mathrm{\SIUnitSymbolCelsius}$ with dry ice pellets to
reduce the higher leakage current in irradiated samples. Unirradiated samples
were measured at Test Beam area temperature, which averaged to
$15\text{\,}\mathrm{\SIUnitSymbolCelsius}$.

Data acquisition of the strip sensors is performed with the ALiBaVa readout
system [7]. It consists of a Daughterboard on which the strip sensors are
wire-bonded to $128$-channel Beetle Readout chips [8]. In addition, the
ALiBaVa readout system comprises a Motherboard for data acquisition and
processing.

The setup described above allows the study of the strip sensor performance
based on the reference track information provided by the beam telescope. For
track reconstruction and test beam data analysis, the Corryvreckan framework
[9] is used. A dedicated module has been developed to read and visualise data
provided by the ALiBaVa readout system.

The clustering algorithm used in the presented analysis is based on the
Signal-to-Noise Ratio (SNR). It takes a cut on the SNR as an input to define
the threshold for seed strips. Based on this cut value, the sensor hit
detection efficiency is studied as a function of the threshold.

###  3.2 Simulation

Initial sensor simulations were conducted to investigate the strip sensors’
electrical properties. Synopsys Sentaurus Technology Computer-Aided Design
(TCAD) [10] was used to simulate the electrical characteristics of the strip
sensors, including the electric field along the sensor thickness at a bias
voltage of $100\text{\,}\mathrm{V}$ [11]. In order to evaluate the impact of
the electric field on charge carriers generated within the sensor, the
electric field is used as an input to the $\text{Allpix}^{2}$ [12] simulation.

$\text{Allpix}^{2}$ is a modular framework that allows the simulation of the
signal generation within silicon sensors. It enables the study of the charge
carrier propagation for the various strip sensor layouts.

##  4 Results

###  4.1 Total Hit Detection Efficiency

The data acquired in the two test beam campaigns described in section 3 is
used to evaluate the hit detection efficiency of the measured samples.
Additionally, this study investigates whether using the stitching technique
affects hit detection efficiency before and after irradiation. Figure 3 shows
the hit detection efficiency for the Regular design of the unirradiated sample
as a function of the threshold used in the clustering algorithm. The sample is
fully depleted at a bias voltage of $100\text{\,}\mathrm{V}$. The threshold
dependency of the total hit detection efficiency for all three strip sensor
layouts is published in [11]. In Figure 3, the threshold dependency is shown
with the SNR distribution comprised of a Gaussian-distributed noise and the
Landau-shaped signal distribution for the Regular design. There is a high-
efficiency region for small seed cuts. The efficiency drops firmly for medium
seed cuts while gradually lowering to zero for larger seed cuts, which matches
the shape of the SNR distribution. With the seed cut value describing a cut in
the SNR distribution, low seed cuts mainly impact the Gaussian distributed
noise. As the cut value increases, the Landau-shaped signal distribution
begins to be affected. Consequently, reconstructed telescope tracks do not
have associated clusters on the DUT, and the hit detection efficiency
decreases.

Figure 3: SNR distribution of the Regular design (red, solid), combined with
the corresponding hit detection efficiency (blue, crosses) for the
unirradiated short strip sensor. The SNR distribution comprises the Gaussian
noise distribution and the Landau-shaped signal distribution. The Gaussian
noise peak is depicted partially as it is significantly larger than the signal
peak.

###  4.2 In-Strip Hit Detection Efficiency

Visualising the hit detection efficiency within one strip allows the
investigation of any structures along or across the strip, leading to
potential inefficiencies. In order to investigate if the technique of
stitching has any impact on the hit detection efficiency, the in-strip
efficiency is studied for all three designs. The corresponding distribution
for the fully depleted Regular and Low Dose 55 design of the unirradiated
sample is shown in Figure 4, based on the folded statistics of available
strips for the analysis of each design (see [11] for the results concerning
the Low Dose 30 design). Overall, the Regular design is more efficient than
the Low Dose 55 design. The Low Dose 55 design shows a slight decrease in
efficiency across the strip towards the strip edge. Apart from statistical
fluctuations, however, the efficiency is distributed homogeneously along the
strip for both designs. Therefore, the stitching does not impact the
efficiency of the sensor, as the stitching lines highlighted in Figure 2 do
not show in the in-strip efficiency.

Figure 5 shows the in-strip efficiency distribution for the Regular and Low
Dose 55 design of the irradiated sample to evaluate if the same finding holds
after irradiation. The irradiated sample is depleted at
$250\text{\,}\mathrm{V}$. Overall, the efficiency decreases after irradiation
for both designs. In particular, the Regular design shows a substantial
decline in efficiency towards the inter-strip region after irradiation.
However, the in-strip efficiency shows no sign of the stitching lines along
the sensor. In addition, no performance differences regarding the hit
detection efficiency have been observed between long and short strip samples
for the unirradiated and irradiated cases.

(a) Regular

(b) Low Dose 55

Figure 4: In-strip efficiency of the Regular (top) and the Low Dose 55
(bottom) designs of the unirradiated short strip sensor at a threshold of
three. The mean efficiency along the X- and Y-axis is shown. The stitching
line across the sensor is located at Y=0.

(a) Regular

(b) Low Dose 55

Figure 5: In-strip efficiency of the Regular (top) and the Low Dose 55
(bottom) designs of a neutron-irradiated long strip sensor at a threshold of
three. The mean efficiency along the X- and Y-axis is shown. The stitching
line across the sensor is located at Y=0.

###  4.3 Simulation

Initial sensor simulations were performed to understand the performance
characteristics in the three sensor layouts. The electric field simulated with
TCAD is used as an input to the $\text{Allpix}^{2}$ framework. That allows for
visualising the path and collection of the generated charge carriers within
the sensor thickness based on the electric field. Figure 6 shows the
corresponding line graphs for the Regular and Low Dose 55 designs. They are
generated by simulating a Minimum Ionising Particle (MIP) impinging on a strip
from the top and ionising the sensor material while travelling through the
depleted sensor thickness. The blue lines indicate the generated electrons’
drift path towards the collection electrode at the top, located at integer
values in $Y$. It is visible that there is no substantial difference in the
charge carrier propagation between the regular and the Low Dose 55 design.
Both designs show significant charge collection by drift (indicated by
straight lines). However, the Regular design exhibits a stronger drift towards
the collection electrode between the strips than the Low Dose 55 design, due
to a larger electric field magnitude near the collection electrode for the
Regular design. The impact of the different electric field configurations on
the various sensor layouts and their final performance needs further
investigation.

(a) Regular

(b) Low Dose 55

Figure 6: Line graphs visualising the drift path of electrons, created by a
traversing MIP, through the sensor thickness to the collection electrode for
the Regular (top) and the Low Dose 55 (bottom) designs.

##  5 Conclusion

Stitched, passive CMOS strip sensors represent an alternative silicon sensor
concept that can be used for charged particle tracking. Two samples with three
sensor designs have been characterised in a test beam environment. Overall,
the Regular implant design shows the best performance regarding hit detection
efficiency. The efficiency is lower for the Low Dose designs and declines
after neutron-irradiation for all designs. The irradiation of the strip
sensors also causes an efficiency decline in the inter-strip region in the
Regular design.

The stitching technique was used in the sensor production to achieve large
sensor formats for large-area coverage in tracking detectors. The
investigation of the in-strip efficiency has shown that stitching does not
impact the hit detection efficiency. The same holds after sensor irradiation.

Finally, a first simulation of the sensor response was conducted with the
$\text{Allpix}^{2}$ framework. The line graph tool revealed no substantial
differences between the Regular and Low Dose 55 strip implant designs. Further
investigation is required to understand the performance differences between
the sensor layouts.

##  6 Acknowledgements

The measurements leading to these results have been performed at the Test Beam
Facility at DESY Hamburg (Germany), a member of the Helmholtz Association
(HGF).

## References

  * [1] D. Cohen et al., Stitching design rules for forming interconnect layers, US patent 6225013 (1999).
  * [2] LFoundry, LFoundry S.r.l, http://www.lfoundry.com, accessed: 15.01.2024 (2024).
  * [3] L. Diehl, M. Baselga, I. M. Gregor, M. Hauser, T. Hemperek, J. C. Hönig, K. Jakobs, S. Mägdefessel, U. Parzefall, A. Rodriguez, S. Sharma, D. Sperlich, L. Wiik-Fuchs, T. Wang, Characterization of passive CMOS strip sensors, Nucl. Instrum. Methods A 1033 (2022) 166671.  arXiv:2204.00501, doi:10.1016/j.nima.2022.166671.
  * [4] R. Diener, J. Dreyling-Eschweiler, H. Ehrlichmann, I. Gregor, U. Kötz, U. Krämer, N. Meyners, N. Potylitsina-Kube, A. Schütz, P. Schütze, M. Stanitzki, The DESY II test beam facility, Nucl. Instrum. Methods A 922 (2019) 265–286, arXiv:1807.09328.  doi:10.1016/j.nima.2018.11.133.
  * [5] Y. Liu, C. Feng, I.-M. Gregor, A. Herkert, L. Huth, M. Stanitzki, Y. Teng, C. Yang, ADENIUM — A demonstrator for a next-generation beam telescope at DESY, J. Instrum. 18 (06) (2023) P06025, arXiv:2301.05909.  doi:10.1088/1748-0221/18/06/p06025.
  * [6] G. Aglieri Rinella, The ALPIDE pixel sensor chip for the upgrade of the ALICE Inner Tracking System, Nucl. Instrum. Methods A 845 (2017) 583–587, arXiv:2009.10517.  doi:10.1016/j.nima.2016.05.016.
  * [7] R. Marco-Hernández, J. Bernabeu, G. Casse, C. García, A. Greenall, C. Lacasta, M. Lozano, S. Martí i García, R. Martínez, M. Miñano, G. Pellegrini, N. A. Smith, M. Ullán, Alibava : A portable readout system for silicon microstrip sensors (2007).  doi:10.5170/CERN-2007-001.412.
  * [8] M. Agari, N. van Bakel, C. Bauer, D. Baumeister, M. van Beuzekom, M. Feuerstack-Raible, N. Harnew, W. Hofmann, E. Jans, S. Klous, K. Knöpfle, S. Löchner, M. Schmelling, E. Sexauer, N. Smale, U. Trunk, H. Verkooijen, Beetle — A radiation hard readout chip for the LHCb experiment, Nucl. Instrum. Methods A 518 (1) (2004) 468–469.  doi:10.1016/j.nima.2003.11.058.
  * [9] D. Dannheim, K. Dort, L. Huth, D. Hynds, I. Kremastiotis, J. Kröger, M. Munker, F. Pitters, P. Schütze, S. Spannagel, T. Vanat, M. Williams, Corryvreckan: a modular 4D track reconstruction and analysis software for test beam data, J. Instrum. 16 (03) (2021) P03008.  arXiv:2011.12730, doi:10.1088/1748-0221/16/03/p03008.
  * [10] Synopsis TCAD, Inc, Synopsis, Inc., https://www.synopsys.com/manufacturing/tcad.html [accessed: 15.01.2024] (2024).
  * [11] I. Zatocilova, J.-H. Arling, M. Baselga, N. Davis, L. Diehl, J. Dingfelder, I.-M. Gregor, M. Hauser, T. Hemperek, F. Hügging, K. Jakobs, M. Karagounis, R. Koppenhöfer, K. Kröninger, F. Lex, U. Parzefall, A. Rodriguez, B. Sari, N. Sorgenfrei, S. Spannagel, D. Sperlich, T. Wang, J. Weingarten, Characterization, simulation and test beam data analysis of stitched passive CMOS strip sensors, Nucl. Instrum. Methods A (2024) 169132. doi:{10.1016/j.nima.2024.169132}.
  * [12] S. Spannagel, K. Wolters, D. Hynds, N. Alipour Tehrani, M. Benoit, D. Dannheim, N. Gauvin, A. Nürnberg, P. Schütze, M. Vicente, Allpix2: A modular simulation framework for silicon detectors, Nucl. Instrum. Methods A 901 (2018) 164–172.  arXiv:1806.05813, doi:10.1016/j.nima.2018.06.020.


# Contextual Clarity: Generating Sentences with Transformer Models using
Context-Reverso Data

Ruslan Musaev

(May 2023)

###### Abstract

In the age of information abundance, the ability to provide users with
contextually relevant and concise information is crucial. Keyword in Context
(KIC) generation is a task that plays a vital role in and generation
applications, such as search engines, personal assistants, and content
summarization. In this paper, we present a novel approach to generating
unambiguous and brief sentence-contexts for given keywords using the T5
transformer model, leveraging data obtained from the Context-Reverso API. The
code is available at [GitHub].

##  1 Introduction

To create a dataset for training the T5 model, we harness the power of that
provides usage examples for words. We prepared a dataset in the form of (query
word, context or example usage) by parsing Context-Reverso webpages based on a
query word. Additionally, we trained t5-small, and t5-base models for
generating context-sentences based on input words. This resource enables us to
obtain diverse and contextually rich sentences that incorporate the target
keywords. We have also developed an application for learning new English words
with a generated context [Telegram bot]. Our method aims to address the
challenges of generating extremely short contexts and mitigating ambiguity in
sentence construction.

Objective: To develop a model that can generate informative and contextually
relevant sentence-contexts for a given set of keywords, benefiting natural
language understanding and generation applications such as search engines,
personal assistants, and content summarization.

##  2 Related Work

  * •

In recent years, transformer[1]-based models such as GPT[2] model family and
T5[3] have gained significant attention for their capabilities in natural
language understanding and generation tasks. These models have been
successfully employed in various applications, including text summarization,
machine translation, and sentiment analysis.

  * •

The Keyword in Context (KIC) generation task is closely related to abstractive
text summarization, which aims to generate concise and informative summaries
of longer texts. Several studies have explored the application of transformer
models for summarization tasks, demonstrating their effectiveness in
generating high-quality summaries.

  * •

The use of external resources, such as APIs and web-based data, has been
explored in the domain of natural language processing for tasks such as
sentiment analysis and entity recognition. Our work builds upon these efforts
by utilizing the Context-Reverso API as a source of rich and diverse context-
sentences for training our T5 model.

##  3 Model Description

Our approach involves using the pretrained Hugging Face’s T5 transformer model
to generate concise and unambiguous context sentences for given keywords. The
T5 model is a state-of-the-art natural language processing model that has
demonstrated exceptional performance in various tasks, including text
generation, summarization, and translation. For our experiments we consider to
use T5-small, T5-base models. The last one deliver the best perfomance for our
target application - telegram bot for learning new words enriched with usage
example.

We train the T5 model on our custom dataset, which contains pairs of query
words and their context sentences. The model learns to generate context
sentences that incorporate the given keywords in a meaningful and unambiguous
manner. When the model is presented with a query word, it generates a context
sentence that provides a clear and concise usage example for the word.

##  4 Dataset

To construct our dataset, the Context-Reverso API was employed, which provides
usage examples for words. Initially, a set of top $N$ common English words
were selected as target keywords, and the Context-Reverso API was queried to
obtain example sentences including those keywords (top $M$ context sentences).
Subsequently, the retrieved webpages were parsed, and relevant context
sentences were extracted to form pairs of query words and their corresponding
context sentences. Ultimately, two datasets of varying sizes were obtained in
the form (keyword, context), with $N\times M=1K\times 10=10K$ samples and
$N\times M=100K\times 10=1M$ samples.

Our dataset contains diverse and contextually rich sentences that incorporate
the target keywords. This ensures that the model learns to generate context
sentences that are both informative and unambiguous. The dataset is split into
training, validation, and test sets, allowing us to evaluate the performance
of our model and ensure it generalizes well to unseen data.

##  5 Experiments

###  5.1 Metrics

We used two metrics to evaluate our models: BLEU and METEOR. These metrics are
commonly used to assess the quality of generated text by comparing it to a
reference text.

####  5.1.1 BLEU

BLEU (Bilingual Evaluation Understudy) is a metric for evaluating the quality
of machine-generated translations. It measures the overlap of n-grams between
the generated text and the reference text. The BLEU score ranges from 0 to 1,
with 1 being the best score.

Formula:

$BLEU=\min\left(1,\frac{len(prediction)}{len(reference)}\right)\times\exp\left(\sum_{n=1}^{N}w_{n}\log
p_{n}\right)$

where $len(prediction)$ is the length of the predicted text, $len(reference)$
is the length of the reference text, $w_{n}$ is the weight of n-grams, $p_{n}$
is the precision of n-grams, and $N$ is the maximum order of n-grams
considered.

####  5.1.2 METEOR

METEOR (Metric for Evaluation of Translation with Explicit ORdering) is
another evaluation metric for machine-generated translations. It computes the
harmonic mean of unigram precision and recall, with a penalty for word order
differences between the generated and reference texts.

Formula:

$METEOR=(1-P)\times\frac{P_{r}\times P_{p}}{\alpha P_{r}+(1-\alpha)P_{p}}$

where $P$ is the penalty term, $P_{r}$ is the recall, $P_{p}$ is the
precision, and $\alpha$ is a tunable parameter that controls the relative
importance of recall and precision.

###  5.2 Experiment Setup

We fine-tuned pre-trained Hugging Face models, T5-small and T5-base, on two
datasets of varying sizes. Training involved 10 epochs, a 128 batch size, a
5e-5 learning rate, Adam optimizer, and a linear learning rate scheduler with
a 0.1 warmup ratio.

For evaluation, we used a validation set with reference sentences and
keywords, comparing T5-small and T5-base to GPT-2 using BLEU and METEOR
metrics to assess generated sentence quality.

###  5.3 Baselines

GPT-2 served as a baseline for our experiments. Developed by OpenAI, GPT-2 is
a state-of-the-art language model. As an open-source model, GPT-2 is
compatible with our models in terms of parameters.

##  6 Results

The validation results can be found in Tab. 1 and Tab. 2.

###  6.1 Function: generate_sentence

⬇

def generate_sentence(model, tokenizer, prompt):

prompts = [

f"Create a sentence using the word {prompt} that showcases its usage in a
common context.",

f"Write a sentence that uses the word {prompt} in everyday language.",

f"Formulate a sentence with the word {prompt} to demonstrate its typical
usage.",

f"Construct a sentence that includes the word {prompt} in a familiar
context.",

f"Compose a sentence that features the word {prompt} in a general setting.",

]

generated_sentences = []

for prompt in prompts:

inputs = tokenizer.encode(prompt, return_tensors="pt").cuda()

with torch.no_grad():

outputs = model.generate(inputs, max_length=50, num_return_sequences=1)

generated_sentence = tokenizer.decode(outputs[0], skip_special_tokens=True)

generated_sentences.append(generated_sentence)

return generated_sentences

The generate_sentence function generates sentences using a given model,
tokenizer, and keyword (prompt). The list of prompts were generated by GPT-4.
The chosen prompt is then used to create a sentence using the given keyword in
a natural context.

###  6.2 Evaluation

To evaluate the performance of each language model, we followed these steps:

  1. 1.

Generate sentences for each model using the generate_sentence function and a
set of keywords.

  2. 2.

Compare the generated sentences to a set of reference sentences using
evaluation metrics, such as BLEU, and METEOR scores.

  3. 3.

Calculate the average scores for each model across all keywords.

  4. 4.

Compare the models’ average scores to determine their performance.

Model | BLEU | METEOR | Number of Parameters
---|---|---|---
T5-small | 0.0213 | 0.1047 | 60 million
T5-base | 0.0226 | 0.1069 | 220 million
GPT-2 | 0.0065 | 0.1050 | 117 million
Table 1: 1M train samples. Performance comparison and number of parameters for T5-small, T5-base, and GPT-2 models. Model | BLEU | METEOR | Number of Parameters
---|---|---|---
T5-small | 0.0185 | 0.0935 | 60 million
T5-base | 0.0220 | 0.1052 | 220 million
Table 2: 10k train samples. Performance comparison and number of parameters
for T5-small, T5-base

In an evaluation of three models, T5-small, T5-base, and GPT-2, we compared
their performance using the BLEU and METEOR metrics, as well as the number of
parameters involved. Table 2 shows the comparison for 10k samples, revealing
that the T5-base model performed better in terms of both BLEU and METEOR
scores. For 1M samples, as shown in Table 1, the T5-base model still
outperformed the other models in terms of BLEU and METEOR scores. It is worth
noting that the T5-small model had fewer parameters than both the T5-base and
GPT-2 models.

Based on the results of our experiments, we have chosen the T5-base model as
the best performing model to serve in our Telegram bot, which you can find at
[Telegram bot].

##  7 Conclusion

In this study, we collected a dataset, annotated it, and developed a model
that showed the best results compared to other models. Based on our
evaluation, we found that the T5-base model performed better than T5-small and
GPT-2 models, achieving higher BLEU and METEOR scores.

The developed model can be used to generate sentences based on a given input
keyword, which can be helpful in various natural language processing tasks.
Future work could involve incorporating additional datasets and experimenting
with various model architectures to further improve performance.

## References

  * [1] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, Ł. Kaiser, and I. Polosukhin, ‘‘Attention is all you need,’’ _Advances in neural information processing systems_ , vol. 30, pp. 5998–6008, 2017.
  * [2] A. Radford, J. Wu, R. Child, D. Luan, D. Amodei, and I. Sutskever, ‘‘Language models are unsupervised multitask learners,’’ _OpenAI Blog_ , vol. 1, no. 8, p. 9, 2019.
  * [3] C. Raffel, N. Shazeer, A. Roberts, K. Lee, S. Narang, M. Matena, Y. Zhou, W. Li, and P. J. Liu, ‘‘Exploring the limits of transfer learning with a unified text-to-text transformer,’’ _Journal of Machine Learning Research_ , vol. 21, no. 140, pp. 1–67, 2020.