Heaps’ law in the Urn Model with Semantic Triggering

We here outline the analysis leading to an estimate for the Heaps’ exponent as a function of the model parameters |$\nu$|⁠, |$\rho$| and |$\eta$|⁠. Observe that in the urn model with semantic triggering, the probability of each ball to be drawn at time |$t$|⁠, depends on the label of the ball drawn at time |$t\,{-}\,1$|⁠. Let this label be |$s$|⁠, we can thus write the differential equation for the number of distinct elements |$D(t)$| appearing in the sequence |${\mathcal S}$|⁠: where |$N^{s}(t)$|⁠, |$N_D^{s}(t)$|⁠, |$N^{\bar{s}}(t)$| and |$N_D^{\bar{s}}(t)$| denote respectively the number of elements with label |$s$|⁠, the number of new (never used in the sequence |$\mathcal{S}$|⁠) elements with label |$s$|⁠, the number of elements with label different from |$s$|⁠, and the number of new elements with label different from |$s$|⁠, that are present in the reservoir |$\mathcal{U}$| at time |$t$|⁠. The following relations hold: where |$U(t)$| is the number of total elements in the reservoir. It is worth remarking that if |$\eta\,{=}\,1$| one recovers Eq. (G.1). We now drop the hypothesis of knowing the label of the last added element, and write a general equation for |$D(t)$| of the form: where the sum is over all the labels |$k$| present at time |$t$| in the reservoir |$\mathcal{U}$| and |$P(k)$| is the probability that the last added element to the sequence |$\mathcal{S}$| at time |$t$| had the label |$k$|⁠. In order to close Eq. (J.3), we should estimate |$N^{k}(t)$| and |$N_D^{k}(t)$| for a generic label |$k$|⁠. Let us start by observing that |$N_D^{k}(t)\,\leq \nu \,{+}\,1$|⁠, and this term can be neglected in the large |$t$| limit with respect to |$D(t)$|⁠. We now leave the more complex problem of estimating |$N^{k}(t)$| and we consider instead the probability |$P(n)$| that |$N^{k}(t)\,\equiv n$|⁠, substituting the sum over |$k$| in Eq. (J.3) with the sum over the labels with the same number of occurrences |$n$| in the reservoir. We can thus write (asymptotically): We do not explicitly compute |$P(n)$|⁠, but we consider two opposite limits: Summarising, we have obtained lower and upper bounds for |$\beta$|⁠: |$\min(\frac{\nu \eta }{\rho},1) \leq \beta \leq \min(\frac{\nu}{\rho},1) $|⁠.