Large Deviations Theory of Increasing Returns

It is known that certain economic markets - especially the technological ones - show increasing returns Arthur nature ; Arthur book ; Arthur , a positive feedback phenomenon where if a company gains some initial advantage (even small) is more likely to get even more in the future, eventually dominating the market share in the long run - this phase is also called lock-in into a monopolistic state. To understand the origin of this effect, a simplified market model has been introduced in the ’80s by the economist W. B. Arthur UM Arthur in the framework of its Increasing Returns theory (IRT) Arthur book ; Arthur . Let consider two competing companies that launch a new kind of product roughly at the same time (as practical example we could think about two smart phones in the early 2000s). Suppose that these products are roughly equivalent, such that there is no practical reason for choosing one over the other, we can imagine that a buyer will base his decision in part on personal opinions (personal tastes, ideologies, advertising, etc.) and in part on those of other people that already purchased one of the products. Then, let us consider a simplified situation in which the new customers are imperfectly informed about the products, so that they will make their choices by looking at the number of adopters who are already using it Arthur ; UM Arthur ; Dosi Ermoliev ; Dosi last . An alternative hypothesis that gives the same effect is to consider positive (or negative) externalities in adoption Dosi Ermoliev ; Dosi last . In both cases, we consider the additional rule that any new adopter will choose the technology used by the majority of the sample only with a certain probability, and the other technology otherwise Dosi Ermoliev ; Dosi last .

This scenario has been considered by G. Dosi, Y. Ermoliev and Y. Kaniovsky (DEK, 1994) Dosi Ermoliev , the proposed model is as follows: consider a binary vector that represents the individual choices of the customers,

$$X_{N}:=\{X_{N,1},\,X_{N,2},\,...\,,X_{N,N}\},$$

(1)

with $X_{N,n}\in\{0,1\}$ and $N$ potential size of the market. This vector represents the full history of the market evolution, from the first sell to full saturation, when the maximal number of customers is reached. The variable $X_{N,n}$ represents the choice of the $n-$th customer, we arbitrarily associate the value one to the first product and zero to the second. The total number of customers of the first product will therefore be

$$\Gamma_{N,n}:=\sum_{m\leq n}X_{N,m}$$

(2)

the market share of the first product up to the $n-$th customer is represented by the variable

$$x_{N,n}:=\frac{\Gamma_{N,n}}{n}=\frac{1}{n}\sum_{m\leq n}X_{N,m}.$$

(3)

Then, the choice of the next customer $X_{N,n+1}$ is determined by the following rule: first, sample $k$ previous customers, where $k$ is an odd integer (this to avoid inconclusive outputs from the poll). Then, if the sample is found to have more customers that bought the first product, the variable $X_{N,n+1}$ will be equal to one with a probability $p$, and will be zero otherwise. On the other hand, if more customers owning the second product are found in the sample, $X_{N,n+1}$ will be zero with probability $p$, and one otherwise. Notice that the new customers follow the majority of the polled sample with probability $p$, that in some sense quantifies the trust of the newcomers in the behavior of their predecessors: hereafter we will call $p$ trust parameter, although it may also reflect more practical constraints, such as a requirement for compatibility with the technology adopted by the polled customers. For $p=1$ the DEK model describes a market where the customers always buy the product owned by the majority of the sample, i.e., the original version introduced by Arthur et al. (1983) and Arthur (1989) UM Arthur ; Arthur : some sample trajectories of this process for $p=1$ and $k=3$ are in Figure 2a of G. Dosi et al. (2017) Dosi last . Concerning the initial conditions, we will distinguish of two kinds: we introduce $\tau\in\left[0,1\right]$ the fraction of customers that made their choices already (market saturation parameter): in this paper we will consider an early start in the market at some fixed number of customers $M<\infty$, also called virgin market condition, that in the limit of infinite customers is equivalent to a debut in the market approximately at $\tau=0$ (and does not affect the LDT theory for $N\rightarrow\infty$) and a late start $M=\tau N$ (a product that enters in the market when the saturation is already macroscopic), that strongly influences the distribution of the final share also at the LDT level.

In this paper we develop a Large Deviations theory (LDT) for the DEK model for any $p$ and $k$ by adapting results from the Hill Lane and Sudderth (HLS) urn model HLS1 ; HLS2 , a very general model for which a mathematically rigorous LDT has been recently developed Franchini , and that includes the DEK model as special case. An HLS urn process Pemantle review ; Mahmoud ; HLS1 ; HLS2 ; Pemantle Touch ; Franchini is a two color urn process controlled by a functional parameter $\pi\left(x\right)$ that we call urn function (actually adoption function in Ref. Arthur ), where the new step $X_{N,n+1}$ is one with probability $\pi\left(x_{N,n}\right)$ and zero otherwise. The relation between IRT and HLS urns is well known since the very beginning, in fact, this model has been introduced independently by HLS (1980) and then also by Arthur et al. (1983) within just three years. The urn function that describes the DEK model can be determined as follows: start with $k=1$, the probability of extracting an owner of the first product is $x$, then their total number will increase with probability

$$\pi_{1}\left(x\right):=p\,x+\left(1-p\right)\left(1-x\right)=\left(1-p\right)+\left(2p-1\right)x,$$

(4)

that is a linear urn function. In case $k=3$: the probability of increasing the owners of the first product is that of extracting two positive and one negative, plus that of extracting three positive, that is Dosi Ermoliev

$$P_{3}\left(x\right):=x^{3}+3x^{2}\left(1-x\right)=3x^{2}-2x^{3},$$

(5)

then, the corresponding urn function is Dosi Ermoliev

$$\pi_{3}\left(x\right):=p\,\left(3x^{2}-2x^{3}\right)+\left(1-p\right)\left(1-\left(3x^{2}-2x^{3}\right)\right)=\left(1-p\right)+\left(2p-1\right)\left(3x^{2}-2x^{3}\right)$$

(6)

and cannot be reduced to the linear case $k=1$. In general, the probability of finding a positive majority when extracting an odd number $k$ of steps is Dosi Ermoliev

$$P_{k}\left(x\right):=\sum_{h>k/2}\frac{k!}{h!\left(k-h\right)!}\,x^{h}\left(1-x\right)^{k-h}$$

(7)

where the $h$ sum runs from $\left(k+1\right)/2$ to $k$. Follows that the urn function that describes a DEK model with $k>2$ extractions per step is Dosi Ermoliev

$$\pi_{k}\left(x\right):=p\,P_{k}\left(x\right)+\left(1-p\right)\left(1-P_{k}\left(x\right)\right)=\left(1-p\right)+\left(2p-1\right)P_{k}\left(x\right),$$

(8)

this is a $k-$th degree polynomial, and is therefore non-linear for all non-trivial values of the trust parameter $p$.

In case of a virgin market start, the convergence properties of the HLS urns with any continuous urn functions have been studied in HLS1 ; HLS2 ; UM Arthur ; Arthur ; Dosi Ermoliev ; Pemantle Touch ; Franchini , finding that the points of convergence of $x_{N,N}$ always belong to the set of solutions of

$$\pi\left(x\right)=x,$$

(9)

and that these solutions are stable only if the derivative of the urn function in those points is smaller than one, i.e., if the $\pi\left(x\right)$ crosses $x$ from top to bottom (down-crossing). For the DEK model with $k=1$, the urn function $\pi_{1}\left(x\right)$ crosses $x$ at $1/2$ for any value of $p<1$, and therefore $1/2$ is the only possible point of convergence for the associated share $x_{N,N}$, see Figure 1. This imply that $x_{N,N}$ converges to $1/2$ almost surely

$$\lim_{N\rightarrow\infty}x_{N,N}=1/2,\ a.s.$$

(10)

for all values of $p<1$ and of the initial condition $x_{N,M}$ a phase diagram for the DEK $k=1$ is shown in Figure 3. This model does not show the lock-in phenomenon, although there is still a value of $p$ where the dynamics is expected to slow down (see Section VIII).

In the DEK with $k>2$ one can see the appearance of the lock-in phase above some critical $p_{c}$. For $k=3$ the Eq. (9) is a third degree equation, and can be solved with the well known formula. In general, we find tree solutions Dosi Ermoliev : $x_{0}=1/2$ and

$$2x_{\pm}=1\pm\sqrt{\frac{6p-5}{2p-1}},$$

(11)

the quantity inside the square root is positive for $p\leq 1/2$ and $p\geq 5/6$, but notice that $x_{\pm}\in\left[0,1\right]$ only if $p\in\left[1/2,1\right]$, then, for $p$ below the critical value $p_{c}=5/6$ there is again a unique stable solution at $1/2$ that crosses $x$ from top to bottom (down crossing), see Figure 2. Above $p_{c}$ the function $\pi$ still crosses $x$ at the point $1/2$, but it now does from bottom to top, i.e. it is an up-crossing and is therefore not stable. Notice that for $p>p_{c}$ two new solutions $x_{+}$ and $x_{-}$ appear, those are both down-crossings, and can be stable attractors for $x_{N,N}$. Therefore, for $p$ above $p_{c}$ there are two attractors separated by an unstable equilibrium point at $x_{0}=1/2$ Dosi Ermoliev . Notice that in the limit of infinite $k$ the probability of finding a majority of first product owners within the sample converges to

$$P_{\infty}\left(x\right):=\theta\left(1-2x\right)$$

(12)

ie, the urn function $\pi_{k}$ converges to a step function

$$\pi_{\infty}\left(x\right):=\left(1-p\right)+\left(2p-1\right)\theta\left(1-2x\right)$$

(13)

that still crosses the diagonal at the point $x_{0}=1/2$ (from top to bottom) for $p<p_{c}=1/2$, and at $x_{-}=p$, $x_{+}=1-p$ if the trust parameter is above $p_{c}$. Then also in the infinite $k$ limit there is a $p_{c}$ above which we find the same region of the phase diagram that is observed for $k=3$. In fact, the phase diagram shows the same structure for all $k>2$, apart from different $p_{c}$ and $x_{\pm}$. For this reason, we will concentrate our analysis to the cases $k=1$ and $k=3$.

Summarizing, under virgin market condition the limit value of $x_{N,N}$ for $p>p_{c}$ converges to the points $x_{-}$ and $x_{+}$ almost surely for any initial condition $x_{N,M}$ with $M<\infty$ (the phases for $k=3$ are shown in the Figure 4) but since the urn functions that we are considering never touches zero or one at any $x\in\left(0,1\right)$, for any initial condition $x_{N,M}$ that is fixed at $M\ll N$ there is a strictly positive probability to reach the nearby of any other $x$ by gaining a finite number of customers at the beginning of the process, then in the limit $N\rightarrow\infty$ both points $x_{\pm}$ carry some non-zero probability mass for any early start. Anyway, it can be shown that the probability mass of that point farther from $x_{N,M}$ will be exponentially suppressed as $M$ grows. Fixing the initial condition at some $M=o\left(N\right)$ but still divergent in $N$ will suppress one of the two possibilities, and concentrate the probability mass in the attraction point $x_{\pm}$ that is closest to the initial share $x_{N,M}$. Concerning the case of late market entry at some $M=\tau_{0}N$, we discuss it in Section V, after introducing the optimal trajectories.

We remark that, apart from economic models, the theory of the HLS urns allows to put IRT in relation with many others interesting situations that can be embedded (or approximated) by this very general urn model: there is a number of computer science problems on preferential attachment, network growth etc. Pemantle review ; Mahmoud that can be studied in this framework. Here we list three that, in our opinion, are of special physical interest. Transfer of knowledge between these field would be certainly fruitful, and should be encouraged.

For example, the case $k=1$ of the DEK is fully equivalent to another well known stochastic model, the Elephant Random Walk (ERW), a simple random walk where each new step is determined by selecting one of the previous, then going in the same direction with probability $p$. This model appears to have been re-descovered independently by G. Schütz and S. Trimper in 2004 ERW shcutz trimper , ten years after the introduction of the DEK model, and has received much attention since then as a paradigmatic example of processes with long range memory. An important advancement in the understanding of this model was made in 2016, when E. Baur and J. Bertoin observed ERW UM Baur Berton that the ERW could be mapped exactly into a two color urn of the Friedman’s type (that is in fact equivalent to a linear HLS urn Pemantle review ; Mahmoud ; Franchini ) where at each time one ball is drawn from the urn, and then replaced together with a fixed numbers of new balls whose color depend on which was drawn. This finding allowed many quantities of interest to be studied from known results on these types of models, ERW UM Baur Berton ; Jack Harris however, this analogy cannot be extended to the $k>2$ case.

Also, Jack Jack LD has identified the urn function describing an interesting irreversible growth model introduced by Klymko, Garrahan and Whitelam KGW ; KGGW , and also this model exhibits a lock-in phase with a sub-linear entropy region, that is similar to the $k>2$ case of the DEK model Jack LD . In this perspective, it would be quite interesting to investigate also the universal HLS scaling for symmetric urn functions recently proposed by Nakayama et al. (2021) Kazuaki . Notice that in Jack (2019) Jack LD a non-rigorous but powerful LDT is presented for a large class of models, whose predictive power should be comparable to the rigorous LD techniques used in Franchini (2017), see also the interesting review Jack 2020 Jack LD-1 .

Finally, the HLS framework allows to relate the DEK model with the very classic Random Walk Range problem Huges ; Franchini Range ; Franchini Range Urns ; Franchini Range Line , that studies the number of different sites visited by a random walk on the lattice $\mathbb{Z}^{d}$. This problem is important to polymer physics as it exhibits a coil-globule transition at some critical range density, and is in the same universality class of the Self-Avoiding Walk above that value Franchini Range . In Ref. Franchini Range Urns is shown that the Range problem can be exactly embedded in the HLS model for some non-linear urn function at any $d$. For $d=2,3$ a strongly non-linear urn function is observed (by numerical analysis), but for $d\geq 4$ the urn function gets surprisingly close to some linear function in the self-avoiding walk-like region of large range values, that would then be related to the DEK model with $k=1$. This model also shows a sub-linear entropy region below some critical range, as can be deduced also from a very detailed analysis of the “moderate deviations” of the Wiener Sausage in the collapsed phase by M. van den Berg, E. Bolthausen, F. Den Hollander (2001) van den Berg . Interestingly, they find cases of non-homogeneous optimal trajectories with sub-linear entropy cost: we conjecture that in this collapsed region the range undergoes a mechanism similar to that observed in the lock-in phase (actually, the non-homogeneous zero-cost trajectories that are described in Corollary 7 of Ref. Franchini ).

We perform a Large Deviations analysis for the HLS model at the sample-path level, and adapt it to find the most probable trajectories taken by the DEK model. Let $\tau\in\left[0,1\right]$ be the level of market saturation (or the fraction of customers that already made their choice): the optimal trajectories, that we indicate with the symbol $u$, are the scaling limit for $n/N\rightarrow\tau$ of the most likely trajectories followed by the share variable $x_{N,n}$ of the first product to reach some given final share $x$. These can be obtained by solving the variational problem that is presentend in Section VI (see also Theorem 4 of Ref. Franchini for a full mathematical derivation). Most interesting, we will show that for any initial condition with positive saturation $\tau_{0}>0$ the scaling limit of the trajectory taken by the share variable

$$\lim_{N\rightarrow\infty}x_{N,\left\lfloor\tau N\right\rfloor}=:u\left(\tau\right)$$

(14)

is non-degenerate for any starting share $u_{0}\in\left[0,1\right]$, and can be found by inverting the following integral:

$$\tau\left(u\right)=\tau_{0}\,\exp\int_{u_{0}}^{u}\frac{d\alpha}{\pi\left(\alpha\right)-\alpha}.$$

(15)

A crucial quantity of our analysis will be the scaling limit of the entropy (logarithm of the probability) of $x_{N,N}$ converging to some given $x$. Define the asymptotic limit of the entropy per customer (hereafter we will call it entropy density)

$$\phi\left(x\right):=-\lim_{N\rightarrow\infty}\frac{1}{N}\log P\left(x_{N,N}=\left\lfloor xN\right\rfloor/N\right),$$

(16)

informally, this is the scaling limit of the entropy respect to the total number of customers, i.e. for a large number of customers the probability of reaching a share $x$ is proportional to

$$P\left(x_{N,N}=\left\lfloor xN\right\rfloor/N\right)\sim\exp\left(-N\phi\left(x\right)\right).$$

(17)

In the Section VI we will show that the shape of the limit entropy density $\phi$ can be linked to the trajectories taken by the number of customers of the first product $\Gamma_{N,n}$ to reach its final value $\Gamma_{N,N}=\left\lfloor xN\right\rfloor$. These trajectories, that we indicate with the symbol $\varphi$, are the scaling limit $n/N\rightarrow\tau$ for the number of customers of the first product, rescaled with the total number of customers $N$,

$$\lim_{N\rightarrow\infty}\Gamma_{N,\left\lfloor\tau N\right\rfloor}/N=:\varphi\left(\tau\right)$$

(18)

this is related to the scaling limit of the share by the formula

$$u\left(\tau\right)=\varphi\left(\tau\right)/\tau.$$

(19)

In Theorem 4 of Ref. Franchini (see Section VI of the present paper for an informal derivation) it is shown that the limit entropy density of any HLS urn model with $\alpha-$Hölder urn function $\pi$ is obtained trough the following LD principle: let $C_{1}\left(\left[0,1\right]\right)$ be the set of absolutely continuous function on $\left[0,1\right]$ (essentially, such that the derivative exists almost everywhere) and let $Q\subset C_{1}\left(\left[0,1\right]\right)$ the subset of those functions with initial value zero, and such that their derivative is positive but smaller than one ($1-$Lipschitz function),

$$Q:=\{\varphi\in C_{1}\left(\left[0,1\right]\right):\,\partial_{\tau}\varphi\left(\tau\right)\in\left[0,1\right],\,\varphi\left(0\right)=0\},$$

(20)

also, let $Q\left(x\right)$ be the subset with final value $x$,

$$Q\left(x\right):=\{\varphi\in Q:\,\varphi\left(1\right)=x\}.$$

(21)

Also, define the auxiliary function

$$L\left(\alpha,\beta\right):=\alpha\log\left(\beta/\alpha\right)+\left(1-\alpha\right)\log\left(\left(1-\beta\right)/\left(1-\alpha\right)\right),$$

(22)

then, the entropy density $\phi\left(x\right)$ can be computed by solving the following variational problem:

$$\phi\left(x\right)=\inf_{\varphi\in Q\left(x\right)}I\left(\varphi\right),$$

(23)

with rate function defined as follows:

$$I\left(\varphi\right):=-\int_{0}^{1}d\tau\,L\left(\partial_{\tau}\varphi\left(\tau\right),\pi\left(\varphi\left(\tau\right)/\tau\right)\right).$$

(24)

From this general result we where able to deduce a method to identify those trajectories followed by the process $x_{N,n}$ that have a sub-linear entropy cost, i.e., such that the entropy cost of following the trajectory $u\left(\tau\right)$ is of the order $o\left(N\right)$: it implies that the probability of following such a trajectory decays sub-exponentially in the number of customers (actually as a power law, see in Section VII), and not exponentially fast as for those with a cost linear in $N$. Hereafter we will improperly call these the zero-cost trajectories, although their absolute entropy cost is not exactly zero. It is shown that these zero-cost trajectories can be deduced from the variational problem in Eq. (23), with the additional constraint that the Lagrangian of the Eq. (24) is exactly zero. In Corollary 6 of the Ref. Franchini explicit formulas are derived for those optimal trajectories ending in the region where $\phi\left(x\right)=0$. Since for the HLS model the function $L$ is a negative concave function, the condition $I\left(\varphi\right)=0$ implies that the trajectory $\varphi$ satisfies the equation

$$L(\partial_{\tau}\varphi\left(\tau\right),\pi\left(\varphi\left(\tau\right)/\tau\right))=0,$$

(25)

if this condition can be explicited in the variable $\partial_{\tau}\varphi\left(\tau\right)$, then it provides the differential equation for the zero-cost trajectories. Remarkably, since $L(\alpha,\beta)=0$ if and only if $\alpha=\beta$, then the condition before reduces to the autonomous equation

$$\partial_{\tau}\varphi\left(\tau\right)=\pi\left(\varphi\left(\tau\right)/\tau\right),$$

(26)

with final condition $\varphi\left(1\right)=x$. Applying the substitution in Eq. (19) we obtain the equation for the scaling of the share,

$$\frac{\partial_{\tau}u\left(\tau\right)}{\pi\left(u\left(\tau\right)\right)-u\left(\tau\right)}=\frac{1}{\tau}$$

(27)

with final condition $u\left(1\right)=x$. This equation can be integrated exactly, in the end one finds that the trajectories $u\left(\tau\right)$ can be computed in implicit form: the result is a simple formula,

$$\Pi\left(u\right)-\Pi\left(x\right)=\log\tau\left(u\right),$$

(28)

where $\Pi$ is the primitive function (indefinite integral) of the reciprocal of $\pi\left(\alpha\right)-\alpha$, that is

$$\Pi\left(\alpha\right):=\int\frac{d\alpha}{\pi\left(\alpha\right)-\alpha}.$$

(29)

We can formally invert the formula of $\tau\left(u\right)$ before, and write the equation for the zero-cost trajectories as follows: let $\Pi^{-1}$ the inverse function of $\Pi$, then

$$u\left(\tau\right)=\Pi^{-1}\left(\Pi\left(x\right)+\log\tau\right).$$

(30)

The first important remark about this formula is that it allows to extend the convergence theory of HLS urns also in case of a late start in the market: let $\tau_{0}$ be the level of market saturation, and let $u_{0}$ be the initial share (for a firm entering in the market at $\tau_{0}$ we would have $u_{0}=0$), then, it can be shown by inverting Eq. (30) that for any positive $\tau_{0}$ there is a unique point

$$\lim_{N\rightarrow\infty}x_{N,N}=x\left(u_{0},\tau_{0}\right)\ \ a.s.$$

(31)

where the final share $x_{N,N}$ converges almost surely,

$$x\left(u_{0},\tau_{0}\right):=\Pi^{-1}\left(\Pi\left(u_{0}\right)-\log\left(\tau_{0}\right)\right),$$

(32)

it can be shown that the convergence points found before for the virgin market case are recovered in the limit $\tau_{0}\rightarrow 0$.

In general, these results about the optimal trajectories could be useful to confront with (and then eventually fit) trajectories followed by real datasets in those cases where both the time series of the share and the saturation are known for the considered market Dosi last . In this respect, it is important to realize that the market saturation is not a time variable: the process describes the competition between firms, but does not need to specify the underlying market grow. Let $n\left(t\right)$ be the total number of customers up to time $t$, growing according to some law in such way that the limit market size is finite and equal to $N$. Then, the share of the first product up to time $t$ would be $x\left(t\right)=x_{N,n\left(t\right)}$, that can be confronted with the predicted scaling limit

$$\lim_{N\rightarrow\infty}x\left(t\left(\tau\right)\right)=u\left(\tau\right).$$

(33)

by plotting $x\left(t\right)$ in function of the saturation $\tau\left(t\right)=n\left(t\right)/N$. We also remark that the Eq. (28) holds for any $\alpha-$Hölder urn function at least, and can be applied out of the box to more advanced IR models that can still be embedded in the HLS urn model, like those considered in Dosi Ermoliev ; Dosi Kaniovsky . For example, we could have considered a market model where multiple products are present, as far as we follow the market share of only one of them (say the first one). If the customers follow the majority of the polled sample with a probability $p$, and buy at random one of the $r>0$ available products with probability $1-p$, the probability that the product is purchased would have been

$$\pi_{k}^{*}\left(x\right):=p\,P_{k}\left(x\right)+\left(1-p\right)/r,$$

(34)

although there are differences in the convergence properties (for example this new function is not symmetric around $1/2$ and the autocorrelation scaling of Ref. Kazuaki may not hold) it is still possible to repeat the same LD analysis, and find a similar phase structure - this model will be discussed in detail elsewhere. Moreover, the LDT techniques shown in Sections VI and IV goes beyond the HLS model, and could be adapted to find trajectories of processes that are not directly embedded in the HLS model, such as the one presented in the Ref. Dosi last , where also the possibility of losing customers is considered. It should be also possible to extend the LDT to time-dependent urn functions that varies on a time scale $O\left(N\right)$, maybe by considering a partition of the range of $\tau$ into small subintervals where the urn function can be approximated as a constant and then apply the equations given before. We expect that even some quenched disordered versions of these models may be studied, either by combining with the Replica Symmetry Breaking theory PMV RSB or the kernel methods of Ref. KERNEL THEO .

We explicitly write trajectories in closed form for the cases $k=1$ and $k=3$, distinguishing between those trajectories for which $u\left(0\right)\in\left[0,1\right]$, the only possible for a virgin market start, from those crossing the boundary values at some positive saturation (ie, $u\left(\tau\right)\in\left\{0,1\right\}$ for some $\tau>0$), that can have zero cost only in the $\tau_{0}>0$ case. For the DEK model with $k=1$ we can evaluate the integral that defines $\Pi_{1}$:

$$\int_{u}^{y}\frac{d\alpha}{\pi_{1}\left(\alpha\right)-\alpha}=\frac{1}{1-p}\int_{u}^{x}\frac{d\alpha}{1-2\alpha}=\frac{1}{2\left(1-p\right)}\log\left(\frac{u-x_{0}}{x-x_{0}}\right),$$

(35)

this formula can be easily inverted, then from Eq. (30) we find the equation for the trajectories

$$u\left(\tau\right)=x_{0}+\left(x-x_{0}\right)/\tau^{\,2\left(1-p\right)},$$

(36)

for $x\neq x_{0}$ these trajectories diverge for any $p>0$ when $\tau\rightarrow 0$, while for $x=x_{0}$ a unique non-divergent trajectory exists for all $p$, and is $u\left(\tau\right)=x_{0}$. Notice that in the limit of perfect trust $p=1$, that is equivalent to the classic Polya Urn Model, each $u\left(\tau\right)=x$ becomes a non divergent zero-cost trajectory for any share value $x$. For both late and early starts, we find that the share $x_{N,n}$ always follows a single zero-cost trajectory, that is therefore optimal. For a virgin market, this trajectory is $u\left(\tau\right)=x_{0}$ and is independent from the initial share, for late start we find the general convergence point

$$x\left(u_{0},\tau_{0}\right)=x_{0}+\left(u_{0}-x_{0}\right)\tau_{0}^{\,2\left(1-p\right)}.$$

(37)

This implies that for any initial condition, either early or late, the entropy density of the DEK model with $k=1$ is zero only at the critical value $x_{0}=1/2$ (and strictly negative otherwise) for $p<1$, while for $p=1$ the entropy density is $\phi\left(x\right)=0$ at any point $x\in\left[0,1\right]$, as is expected for the Polya Model Mahmoud .

Most interesting to the IRT is the case $k=3$ with $p>p_{c}$, where the lock-in phenomenon is possible: the general picture below $p_{c}=5/6$ is qualitatively the same that is found in the $k=1$ case, but above $p_{c}$ and for virgin market start we observe a whole region $[x_{-},x_{+}]$ where the trajectories have sub linear entropy cost, although only $u\left(\tau\right)=x_{\pm}$ are really optimal. Let compute the trajectories for $k=3$: also in this case the integral can be evaluated exactly, define the parameters

$$\Delta:=6p-5,\ \ \Lambda^{2}:=\frac{\Delta}{4\left(2p-1\right)},$$

(38)

the integral for $\Pi_{3}$ can be found via computer algebra,

$$\int_{u}^{x}\frac{d\alpha}{\pi_{3}\left(\alpha\right)-\alpha}=\frac{1}{\Delta}\log\left(\frac{1-\Lambda^{2}/\left(u-x_{0}\right)^{2}}{1-\Lambda^{2}/\left(x-x_{0}\right)^{2}}\right),$$

(39)

let introduce the $x-$dependent coefficient

$$\rho\left(x\right):=\Lambda^{2}/\left(x-x_{0}\right)^{2}-1,$$

(40)

we can invert the Eq. (39), and compute the equation for the zero-cost trajectories also in the case $k=3$

$$u\left(\tau\right)=x_{0}\pm\sqrt{\frac{\Lambda^{2}}{1+\rho\left(x\right)/\tau^{\,\Delta}}},$$

(41)

where the plus and minus depends on weather the parameter $x$ lies above or below $x_{0}=1/2$. Also in this case, for $x=x_{0}$ there is a zero-cost trajectory for any $p$, in fact, for this value $\rho$ diverges, and the trajectory is $u\left(\tau\right)=1/2$. For $x\neq x_{0}$ we have to look weather the sign of $\Lambda^{2}$ is positive or not, and we can see from Eq. (38) that when $p>p_{c}=5/6$ both $\Delta$ and $\Lambda^{2}$ are indeed positive quantities. This implies that $\tau^{\Delta}$ converges to zero when also $\tau$ does, then the $u\left(\tau\right)-x_{0}$ converges to zero at the admissible point $u\left(0\right)=1/2$. Finally, notice that $\rho\left(x\right)$ also must be positive, otherwise the formula inside the radical would become negative for some $\tau>0$: then, any admissible trajectory requires the further condition $x-x_{0}\in\left[-\Lambda,\,\Lambda\right],$ by confronting Eq. (38) with Eq. (11) we can readily see that, as expected, $\Lambda$ is equal to half distance between the convergence points $\left|x_{\pm}-x_{0}\right|$. Then, the condition reduces to $x\in\left[x_{-},x_{+}\right]$, implying that a non divergent zero-cost trajectory exists for any $x$ lying between the convergence points. On the other hand, in the case of a late start with an initial share $u\left(\tau_{0}\right)=u_{0}$ at some initial saturation $\tau_{0}>0$ there is always a unique zero-cost trajectory emanating from $u_{0}$ and ending in

$$x\left(u_{0},\tau_{0}\right)=x_{0}\pm\sqrt{\frac{\Lambda^{2}}{1+\rho\left(u_{0}\right)\tau_{0}^{\,\Delta}}},$$

(42)

that is also optimal. In Figures (5) and (6) a simulation of the DEK model in the lock-in phase is shown for different initial conditions, and confronted with its predicted trajectory. See also Figure 1 and 2a of G. Dosi et al. (2019) Dosi last with the Figure 2.1 of Franchini (2017) Franchini for the zero-cost trajectories of the seminal model with $p=1$ by Arthur et al. with virgin market initial conditions.

The variational problem shown in Eq. (23) is deduced from two central results of LDT, the Varadhan Integral Lemma and the Mogulskii theorem (see the recent paper by Touchette Touchette for an introductory presentation, Pham for some applications to economy, or the very detailed book by A. Dembo and O. Zeitouni Dembo Zeitouni for a mathematical review). Now, instead of considering the event $x_{N,N}=\left\lfloor xN\right\rfloor/N$, let first study the simpler situation

$$\Omega:=\{X_{N}\in\left\{0,1\right\}^{N}:\,x_{N,N}\in\left[\alpha,\beta\right]\},$$

(43)

where the sample paths end in the interval $\left[\alpha,\beta\right]$ that contains $x$. The limit entropy density of such event is

$$\phi\left(\alpha,\beta\right):=-\lim_{N\rightarrow\infty}\frac{1}{N}\log P\left(X\in\Omega\right).$$

(44)

The starting point is the formula for the probability mass of a sample trajectory. Let

$$Y_{N}=\{Y_{N,1},\,Y_{N,2},\,...\,,\,Y_{N,N}\}$$

(45)

with $Y_{N,n}\in\{0,1\}$ be a possible path, hereafter sample path, of the process $X_{N}$, then, its probability mass $P\left(X_{N}=Y_{N}\right)$ according to the measure $P$ is given by the formula

$$P\left(X_{N}=Y_{N}\right)=\prod_{n\leq N}\pi\left({\textstyle y_{N,n}}\right)^{Y_{N,n}}\left(1-\pi\left(y_{N,n}\right)\right)^{1-Y_{N,n}}.$$

(46)

From here we define the entropy density of the path:

$$S^{*}\left(Y_{N}\right):=-\frac{1}{N}\log P\left(X_{N}=Y_{N}\right),$$

(47)

introducing the auxiliary function

$$H\left(\alpha,\beta\right):=\alpha\log\beta+\left(1-\alpha\right)\log\left(1-\beta\right)$$

(48)

the entropy density before can be rewritten as

$$S^{*}\left(Y_{N}\right)=-\frac{1}{N}\sum_{n\leq N}H\left(Y_{N,n},\pi\left({\textstyle y_{N,n}}\right)\right).$$

(49)

It will be useful to introduce a notation for the average respect to the measure $P$

$$Ef\left(X_{N}\right):=\sum_{Y_{N}\in\left\{0,1\right\}^{N}}P\left(X_{N}=Y_{N}\right)f\left(Y_{N}\right),$$

(50)

in this notation the probability mass of the event $\Omega$ is

$$P\left(X_{N}\in\Omega\right)=EI\left(X_{N}\in\Omega\right)$$

(51)

We perform a change of measure

$$P\left(X_{N}\in\Omega\right)=\sum_{Y_{N}\in\Omega}P\left(X_{N}=Y_{N}\right)=\sum_{Y_{N}\in\left\{0,1\right\}^{N}}P\left(X_{N}=Y_{N}\right)I\left(Y_{N}\in\Omega\right)=\sum_{Y_{N}\in\left\{0,1\right\}^{N}}e^{-NS^{*}\left(Y_{N}\right)}I\left(Y_{N}\in\Omega\right).$$

(52)

such that the probability of $\Omega$ can be represented as follows:

$$P\left(X_{N}\in\Omega\right)=2^{N}E_{0}\,e^{-NS^{*}\left(Y_{N}\right)}I\left(Y_{N}\in\Omega\right),$$

(53)

where $E_{0}$ is the average according to the uniform measure

$$E_{0}f\left(X_{N}\right):=\frac{1}{2^{N}}\sum_{X_{N}\in\left\{0,1\right\}^{N}}f\left(X_{N}\right)$$

(54)

ie, the measure of a binary random walk.

The next step is to construct a continuous interpolation for the path $Y_{N}$, we introduce the function

$$\varphi:=\{\,\left(\left\lfloor\tau N\right\rfloor/N\right)\,y_{N,\left\lfloor\tau N\right\rfloor}+(\tau-\left\lfloor\tau N\right\rfloor/N)\,Y_{N,\left\lfloor\tau N\right\rfloor}:\,\tau\in\left[0,1\right]\},$$

(55)

so that the probability of the sample path can be represented in terms of $\varphi$. The interpolated trajectories are supported by

$$Q\left(\Omega\right):=\{\,\varphi\in Q:\,Y_{N}\in\Omega\}.$$

(56)

It can be shown that $S^{*}$ admits a continuous representation. This representation can be informally derived by changing the sum in Eq. (49) into an integral

$$\frac{1}{N}\sum_{n\leq N}\rightarrow\int_{0}^{1}d\tau$$

(57)

and apply the proper scaling to the arguments of $H$, i.e.

$$Y_{N,n}\rightarrow\partial_{\tau}\varphi\left(\tau\right),\ \ \pi\left({\textstyle y_{N,n}}\right)\rightarrow\pi\left(\varphi\left(\tau\right)/\tau\right).$$

(58)

Applying these substitutions we obtain the following entropy functional that approximate $S^{*}$:

$$S\left(\varphi\right):=-\int_{0}^{1}d\tau\,H\left(\partial_{\tau}\varphi\left(\tau\right),\pi\left(\varphi\left(\tau\right)/\tau\right)\right).$$

(59)

It can be shown that if $\pi\in\left(0,1\right)$ this functional is continuous respect to the sup norm

$$\left\|\varphi-\eta\right\|:=\sup_{\tau\in\left[0,1\right]}\left|\varphi\left(\tau\right)-\eta\left(\tau\right)\right|$$

(60)

ie, is such that if $\varphi$ converges to $\eta$ in sup norm then also

$$\left|S\left(\varphi\right)-S\left(\eta\right)\right|\rightarrow 0.$$

(61)

In Ref. Franchini it is actually shown that

$$\lim_{N\rightarrow\infty}\left|S^{*}\left(Y_{N}\right)-S\left(\varphi_{N}\right)\right|=0,$$

(62)

then, if $S$ is continuous in the large $N$ limit holds

$$\log 2-\phi\left(\alpha,\beta\right)=\lim_{N\rightarrow\infty}\frac{1}{N}\log E_{0}\,e^{-NS^{*}\left(Y_{N}\right)}I\left(Y_{N}\in\Omega\right)=\lim_{N\rightarrow\infty}\frac{1}{N}\log E_{0}\,e^{-NS\left(\varphi\right)}I\left(\varphi\in Q\left(\Omega\right)\right).$$

(63)

This is enough to compute the rate function from Varadhan Integral Lemma Dembo Zeitouni . Informally, this theorem can be seen as a rigorous functional version of the well known saddle-point method. From Lemmas 4.3.2 and 4.3.4 of the book by Dembo and Zeitouni Dembo Zeitouni we obtain

$$\lim_{N\rightarrow\infty}\frac{1}{N}\log E_{0}e^{-NS\left(\varphi\right)}I\left(\varphi\in Q\left(\Omega\right)\right)=-\inf_{\varphi\in Q\left(\alpha,\beta\right)}\left\{S\left(\varphi\right)-S_{0}\left(\varphi\right)\right\}$$

(64)

where $Q\left(\alpha,\beta\right)$ is the limit of the set $Q\left(\Omega\right)$, i.e.

$$\lim_{N\rightarrow\infty}Q\left(\Omega\right)=Q\left(\alpha,\beta\right)=\bigcup_{\gamma\in\left[\alpha,\beta\right]}Q\left(\gamma\right),$$

(65)

and $S_{0}$ the rate function of a simple random walk with binary steps, in our context would be the case $p=1/2$.

The rate function $S_{0}$ is provided by the Mogulskii Theorem Dembo Zeitouni : it states that the rate function of any process where the increments form an i.i.d. sequence is given by

$$S_{0}\left(\varphi\right)=-\int_{0}^{1}d\tau\,M\left(\partial_{\tau}\varphi\left(\tau\right)\right).$$

(66)

where $M$ is the Legendre transform

$$M\left(\alpha\right):=\inf_{\beta\in\left[0,\infty\right)}\left\{\alpha\beta-\zeta\left(\beta\right)\right\},$$

(67)

of the moment generating function of the increments

$$\zeta\left(\beta\right):=E_{0}\exp\left(\beta Y_{N,1}\right),$$

(68)

in case of coin-flip distributed binary variables:

$$E_{0}\exp\left(\beta Y_{N,1}\right)=\frac{1}{2}\sum_{Y_{N,1}\in\left\{0,1\right\}}\exp\left(\beta Y_{N,1}\right)=\frac{1+e^{\,\beta}}{2}.$$

(69)

Applying the Legendre transform, and following the Mogulskii Theorem Franchini ; Dembo Zeitouni , we find:

$$S_{0}\left(\varphi\right)=-\log 2+J\left(\varphi\right),$$

(70)

where the functional $J$ is defined

$$J\left(\varphi\right):=-\int_{0}^{1}d\tau H\left(\partial_{\tau}\varphi\left(\tau\right),\partial_{\tau}\varphi\left(\tau\right)\right),$$

(71)

for any absolutely continuous $\varphi\in Q$, and is $-\infty$ otherwise, i.e. those trajectories that are not absolutely continuous have zero probability mass (and can be ignored). In the end it is found Franchini that the rate function is equal to

$$I\left(\varphi\right)=J\left(\varphi\right)-S\left(\varphi\right),$$

(72)

Noticing that

$$L\left(\alpha,\beta\right)=H\left(\alpha,\beta\right)-H\left(\alpha,\alpha\right)$$

(73)

we arrive to the rate function as presented in Eq. (24).

We remark that Eq. (23) cannot be deduced by contraction principle, because the internal part of $Q\left(x\right)$ (the set minus its boundary) is void, and then cannot be a continuity set for the rate function $I\left(\varphi\right)$. Some additional arguments would then be necessary to rigorously prove this result, where we apply the contraction principle to the mass of $Q\left(\alpha,\beta\right)$, and then show that is possible to take $\alpha,\beta\rightarrow x$.

This proof is rather technical and we do not need to discuss it here, the interested readers can find it in the proof section of the Ref. Franchini . Also, notice that the requirement that $\pi\in\left(0,1\right)$ is not fulfilled if $p=1$, in Ref. Franchini a special surgery on the set $Q$ is performed to a priori exclude the problematic trajectories and extend the result to the general case $\pi\in\left[0,1\right]$.

For a late market start at saturation $\tau_{0}>0$ and initial share $u_{0}$ we have shown that the process follows a well defined trajectory if $N$ is large enough, with a single convergence point $x\left(u_{0},\tau_{0}\right)$ where the $\phi$ is zero. The scaling of the entropy can be deduced by noticing that this is the unique concentration point of the process, then the probability mass of its nearby should be $O\left(1\right)$: since for finite $N$ and any finite nearby of $x\left(u_{0},\tau_{0}\right)$ the mass must be distributed between a number of possible share values that is of order $O\left(N\right)$, we expect that at the concentration points the mass decays with some power of $N$. This reasoning suggests that in the sub-linear region the entropy of the trajectory is logarithmic in the number of potential customers, let define the sub-linear scaling

$$\phi^{*}\left(x\right):=-\lim_{N\rightarrow\infty}\,\frac{1}{\log N}\log P\left(x_{N,N}=\left\lfloor xN\right\rfloor/N\right)$$

(74)

since there is a is unique concentration point, for any $\tau_{0}>0$ we can expect a monovariate probability mass function, then the predicted sub-linear scaling would be divergent for any $x$ different from $x\left(u_{0},\tau_{0}\right)$ and equal to some positive constant otherwise. On the contrary, in the case of a virgin market start at $\tau_{0}=0$ and for $p>p_{c}$ the limit of the entropy density is found to be zero for any $x\in[x_{-},x_{+}]$, and therefore in the lock-in phase the entropy of any trajectory that ends between the points $x_{\pm}$ has a cost that is sub-linear in the potential number of customers. In fact, is also possible to show Franchini that, for any continuous and invertible urn function, the limit $\phi\left(x\right)$ exists, it is strictly convex and negative from $x=0$ up to the first point where the urn function crosses the diagonal, is zero from that point to the last crossing, and then is convex negative again. A numeric example of the scaling of $\phi$ and $\phi^{*}$ is in Figures (7) and (8).

Although the analysis of the zero-cost trajectories allows to establish that in the early entry case the entropy in the region between the convergence points is sub-linear, the exact scaling of the entropy is not captured by this analysis. By the way, we remark that any deviation from these trajectories on time scale $O(N)$ implies exponential cost. Moreover, from the Corollary 6 of Ref. Franchini follows also the uniqueness of the solution for each $x\in\left(x_{1},x_{2}\right)$. The probability mass current can flow along these trajectories only, therefore, the current flowing through $(\varphi_{1},\varphi_{2})$ is a constant in $\tau$,

$$P\left(\varphi\left(1\right)\in\left(x_{1},x_{2}\right)\right)=P\left(\varphi\left(\tau\right)\in\left(\varphi_{1}\left(\tau\right),\varphi_{2}\left(\tau\right)\right)\right),$$

(75)

since can be also shown Franchini that zero-cost trajectories always emanate from the closest unstable equilibrium point, follows that the entropy of the event $x_{N,N}\in\left(x_{1},x_{2}\right)$ should scale like the entropy near that point, that in this case is $x_{0}=1/2$. It would be very interesting to have a general mathematical theory that allows to find the exact rate at which the point $x_{0}$ expels its probability mass. An informal but general argument can be found in Section III.B.2 of Jack (2019) Jack LD .

Interestingly, also Nakayama and Mori (2021) find that for urn functions that are symmetric around $x_{0}$ the autocorrelation function satisfy a universal logarithmic scaling for a suitable definition of the correlation length. See Ref. Kazuaki for further details.

We still didn’t found much about the region $\phi\left(x\right)<0$: it would be very interesting to have a method to compute the optimal trajectories also in this region, perhaps this could be achieved by properly deforming the zero-cost trajectories, or applying techniques from Lagrange mechanics, or other optimal control methods. Although this has not yet been achieved, we can still compute the shape of $\phi$ outside the sub linear-region by analyzing the cumulant generating function (CGF)

$$\xi\left(\lambda\right):=\lim_{N\rightarrow\infty}\frac{1}{N}\log\sum_{\Gamma\leq N}e^{-\lambda\Gamma}P\left(x_{N,N}=\Gamma/N\right),$$

(76)

the right (left) behavior of $\phi\left(x\right)$ near the convergence points can be deduced from the left (right) limit $\lambda\rightarrow 0^{\pm}$ of the CGF before. Since the convergence points are always symmetric around $x_{0}=1/2$ we only compute the limit from right. In Ref. Franchini is shown that, in general, the CGF satisfies the following nonlinear differential equation at any $p$ and $k$ (eventually any invertible $\pi$)

$$\partial_{\lambda}\xi\left(\lambda\right)=\pi^{-1}\left(\frac{e^{\,\xi\left(\lambda\right)}-1}{e^{\,\lambda}-1}\right)$$

(77)

with $\pi^{-1}$ inverse urn function, and we can study the behavior at small lambda with a suitable perturbations theory (see next section). The shape of $\phi$ near the convergence points is then computed via the Legendre transform

$$\phi\left(x\right)=\inf_{\lambda\in\left[0,\infty\right)}\left\{\lambda x-\xi\left(\lambda\right)\right\}.$$

(78)

A possible informal derivation is as follows: let consider the difference between the partition functions of the system at $N+1$ and $N$ customers

$$E\exp\,(\lambda Nx_{N,N}+\lambda X_{N+1,N+1})-E\exp\,(\lambda Nx_{N,N})={\textstyle\left(e^{\lambda}-1\right)}\,E(\pi\left(x_{N,N}\right)\exp\,(\lambda Nx_{N,N})),$$

(79)

consider the following equivalent expression for the CGF

$$\xi_{N}\left(\lambda\right)=\frac{1}{N}\log\,E\exp\,(\lambda Nx_{N,N}),$$

(80)

define the auxiliary function

$$\delta_{N}\left(\lambda\right):=\left(N+1\right)\left(\xi_{N+1}\left(\lambda\right)-\xi_{N}\left(\lambda\right)\right),$$

(81)

and the notation $E_{\lambda}$ for the tilted average,

$$E_{\lambda}f\left(X_{N}\right):=\frac{Ef\left(X_{N}\right)\exp\left(\lambda Nx_{N,N}\right)}{E\exp\left(\lambda Nx_{N,N}\right)}.$$

(82)

Using this notation and after some manipulations we arrive to the identity

$$\delta_{N}\left(\lambda\right)+\xi_{N}\left(\lambda\right)=\log\left(1+{\textstyle\left(e^{\lambda}-1\right)}\,E_{\lambda}\pi\left(x_{N,N}\right)\right),$$

(83)

now we take the limit $N\rightarrow\infty$: from the existence of $\phi$ follows that of $\xi$, then the limit of $\xi_{N}$ exists and is

$$\lim_{N\rightarrow\infty}\xi_{N}\left(\lambda\right)=\xi\left(\lambda\right),$$

(84)

and can be shown Franchini that, if the urn function $\pi$ is invertible, which is our case, then also its derivative exists, and converges to $\partial_{\lambda}\xi$ in the limit

$$\lim_{N\rightarrow\infty}E_{\lambda}x_{N,N}=\lim_{N\rightarrow\infty}\partial_{\lambda}\xi_{N}\left(\lambda\right)=\partial_{\lambda}\xi\left(\lambda\right).$$

(85)

It is also possible to prove Franchini that $x_{N,N}$ weakly concentrates on its convergence point under the tilted average $E_{\lambda}$, notice that the tilted average of $x_{N,N}$ is

$$E_{\lambda}x_{N,N}=\partial_{\lambda}\xi_{N,N}\left(\lambda\right),$$

(86)

therefore by weak convergence

$$\lim_{N\rightarrow\infty}E_{\lambda}\pi\left(x_{N,N}\right)=\lim_{N\rightarrow\infty}\pi\left(E_{\lambda}x_{N,N}\right)=\pi\left(\partial_{\lambda}\xi\left(\lambda\right)\right).$$

(87)

Finally, with a slightly more technical argument (see the proof section of Ref. Franchini ) one can show that $\delta_{N}$ converges to zero

$$\lim_{N\rightarrow\infty}\delta_{N}\left(\lambda\right)=0,$$

(88)

putting together we find

$$\xi\left(\lambda\right)=\log\left(1+{\textstyle\left(e^{\lambda}-1\right)}\,\pi\left(\partial_{\lambda}\xi\left(\lambda\right)\right)\right),$$

(89)

that is equivalent to Eq. (77).