# Proactive Detractor Detection Framework Based on Message-Wise Sentiment
Analysis Over Customer Support Interactions

J. S. Salcedo-Gallo  Rappi AI Research  J. Solano  Rappi AI Research  H.
García  Rappi AI Research  D. Zarruk-Valencia  {sebastian.salcedo,
jesus.solano, javier.garcia<EMAIL_ADDRESS><EMAIL_ADDRESS>A. Correa-Bahnsen  Rappi AI Research

###### Abstract

In this work, we propose a framework relying solely on chat-based customer
support (CS) interactions for predicting the recommendation decision of
individual users. For our case study, we analyzed a total number of 16.4k
users and 48.7k customer support conversations within the financial vertical
of a large e-commerce company in Latin America. Consequently, our main
contributions and objectives are to use Natural Language Processing (NLP) to
assess and predict the recommendation behavior where, in addition to using
static sentiment analysis, we exploit the predictive power of each user’s
sentiment dynamics. Our results show that, with respective feature
interpretability, it is possible to predict the likelihood of a user to
recommend a product or service, based solely on the message-wise sentiment
evolution of their CS conversations in a fully automated way.

##  1 Introduction

Since the introduction of the Net Promoter Score (NPS) [1] in the early 2000s,
it has become an important metric for measuring customer recommendation
behavior across multiple industries [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13,
14, 15]. This score is based on a rather straightforward question, namely ’How
likely would you be to recommend us to your friends or family?’ Moreover,
these surveys are massively conducted at a frequency ranging from monthly to
an annual basis [11], or even immediately after individual interaction with
Customer Support (CS) [6]. In practice, the NPS score can be segmented into
three main groups, namely promoters, passives, and detractors [1].

Figure 1: Our proposed framework for proactive promoter/non-promoter user
detection for any chat-based user interaction.

Previous studies on sentiment analysis related to NPS recommendation behavior
have not been studied in chat-based customer relationship interactions, which
have gained popularity given the massive outreach of widely adopted messaging
applications and Client Resource Management (CRM) platforms. Furthermore, it
is of compelling interest for companies to predict recommendation decisions to
proactively and effectively correct service failures, and retribute customers
with incentives, which ultimately could improve the company’s ratings.
Therefore, our main contribution and objective are to use NLP to assess and
predict the recommendation behavior of the users where, in addition to using
static sentiment analysis, we exploit each user’s sentiment evolution
throughout a particular conversation, inspired by the inherently dynamic
nature of human conversations [16], while employing widely-known and robust ML
transformed-based architectures [17].

In this work, we address the NPS binary classification problem, namely
predicting whether a given user would be a promoter or not. We have a total
number of 16.4k users and 48.7k CS conversations with a large e-commerce
company in Latin-America for one specific city, where each particular
recommendation rating is obtained directly from the users themselves in
corresponding survey responses. With this, we have performed sentiment
classification based on transformer-based architecture over each user’s CS
chat-based interactions to predict well in advance the recommendation behavior
of particular users. Each turn-level inherent sentiment evolution feature is
used to perform a classification task at hand. We draw inspiration from
existing approaches for conversational discourse-aware response generation
such as DialogBERT [18], DialoGPT [19], or Blender [20] for our analysis.

Furthermore, we propose a message-wise sentiment evolution analysis of the
customer-sent messages throughout the conversation. This message-wise approach
consists of obtaining a sentiment score for each message the user sends in a
particular chat-based CS conversation. Thus, allowing us to analyze the trend
and overall sentiment evolution and their relation with the recommendation
behavior of any particular user. Our results show that overall, message-wise
evolution analysis is substantially superior in predicting the recommendation
behavior of individual users compared to a traditional review-based approach
of computing the overall sentiment of the complete interactions. To the best
of our knowledge, this is the first message-wise sentiment evolution analysis
over chat-based CS interactions to predict the recommendation behavior of
users, which is highly extensible for any particular domain and any specific
business-driven metric. For instance, N-class or binary problems, such as the
Satisfaction Score (CSAT), Churn score, Recency-Frequency-Monetary (RFM)
score, or even fraud detection, to name a few.

##  2 Background

The most relevant advances in algorithms to predict the NPS score are based on
online reviews [5], word of mouth (WOM) [2], social media data analytics [21],
explicit quantitative experience attributes and service ratings [11, 14],
among others[13]. These previous approaches used simple regression models
[22], tree-based classification approaches such as simple Decision Trees [11],
as well as Support Vector Machines [11], Deep Neural Networks [6], and
probabilistic approaches [14]. Moreover, for obtaining quantitative insights
from text, there is evidence of manually and empirically performed analysis
based on explicit human annotations to assess the negative, neutral, and
positive polarity of eWOM messages, and their correlation with detractors,
passives, and promoters recommendation decisions [2]. Also, other
classification approaches for ‘Recommend’ or ‘No-recommend’ behavior have
considered more robust modeling such as bag-of-words and aspect-based
sentiment analysis over online airline reviews [7, 5]. However, on one hand,
the actual predictive powers of combining qualitative and quantitative user-
generated content on the recommendation behavior were not explored and are
limited to correlation and statistical analysis so far. On the other hand, in
the case of online reviews, where authors [5] used overall-sentiment, aspect-
specific-sentiment, and bag-of-words, they indeed address the performance on
the prediction task of recommending/non-recommending. However, their results
and approach are not generally comparable with ours, given the fundamental
difference between chat-based interactions and online reviews [5, 11, 6, 4,
12]. Consequently, the actual predictive powers of inherent characteristics
obtained from the sentiment evolution in chat-based interactions were yet to
be explored and assessed in general, and in a real-world environment.

An earlier study [7] showed that positive emotions have a positive
relationship with customer outcomes, whereas negative emotions had a negative
relation with recommendation behavior regardless of the nature of the service.
As such, the author made relevant contributions from a theoretical point of
view. However, the actual predictive powers on a classification task were not
addressed nor explored.

Finally, authors in [13] stated that, for future work, ensembles and
optimization procedures should be applied for getting predictive
recommendation decisions in the scope of the NPS prediction problem. As such,
we here explore the use of an ML Ensemble model, more specifically Gradient
Boosting Trees. All of this, in the light of a real-life dataset, while
studying the impact of using a random under-sampling technique for training in
order to improve generalization.

##  3 Detractor Detection Framework Based on Sentiment Analysis

In this work, we propose a framework for proactive detection of the
recommendation behavior in the scope of the NPS classification problem
considering the user’s chat-based CS interactions, as shown in Figure 1. The
main idea lies in the hypothesis that the trend and sentiment evolution of
chat-based conversations can better capture the overall behavior of the
customers toward their recommendation decisions. Our method consists on
classifying the sentiment of each message with language modeling based on ML
transformers architecture. For instance, let us consider a user that started a
conversation rather neutral, then swung to rather negative consecutive
messages while the issue is being exposed, to then end the conversation rather
positively as the issue might have been effectively solved. In this case, the
user is presumably more likely to recommend the service as a result of good
customer experience or low frustration.

###  3.1 Sentiment analysis of CS conversations

Specifically, for the sentiment measure $SS(\cdot)$ we use a sentiment
classifier based on the Bidirectional Encoder Representations from
Transformers (BERT) architecture [17], which is a transformers-based ML
technique for NLP applications such as sentiment classification [23], question
answering [24], masked language models[25], Next Sentence prediction tasks
[26], among others [27]. In this case, we used a specific pre-trained model
that is fine-tuned and intended for direct use as a sentiment classification
model for product reviews in English, Dutch, German, French, Spanish, or
Italian. Regardless of the language, this model has a sufficiently robust off-
by-one accuracy ranging from 93% to 95%, corresponding to the percentage of
reviews where the number of stars the model predicts differs by a maximum of 1
from the number given by the human reviewer in a 0-4 scale.

Once we obtain the message-wise sentiment per user’s responses in each
specific longest conversation, we perform manual feature extraction and
feature engineering based on the retrieved sentiment classification. For the
conversation $\hat{c}\in C_{i}$ we construct the discrete sentiment line as
the curve associated to the vector $\text{disc}=MWS(\hat{c})$. More precisely,
for a given message $m$ the model return the number of stars associated to $m$
as the value $SS(m)$. This model also returns the probability
$\mathbb{P}(SS(m))$. Given that this ‘discrete’ approach ($MWS(\hat{c})$)
might result in a very step-like behavior in general, we therefore opted for
having a ‘continuous’ sentiment, namely the actual star having the largest
probability score plus the actual score associated with that particular star.
Formally, we define the continuous sentiment curve  as the curve associated to
the vector:

$\text{cont}(\hat{c}):=(SS(\hat{m}_{1})+\mathbb{P}(SS(\hat{m}_{1})),..,SS(\hat{m}_{N})+\mathbb{P}(SS(\hat{m}_{N})))$
(1)

where $\hat{c}:=(\hat{m}_{1},...,\hat{m}_{N})$.

To further smooth the sentiment message-wise series, we apply an exponential
weighted mean function to Eq. 1, so that we obtain a more flexible evolution
onset, more suitable for trend and concavity analysis:

$MA_{j}:=\alpha\cdot\text{cont}(\hat{c})_{j}+(1-\alpha)\cdot MA_{j-1}$ (2)

which we depict as a red dashed line in Fig. 2, where we consider an static
decay parameter of $\alpha=2/3$. We apply a simple linear regression to
capture the trend, which in general can give an approximation for overall
evolution of the conversation. Then this value slope is used as a feature for
our classification model.

Finally, we define the experiments, namely the sampling technique for
unbalanced treatment, target labels, and the classification model to train.
For this, we use a widely-known ML classification algorithm, namely Gradient
Boosting Trees (XGBoost) [28] and Random Search hyper-parameter tuning for the
classifier [29]. The proposed framework is very flexible as it could be easily
extended to any chat-based interactions to predict any business-driven metric
or N-class customer rating classification task, such as Satisfaction Score
(CSAT), Churn score, Recency-Frequency-Monetary (RFM) score, or even fraud
detection.

###  3.2 Baseline Model

In order to assess the relevance of the here proposed framework for chat-based
CS interactions, we obtain a baseline model that mimics an empirical sentiment
estimation for batch text of the complete interaction. First, for our baseline
model, we consider the static sentiment of each complete interaction. Let
$C_{i}$ be the set of complete conversations of the user $u_{i}$. For each
$c\in C_{i}$ we compute the static sentiment $SS(c)$ using the architecture
described in section 3.1. Therefore, we compute the descriptive statistics
variables such as the mean, minimum, maximum, and median sentiment of the
vector $(SS(c))_{c\in C_{i}}$, as well as the number of CS interactions,
$|C_{i}|$. Accordingly, with this baseline set-up features we can train a
model, following procedure described in Section 4.2, that gives an estimation
of the probability of a given user to be a promoter based on overall static
sentiment evaluation. However, it is very relevant to make clear that our main
contribution is not just to use sentiment analysis and Natural Language
Processing (NLP) to predict recommendation behavior, but rather to use highly
mature components [17] in a novel way for capturing the actual sentiment
evolution throughout the CS conversations, as presented in Sec. 3.1.

###  3.3 Line-wise Sentiment Analysis Model

Figure 2: We depict a typical example of user-sent messages to CS in a
particular interaction. The blue solid line represent the ‘discrete’
sentiment, which corresponds to the star rating computed with the sentiment
classifier per each user’s message. The red solid line represent the
‘continuous’ sentiment, which corresponds to the discrete star rating plus the
actual score associated with that particular star. The red dashed line
represents an exponential weighted mean function (MA), and the black dashed
line represent a linear fit over the smoothed MA curve. The shaded region
corresponds to the last third of the conversation, which we have used to
extract some features for our analysis. We only plot the linear fit to the
conversation, even though concavity and descriptive statistics features are
also computed from this message-wise analysis.

We perform granular, flexible and general message-wise sentiment analysis to
assess the inherent sentiment dynamic nature of conversations and how it
relates to the recommendation behavior of a given user. To the best of our
knowledge, there is no scientific evidence showing that the actual predictive
powers of sentiment evolution in chat-based interactions have been explored
and assessed regarding general binary classification tasks.

As such, we assess the predictive power of quantitative message-wise sentiment
analysis features extracted from individual CS conversations. Consider a
conversation $c\in C_{i}$ and its vector representation
$c:=(m_{1},...,m_{N})$, where $m_{j}$ is the $j$-th user message or turn
appearing in the conversation, thus neglecting agent responses. We begin
considering the vector of message-wise sentiment as
$MWS(c):=(SS(m_{1}),...,SS(m_{N}))$. Figure 2 shows an example of a typical CS
conversation, where each message has an associated sentiment on the message-
wise panel on the right. It can be seen that the conversation started rather
neutral, then there were some issues exposed in the middle part of the
conversation, which were effectively solved by the agent.

Let $\hat{c}$ be the longest conversation in $C_{i}$. Once the message-wise
sentiment vector $MWS(\hat{c})$ is computed, we obtain descriptive statistics
features, as well as concavity analysis related to the mean of the numerical
second derivative and the overall trend fitted as a linear slope. With this,
we are able to capture not only the overall trend, but also the evolution of
the conversation in terms of concavity analysis. A more detailed description
of this process appears in Section 3.1. We look at the evolution of the
message-wise sentiment vector $MWS(C_{i})$ over time. This includes both the
number of messages belonging to each specific discrete sentiment class, as
well as the descriptive statistics features extracted from the last third of
the conversation. For the here presented framework, the overall sentiment of
the complete interaction is compared against the granular sentiment evolution
of the chat-based messages.

##  4 Evaluation

###  4.1 Dataset

Our dataset consists of the CS conversations and NPS surveys conducted in the
second semester of 2021, of users within the financial vertical of a large
e-commerce company for one specific city. In our case study we consider around
16.4k users having CS interactions whom also have filled the NPS survey, for a
total number of interactions to the CS center $\bigcup C_{i}\approx$ 48.7k+.
Also, the mean number of interactions correspond to 2.39. Therefore, we
predominantly base our analysis on the largest conversation of a given user,
while still considering general features for the overall CS interactions.
Moreover, the mean number of messages for the largest conversations per user
corresponds to 13.85 messages. We use only the customer responses, thus
ignoring the agent’s prompts. After querying the conversations, we then apply
a simple preprocessing step, namely removing special characters and blank
messages. As for the count of each recommendation behavior annotated by the
users themselves in our dataset, we have a total of 10701 promoter users,
whereas 5700 non-promoter ones, making it a slightly imbalanced classification
problem. It is of compelling relevance to point out that we use only features
extracted from text, thus preventing ourselves from using behavioral data or
other specific service ratings.

###  4.2 Experimental Setup

We use Random Search for hyper-parameter tuning of the XGBoost classifier used
in this work, where both the number of folds in a (Stratified)-KFold and the
number of parameter settings that are sampled for each classifier were set to
10. For our experimental setup, we have a total of 16401 users, for which we
use a user-wise train/test split ratio of 80% / 20% for the train and test
set, respectively. We also explore the impact of sampling the train set over
the predictive power in terms of validation metrics such as the F1-score, and
Specificity [30]. Moreover, we also assess the influence of passive (2470)
users on the predictive power of the algorithm, so that we additionally obtain
classification results considering only promoters (10701) and detractors
(3230) users. In that regard, we consider three experiments in our setup,
namely our (1) static-like sentiment baseline (B), (2) message-wise sentiment
evolution analysis considering passive users (B + LW) , and (3) message-wise
sentiment evolution ignoring passive users (B + LW{NP}).

We then validate the performance of the classification models for the
different experiments using the Area Under the Curve (AUC) [31], Kolmogorov-
Smirnov (KS) metric [32], and Macro F1 score [30] as our validation metrics
for one-to-one comparison.

##  5 Results and Discussion

Table 1 shows the results of our classification task, namely predicting
whether the given customer would be a promoter (1) or not (0). Results are
presented by considering Random Undersampling only over our train set for
dealing with imbalanced nature of our dataset. We show results for our
baseline (B) approach, as well as for our dynamic line-wise sentiment analysis
considering (B + LW) and ignoring (B + LW{NP}) passives users.

First, the results presented in Table 1 for our baseline (B) show that this
model is only marginally doing better than a random guesser. Therefore, the
overall and static sentiment of complete CS interactions does not present
strong predictive power considering only CS chat-based interactions.
Nonetheless, they do have comparable performance if compared against to
previous works where explicit service ratings were used as features,
exhibiting a similar Macro F1 score of about 0.55 for a similar problem in the
scope of the NPS classification task [33, 11]. The observed low statistical
accuracy of our baseline and previous approaches suggests that there should be
additional attributes not captured in the sentiment of the whole interaction
or surveys that explain the recommendation behavior of the users, which is the
problem we are trying to tackle here.

Table 1: XGBoost Classification results in terms of Area Under the Curve (AUC), Kolmogorov-Smirnov (KS) and Macro F1 score for our three experiments on the NPS binary classification task. As such, we have depicted the abbreviations for each experiment as: baseline (B), our message-wise sentiment evolution analysis including passive users (B + LW), and line-wise sentiment evolution ignoring passive users (B+LW{NP}). | XGBoost
---|---
Experiment | AUC | KS | Macro F1
B | 0.5513 | 0.0801 | 0.54
B + LW | 0.6199 | 0.1843 | 0.58
B + LW{NP} | 0.6455 | 0.2389 | 0.58

The results for our (B + LW) experiment are significantly better than those
exhibited by our baseline (B) and also than those reported in previous works,
in terms of the AUC, KS, and F1 scores. This suggests that the message-wise
sentiment evolution analysis and derived features improve the predictive power
of the classification algorithm at hand, having performance gains in terms of
the AUC of about 10-14% in any case. Moreover, when observing the validation
metrics for the (B+LW{NP}) experiment, it is evident that the AUC and the KS
metrics further increase, so that the model is separating better the
detractors from promoters, even when the problem had a higher class imbalance.
This might be because the input space for passive users is more diverse and
sparse than for both detractors or promoters. Thus, suggesting that there
might not be clear patterns to learn from the passives population so that
extensive inspection in that regard is encouraged in future works.

Figure 3: Relative distribution of number of samples belonging to each
respective promoters/non-promoters class per score bin. The score represents
the probability of each sample belonging to the promoters class (Class 1)
according to the trained XGBoost model for our (B+LW) experiment. Numbers
inside each bin represent the number of samples classified per each score
interval.

Figure 3 show a plot of the scorecard for our XGBoost model for the (B+LW)
experiment. It can be seen that overall, the relative number of users
classified as non-promoters does increase monotonically as the score
decreases, which is a good indicator in this case. The score represents the
probability of a sample belonging to the promoters class. In that regard, the
model is capable of separate between each class, though it is not entirely
sure about none, given that the bins with scores higher (lower) than 0.8 (0.1)
are empty. This can be due to a fundamental selection bias, as users contact
CS only when they have issues with the product or service. Correspondingly,
their recommendation behavior might be biased and lowered by itself
considering the inherent nature of the CS interactions. However, the here
presented results, are significantly better to those obtained in previous
works [11] considering explicit quantitative service ratings, for instance.

In addition, we use the SHapley Additive exPlanations (SHAP) [34] algorithm to
obtain the feature-level interpretability of our ensemble model. SHAP values
can tell us the extent and relationship to which each feature in a model has
contributed to the final prediction. Figure 4 shows the SHAP values for our (B
+ LW) experiment. These values are in very good agreement with a rather
intuitive reasoning, as well as previous similar studies based on text reviews
[7]. For instance, we can see that a higher number of messages from a customer
to the CS center leads to a lower value on the classification task, i.e., a
lower probability of being a promoter user. This is very sensible given that
if a single client has sent a very large number of messages, it might indicate
angriness or frustration, then leading to a rather poor customer experience,
and thus a low recommendation decision. A similar interpretation can be
extended to the number of messages having the lowest possible sentiment in our
discrete sentiment scale, as well as the other corresponding features.

Furthermore, when interpreting variables such as the last sentiment of the
longest conversation, the slope of the linear fitting (Fig. 2), or the average
sentiment over all CS conversations, we can see that the larger these values,
the more likely a person to recommend the service is. This is very relevant
given that a high slope value, means that a given conversation started rather
neutral/negative but ended rather positive, and this might be associated with
low customer frustration and then better recommendation behavior overall, thus
validating our sensible hypothesis stated in Section 3.

Figure 4: SHapley Additive exPlanations (SHAP) values for individual features
of the line-wise sentiment analysis considering passive users (B + LW)
experiment.

Very relevantly, it can be observed that the concavity analysis demonstrated
that rather low acceleration values (i.e., low mean value of the numerical
second derivative) leads to rather low SHAP values, whereas rather convex-like
sentiment series (high acceleration values) leads to higher SHAP values. This
is also in very good agreement with intuitive reasoning, as for a twice-
differentiable function, if its acceleration is positive, then the line-wise
series is concave upward. Likewise, if the second derivative is negative, then
the graph is concave downward. Therefore, the more convex-like the line-wise
sentiment series is, the more likely the user to be a promoter is. For
instance, the overall evolution of a convex-like conversation would be, in
general, a conversation starting very gentle and positive, then swinging
through a rather neutral-negative stage, then ending rather positively.
Therefore such a convex-like pattern is also associated with better
recommendation behavior, whereas concave-like shape results generally in the
opposite outcome.

The more noisy and volatile a series is, the more likely the user is to be a
promoter, as confirmed by the coefficient of variation. This might be due to
the fact that non-promoter users might tend to have a more negatively biased
behavior, causing also the overall standard deviation of the distribution to
be small. Furthermore, for the sum of other features in the last row of Fig. 4
we can see that their overall aggregated SHAP values do not have strong
predicting power, yet can further segment our target population.

In general, the here presented results represent the first analysis and
assessment of the actual predictive powers of the message-wise sentiment
evolution throughout chat-based CS interactions on the recommendation behavior
of individual users. As such, this work represents a highly flexible and
interpretable framework for proactive intervention of promoter/non-promoter
users which is particularly relevant, given that in our case-study the NPS
survey is sent periodically once every few months. Therefore, the framework
could be used in other classification tasks regarding other business-driven
metrics or customer ratings based on chat-based interactions in any particular
domain.

Finally, we would like to discuss that even though we do not have a clear
baseline model present in the literature to which we can fairly compare
against, we do observe that our baseline is comparable in performance to
different available studies in the field [5, 11, 7, 6]. Generally, the lack of
baselines or benchmark comparisons are grounded in the fact that there are no
publicly available datasets containing chat-based conversations with NPS
annotations obtained directly from the users; as these datasets typically
belong to private companies, highly regulated by the authorities, as in our
study case. However, there is no foreseeable fact that would prevent the here
presented results and employed ML techniques to be generally extensible to any
industry domain.

##  6 Conclusions

In this work, we propose and evaluate our framework on the NPS classification
problem in the field of CS interactions, showing its value, flexibility and
interpretability in a real-world case study, where rating annotations were
provided directly by the users in corresponding surveys. Our results show that
it is possible to predict the recommendation decision of users based on
dynamic sentiment classification of chat-based data sources employing
transformer-based methods. Results show performance gains of about 10-14%
obtained when considering a sentiment evolution analysis versus a purely
aggregated, review-based, sentiment classification. Moreover, our explainable
features explicitly allowed us to draw important and intuitive insights
regarding the complex relations that do arise between the recommendation
behavior of a given user and the sentiment evolution of their CS messages.
More importantly, we here present a framework that can be easily extended to
other prediction tasks in any business environment, considering any customer
ratings of interest. We therefore hope that this work could spark interest
among data-driven companies, and will inspire other works in this research
area, where inherent attributes related to the evolution of conversations
could be exploited to further develop state-of-the-art techniques and
applications.

## Acknowledgements

We would like to thank Luisa F. Roa, Ana M. Quintero, Jaime Acevedo, V. Maya,
and R. Saavedra for their insightful ideas and valuable discussions during the
development of this research project.

## References

  * [1] F. F. Reichheld, “The one number you need to grow,” _Harvard Business Review_ , vol. 81, pp. 46–54, 2003. [Online]. Available: www.hbr.org
  * [2] N. Raassens and H. Haans, “Nps and online wom: Investigating the relationship between customers’ promoter scores and ewom behavior,” _Journal of Service Research_ , vol. 20, pp. 322–334, 8 2017.
  * [3] A. Ando, R. Masumura, H. Kamiyama, S. Kobashikawa, and Y. Aono, “Hierarchical lstms with joint learning for estimating customer satisfaction from contact center calls,” vol. 2017-August. International Speech Communication Association, 2017, pp. 1716–1720.
  * [4] J. Bockhorst, S. Yu, L. Polania, and G. Fung, “Predicting self-reported customer satisfaction of interactions with a corporate call center,” _ECML PKDD 2017: Machine Learning and Knowledge Discovery in Databases_ , pp. 179–190, 2017. [Online]. Available: https://github.com/cyberyu/ecml2017.
  * [5] M. Siering, A. V. Deokar, and C. Janze, “Disentangling consumer recommendations: Explaining and predicting airline recommendations based on online reviews,” _Decision Support Systems_ , vol. 107, pp. 52–63, 3 2018\.
  * [6] J. Auguste, D. Charlet, G. Damnati, F. Bechet, and B. Favre, “Can we predict self-reported customer satisfaction from interactions?” _2018 IEEE International Conference on Acoustics, Speech and Signal Processing : proceedings_ , pp. 1–5, 2018.
  * [7] S. Chatterjee, “Explaining customer ratings and recommendations by combining qualitative and quantitative user generated contents,” _Decision Support Systems_ , vol. 119, pp. 14–22, 4 2019.
  * [8] S. Rose, R. Sreejith, and S. Senthil, “Social media data analytics to improve the customer services: The case of fast-food companies,” _International Journal of Recent Technology and Engineering_ , vol. 8, pp. 6359–6366, 7 2019\.
  * [9] B. Vanderheyden, Y. Xie, and M. Rachumallu, “Net promoter sentiment classifier using ohpl-al,” 2019, pp. 2494–2502.
  * [10] C. Lewis and M. Mehmet, “Does the nps® reflect consumer sentiment? a qualitative examination of the nps using a sentiment analysis approach,” _International Journal of Market Research_ , vol. 62, pp. 9–17, 1 2020.
  * [11] I. Markoulidakis, I. Rallis, I. Georgoulas, G. Kopsiaftis, A. Doulamis, and N. Doulamis, “A machine learning based classification method for customer experience survey analysis,” _Technologies_ , vol. 8, p. 76, 12 2020.
  * [12] S. Baehre, M. O’Dwyer, L. O’Malley, and N. Lee, “The use of net promoter score (nps) to predict sales growth: insights from an empirical investigation,” _Journal of the Academy of Marketing Science_ , 2021.
  * [13] P. K. Jain, R. Pamula, and G. Srivastava, “A systematic literature review on machine learning applications for consumer sentiment analysis using online reviews,” p. 100413, 8 2021.
  * [14] I. Markoulidakis, I. Rallis, I. Georgoulas, G. Kopsiaftis, A. Doulamis, and N. Doulamis, “Multiclass confusion matrix reduction method and its application on net promoter score classification problem,” _Technologies_ , vol. 9, p. 81, 11 2021.
  * [15] M. Zaki, D. Kandeil, A. Neely, and J. R. Mccoll-Kennedy, “The fallacy of the net promoter score: Customer loyalty predictive model why this paper might be of interest to alliance partners,” _University of Cambridge_ , 2016. [Online]. Available: www.cambridgeservicealliance.org
  * [16] A. Garas, D. Garcia, M. Skowron, and F. Schweitzer, “Emotional persistence in online chatting communities,” _Scientific Reports_ , vol. 2, no. 1, p. 402, May 2012. [Online]. Available: https://doi.org/10.1038/srep00402
  * [17] J. Devlin, M.-W. Chang, K. Lee, and K. Toutanova, “Bert: Pre-training of deep bidirectional transformers for language understanding,” 2018, cite arxiv:1810.04805Comment: 13 pages. [Online]. Available: http://arxiv.org/abs/1810.04805
  * [18] X. Gu, K. M. Yoo, and J.-W. Ha, “Dialogbert: Discourse-aware response generation via learning to recover and rank utterances,” 2021. [Online]. Available: www.aaai.org
  * [19] Y. Zhang, S. Sun, M. Galley, Y.-C. Chen, C. Brockett, X. Gao, J. Gao, J. Liu, and B. Dolan, “Dialogpt: Large-scale generative pre-training for conversational response generation,” 11 2019. [Online]. Available: http://arxiv.org/abs/1911.00536
  * [20] S. Roller, E. Dinan, N. Goyal, D. Ju, M. Williamson, Y. Liu, J. Xu, M. Ott, K. Shuster, E. M. Smith, Y.-L. Boureau, and J. Weston, “Recipes for building an open-domain chatbot,” 4 2020. [Online]. Available: http://arxiv.org/abs/2004.13637
  * [21] N. A. Vidya, M. I. Fanany, and I. Budi, “Twitter sentiment to analyze net brand reputation of mobile phone providers,” _Procedia Computer Science_ , vol. 72, pp. 519–526, 2015.
  * [22] D. Vélez, A. Ayuso, C. Perales-González, and J. T. Rodríguez, “Churn and net promoter score forecasting for business decision-making through a new stepwise regression methodology,” _Knowledge-Based Systems_ , vol. 196, p. 105762, 2020. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0950705120301684
  * [23] M. Munikar, S. Shakya, and A. Shrestha, “Fine-grained sentiment classification using bert,” in _2019 Artificial Intelligence for Transforming Business and Society (AITB)_ , vol. 1, 2019, pp. 1–5.
  * [24] M. Zaib, D. H. Tran, S. Sagar, A. Mahmood, W. E. Zhang, and Q. Z. Sheng, “Bert-coqac: Bert-based conversational question answering in context,” _ArXiv_ , vol. abs/2104.11394, 2020.
  * [25] H. Bao, L. Dong, F. Wei, W. Wang, N. Yang, X. Liu, Y. Wang, S. Piao, J. Gao, M. Zhou, and H.-W. Hon, “Unilmv2: Pseudo-masked language models for unified language model pre-training,” in _Proceedings of the 37th International Conference on Machine Learning_ , ser. ICML’20. JMLR.org, 2020.
  * [26] W. Shi and V. Demberg, “Next sentence prediction helps implicit discourse relation classification within and across domains,” in _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_. Hong Kong, China: Association for Computational Linguistics, Nov. 2019, pp. 5790–5796. [Online]. Available: https://aclanthology.org/D19-1586
  * [27] Y. Liu, M. Ott, N. Goyal, J. Du, M. Joshi, D. Chen, O. Levy, M. Lewis, L. Zettlemoyer, and V. Stoyanov, “Roberta: A robustly optimized bert pretraining approach,” _ArXiv_ , vol. abs/1907.11692, 2019.
  * [28] T. Chen and C. Guestrin, “Xgboost: A scalable tree boosting system,” _CoRR_ , vol. abs/1603.02754, 2016. [Online]. Available: http://arxiv.org/abs/1603.02754
  * [29] R. G. Mantovani, A. L. D. Rossi, J. Vanschoren, B. Bischl, and A. C. P. L. F. de Carvalho, “Effectiveness of random search in svm hyper-parameter tuning,” _2015 International Joint Conference on Neural Networks (IJCNN)_ , pp. 1–8, 2015.
  * [30] C. Goutte and E. Gaussier, “A probabilistic interpretation of precision, recall and f-score, with implication for evaluation,” in _Advances in Information Retrieval_ , D. E. Losada and J. M. Fernández-Luna, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2005, pp. 345–359.
  * [31] J. A. Hanley and B. J. McNeil, “The meaning and use of the area under a receiver operating characteristic (roc) curve.” _Radiology_ , vol. 143 1, pp. 29–36, 1982.
  * [32] _Kolmogorov–Smirnov Test_. New York, NY: Springer New York, 2008, pp. 283–287. [Online]. Available: https://doi.org/10.1007/978-0-387-32833-1_214
  * [33] I. Rallis, I. Markoulidakis, I. Georgoulas, and G. Kopsiaftis, “A novel classification method for customer experience survey analysis.” ICST, 6 2020, pp. 1–9.
  * [34] S. M. Lundberg and S. Lee, “A unified approach to interpreting model predictions,” _Proceedings of the 31st International Conference on Neural Information Processing Systems (NIPS)_ , p. 4768–4777, 2017.


# On spectral distribution of sample covariance matrices from large
dimensional and large $k$-fold tensor products

Benoît Collins Department of Mathematics, Kyoto University. E-mail:
<EMAIL_ADDRESS>Jianfeng Yao School of Data Science, The Chinese
University of Hong Kong (Shenzhen). E-mail<EMAIL_ADDRESS>Wangjun Yuan
Department of Mathematics and Statistics, University of Ottawa. E-mail:
<EMAIL_ADDRESS>
###### Abstract

We study the eigenvalue distributions for sums of independent rank-one
$k$-fold tensor products of large $n$-dimensional vectors. Previous results in
the literature assume that $k=o(n)$ and show that the eigenvalue distributions
converge to the celebrated Marčenko-Pastur law under appropriate moment
conditions on the base vectors. In this paper, motivated by quantum
information theory, we study the regime where $k$ grows faster, namely
$k=O(n)$. We show that the moment sequences of the eigenvalue distributions
have a limit, which is different from the Marčenko-Pastur law. As a byproduct,
we show that the Marčenko-Pastur law limit holds if and only if $k=o(n)$ for
this tensor model. The approach is based on the method of moments.

AMS 2000 subject classifications: Primary 60B20; Secondary 15B52.

Keywords and phrases: Large $k$-fold tensors; Eigenvalue distribution;
Marčenko-Pastur law; Quantum information theory.

##  1 Introduction

For $n\in\mathbb{N}$, let $\\{\xi_{1},\ldots,\xi_{n}\\}$ be a family of i.i.d.
centered complex random variables with unit variance. Denote
$\mathbf{y}=\frac{1}{\sqrt{n}}(\xi_{1},\ldots,\xi_{n})\in\mathbb{C}^{n}$. Let
$\\{\mathbf{y}_{\alpha}^{(l)}:1\leq\alpha\leq m,1\leq l\leq k\\}$ be a family
of i.i.d. copies of $\mathbf{y}$, and let
$Y_{\alpha}=\mathbf{y}_{\alpha}^{(1)}\otimes\cdots\otimes\mathbf{y}_{\alpha}^{(k)}$
for $1\leq\alpha\leq m$. Let $\\{\tau_{1},\tau_{2},\ldots\\}$ be a sequence of
real numbers, and $Y=(Y_{1},\ldots,Y_{m})$ be a $n^{k}\times m$ matrix.
Consider the $n^{k}\times n^{k}$ Hermitian matrix

$\displaystyle
M_{n,k,m}=\sum_{\alpha=1}^{m}\tau_{\alpha}Y_{\alpha}Y_{\alpha}^{*}.$ (1.1)

Therefore, each $n^{k}$-dimensional vector $Y_{\alpha}$ is a $k$-fold tensor
product of $n$-dimensional i.i.d. vectors, and $M_{n,k,m}$ is a sum of $m$
independent rank-$1$ Hermitian matrices of dimension $n^{k}$.

The simplest case of $k=1$ and $\tau_{\alpha}\equiv 1$ was studied in the
seminal paper [MP67] where the celebrated Marčenko-Pastur law was derived
under appropriate moment conditions on the entries of the base vector
$\mathbf{y}$ and the limiting scheme where $n\to\infty$ and $m/n\to c>0$. Many
subsequent improvements on the Marčenko-Pastur law appeared in the literature,
including [Silv95], [BaiZhou08] and [Pajor09]. These papers were able to deal
with the model (1.1) with general sequence
$\\{\tau_{\alpha}:\alpha\in\mathbb{N}_{+}\\}$. Notably, the latter paper
extended the law to a broad family of $\mathbf{y}$-vectors, called good
vectors, that includes the current setting with i.i.d. components. Later, for
the setting $\tau_{\alpha}\equiv 1$, the necessary and sufficient conditions
on $Y_{1}$ that the Marčenko-Pastur law serves as the limiting spectral
distribution (LSD) of $M_{n,1,m}$ were carried out in [Yaskov2016].

Recently, [Lytova2018] considered the $k$-fold tensor model $M_{n,k,m}$ and
established a LSD for its $n^{k}$ real-valued eigenvalues. For the special
case $\tau_{\alpha}\equiv 1$, the LSD is exactly the Marčenko-Pastur law. A
central limit theorem (CLT) is also established for a class of linear spectral
statistics following the approach of [LytovaPastur09]. The main setup
[Lytova2018] is that the tensor product number $k$ must be small enough
compared to the space dimension $n$. Precisely, $k/n\to 0$ is required for the
validity of the LSD while $k\equiv 2$ is required when $n\to\infty$ for the
validity of the CLT. It is natural to consider the setting where $k$ is large.
Noting that large $k$ means more dependence among the entries of the vector
$Y_{1}$, it is expected that the LSD of $M_{n,k,m}$ does not obey the
Marčenko-Pastur law when $k$ is large enough. However, the martingale moment
bound employed [Lytova2018] is less useful when $k$ is large, and the method
cannot be directly extended to the case $k=O(n)$. The present paper deals with
the case $k=O(n)$ for the model (1.1) and shows that the empirical spectral
distribution (ESD) of $M_{n,k,m}$ with $\tau_{\alpha}\equiv 1$ converges to
the Marčenko-Pastur law if and only if $k=o(n)$. Therefore, the matrix
$M_{n,k,m}$ with $k=O(n)$ can be seen as a new example of _bad vectors_ , for
which the necessary and sufficient condition in [Yaskov2016] does not hold.

Another motivation for studying the model (1.1) is from quantum information
theory. In [Hastings2012], the model $M_{n,k,m}$ was introduced as a quantum
analog of the classical probability problem of allocating $r$ balls into $s$
bins. The random vector $Y_{1}$ was interpreted as random product states in
$(\mathbb{C}^{n})^{\otimes k}$. When $k$ is fixed and $m=cn^{k}$ for some
$c>0$, [Hastings2012] established the convergence in expectation of the
normalized trace of moments $n^{-k}\mathrm{Tr}M_{n,k,m}^{p}$, which coincide
with the corresponding moments of the Marčenko-Pastur law. In quantum physics
and quantum information theory, it is natural to investigate the behavior of a
large number of quantum states. In [Collins2011], the quantum entanglement of
structured random states was characterized, and the spectral density of the
reduced state was studied when the number of the quantum states $k$ is large.
In [Collins2013], the asymptotic behavior of the average entropy of
entanglement for elements of an ensemble of random states associated with a
graph was studied when the dimension of the quantum subsystem is large.

This paper considers the scenario where $k$ grows to infinity quickly. Namely,
we assume that there exist constants $c,d\in(0,\infty)$, such that

$\displaystyle\dfrac{k}{n}\to d,\quad\dfrac{m}{n^{k}}\to c.$ (1.2)

Let us add one more word of motivation for the choice of regime $k=O(n)$. In
hindsight, this is a natural threshold in our quest for limiting theorems, and
from the point of view of probability theory, our result extends existing
results. However, the need for large $k$ is real in Quantum Information
Theory. Actually, a typical real world scenario would be $n$ fixed (the
dimension of the system and $k$ would go to infinity – the system can be used
many times, i.e., one works on regularized quantities. In practice, we do not
know how to fix $n$ and send $k$ to infinity, so we take this scenario as our
next model.

Our approach is based on the method of moments. Under appropriate moment
conditions on the base variable $\xi_{1}$ and the sequence of coefficients
$\\{\tau_{\alpha}\\}$, we derive the limits for the spectral moments of
$M_{n,k,m}$ under the limiting scheme (1.2). A striking fact from our result
is that contrary to all the previous results, [Lytova2018], the limiting
spectral moments found here involve the $4$th moment of the base variable
$\xi_{1}$.

##  2 Almost sure convergence of spectral moments

For fixed $\alpha=(\alpha_{1},\ldots,\alpha_{p})$, for each value $t$
appearing in $\alpha$, we count its frequency by

$\displaystyle\mathrm{deg}_{t}(\alpha)=\left|\\{j\in[p]:\alpha_{j}=t\\}\right|.$
(2.1)

The main result of the paper is the following theorem.

######  Theorem 2.1.

Assume $d>0$ and the following moment conditions hold.

  1. 1.

For all $p\in\mathbb{N}$. $p$-th moment $m_{p}=E[|\xi_{1}|^{p}]<\infty$.

  2. 2.

For all $q\in\mathbb{N}$,

$\displaystyle\dfrac{1}{m}\sum_{j=1}^{m}\tau_{j}^{q}\to m_{q}^{(\tau)},\
m\to\infty.$ (2.2)

We have

  1. (i)

$\displaystyle\lim_{n\to\infty}\dfrac{1}{n^{k}}\mathbb{E}\big{[}\mathrm{Tr}M_{n,k,m}^{p}\big{]}=$
$\displaystyle\sum_{s=1}^{p}c^{s}\sum_{\alpha\in\mathcal{C}_{s,p}^{(1)}}\left(\prod_{t=1}^{s}m_{\mathrm{deg}_{t}(\alpha)}^{(\tau)}\right)\exp\left(d(m_{4}-1)\sum_{t=1}^{s}\binom{\mathrm{deg}_{t}(\alpha)}{2}\right).$
(2.3)

Here $\mathcal{C}_{s,p}^{(1)}$ is a special class of graphs that will be
defined in the course of the proof (see Lemma 3.1).

  2. (ii)

For all fixed $p\in\mathbb{N}_{+}$, if $k\geq 2$, we have

$\displaystyle\sum_{n=1}^{\infty}\mathrm{Var}\left(\dfrac{1}{n^{k}}\mathrm{Tr}M_{n,k,m}^{p}\right)<\infty.$

In particular, (i) and (ii) imply that $n^{-k}\mathrm{Tr}M_{n,k,m}^{p}$
converge almost surely to the limit given in the r.h.s. of (2.3).

The proof of the theorem is given in Section 3.

######  Remark 2.1.

Here, we require the random variable $\xi_{1}$ to have finite moments of any
order. For most matrix models, such moment conditions can be removed by a
standard truncation argument. However, the centralization step in the
truncation argument fails for our matrix model. More precisely, let
$\hat{\mathbf{y}}_{\alpha}^{(l)}$ be the truncated vector for all
$1\leq\alpha\leq m$ and $1\leq l\leq k$, then we have the following identity

$\displaystyle\hat{\mathbf{y}}_{\alpha}^{(1)}\otimes\cdots\otimes\hat{\mathbf{y}}_{\alpha}^{(k)}-\big{(}\hat{\mathbf{y}}_{\alpha}^{(1)}-\mathbb{E}\big{[}\hat{\mathbf{y}}_{\alpha}^{(1)}\big{]}\big{)}\otimes\cdots\otimes\big{(}\hat{\mathbf{y}}_{\alpha}^{(k)}-\mathbb{E}\big{[}\hat{\mathbf{y}}_{\alpha}^{(k)}\big{]}\big{)}$
$\displaystyle=$
$\displaystyle\sum_{l=1}^{k}\hat{\mathbf{y}}_{\alpha}^{(1)}\otimes\cdots\otimes\hat{\mathbf{y}}_{\alpha}^{(l-1)}\otimes\mathbb{E}\big{[}\hat{\mathbf{y}}_{\alpha}^{(l)}\big{]}\otimes\big{(}\hat{\mathbf{y}}_{\alpha}^{(l+1)}-\mathbb{E}\big{[}\hat{\mathbf{y}}_{\alpha}^{(l+1)}\big{]}\big{)}\otimes\cdots\otimes\big{(}\hat{\mathbf{y}}_{\alpha}^{(k)}-\mathbb{E}\big{[}\hat{\mathbf{y}}_{\alpha}^{(k)}\big{]}\big{)}.$
(2.4)

Note that for $1\leq l\leq k$, the $n^{k}\times m$ matrix, whose $\alpha$-th
column is

$\displaystyle\hat{\mathbf{y}}_{\alpha}^{(1)}\otimes\cdots\otimes\hat{\mathbf{y}}_{\alpha}^{(l-1)}\otimes\mathbb{E}\big{[}\hat{\mathbf{y}}_{\alpha}^{(l)}\big{]}\otimes\big{(}\hat{\mathbf{y}}_{\alpha}^{(l+1)}-\mathbb{E}\big{[}\hat{\mathbf{y}}_{\alpha}^{(l+1)}\big{]}\big{)}\otimes\cdots\otimes\big{(}\hat{\mathbf{y}}_{\alpha}^{(k)}-\mathbb{E}\big{[}\hat{\mathbf{y}}_{\alpha}^{(k)}\big{]}\big{)},$

has rank at most $n^{k-1}$. Thus, the $n^{k}\times m$ matrix, whose
$\alpha$-th column is (2.1), has rank at most $kn^{k-1}$. Hence, by [Bai2010,
Theorem A.44], the sup norm of the difference of the cumulative distribution
functions in the centralization step does not exceed $k/n$, which is not
negligible when $d>0$.

Let $\theta=e^{d(m_{4}-1)}$. The limit moments in (2.3), say $\gamma_{p}$, are
polynomial functions of $\theta$. The first four moments are

$\displaystyle\gamma_{1}$ $\displaystyle=1,$ $\displaystyle\gamma_{2}$
$\displaystyle=c\theta+c^{2},$ $\displaystyle\gamma_{3}$
$\displaystyle=c\theta^{3}+3c^{2}\theta+c^{3},$ $\displaystyle\gamma_{4}$
$\displaystyle=c\theta^{6}+4c^{2}\theta^{3}+2c^{2}\theta^{2}+6c^{3}\theta+c^{4}.$

However, for higher exponent $p$, some computing code is needed to find an
explicit expression for $\gamma_{p}$.

######  Remark 2.2.

The limiting moment sequence $(\gamma_{p})$ grow to infinity extremely fast
with $p$. To see this, let $\tau_{\alpha}\equiv 1$. Then $\gamma_{p}$ is lower
bounded by the first term ($s=1$) in (2.3) is $c\theta^{p(p-1)/2}$. Thus the
Carleman’s condition, that is,
$\sum_{p=1}^{\infty}\gamma_{2p}^{-1/(2p)}=\infty$, is not satisfied (see also
[Lin2017]). In particular, it is not clear whether the moment sequence
$(\gamma_{p})$ uniquely determines a limiting distribution. However, by the
convergence of the moments, we know that the sequence of eigenvalue
distributions is tight (almost surely).

As a byproduct of our moment method, we give an alternative method for
deriving a limiting spectral distribution in the case of $d=0$, a result
already given in [Lytova2018] using the Stieltjes transform method.

######  Proposition 2.1.

Assume $d=0$. We have

  1. (i)

$\displaystyle\lim_{n\to\infty}\dfrac{1}{n^{k}}\mathbb{E}\big{[}\mathrm{Tr}M_{n,k,m}^{p}\big{]}=\sum_{s=1}^{p}c^{s}\sum_{\alpha\in\mathcal{C}_{s,p}^{(1)}}\left(\prod_{t=1}^{s}m_{\mathrm{deg}_{t}(\alpha)}^{(\tau)}\right).$
(2.5)

Here $\mathcal{C}_{s,p}^{(1)}$ is a special class of graphs defined later in
Lemma 3.1.

  2. (ii)

For all fixed $p\in\mathbb{N}_{+}$, if $k\geq 2$, we have

$\displaystyle\sum_{n=1}^{\infty}\mathrm{Var}\left(\dfrac{1}{n^{k}}\mathrm{Tr}M_{n,k,m}^{p}\right)<\infty.$

In particular, (i) and (ii) imply that $n^{-k}\mathrm{Tr}M_{n,k,m}^{p}$
converge almost surely to the limit given in the r.h.s. of (2.5).

The proof of the proposition is given in Appendix A.

Finally, comparing the two cases $d>0$ and $d=0$, it is worth noticing that
the fourth moment $m_{4}$ contributes to the limiting spectral moments only in
the case of $d>0$ (Theorem 2.1).

##  3 Proof of Theorem 2.1

Before proceeding to the proof, we introduce some preliminaries on graph
combinatorics. We first introduce some terminologies and notations from graph
theory. Denote $[m]$ by the set of integers in the closed interval $[1,m]$. We
call $\alpha=(\alpha_{1},\ldots,\alpha_{p})\in[m]^{p}$ a sequence of length
$p$ with vertices $\alpha_{j}$ for $1\leq j\leq p$. We denote by $|\alpha|$
the number of distinct elements in $\alpha$. If $s=|\alpha|$, then we call
$\alpha$ an $s$-sequence. Two sequence are equivalent if one becomes the other
by a suitable permutation on $[m]$. The sequence $\alpha$ is canonical if
$\alpha_{1}=1$ and $\alpha_{u}\leq\max\\{\alpha_{1},\ldots,\alpha_{u-1}\\}+1$
for $u\geq 2$. We denote by $\mathcal{C}_{s,p}$ the set of all canonical
$s$-sequences of length $p$, and denote $\mathcal{J}_{s,p}(m)$ by the set of
all $s$-sequences $\alpha\in[m]^{p}$. Then

$\displaystyle[m]^{p}=\bigcup_{s=1}^{p}\mathcal{J}_{s,p}(m).$ (3.1)

From the definition above, one can see that the set of distinct vertices of a
canonical $s$-sequence is $[s]$. Denote by $\mathcal{I}_{s,m}$ the set of
injective maps from $[s]$ to $[m]$. For a canonical $s$-sequence $\alpha$ and
a map $\varphi\in\mathcal{I}_{s,m}$, we call $\varphi(\alpha)$ the
$s$-sequence $(\varphi(\alpha_{1}),\ldots,\varphi(\alpha_{p}))$. For each
canonical $s$-sequence, its image under the maps in $\mathcal{I}_{s,m}$ gives
all its equivalent sequence, and hence its equivalent class of sequence in
$[m]^{p}$ has exactly $m(m-1)\cdots(m-s+1)$ distinct elements.

Let $\alpha=(\alpha_{1},\ldots,\alpha_{p})\in[m]^{p}$ be a fixed canonical
$s$-sequence. For $i_{1}=(i_{1}^{(1)},\ldots,i_{1}^{(p)})\in[n]^{p}$, draw two
parallel lines, referring to the $\alpha$-line and the $i$-line. Plot
$i_{1}^{(1)},\ldots,i_{1}^{(p)}$ on the $i$-line and
$\alpha_{1},\ldots,\alpha_{p}$ on the $\alpha$-line. Draw $p$ down edges from
$\alpha_{u}$ to $i_{1}^{(u)}$ and $p$ up edges from $i_{1}^{(u)}$ to
$\alpha_{u+1}$ for $1\leq u\leq p$. Here, we use the convention that
$\alpha_{1}=\alpha_{p+1}$. We call a down edge from $\alpha_{u}$ to
$i_{1}^{(u)}$ a down innovation if $i_{1}^{(u)}$ is different from
$i_{1}^{(1)},\ldots,i_{1}^{(u-1)}$. We also call an up edge from $i_{1}^{(u)}$
to $\alpha_{u+1}$ an up innovation if $\alpha_{u+1}$ is different from
$\alpha_{1},\ldots,\alpha_{u}$. We denote the graph by $g(i_{1},\alpha)$ and
call such graph a $\Delta(p;\alpha)$-graph. Two graphs $g(i_{1},\alpha)$ and
$g(i_{1}^{\prime},\alpha)$ are said to be equivalent if the two sequences
$i_{1}$ and $i_{1}^{\prime}$ are equivalent. We write $g(i_{1},\alpha)\sim
g(i_{1}^{\prime},\alpha)$ if they are equivalent. For each equivalent class,
we choose the canonical graph such that
$i_{1}=(i_{1}^{(1)},\ldots,i_{1}^{(p)})\in[n]^{p}$ is a canonical $r$-sequence
for some $r\in\mathbb{N}_{+}$. A canonical $\Delta(p;\alpha)$-graph is denoted
by $\Delta(p,r,s;\alpha)$ if it has $r$ noncoincident $i$-vertices and $s$
noncoincident $\alpha$-vertices. We classify $\Delta(p,r,s;\alpha)$-graphs
into the following five categories.

  1. $\Delta_{1}(p,s;\alpha)$. $\Delta(p;\alpha)$-graphs in which each down edge must coincide with one and only one up edge. If we glue the coincident edges, the resulting graph is a tree of $p$ edges and $p+1$ vertices, which implies $r+s=p+1$.

  2. $\Delta_{2}(p,r,s;\alpha)$. $\Delta(p;\alpha)$-graphs that contain at least one single edge.

  3. $\Delta_{3}(p,s;\alpha)$. $\Delta(p;\alpha)$-graphs such that the number of the edges between two vertices is $0$ or $2$. If we glue the coincident edges, the resulting graph is a connected graph with exactly one cycle. The graph has $p$ edges and $p$ vertices, which implies $r+s=p$.

  4. $\Delta_{4}(p,s;\alpha)$. $\Delta(p;\alpha)$-graphs that have two up edges and two down edges with the same endpoints and all other down edges coincide with one and only one up edge. If we glue the coincident edges, the resulting graph is a tree of $p-1$ edges and $p$ vertices, implying $r+s=p$.

  5. $\Delta_{5}(p,r,s;\alpha)$. $\Delta(p;\alpha)$-graphs that do not belong to the categories above. In this case, the graph has at most $p-1$ vertices, since the in-degree equals to out-degree and at least $2$ for all vertices. Thus, $r+s\leq p-1$.

Next, we determine the number of sequence $i_{1}\in\mathcal{C}_{p+1-s,p}$ such
that $g(i_{1},\alpha)\in\Delta_{1}(p,s;\alpha)$ for given sequence
$\alpha\in\mathcal{C}_{s,p}$. We have the following lemma, which is motivated
by [Bai2010, Lemma 3.4].

######  Lemma 3.1.

For any sequence $\alpha\in\mathcal{C}_{s,p}$, there is at most one sequence
$i_{1}\in\mathcal{C}_{p+1-s,p}$ such that
$g(i_{1},\alpha)\in\Delta_{1}(p,s;\alpha)$. We denote by
$\mathcal{C}_{s,p}^{(1)}$ the set of such canonical sequences $\alpha$. Then
the number of the elements in $\mathcal{C}_{s,p}^{(1)}$ is

$\displaystyle\dfrac{1}{p}\binom{p}{s-1}\binom{p}{s}.$

###### Proof.

We denote

$\displaystyle\Delta_{1}(p,s)=\bigcup_{\alpha\in\mathcal{C}_{s,p}}\Delta_{1}(p,s;\alpha).$

We define a pair of characteristic sequences $\\{u_{1},\ldots,u_{p}\\}$ and
$\\{d_{1},\ldots,d_{p}\\}$ by

$\displaystyle
u_{l}=\begin{cases}1,&\alpha_{l+1}=\max\\{\alpha_{1},\ldots,\alpha_{l}\\}+1,\\\
0,&\mathrm{otherwise},\end{cases}$ (3.2)

and

$\displaystyle
d_{l}=\begin{cases}-1,&\alpha_{l}\notin\\{1,\alpha_{l+1},\ldots,\alpha_{p}\\},\\\
0,&\mathrm{otherwise}.\end{cases}$ (3.3)

By definition, we always have $u_{p}=0$, and since $\alpha_{1}=1$, we always
have $d_{1}=0$.

For a graph belongs to $\Delta_{1}(p,s)$, there are exactly $s-1$ up
innovations and hence there are $s-1$ $u$-variables equal to $1$ and $s-1$
$d$-variables equal to $-1$. From its definition, one sees that $d_{l}=-1$
means that after plotting the $l$-th down edge $(\alpha_{l},i_{1}^{(l)})$, the
future path will never revisit the vertices $\alpha_{l}$, which means that the
edge $(\alpha_{l},i_{1}^{(l)})$ must coincide with the up innovation leading
to the vertex $\alpha_{l}$. Since there are $r=p+1-s$ down innovations to lead
out the $r$ $i_{1}$-vertices, $d_{l}=0$ implies that the edge
$(\alpha_{l},i_{1}^{(l)})$ must be a down innovation. Therefore, $d_{l}=-1$
must follow a $u_{j}=1$ for some $j<l$, which leads to the restriction of the
pair of characteristic sequences

$\displaystyle u_{1}+\cdots+u_{l-1}+d_{2}+\cdots+d_{l}\geq 0,\qquad 2\leq
l\leq p.$ (3.4)

Next, we show that each pair of characteristic sequences satisfying (3.4)
defines a graph in $\Delta_{1}(p,s)$ uniquely.

Firstly, we have $i_{1}^{(1)}=1$. Besides, $\alpha_{2}=1$ if $u_{1}=0$ and
$\alpha_{2}=2$ if $u_{1}=1$. We use induction to determine the unique graph in
$\Delta_{1}(p,s)$. Suppose that the first $l$ pairs of the down and up edges
are uniquely determined by the two sequences $\\{u_{1},\ldots u_{l}\\}$ and
$\\{d_{1},\ldots d_{l}\\}$, and the subgraph of the first $l$ pairs of down
and up edges satisfies the following properties

  1. (a1)

The subgraph is connected, and the unidirectional noncoincident edges form a
tree.

  2. (a2)

If $\alpha_{l+1}=1$, then each down edge coincides with an up edge, which
means that the subgraph not have single innovations.

  3. (a3)

If $\alpha_{l+1}\neq 1$, then from the vertex $\alpha_{1}$ to $\alpha_{l+1}$,
there is only one path (chain without cycles) of down-up-down-up single
innovations and all other down edges coincide with an up edge.

We consider the following four cases to determine the $(l+1)$-th pair of down
and up edges.

  1. Case 1.

$d_{l+1}=0$ and $u_{l+1}=1$. Then both edges of the $(l+1)$-th pair are
innovations, which implies that $i_{1}^{(l+1)}=|\\{j\leq l+1:d_{j}=0\\}|$ and
$\alpha_{l+2}=1+|\\{j\leq l+1:u_{j}=1\\}|$. After adding the two edges, the
subgraph with the first $l+1$ pairs of down and up edges satisfies the
properties (a1) - (a3).

  2. Case 2.

$d_{l+1}=0$ and $u_{l+1}=0$. Then the down edge $(\alpha_{l+1},i_{1}^{(l+1)})$
is an innovation so $i_{1}^{(l+1)}=|\\{j\leq l+1:d_{j}=0\\}|$. The up edge
$(i_{1}^{(l+1)},\alpha_{l+2})$ is not an innovation so $\alpha_{l+2}$
coincides with some vertex $\alpha_{j}$ for $1\leq j\leq l+1$. If
$\alpha_{j}\neq\alpha_{l+1}$, then there is a path
$i_{1}^{(l)}\to\alpha_{l+1}\to i_{1}^{(l+1)}\to\alpha_{j}$. Also note that
there should be a path connecting $\alpha_{j}$ and $i_{1}^{(l)}$ in the
subgraph of first $l$ pairs of down and up edges. The two paths with
undirectional noncoincident edges will lead to a circle, which is a
contradiction. Hence, $\alpha_{l+2}=\alpha_{j}=\alpha_{l+1}$ and the
$(l+1)$-th up edge coincide with the $(l+1)$-th down edge. After adding the
two edges, the subgraph with the first $l+1$ pairs of down and up edges
satisfies the properties (a1) - (a3).

  3. Case 3.

$d_{l+1}=-1$ and $u_{l+1}=1$. By (3.4), we have

$\displaystyle u_{1}+\cdots+u_{l}+d_{2}+\cdots+d_{l}\geq 1.$

Hence, there is at least one vertex in $\\{\alpha_{2},\ldots,\alpha_{l+1}\\}$
which is not $\alpha_{1}$, such that the vertex will be visited in the last
$p-(l+1)$ pairs of down and up edges. Thus, by property (a1) and (a2), we have
$\alpha_{l+1}\neq\alpha_{1}$. Hence, there must be a single up innovation
leading to the vertex $\alpha_{l+1}$. We denote the up innovation by
$(i_{1}^{(j)},\alpha_{l+1})$ for some $1\leq j\leq l$. Hence, we choose
$i_{1}^{(l+1)}=i_{1}^{(j)}$, which means that the down edge starting from
$\alpha_{l+1}$ coincides with the up innovation leading to $\alpha_{l+1}$.
Besides, the $(l+1)$-th up edge is an innovation, which starts from
$i_{1}^{(l+1)}$ and ends in $\alpha_{l+2}=1+|\\{j\leq l+1:u_{j}=1\\}|$. After
adding the two edges, the subgraph with the first $l+1$ pairs of down and up
edges satisfies the properties (a1) - (a3).

  4. Case 4.

$d_{l+1}=-1$ and $u_{l+1}=0$. As discussed in Case 3, the $(l+1)$-th down edge
coincides with the only up innovation ended at $\alpha_{l+1}$. Before this up
innovation, there must be a single down innovation by property (a3). Then the
up edge can be drawn to coincide with this down innovation. If the path of
single innovations of the subgraph with first $l$ pairs of down and up edges
has only one pair of down-up innovations, then $\alpha_{l+2}=1$, and hence the
subgraph with first $l+1$ pairs of down and up edges has no single
innovations, which implies that the properties (a1) and (a2) hold. Otherwise,
$\alpha_{l+2}\neq 1$ and the subgraph with first $l+1$ pairs of down and up
edges satisfies properties (a1) and (a3).

By induction, it is shown that two characteristic sequences
$\\{u_{1},\ldots,u_{p}\\}$ and $\\{d_{1},\ldots,d_{p}\\}$ satisfying (3.4)
determine a graph in $\Delta_{1}(p,s)$ uniquely.

For a given sequence
$\alpha=(\alpha_{1},\ldots,\alpha_{p})\in\mathcal{C}_{s,p}$, the two
characteristic sequences are uniquely determined by (3.2) and (3.3). This
shows that there is at most one sequence $i_{1}\in\mathcal{C}_{p+1-s,p}$ such
that $g(i_{1},\alpha)\in\Delta_{1}(p,s;\alpha)$. More precisely, there is
exactly one sequence $i_{1}\in\mathcal{C}_{p+1-s,p}$ such that
$g(i_{1},\alpha)\in\Delta_{1}(p,s;\alpha)$ if and only if the pair of two
characteristic sequences satisfies (3.4).

Moreover, by [Bai2010, Lemma 3.5], the number of the elements in
$\mathcal{C}_{s,p}^{(1)}$ equals to the number of graphs in

$\displaystyle\bigcup_{\alpha\in\mathcal{C}_{s,p}}\Delta_{1}(p,s;\alpha),$

which is

$\displaystyle\dfrac{1}{s}\binom{p}{s-1}\binom{p-1}{s-1}=\dfrac{1}{p}\binom{p}{s-1}\binom{p}{s}.$

∎

######  Remark 3.1.

There exists $\alpha\in\mathcal{C}_{s,p}\setminus\mathcal{C}_{s,p}^{(1)}$,
such that the $u$ sequence and $d$ sequence defined by (3.2) and (3.3)
respectively satisfy the restriction (3.4). Consider the canonical
$2$-sequence $\alpha=(1,2,1,2)$, the corresponding $u$ sequence is
$\\{1,0,0,0\\}$ and the corresponding $d$ sequence is $\\{0,0,0,-1\\}$, which
satisfy (3.4). However, the graph of $\alpha$ belongs to
$\Delta_{3}(4,2;\alpha)$, which means that
$\alpha\in\mathcal{C}_{2,4}\setminus\mathcal{C}_{2,4}^{(1)}$. Indeed, the
$\alpha$ sequence of the graph in $\Delta_{1}(4,2;\alpha)$ corresponding to
the pair of characteristic sequence is $(1,2,2,2)$.

###  3.1 Proof of (i)

We will use the index $\alpha,\beta$ for the columns of $Y$, which should be
in $[m]$. We will also use the index $\mathbf{i}$, a multiple index of the
form $\mathbf{i}=(i_{1},\ldots,i_{k})$, for the rows of $Y$. Then $\mathbf{i}$
should be in $[n^{k}]$. For any $p\in\mathbb{N}$, we compute the moment

$\displaystyle\dfrac{1}{n^{k}}\mathbb{E}\big{[}\mathrm{Tr}M_{n,k,m}^{p}\big{]}.$

We use the convention that $\mathbf{i}^{(p+1)}=\mathbf{i}^{(1)}$. We have

$\displaystyle\dfrac{1}{n^{k}}\mathbb{E}\big{[}\mathrm{Tr}M_{n,k,m}^{p}\big{]}=$
$\displaystyle\dfrac{1}{n^{k}}\sum_{\alpha_{1},\ldots,\alpha_{p}=1}^{m}\left(\prod_{t=1}^{p}\tau_{\alpha_{t}}\right)\mathbb{E}\Big{[}\mathrm{Tr}\big{(}Y_{\alpha_{1}}Y_{\alpha_{1}}^{*}\cdots
Y_{\alpha_{p}}Y_{\alpha_{p}}^{*}\big{)}\Big{]}$ $\displaystyle=$
$\displaystyle\dfrac{1}{n^{k}}\sum_{\alpha_{1},\ldots,\alpha_{p}=1}^{m}\left(\prod_{t=1}^{p}\tau_{\alpha_{t}}\right)\mathbb{E}\Bigg{[}\sum_{\mathbf{i}^{(1)},\ldots,\mathbf{i}^{(p)}=1}^{n^{k}}\prod_{t=1}^{p}Y_{\mathbf{i}^{(t)}\alpha_{t}}\overline{Y_{\mathbf{i}^{(t+1)}\alpha_{t}}}\Bigg{]}$
$\displaystyle=$
$\displaystyle\dfrac{1}{n^{k}}\sum_{\alpha_{1},\ldots,\alpha_{p}=1}^{m}\left(\prod_{t=1}^{p}\tau_{\alpha_{t}}\right)\mathbb{E}\Bigg{[}\sum_{\mathbf{i}^{(1)},\ldots,\mathbf{i}^{(p)}=1}^{n^{k}}\prod_{t=1}^{p}\prod_{l=1}^{k}\bigg{(}\big{(}\mathbf{y}_{\alpha_{t}}^{(l)}\big{)}_{i^{(t)}_{l}}\overline{\big{(}\mathbf{y}_{\alpha_{t}}^{(l)}\big{)}_{i^{(t+1)}_{l}}}\bigg{)}\Bigg{]}$
$\displaystyle=$
$\displaystyle\dfrac{1}{n^{k}}\sum_{\alpha_{1},\ldots,\alpha_{p}=1}^{m}\left(\prod_{t=1}^{p}\tau_{\alpha_{t}}\right)\mathbb{E}\Bigg{[}\prod_{l=1}^{k}\sum_{i_{l}^{(1)},\ldots,i_{l}^{(p)}=1}^{n}\prod_{t=1}^{p}\bigg{(}\big{(}\mathbf{y}_{\alpha_{t}}^{(l)}\big{)}_{i^{(t)}_{l}}\overline{\big{(}\mathbf{y}_{\alpha_{t}}^{(l)}\big{)}_{i^{(t+1)}_{l}}}\bigg{)}\Bigg{]}$
$\displaystyle=$
$\displaystyle\dfrac{1}{n^{k}}\sum_{\alpha_{1},\ldots,\alpha_{p}=1}^{m}\left(\prod_{t=1}^{p}\tau_{\alpha_{t}}\right)\left(\mathbb{E}\left[\sum_{i_{1}^{(1)},\ldots,i_{1}^{(p)}=1}^{n}\prod_{t=1}^{p}\bigg{(}\big{(}\mathbf{y}_{\alpha_{t}}^{(1)}\big{)}_{i^{(t)}_{1}}\overline{\big{(}\mathbf{y}_{\alpha_{t}}^{(1)}\big{)}_{i^{(t+1)}_{1}}}\bigg{)}\right]\right)^{k}.$
(3.5)

Here, we use the i.i.d. setting in the last equality.

For two sequences $\alpha=(\alpha_{1},\ldots,\alpha_{p})\in[m]^{p}$ and
$i_{1}=(i_{1}^{(1)},\ldots,i_{1}^{(p)})\in[n]^{p}$, we denote

$\displaystyle
E(i_{1},\alpha)=\mathbb{E}\left[\prod_{t=1}^{p}\bigg{(}\big{(}\mathbf{y}_{\alpha_{t}}^{(1)}\big{)}_{i^{(t)}_{1}}\overline{\big{(}\mathbf{y}_{\alpha_{t}}^{(1)}\big{)}_{i^{(t+1)}_{1}}}\bigg{)}\right].$
(3.6)

An observation is that $E(i_{1},\alpha)=E(i_{1}^{\prime},\alpha^{\prime})$ if
the two sequences $i_{1}$ and $\alpha$ are equivalent to $i_{1}^{\prime}$ and
$\alpha^{\prime}$ respectively. Hence, by (3.1) and (3.1), we have

$\displaystyle\dfrac{1}{n^{k}}\mathbb{E}\big{[}\mathrm{Tr}M_{n,k,m}^{p}\big{]}=$
$\displaystyle\dfrac{1}{n^{k}}\sum_{s=1}^{p}\sum_{\alpha\in\mathcal{J}_{s,p}(m)}\left(\prod_{t=1}^{p}\tau_{\alpha_{t}}\right)\left(\sum_{r=1}^{p}\sum_{i_{1}\in\mathcal{J}_{r,p}(n)}E(i_{1},\alpha)\right)^{k}$
$\displaystyle=$
$\displaystyle\dfrac{1}{n^{k}}\sum_{s=1}^{p}\sum_{\alpha\in\mathcal{C}_{s,p}}\left(\sum_{\varphi\in\mathcal{I}_{s,m}}\prod_{t=1}^{p}\tau_{\varphi(\alpha_{t})}\right)\left(\sum_{r=1}^{p}n\cdots(n-r+1)\sum_{i_{1}\in\mathcal{C}_{r,p}}E(i_{1},\alpha)\right)^{k}.$
(3.7)

We first compute the sum on $i_{1}$ in (3.1). For any sequences
$\alpha\in\mathcal{C}_{s,p}$, we can split the sum according to the category
of the graph $g(i_{1},\alpha)$ in the following way:

$\displaystyle\sum_{i_{1}\in\mathcal{C}_{r,p}}E(i_{1},\alpha)=$
$\displaystyle\sum_{i_{1}\in\mathcal{C}_{r,p}\atop
g(i_{1},\alpha)\in\Delta_{1}(p,s;\alpha)}E(i_{1},\alpha)+\sum_{i_{1}\in\mathcal{C}_{r,p}\atop
g(i_{1},\alpha)\in\Delta_{3}(p,s;\alpha)}E(i_{1},\alpha)$
$\displaystyle+\sum_{i_{1}\in\mathcal{C}_{r,p}\atop
g(i_{1},\alpha)\in\Delta_{4}(p,s;\alpha)}E(i_{1},\alpha)+\sum_{i_{1}\in\mathcal{C}_{r,p}\atop
g(i_{1},\alpha)\in\Delta_{5}(p,r,s;\alpha)}E(i_{1},\alpha)$ (3.8)

We deal with the four terms on the right hand side of (3.1) one by one. For
$i_{1}\in\mathcal{C}_{r,p}$ with $g(i_{1},\alpha)\in\Delta_{1}(p,s;\alpha)$,
by the definition of $\Delta_{1}(p,s;\alpha)$, we have
$E(i_{1},\alpha)=n^{-p}$ and $p=r+s-1$. Hence,

$\displaystyle\sum_{i_{1}\in\mathcal{C}_{r,p}\atop
g(i_{1},\alpha)\in\Delta_{1}(p,s;\alpha)}E(i_{1},\alpha)=n^{1-r-s}\sum_{i_{1}\in\mathcal{C}_{r,p}\atop
g(i_{1},\alpha)\in\Delta_{1}(p,s;\alpha)}1.$ (3.9)

For $i_{1}\in\mathcal{C}_{r,p}$ with
$g(i_{1},\alpha)\in\Delta_{3}(p,s;\alpha)$, by the definition of
$\Delta_{3}(p,s;\alpha)$, we have $E(i_{1},\alpha)=n^{-p}$ and $p=r+s$. Hence,

$\displaystyle\sum_{i_{1}\in\mathcal{C}_{r,p}\atop
g(i_{1},\alpha)\in\Delta_{3}(p,s;\alpha)}E(i_{1},\alpha)=n^{-r-s}\sum_{i_{1}\in\mathcal{C}_{r,p}\atop
g(i_{1},\alpha)\in\Delta_{3}(p,s;\alpha)}1.$ (3.10)

For $i_{1}\in\mathcal{C}_{r,p}$ with
$g(i_{1},\alpha)\in\Delta_{4}(p,s;\alpha)$, by the definition of
$\Delta_{4}(p,s;\alpha)$, we have $E(i_{1},\alpha)=n^{-p}m_{4}$ and $p=r+s$.
Hence,

$\displaystyle\sum_{i_{1}\in\mathcal{C}_{r,p}\atop
g(i_{1},\alpha)\in\Delta_{4}(p,s;\alpha)}E(i_{1},\alpha)=n^{-r-s}m_{4}\sum_{i_{1}\in\mathcal{C}_{r,p}\atop
g(i_{1},\alpha)\in\Delta_{4}(p,s;\alpha)}1.$ (3.11)

For $i_{1}\in\mathcal{C}_{r,p}$ with
$g(i_{1},\alpha)\in\Delta_{5}(p,r,s;\alpha)$, by the definition of
$\Delta_{5}(p,r,s;\alpha)$, we have $E(i_{1},\alpha)=O(n^{-p})$ and $p\geq
r+s+1$. Hence,

$\displaystyle\sum_{i_{1}\in\mathcal{C}_{r,p}\atop
g(i_{1},\alpha)\in\Delta_{5}(p,r,s;\alpha)}E(i_{1},\alpha)=O(n^{-p})\sum_{i_{1}\in\mathcal{C}_{r,p}\atop
g(i_{1},\alpha)\in\Delta_{5}(p,r,s;\alpha)}1.$ (3.12)

Substituting (3.9), (3.10), (3.11) and (3.12) to (3.1), and noting that

$\displaystyle
n\cdots(n-r+1)=n^{r}\left(1-\dfrac{r(r-1)}{2n}+O(n^{-2})\right),$

we have

$\displaystyle\sum_{r=1}^{p}n\cdots(n-r+1)\sum_{i_{1}\in\mathcal{C}_{r,p}}E(i_{1},\alpha)$
$\displaystyle=$ $\displaystyle
n^{1-s}\left(1-\dfrac{(p+1-s)(p-s)}{2n}+O(n^{-2})\right)\sum_{i_{1}\in\mathcal{C}_{p+1-s,p}\atop
g(i_{1},\alpha)\in\Delta_{1}(p,s;\alpha)}1$
$\displaystyle+n^{-s}\left(1-\dfrac{(p-s)(p-s-1)}{2n}+O(n^{-2})\right)\sum_{i_{1}\in\mathcal{C}_{r,p}\atop
g(i_{1},\alpha)\in\Delta_{3}(p,s;\alpha)}1$
$\displaystyle+n^{-s}\left(1-\dfrac{(p-s)(p-s-1)}{2n}+O(n^{-2})\right)m_{4}\sum_{i_{1}\in\mathcal{C}_{r,p}\atop
g(i_{1},\alpha)\in\Delta_{4}(p,s;\alpha)}1$
$\displaystyle+\sum_{r=1}^{p-s-1}n^{r}\left(1-\dfrac{r(r-1)}{2n}+O(n^{-2})\right)\sum_{i_{1}\in\mathcal{C}_{r,p}\atop
g(i_{1},\alpha)\in\Delta_{5}(p,r,s;\alpha)}O(n^{-p})$ $\displaystyle=$
$\displaystyle
n^{1-s}\left(1-\dfrac{(p+1-s)(p-s)}{2n}\right)\sum_{i_{1}\in\mathcal{C}_{p+1-s,p}\atop
g(i_{1},\alpha)\in\Delta_{1}(p,s;\alpha)}1$
$\displaystyle+n^{-s}\left(\sum_{i_{1}\in\mathcal{C}_{r,p}\atop
g(i_{1},\alpha)\in\Delta_{3}(p,s;\alpha)}1+m_{4}\sum_{i_{1}\in\mathcal{C}_{r,p}\atop
g(i_{1},\alpha)\in\Delta_{4}(p,s;\alpha)}1\right)+O(n^{-s-1})$ (3.13)
$\displaystyle=$
$\displaystyle\begin{cases}O(n^{1-s}),&\alpha\in\mathcal{C}_{s,p}^{(1)},\\\
O(n^{-s}),&\alpha\in\mathcal{C}_{s,p}\setminus\mathcal{C}_{s,p}^{(1)},\end{cases}$
(3.14)

where the last equality follows from Lemma 3.1. Hence, by (3.13), (3.14) and
Lemma 3.1, (3.1) can be written as

$\displaystyle\dfrac{1}{n^{k}}\mathbb{E}\big{[}\mathrm{Tr}M_{n,k,m}^{p}\big{]}=$
$\displaystyle\dfrac{1}{n^{k}}\sum_{s=1}^{p}\sum_{\alpha\in\mathcal{C}_{s,p}}\left(\sum_{\varphi\in\mathcal{I}_{s,m}}\prod_{t=1}^{p}\tau_{\varphi(\alpha_{t})}\right)\left(\sum_{r=1}^{p}n\cdots(n-r+1)\sum_{i_{1}\in\mathcal{C}_{r,p}}E(i_{1},\alpha)\right)^{k}$
$\displaystyle=$
$\displaystyle\sum_{s=1}^{p}\left(\dfrac{m}{n^{k}}\right)^{s}(1+o(1))\sum_{\alpha\in\mathcal{C}_{s,p}^{(1)}}\left(\dfrac{1}{m^{s}}\sum_{\varphi\in\mathcal{I}_{s,m}}\prod_{t=1}^{p}\tau_{\varphi(\alpha_{t})}\right)$
$\displaystyle\left(1-\dfrac{(p+1-s)(p-s)}{2n}+\dfrac{1}{n}\left(\sum_{i_{1}\in\mathcal{C}_{r,p}\atop
g(i_{1},\alpha)\in\Delta_{3}(p,s;\alpha)}1+m_{4}\sum_{i_{1}\in\mathcal{C}_{r,p}\atop
g(i_{1},\alpha)\in\Delta_{4}(p,s;\alpha)}1\right)\right)^{k}.$ (3.15)

Recall the definition of $\mathrm{deg}_{t}(\alpha)$ given in (2.1) Then the
sequence $\alpha$ has exactly $\mathrm{deg}_{t}(\alpha)$ vertices that equals
to $t$. Thus, we have the following identity

$\displaystyle\sum_{t=1}^{s}\mathrm{deg}_{t}(\alpha)=p.$

The following lemma computes the size of $\Delta_{4}(p,s;\alpha)$ for given
$\alpha\in\mathcal{C}_{s,p}^{(1)}$.

######  Lemma 3.2.

For fixed $\alpha=(\alpha_{1},\ldots,\alpha_{p})\in\mathcal{C}_{s,p}^{(1)}$,
the number of $i_{1}\in\mathcal{C}_{r,p}$ such that
$g(i_{1},\alpha)\in\Delta_{4}(p,s;\alpha)$ is

$\displaystyle\sum_{t=1}^{s}\binom{\mathrm{deg}_{t}(\alpha)}{2}.$ (3.16)

###### Proof.

We sort the graphs in $\Delta_{4}(p,s;\alpha)$ into two classes. We will show
that graphs in $\Delta_{4}(p,s;\alpha)$ can be transferred to graphs in
$\Delta_{1}(p,s;\alpha)$ by splitting the vertex on the sequence $i_{1}$
associated to the multiple edges.

The first class consists of graphs whose the first $l-1$ up edges are
distinct, and the $l$-th down edge $(\alpha_{l},i_{1}^{(l)})$ coincide with
the $j$-th down edge for some $1\leq j<l\leq p$. Hence,
$\alpha_{l}=\alpha_{j}$ and $i_{1}^{(l)}=i_{1}^{(j)}$. Since the subgraph of
the path from $\alpha_{j}$ to $\alpha_{l}$ does not have a cycle, one can find
$1\leq j^{\prime}<l$, such that the $j^{\prime}$-th up edge is from
$i_{1}^{(l)}$ to $\alpha_{l}$. Another up edge from $i_{1}^{(l)}$ to
$\alpha_{l}$ belongs to the set of the last $p-(l-1)$ up edges. Hence, the
edge $(\alpha_{l},i_{1}^{(l)})$ is not a down innovation. Now we split the
vertex $i_{1}^{(l)}$ into two vertices $i_{1}^{(l,1)}$ and $i_{1}^{(l,2)}$.
The new vertex $i_{1}^{(l,1)}$ is still labeled by the value of $i_{1}^{(l)}$
and the first $l-1$ pairs of up and down edges which connect $i_{1}^{(l)}$ are
plotted to connect the new vertex $i_{1}^{(l,1)}$. The $l$-th down edge
connect $i_{1}^{(l)}$ is plotted to connect the new vertex $i_{1}^{(l,2)}$,
which is a down innovation. The rest of the edges can be plotted such that the
new graph belongs to $\Delta_{1}(p,s;\alpha)$. See the graph below.

$\bm{\longrightarrow}$

Figure 1: A graph in the first class of $\Delta_{4}(p,s;\alpha)$ (left column)
and corresponding $\Delta_{1}(p,s;\alpha)$ graph (right column).

The second class consists of graphs whose first $l$ down edges are distinct,
and the $l$-th up edge $(i_{1}^{(l)},\alpha_{l+1})$ coincide with the $j$-th
up edge for some $1\leq j<l\leq p-1$. This means that
$i_{1}^{(l)}=i_{1}^{(j)}$ and $\alpha_{l+1}=\alpha_{j+1}$. Since the subgraph
of the path from $i_{1}^{(j)}$ to $i_{1}^{(l)}$ does not have a cycle, one can
find $j<j^{\prime}\leq l$, such that the $j^{\prime}$-th down edge is from
$\alpha_{l+1}$ to $i_{1}^{(l)}$, which means that
$\alpha_{j^{\prime}}=\alpha_{l+1}$, $i_{1}^{(j^{\prime})}=i_{1}^{(l)}$ and the
$j^{\prime}$-th down edge is not a down innovation. Another down edge from
$\alpha_{l+1}$ to $i_{1}^{(l)}$ belongs to the set of the last $p-l$ down
edges. Now we split the vertex $i_{1}^{(l)}$ into two vertices $i_{1}^{(l,1)}$
and $i_{1}^{(l,2)}$. The new vertex $i_{1}^{(l,1)}$ is still labeled by the
value of $i_{1}^{(l)}$ and the first $j^{\prime}-1$ pairs of up and down edges
which connect $i_{1}^{(l)}$ are plotted to connect the new vertex
$i_{1}^{(l,1)}$. The $j^{\prime}$-th down edge connect
$i_{1}^{(j^{\prime})}=i_{1}^{(l)}$ is plotted to connect the new vertex
$i_{1}^{(l,2)}$, which is a down innovation. The $l$-th up edge starts from
$i_{1}^{(l,2)}$. The rest of the edges can be plotted such that the new graph
belongs to $\Delta_{1}(p,s;\alpha)$. See the graph below.

$\bm{\longrightarrow}$

Figure 2: A graph in the second class of $\Delta_{4}(p,s;\alpha)$ (left
column) and corresponding $\Delta_{1}(p,s;\alpha)$ graph (right column).

Therefore, for any graphs in $\Delta_{4}(p,s;\alpha)$, one can split the
vertex on the sequence $i_{1}$ associated to the multiple edges to get a graph
in $\Delta_{1}(p,s;\alpha)$. Equivalently, any graphs in
$\Delta_{4}(p,s;\alpha)$ can be obtained from graphs in
$\Delta_{1}(p,s;\alpha)$ by gluing two vertices on the sequence $i_{1}$ that
has a same neighborhood. Moreover, gluing different pairs of vertices on the
sequence $i_{1}$ leads to different graphs in $\Delta_{4}(p,s;\alpha)$.

For fixed $\alpha\in\mathcal{C}_{s,p}^{(1)}$, by Lemma 3.1, there exists a
unique sequence $i_{1}$, such that the graph
$g(i_{1},\alpha)\in\Delta_{1}(p,s;\alpha)$. For the vertex $t$ on the
$\alpha$-line, an observation is that the number of its neighborhoods on the
$i$-line is $\mathrm{deg}_{t}(\alpha)$. Hence, the choice to glue two vertices
on the sequence $i_{1}$ with the same neighborhood $t$ on the $\alpha$-line is

$\displaystyle\binom{\mathrm{deg}_{t}(\alpha)}{2}.$

Thus, for fixed $\alpha\in\mathcal{C}_{s,p}^{(1)}$, the number of
$i_{1}\in\mathcal{C}_{r,p}$ such that
$g(i_{1},\alpha)\in\Delta_{4}(p,s;\alpha)$ is given by (3.16). ∎

The following lemma is a property of the sequence in
$\mathcal{C}_{s,p}^{(1)}$.

######  Lemma 3.3.

For $\alpha\in\mathcal{C}_{s,p}$, if there exist different integers
$t_{1},t_{2}\in[s]$, such that $\alpha_{j_{1}}=\alpha_{j_{1}^{\prime}}=t_{1}$
and $\alpha_{j_{2}}=\alpha_{j_{2}^{\prime}}=t_{2}$ for some $1\leq
j_{1}<j_{2}<j_{1}^{\prime}<j_{2}^{\prime}\leq p$, then
$\alpha\notin\mathcal{C}_{s,p}^{(1)}$.

###### Proof.

We prove by contradiction. Suppose not, then there exists a
$w\in\mathcal{C}_{p+1-s,p}$, such that $g(w,\alpha)\in\Delta_{1}(p,s;\alpha)$.
Note that the path from $\alpha_{j_{1}}$ to $\alpha_{j_{2}}$ and the path from
$\alpha_{j_{1}^{\prime}}$ to $\alpha_{j_{2}^{\prime}}$ are two paths from the
vertex on the $\alpha$-line with labeled $t_{1}$ to the vertex on the
$\alpha$-line with labeled $t_{2}$. The two paths will lead to multiple
directed edges or undirected cycle, which is contradicted to the definition of
$\Delta_{1}(p,s;\alpha)$. ∎

The following corollary is a direct consequence of Lemma 3.3.

######  Corollary 3.1.

For $\alpha\in\mathcal{C}_{s,p}^{(1)}$, graphs in $\Delta_{3}(p,s;\alpha)$ are
the $\Delta(p;\alpha)$-graphs in which each down edge must coincide with one
and only one up edge. If we glue the coincident edges, the resulting graph is
a connected graph with exactly one cycle.

The following lemma computes the size of $\Delta_{3}(p,s;\alpha)$ for given
$\alpha\in\mathcal{C}_{s,p}^{(1)}$.

######  Lemma 3.4.

For fixed $\alpha=(\alpha_{1},\ldots,\alpha_{p})\in\mathcal{C}_{s,p}^{(1)}$,
the number of $i_{1}\in\mathcal{C}_{r,p}$ such that
$g(i_{1},\alpha)\in\Delta_{3}(p,s;\alpha)$ is

$\displaystyle\binom{p+1-s}{2}-\sum_{t=1}^{s}\binom{\mathrm{deg}_{t}(\alpha)}{2}.$
(3.17)

###### Proof.

Recall that down edges of graphs in $\Delta_{3}(p,s;\alpha)$ coincide with
exactly one up edge, and the graph is connected with exactly one cycle when
gluing coincident edges.

We also sort the graphs in $\Delta_{3}(p,s;\alpha)$ into two classes. We will
show that graphs in $\Delta_{3}(p,s;\alpha)$ can be transferred to graphs in
$\Delta_{1}(p,s;\alpha)$ by splitting an appropriate vertex on the sequence
$i_{1}$.

The first class consists of graphs whose subgraph with first $l-1$ up and down
edges has no cycle when orientation is removed and multiple edges are
identified, but has a cycle when adding the $l$-th down edge. Hence, we have
$3\leq l\leq p$, and both $\alpha_{l}$ and $i_{1}^{(l)}$ are not new vertices.
Now we split the vertex $i_{1}^{(l)}$ into two vertices $i_{1}^{(l,1)}$ and
$i_{1}^{(l,2)}$. The new vertex $i_{1}^{(l,1)}$ is still labeled by the value
of $i_{1}^{(l)}$, and the first $l-1$ pairs of up and down edges which connect
$i_{1}^{(l)}$ are plotted to connect the new vertex $i_{1}^{(l,1)}$. The
$l$-th down edge $(\alpha_{l},i_{1}^{(l)})$ is replaced by the new down edge
$(\alpha_{l},i_{1}^{(l,2)})$, which is a down innovation. The $l$-th up edge
starts from $i_{1}^{(l,2)}$. The rest of the edges can be plotted such that
the new graph belongs to $\Delta_{1}(p,s;\alpha)$. See the graph below.

$\bm{\longrightarrow}$

Figure 3: A graph in the first class of $\Delta_{3}(p,s;\alpha)$ (left column)
and corresponding $\Delta_{1}(p,s;\alpha)$ graph (right column). The dashed
line describes the existence of a cycle.

The second class consists of graphs whose subgraph with first $l-1$ up edges
and first $l$ down edges has no cycle when orientation is removed and multiple
edges are identified, but has a cycle when adding the $l$-th up edge. Thus,
there exists a $1\leq j<l$, such that $\alpha_{l+1}=\alpha_{j}$ and the $j$-th
down edge belongs to the cycle. Since the subgraph with first $l-1$ up edges
and first $l$ down edges has no cycle, we have $\alpha_{u}\neq\alpha_{j}$ for
all $j<u<l+1$. By Lemma 3.3, the first $j-1$ pairs as well as the last $p-l$
pairs of down and up edges never visit the vertex $\alpha_{u}$ for all
$j<u<l+1$. Hence, along the path from $i_{1}^{(j)}$ to $i_{1}^{(l)}$, all down
edges are paired with exactly one up edge. Note that along the path from
$\alpha_{j}$ to $i_{1}^{(l)}$, there must be a single edge, which can only be
$(\alpha_{j},i_{1}^{(j)})$. If $i_{1}^{(j)}\neq i_{1}^{(l)}$, then in the
subgraph of path from $\alpha_{j}$ to $\alpha_{l+1}$, the degree of the
vertices $i_{1}^{(j)}$ and $i_{1}^{(l)}$ are both odd number. This is
impossible. However, $i_{1}^{(j)}=i_{1}^{(l)}$ implies that the $l$-th up edge
$(i_{1}^{(l)},\alpha_{l+1})$ coincide with the $j$-th down edge
$(\alpha_{j},i_{1}^{(j)})$. This contradicts to the assumption that the
subgraph with first $l$ pairs of down and up edges has a cycle but has no
cycle if deleting the $l$-th up edges, when the orientation is removed and
multiple edges are identified. Thus, the second class is empty.

Therefore, for any graphs in $\Delta_{3}(p,s;\alpha)$, one can split an
appropriate vertex on the sequence $i_{1}$ to get a graph in
$\Delta_{1}(p,s;\alpha)$. Equivalently, any graphs in $\Delta_{3}(p,s;\alpha)$
can be obtained from graphs in $\Delta_{1}(p,s;\alpha)$ by gluing two vertices
on the sequence $i_{1}$ without common neighborhood. Moreover, gluing
different pairs of vertices on the sequence $i_{1}$ leads to different graphs
in $\Delta_{3}(p,s;\alpha)$.

For fixed $\alpha\in\mathcal{C}_{s,p}^{(1)}$, by Lemma 3.1, there exists a
unique sequence $i_{1}$, such that the graph
$g(i_{1},\alpha)\in\Delta_{1}(p,s;\alpha)$. Moreover, the sequence $i_{1}$ has
$p+1-s$ different vertices. Hence, the choice to glue two vertices on the
sequence $i_{1}$ is $\binom{p+1-s}{2}$. By Lemma 3.2, the choice to glue two
vertices on the sequence $i_{1}$ that has different neighborhoods is given by
(3.17). ∎

By Lemma 3.2 ,3.4 and (3.1), we have

$\displaystyle\dfrac{1}{n^{k}}\mathbb{E}\big{[}\mathrm{Tr}M_{n,k,m}^{p}\big{]}$
$\displaystyle=$
$\displaystyle\sum_{s=1}^{p}\left(\dfrac{m}{n^{k}}\right)^{s}(1+o(1))\sum_{\alpha\in\mathcal{C}_{s,p}^{(1)}}\left(\sum_{\varphi\in\mathcal{I}_{s,m}}\prod_{t=1}^{s}\dfrac{1}{m}\tau_{\varphi(t)}^{\mathrm{deg}_{t}(\alpha)}\right)$
$\displaystyle\left[1-\dfrac{(p+1-s)(p-s)}{2n}+\dfrac{1}{n}\left(\binom{p+1-s}{2}-\sum_{t=1}^{s}\binom{\mathrm{deg}_{t}(\alpha)}{2}+m_{4}\sum_{t=1}^{s}\binom{\mathrm{deg}_{t}(\alpha)}{2}\right)\right]^{k}$
$\displaystyle=$
$\displaystyle\sum_{s=1}^{p}\left(\dfrac{m}{n^{k}}\right)^{s}(1+o(1))\sum_{\alpha\in\mathcal{C}_{s,p}^{(1)}}\left(\sum_{\varphi\in\mathcal{I}_{s,m}}\prod_{t=1}^{s}\dfrac{1}{m}\tau_{\varphi(t)}^{\mathrm{deg}_{t}(\alpha)}\right)\left[1+\dfrac{m_{4}-1}{n}\sum_{t=1}^{s}\binom{\mathrm{deg}_{t}(\alpha)}{2}\right]^{k}$
$\displaystyle=$
$\displaystyle\sum_{s=1}^{p}\left(\dfrac{m}{n^{k}}\right)^{s}(1+o(1))\sum_{\alpha\in\mathcal{C}_{s,p}^{(1)}}\prod_{t=1}^{s}\left(\dfrac{1}{m}\sum_{j=1}^{m}\tau_{j}^{\mathrm{deg}_{t}(\alpha)}\right)\left[1+\dfrac{m_{4}-1}{n}\sum_{t=1}^{s}\binom{\mathrm{deg}_{t}(\alpha)}{2}\right]^{k},$
(3.18)

where we use the following equality in the last equality

$\displaystyle\sum_{\varphi\in\mathcal{I}_{s,m}}\prod_{t=1}^{s}\dfrac{1}{m}\tau_{\varphi(t)}^{\mathrm{deg}_{t}(\alpha)}=\sum_{j_{1},\ldots,j_{s}=1\atop\forall
p\neq q,j_{p}\neq
j_{q}}^{m}\prod_{t=1}^{s}\dfrac{1}{m}\tau_{j_{t}}^{\mathrm{deg}_{t}(\alpha)}=\prod_{t=1}^{s}\left(\dfrac{1}{m}\sum_{j=1}^{m}\tau_{j}^{\mathrm{deg}_{t}(\alpha)}\right)(1+o(1)).$

Letting $m,n,k\to\infty$ in (3.1) with the ratio (1.2) and the limit
assumption (2.2), we have

$\displaystyle\lim_{n\to\infty}\dfrac{1}{n^{k}}\mathbb{E}\big{[}\mathrm{Tr}M_{n,k,m}^{p}\big{]}=$
$\displaystyle\sum_{s=1}^{p}c^{s}\sum_{\alpha\in\mathcal{C}_{s,p}^{(1)}}\left(\prod_{t=1}^{s}m_{\mathrm{deg}_{t}(\alpha)}^{(\tau)}\right)\exp\left(d(m_{4}-1)\sum_{t=1}^{s}\binom{\mathrm{deg}_{t}(\alpha)}{2}\right).$
(3.19)

###  3.2 Proof of (ii)

For any $p\in\mathbb{N}$, we compute the variance of the moment

$\displaystyle\mathrm{Var}\left(\dfrac{1}{n^{k}}\mathrm{Tr}M_{n,k,m}^{p}\right)=\dfrac{1}{n^{2k}}\mathbb{E}\left[\big{(}\mathrm{Tr}M_{n,k,m}^{p}\big{)}^{2}\right]-\dfrac{1}{n^{2k}}\left(\mathbb{E}\left[\mathrm{Tr}M_{n,k,m}^{p}\right]\right)^{2}.$
(3.20)

We use the convention that $\mathbf{i}^{(p+1)}=\mathbf{i}^{(1)}$ and
$\mathbf{j}^{(p+1)}=\mathbf{j}^{(1)}$. Recalling the model (1.1), we can write

$\displaystyle\dfrac{1}{n^{2k}}\mathbb{E}\left[\big{(}\mathrm{Tr}M_{n,k,m}^{p}\big{)}^{2}\right]$
$\displaystyle=$
$\displaystyle\dfrac{1}{n^{2k}}\sum_{\alpha_{1},\ldots,\alpha_{p}=1}^{m}\sum_{\beta_{1},\ldots,\beta_{p}=1}^{m}\left(\prod_{t=1}^{p}\tau_{\alpha_{t}}\tau_{\beta_{t}}\right)\mathbb{E}\Big{[}\mathrm{Tr}\big{(}Y_{\alpha_{1}}Y_{\alpha_{1}}^{*}\cdots
Y_{\alpha_{p}}Y_{\alpha_{p}}^{*}\big{)}\mathrm{Tr}\big{(}Y_{\beta_{1}}Y_{\beta_{1}}^{*}\cdots
Y_{\beta_{p}}Y_{\beta_{p}}^{*}\big{)}\Big{]}$ $\displaystyle=$
$\displaystyle\dfrac{1}{n^{2k}}\sum_{\alpha_{1},\ldots,\alpha_{p}=1}^{m}\sum_{\beta_{1},\ldots,\beta_{p}=1}^{m}\left(\prod_{t=1}^{p}\tau_{\alpha_{t}}\tau_{\beta_{t}}\right)\mathbb{E}\Bigg{[}\sum_{\mathbf{i}^{(1)},\ldots,\mathbf{i}^{(p)}=1}^{n^{k}}\sum_{\mathbf{j}^{(1)},\ldots,\mathbf{j}^{(p)}=1}^{n^{k}}\prod_{t=1}^{p}Y_{\mathbf{i}^{(t)}\alpha_{t}}\overline{Y_{\mathbf{i}^{(t+1)}\alpha_{t}}}Y_{\mathbf{j}^{(t)}\beta_{t}}\overline{Y_{\mathbf{j}^{(t+1)}\beta_{t}}}\Bigg{]}$
$\displaystyle=$
$\displaystyle\dfrac{1}{n^{2k}}\sum_{\alpha_{1},\ldots,\alpha_{p}=1}^{m}\sum_{\beta_{1},\ldots,\beta_{p}=1}^{m}\left(\prod_{t=1}^{p}\tau_{\alpha_{t}}\tau_{\beta_{t}}\right)$
$\displaystyle\times\mathbb{E}\Bigg{[}\sum_{\mathbf{i}^{(1)},\ldots,\mathbf{i}^{(p)}=1}^{n^{k}}\sum_{\mathbf{j}^{(1)},\ldots,\mathbf{j}^{(p)}=1}^{n^{k}}\prod_{t=1}^{p}\prod_{l=1}^{k}\bigg{(}\big{(}\mathbf{y}_{\alpha_{t}}^{(l)}\big{)}_{i^{(t)}_{l}}\overline{\big{(}\mathbf{y}_{\alpha_{t}}^{(l)}\big{)}_{i^{(t+1)}_{l}}}\big{(}\mathbf{y}_{\beta_{t}}^{(l)}\big{)}_{j^{(t)}_{l}}\overline{\big{(}\mathbf{y}_{\beta_{t}}^{(l)}\big{)}_{j^{(t+1)}_{l}}}\bigg{)}\Bigg{]}.$

The terms in the last line can be factored in the following way:

$\displaystyle\dfrac{1}{n^{2k}}\mathbb{E}\left[\big{(}\mathrm{Tr}M_{n,k,m}^{p}\big{)}^{2}\right]$
$\displaystyle=$
$\displaystyle\dfrac{1}{n^{2k}}\sum_{\alpha_{1},\ldots,\alpha_{p}=1}^{m}\sum_{\beta_{1},\ldots,\beta_{p}=1}^{m}\left(\prod_{t=1}^{p}\tau_{\alpha_{t}}\tau_{\beta_{t}}\right)$
$\displaystyle\times\mathbb{E}\Bigg{[}\prod_{l=1}^{k}\sum_{i_{l}^{(1)},\ldots,i_{l}^{(p)}=1}^{n}\sum_{j_{l}^{(1)},\ldots,j_{l}^{(p)}=1}^{n}\prod_{t=1}^{p}\bigg{(}\big{(}\mathbf{y}_{\alpha_{t}}^{(l)}\big{)}_{i^{(t)}_{l}}\overline{\big{(}\mathbf{y}_{\alpha_{t}}^{(l)}\big{)}_{i^{(t+1)}_{l}}}\big{(}\mathbf{y}_{\beta_{t}}^{(l)}\big{)}_{j^{(t)}_{l}}\overline{\big{(}\mathbf{y}_{\beta_{t}}^{(l)}\big{)}_{j^{(t+1)}_{l}}}\bigg{)}\Bigg{]}$
$\displaystyle=$
$\displaystyle\dfrac{1}{n^{2k}}\sum_{\alpha_{1},\ldots,\alpha_{p}=1}^{m}\sum_{\beta_{1},\ldots,\beta_{p}=1}^{m}\left(\prod_{t=1}^{p}\tau_{\alpha_{t}}\tau_{\beta_{t}}\right)$
$\displaystyle\times\left(\mathbb{E}\left[\sum_{i_{1}^{(1)},\ldots,i_{1}^{(p)}=1}^{n}\sum_{j_{1}^{(1)},\ldots,j_{1}^{(p)}=1}^{n}\prod_{t=1}^{p}\bigg{(}\big{(}\mathbf{y}_{\alpha_{t}}^{(1)}\big{)}_{i^{(t)}_{1}}\overline{\big{(}\mathbf{y}_{\alpha_{t}}^{(1)}\big{)}_{i^{(t+1)}_{1}}}\big{(}\mathbf{y}_{\beta_{t}}^{(1)}\big{)}_{j^{(t)}_{1}}\overline{\big{(}\mathbf{y}_{\beta_{t}}^{(1)}\big{)}_{j^{(t+1)}_{1}}}\bigg{)}\right]\right)^{k}.$
(3.21)

Here, we use the i.i.d. setting in the last equality. By (3.1), we have

$\displaystyle\dfrac{1}{n^{2k}}\left(\mathbb{E}\big{[}\mathrm{Tr}M_{n,k,m}^{p}\big{]}\right)^{2}$
$\displaystyle=$
$\displaystyle\dfrac{1}{n^{2k}}\sum_{\alpha_{1},\ldots,\alpha_{p}=1}^{m}\sum_{\beta_{1},\ldots,\beta_{p}=1}^{m}\left(\prod_{t=1}^{p}\tau_{\alpha_{t}}\tau_{\beta_{t}}\right)$
$\displaystyle\times\left(\mathbb{E}\left[\sum_{i_{1}^{(1)},\ldots,i_{1}^{(p)}=1}^{n}\prod_{t=1}^{p}\bigg{(}\big{(}\mathbf{y}_{\alpha_{t}}^{(1)}\big{)}_{i^{(t)}_{1}}\overline{\big{(}\mathbf{y}_{\alpha_{t}}^{(1)}\big{)}_{i^{(t+1)}_{1}}}\bigg{)}\right]\mathbb{E}\left[\sum_{j_{1}^{(1)},\ldots,j_{1}^{(p)}=1}^{n}\prod_{t=1}^{p}\bigg{(}\big{(}\mathbf{y}_{\beta_{t}}^{(1)}\big{)}_{j^{(t)}_{1}}\overline{\big{(}\mathbf{y}_{\beta_{t}}^{(1)}\big{)}_{j^{(t+1)}_{1}}}\bigg{)}\right]\right)^{k}.$
(3.22)

Substitute (3.2) and (3.2) to (3.20), we have

$\displaystyle\mathrm{Var}\left(\dfrac{1}{n^{k}}\mathrm{Tr}M_{n,k,m}^{p}\right)$
$\displaystyle=$
$\displaystyle\dfrac{1}{n^{2k}}\sum_{\alpha_{1},\ldots,\alpha_{p}=1}^{m}\sum_{\beta_{1},\ldots,\beta_{p}=1}^{m}\left(\prod_{t=1}^{p}\tau_{\alpha_{t}}\tau_{\beta_{t}}\right)$
$\displaystyle\times\left\\{\left(\mathbb{E}\left[\sum_{i_{1}^{(1)},\ldots,i_{1}^{(p)}=1}^{n}\sum_{j_{1}^{(1)},\ldots,j_{1}^{(p)}=1}^{n}\prod_{t=1}^{p}\bigg{(}\big{(}\mathbf{y}_{\alpha_{t}}^{(1)}\big{)}_{i^{(t)}_{1}}\overline{\big{(}\mathbf{y}_{\alpha_{t}}^{(1)}\big{)}_{i^{(t+1)}_{1}}}\big{(}\mathbf{y}_{\beta_{t}}^{(1)}\big{)}_{j^{(t)}_{1}}\overline{\big{(}\mathbf{y}_{\beta_{t}}^{(1)}\big{)}_{j^{(t+1)}_{1}}}\bigg{)}\right]\right)^{k}\right.$
$\displaystyle\left.-\left(\mathbb{E}\left[\sum_{i_{1}^{(1)},\ldots,i_{1}^{(p)}=1}^{n}\prod_{t=1}^{p}\bigg{(}\big{(}\mathbf{y}_{\alpha_{t}}^{(1)}\big{)}_{i^{(t)}_{1}}\overline{\big{(}\mathbf{y}_{\alpha_{t}}^{(1)}\big{)}_{i^{(t+1)}_{1}}}\bigg{)}\right]\mathbb{E}\left[\sum_{j_{1}^{(1)},\ldots,j_{1}^{(p)}=1}^{n}\prod_{t=1}^{p}\bigg{(}\big{(}\mathbf{y}_{\beta_{t}}^{(1)}\big{)}_{j^{(t)}_{1}}\overline{\big{(}\mathbf{y}_{\beta_{t}}^{(1)}\big{)}_{j^{(t+1)}_{1}}}\bigg{)}\right]\right)^{k}\right\\}.$
(3.23)

Denote the sequences $\alpha=(\alpha_{1},\ldots,\alpha_{p})$,
$\beta=(\beta_{1},\ldots,\ldots,\beta_{p})$,
$i_{1}=(i_{1}^{(1)},\ldots,i_{1}^{(p)})$ and
$j_{1}=(j_{1}^{(1)},\ldots,j_{1}^{(p)})$. We use the notation
$\alpha\cap\beta=\emptyset$ if the two sequences $\alpha$ and $\beta$ have no
common vertices. Note that when $\alpha\cap\beta=\emptyset$, the two random
variables

$\displaystyle\prod_{t=1}^{p}\bigg{(}\big{(}\mathbf{y}_{\alpha_{t}}^{(1)}\big{)}_{i^{(t)}_{1}}\overline{\big{(}\mathbf{y}_{\alpha_{t}}^{(1)}\big{)}_{i^{(t+1)}_{1}}}\bigg{)},~{}\mathrm{and}~{}\prod_{t=1}^{p}\bigg{(}\big{(}\mathbf{y}_{\beta_{t}}^{(1)}\big{)}_{j^{(t)}_{1}}\overline{\big{(}\mathbf{y}_{\beta_{t}}^{(1)}\big{)}_{j^{(t+1)}_{1}}}\bigg{)}$

are independent, for any sequences $i_{1},j_{1}\in[n]^{p}$. Hence, (3.2) can
be written as

$\displaystyle\mathrm{Var}\left(\dfrac{1}{n^{k}}\mathrm{Tr}M_{n,k,m}^{p}\right)$
$\displaystyle=$
$\displaystyle\dfrac{1}{n^{2k}}\sum_{\alpha,\beta\in[m]^{p},\alpha\cap\beta\neq\emptyset}\left(\prod_{t=1}^{p}\tau_{\alpha_{t}}\tau_{\beta_{t}}\right)$
$\displaystyle\times\left\\{\left(\sum_{i_{1},j_{1}\in[n]^{p}}\mathbb{E}\left[\prod_{t=1}^{p}\bigg{(}\big{(}\mathbf{y}_{\alpha_{t}}^{(1)}\big{)}_{i^{(t)}_{1}}\overline{\big{(}\mathbf{y}_{\alpha_{t}}^{(1)}\big{)}_{i^{(t+1)}_{1}}}\big{(}\mathbf{y}_{\beta_{t}}^{(1)}\big{)}_{j^{(t)}_{1}}\overline{\big{(}\mathbf{y}_{\beta_{t}}^{(1)}\big{)}_{j^{(t+1)}_{1}}}\bigg{)}\right]\right)^{k}\right.$
$\displaystyle\left.-\left(\sum_{i_{1},j_{1}\in[n]^{p}}\mathbb{E}\left[\prod_{t=1}^{p}\bigg{(}\big{(}\mathbf{y}_{\alpha_{t}}^{(1)}\big{)}_{i^{(t)}_{1}}\overline{\big{(}\mathbf{y}_{\alpha_{t}}^{(1)}\big{)}_{i^{(t+1)}_{1}}}\bigg{)}\right]\mathbb{E}\left[\prod_{t=1}^{p}\bigg{(}\big{(}\mathbf{y}_{\beta_{t}}^{(1)}\big{)}_{j^{(t)}_{1}}\overline{\big{(}\mathbf{y}_{\beta_{t}}^{(1)}\big{)}_{j^{(t+1)}_{1}}}\bigg{)}\right]\right)^{k}\right\\}$
$\displaystyle=$
$\displaystyle\dfrac{1}{n^{2k}}\sum_{\alpha,\beta\in[m]^{p},\alpha\cap\beta\neq\emptyset}\left(\prod_{t=1}^{p}\tau_{\alpha_{t}}\tau_{\beta_{t}}\right)$
$\displaystyle\times\left\\{\left(\sum_{i_{1},j_{1}\in[n]^{p}}E^{\prime}(i_{1},\alpha;j_{1},\beta)\right)^{k}-\left(\sum_{i_{1},j_{1}\in[n]^{p}}E(i_{1},\alpha)E(j_{1},\beta)\right)^{k}\right\\},$
(3.24)

where $E(\cdot,\cdot)$ is defined in (3.6), and
$E^{\prime}(i_{1},\alpha;j_{1},\beta)$ is given by

$\displaystyle
E^{\prime}(i_{1},\alpha;j_{1},\beta)=\mathbb{E}\left[\prod_{t=1}^{p}\bigg{(}\big{(}\mathbf{y}_{\alpha_{t}}^{(1)}\big{)}_{i^{(t)}_{1}}\overline{\big{(}\mathbf{y}_{\alpha_{t}}^{(1)}\big{)}_{i^{(t+1)}_{1}}}\big{(}\mathbf{y}_{\beta_{t}}^{(1)}\big{)}_{j^{(t)}_{1}}\overline{\big{(}\mathbf{y}_{\beta_{t}}^{(1)}\big{)}_{j^{(t+1)}_{1}}}\bigg{)}\right].$

We use the notation $g(i_{1},\alpha)\cup g(j_{1},\beta)$ for the graph
obtained from $g(i_{1},\alpha)$ and $g(j_{1},\beta)$ by joining two graphs
together and keep the coincident edges. If the graph $g(i_{1},\alpha)\cup
g(j_{1},\beta)$ has a single edge, then this single edge must belong to one of
the graphs $g(i_{1},\alpha)$ and $g(j_{1},\beta)$. Since the variables have
mean zero, only the summation indices $i_{1},j_{1}$ such that the graph
$g(i_{1},\alpha)\cup g(j_{1},\beta)$ has no single edge contribute to (3.2).
Note that the graph $g(i_{1},\alpha)\cup g(j_{1},\beta)$ is connected with
$4p$ edges, the degrees of the vertices is at least $4$ with at most two
exceptions, whose degrees are at least $2$. Denote $s=|(\alpha,\beta)|$ and
$r=|(i_{1},j_{1})|$, then the term $E^{\prime}(i_{1},\alpha;j_{1},\beta)$ is
non-vanishing when $r+s\leq 2p+1$.

Besides, if $\alpha\cap\beta\neq\emptyset$, then $s\leq|\alpha|+|\beta|-1$.
Hence, the term $E(i_{1},\alpha)E(j_{1},\beta)$ is non-vanishing when
$|i_{1}|+|\alpha|\leq p+1$ and $|j_{1}|+|\beta|\leq p+1$, which implies that
$r+s\leq|i_{1}|+|j_{1}|+(|\alpha|+|\beta|-1)\leq 2p+1$. Hence, for $n$ large,

$\displaystyle\mathrm{Var}\left(\dfrac{1}{n^{k}}\mathrm{Tr}M_{n,k,m}^{p}\right)$
$\displaystyle=$
$\displaystyle\dfrac{1}{n^{2k}}\sum_{s=1}^{2p}\sum_{(\alpha,\beta)\in\mathcal{C}_{s,2p},\alpha\cap\beta\neq\emptyset}\left(\sum_{\varphi\in\mathcal{I}_{s,m}}\prod_{t=1}^{p}\tau_{\varphi(\alpha_{t})}\tau_{\varphi(\beta_{t})}\right)$
$\displaystyle\times\left\\{\left(\sum_{r=1}^{2p}n^{r}(1+O(n^{-1}))\sum_{(i_{1},j_{1})\in\mathcal{C}_{r,2p}}E^{\prime}(i_{1},\alpha;j_{1},\beta)\right)^{k}\right.$
$\displaystyle\qquad\left.-\left(\sum_{r=1}^{2p}n^{r}(1+O(n^{-1}))\sum_{(i_{1},j_{1})\in\mathcal{C}_{r,2p}}E(i_{1},\alpha)E(j_{1},\beta)\right)^{k}\right\\}$
$\displaystyle\leq$
$\displaystyle\dfrac{1}{n^{2k}}\sum_{s=1}^{2p}\sum_{(\alpha,\beta)\in\mathcal{C}_{s,2p},\alpha\cap\beta\neq\emptyset}\left(\sum_{\varphi\in\mathcal{I}_{s,m}}\prod_{t=1}^{s}\tau_{\varphi(t)}^{\mathrm{deg}_{t}(\alpha)+\mathrm{deg}_{t}(\beta)}\right)\times
C_{p}^{k}n^{(1-s)k}$ $\displaystyle=$
$\displaystyle\dfrac{C_{p}^{k}}{n^{k}}\sum_{s=1}^{2p}\left(\dfrac{m}{n^{k}}\right)^{s}\sum_{(\alpha,\beta)\in\mathcal{C}_{s,2p},\alpha\cap\beta\neq\emptyset}\left(\sum_{\varphi\in\mathcal{I}_{s,m}}\prod_{t=1}^{s}\dfrac{1}{m}\tau_{\varphi(t)}^{\mathrm{deg}_{t}(\alpha)+\mathrm{deg}_{t}(\beta)}\right)$
$\displaystyle\leq$
$\displaystyle\dfrac{C_{p}^{k}}{n^{k}}\sum_{s=1}^{2p}\left(\dfrac{m}{n^{k}}\right)^{s}\sum_{(\alpha,\beta)\in\mathcal{C}_{s,2p},\alpha\cap\beta\neq\emptyset}\prod_{t=1}^{s}\left(\dfrac{1}{m}\sum_{j=1}^{m}|\tau_{j}|^{\mathrm{deg}_{t}(\alpha)+\mathrm{deg}_{t}(\beta)}\right)$
$\displaystyle\leq$ $\displaystyle\dfrac{C_{p}^{k}}{n^{k}}.$ (3.25)

where $C_{p}$ is a positive number that depends only on $p$ and may varies in
different places. Therefore, for all fixed $p\in\mathbb{N}_{+}$, if $k\geq 2$,
we have

$\displaystyle\sum_{n=1}^{\infty}\mathrm{Var}\left(\dfrac{1}{n^{k}}\mathrm{Tr}M_{n,k,m}^{p}\right)<\infty.$

##  Appendix A The case $d=0$.

The variance calculation (ii) is identical to the one given in the proof of
Theorem 2.1, see Section 3.2. It remains to establish the moment limit (i).

Note that the moment formula (3.1) is also valid for the case $d=0$. We use
the graph $g(i_{1},\alpha)$ to compute the sum on $i_{1}$ in (3.1). For any
sequences $\alpha\in\mathcal{C}_{s,p}$ and $i_{1}\in\mathcal{C}_{r,p}$
satisfying $g(i_{1},\alpha)\in\Delta_{1}(p,s;\alpha)$, we have $r+s=p+1$ and
$E(i_{1},\alpha)=n^{-p}$. Besides, $E(i_{1},\alpha)=0$ if the graph
$g(i_{1},\alpha)\in\Delta_{2}(p,r,s;\alpha)$. Moreover, if
$g(i_{1},\alpha)\notin\Delta_{1}(p,s;\alpha)\cup\Delta_{2}(p,r,s;\alpha)$,
then $r+s\leq p$ and $E(i_{1},\alpha)=O(n^{-p})$. Hence,

$\displaystyle\sum_{r=1}^{p}n\cdots(n-r+1)\sum_{i_{1}\in\mathcal{C}_{r,p}}E(i_{1},\alpha)$
$\displaystyle=$
$\displaystyle\sum_{r=1}^{p}n^{r}\big{(}1+O(n^{-1})\big{)}\sum_{i_{1}\in\mathcal{C}_{r,p}}E(i_{1},\alpha)$
$\displaystyle=$
$\displaystyle\sum_{r=1}^{p}n^{r}\big{(}1+O(n^{-1})\big{)}\sum_{i_{1}\in\mathcal{C}_{r,p}\atop
g(i_{1},\alpha)\in\Delta_{1}(p,s;\alpha)}E(i_{1},\alpha)$
$\displaystyle+\sum_{r=1}^{p}n^{r}(1+O(n^{-1}))\sum_{i_{1}\in\mathcal{C}_{r,p}\atop
g(i_{1},\alpha)\notin\Delta_{1}(p,s;\alpha)\cup\Delta_{2}(p,r,s;\alpha)}E(i_{1},\alpha)$
$\displaystyle=$ $\displaystyle
n^{1-s}\big{(}1+O(n^{-1})\big{)}\sum_{i_{1}\in\mathcal{C}_{p+1-s,p}\atop
g(i_{1},\alpha)\in\Delta_{1}(p,s;\alpha)}1+O(n^{-s}).$ (A.1)

Therefore, by (3.1), (A) and Lemma 3.1, we have

$\displaystyle\dfrac{1}{n^{k}}\mathbb{E}\big{[}\mathrm{Tr}M_{n,k,m}^{p}\big{]}=$
$\displaystyle\dfrac{1}{n^{k}}\sum_{s=1}^{p}\sum_{\alpha\in\mathcal{C}_{s,p}}\left(\sum_{\varphi\in\mathcal{I}_{s,m}}\prod_{t=1}^{p}\tau_{\varphi(\alpha_{t})}\right)\left(n^{1-s}\big{(}1+O(n^{-1})\big{)}\sum_{i_{1}\in\mathcal{C}_{p+1-s,p}\atop
g(i_{1},\alpha)\in\Delta_{1}(p,s;\alpha)}1+O(n^{-s})\right)^{k}$
$\displaystyle=$
$\displaystyle\dfrac{1}{n^{k}}\sum_{s=1}^{p}\sum_{\alpha\in\mathcal{C}_{s,p}^{(1)}}\left(\sum_{\varphi\in\mathcal{I}_{s,m}}\prod_{t=1}^{p}\tau_{\varphi(\alpha_{t})}\right)\Big{(}n^{1-s}\big{(}1+O(n^{-1})\big{)}+O(n^{-s})\Big{)}^{k}$
$\displaystyle+\dfrac{1}{n^{k}}\sum_{s=1}^{p}\sum_{\alpha\in\mathcal{C}_{s,p}\setminus\mathcal{C}_{s,p}^{(1)}}\left(\sum_{\varphi\in\mathcal{I}_{s,m}}\prod_{t=1}^{p}\tau_{\varphi(\alpha_{t})}\right)\big{(}O(n^{-s})\big{)}^{k}$
$\displaystyle=$
$\displaystyle\dfrac{1}{n^{k}}\sum_{s=1}^{p}\sum_{\alpha\in\mathcal{C}_{s,p}^{(1)}}\left(\sum_{\varphi\in\mathcal{I}_{s,m}}\prod_{t=1}^{p}\tau_{\varphi(\alpha_{t})}\right)\times
n^{k(1-s)}(1+o(1))$ $\displaystyle=$
$\displaystyle\sum_{s=1}^{p}\left(\dfrac{m}{n^{k}}\right)^{s}\sum_{\alpha\in\mathcal{C}_{s,p}^{(1)}}\left(\dfrac{1}{m^{s}}\sum_{\varphi\in\mathcal{I}_{s,m}}\prod_{t=1}^{p}\tau_{\varphi(\alpha_{t})}\right)(1+o(1))$
$\displaystyle=$
$\displaystyle\sum_{s=1}^{p}\left(\dfrac{m}{n^{k}}\right)^{s}\sum_{\alpha\in\mathcal{C}_{s,p}^{(1)}}\left(\prod_{t=1}^{s}\left(\dfrac{1}{m}\sum_{j=1}^{m}\tau_{j}^{\mathrm{deg}_{t}(\alpha)}\right)\right)(1+o(1)),$
(A.2)

where we use $k=o(n)$ in the third equality. Letting $m,n,k\to\infty$ with the
ratio (1.2), we have

$\displaystyle\lim_{n\to\infty}\dfrac{1}{n^{k}}\mathbb{E}\big{[}\mathrm{Tr}M_{n,k,m}^{p}\big{]}=\sum_{s=1}^{p}c^{s}\sum_{\alpha\in\mathcal{C}_{s,p}^{(1)}}\left(\prod_{t=1}^{s}m_{\mathrm{deg}_{t}(\alpha)}^{(\tau)}\right).$

######  Remark A.1.

In the case $\tau_{1}=\tau_{2}=\cdots=1$, by Lemma 3.1, we have

$\displaystyle\lim_{n\to\infty}\dfrac{1}{n^{k}}\mathbb{E}\big{[}\mathrm{Tr}M_{n,k,m}^{p}\big{]}=\sum_{s=1}^{p}\dfrac{1}{p}\binom{p}{s-1}\binom{p}{s}c^{s},$

which is the $p$-th moment of the Marchenko-Pastur law.

Acknowledgments: BC was partially supported by JSPS Kakenhi 17H04823,
20K20882, 21H00987, JPJSBP120203202.

## References