\section{Introduction}
\label{sec:introduction}

According to the dramatic growth of the internet of things (IoT) technologies, IoT systems are utilized in a wide range of applications. In particular, wireless sensor networks (WSNs), which can play a significant role in serving IoT based applications such as smart cities, vehicular networks, environmental and earth monitoring, electrical power lines management, renewable energy adaptation, etc \cite{kim2017smart,lazarescu2013design,fernandes2017internet}. However, WSNs suffer from some weaknesses such as limited power, low processing capabilities, and especially the security and data trustworthiness (DT) aspects. Therefore, WSNs-based IoT security and DT are enormous problems that desire an intelligent and adaptive solution to optimally confront the day-to-day intellectual threats such as selective forwarding (SF), injection, and jamming attacks \cite{hassan2019current,rani2019trust}.

In the literature context, various trust mechanisms have been proposed to resolve the WSNs security issues. In \cite{butun2013survey}, the authors discussed different intrusion detection systems (IDS), e.g., game theory-based IDS, watchdog-based IDS, cluster-based IDS, etc., to mitigate the WSNs security problems. More particularly, in \cite{shen2018multistage}, game theory has been deployed to establish a valid IDS to realize malware detection infrastructure. In fact, game theory is a dedicated optimization branch that is utilized to handle the interactions of a set of intelligent rational players. More particularly, it aims to enhance their individual payoffs by an intellectual and adaptive manner \cite{ref_5}. More concretely, game theory has emerged due to the distinguishing features in managing the rational players interactions and mitigating several security threats in WSNs such as packet dropping, false data injection, and data delivery corruption \cite{abdalzaher2016game,abdalzaher2017usingiet,abdalzaher2016using,abdalzaher2017effective,abdalzaher2019non,abdalzaher2017using}. However, the above proposals do not consider the hardware (HW) failure which can make the system critically unstable.

The security issue and HW failure (fault) are among the eminent causes of packet dropping in WSNs, which have a severe impact on the DT, network stability, and power consumption. From the security front, dropping packets is a malicious incentive for saving transmission power in clustered WSNs-based IoT. Accordingly, the decision taken can be harmful, which causes a steep degradation for the IoT networks' DT. Moreover, HW failure has several defects. It can cause packet dropping, packet repeating, or over packet transmission. The fault types can be categorized as offset fault, gain fault, stuck-at fault, out of bounds, spike fault, noise fault, data loss fault, redundant data transmission \cite{noshad2019fault}. In {\cite{duche2013sensor}}, the transmission round trip delay of the packets to detect the nodes that suffer from HW failure has been utilized. In {\cite{noshad2019fault}}, the authors extensively studied the HW failure classifier methods such as support vector machine (SVM), machine learning (ML), and random forest. However, most of the presented works in the literature context have only considered the HW faults regardless of the security issue effect and how to distinguish between them. In \cite{abdalzaher2019access}, a Stackelberg game has used to mitigate the corrupted delivered reports in cognitive radio networks due to the selective forwarding data falsification attack in presence of an HW malfunction. However, to the best of our knowledge, no further work has been presented in the literature focusing on classifying between attack effect and HW failure for packet drop. Consequently, an intellectual and adaptive solution is desired to resolve these crucial issues along with the WSNs limited power source.

In this paper, we propose a game-theoretic approach using a repeated game to enhance WSNs-based IoT security and DT against the SF attack and pinpoint the nodes that suffer from HW failure. The main contributions of the paper are three folds:

\begin{itemize}

\item

The proposed repeated game aims to detect the malicious CMs in clustered WSNs-based IoT due to the SF attack impact, and simultaneously guarantee  that no wrong action is taken even for a node caused by a HW failure at a low probability. The TDMA protocol is used to preserve the synchronization between the CH and CMs, which reduces the detection mechanism complexity and avoids the collision between the delivered packets at the CH. In addition, the isotropic and non-isotropic packet transmissions have been taken in the model consideration.

\item

The proposed approach models a real situation in which some packets can be dropped or over transmitted due to HW failure of the CMs at the presence of SF attack. We verified that the model could improve the DT performance with the presence of HW failure. It can determine the CMs that suffer from HW malfunction among the CMs infected by the SF attack.

\item

The model attains the Pareto optimality at the optimal DT by resolving the issue of dropping packets due to the SF attack effect. In other words, the model can prevent the designated malicious CMs from dropping packets by supporting these CMs the incentive to act benevolently at which their battery life is conserved. Furthermore, the model can preserve the lost power of packets over transmission or re-transmission as a result of HW failure. The model efficiency is verified through simulation evaluation over six different environments, outdoor line-of-sight (OL), outdoor non-line-of-sight (ON), underground line-of-sight (UL), underground non-line-of-sight (UN), indoor line-of-sight (IL), and indoor non-line-of-sight (IN). Moreover, to draw a realistic WSNs-based IoT system, Tmote Sky mote over the six different environments has been used.

\end{itemize}

The rest of the paper is portrayed as follows. Section \ref{related} presents the related work. In Section \ref{system model}, the system model is discussed. The proposed game approach is then presented in Section \ref{game approach}, while the Pareto optimality and game formulations are addressed in Section \ref{proof}. Section \ref{results} shows the obtained results. Finally, the paper conclusion is revealed in Section \ref{conclusion}.

\section{Related Work}\label{related}

This section discusses the related works of the different WSNs HW failure detection methods and the security front to promote WSNs performance. The security and HW failure in IoT is a prominent problem that can yield into losing data privacy, DT, and wasting power as well. On the one hand, most of the works in the literature context concerning the HW failure utilize the conventional paradigms, e.g., SVM, ML, and random forest by \cite{noshad2019fault,duche2013sensor} and self-diagnosis and cooperative-diagnosis by \cite{jiang2011sensor,jia2018fault,muhammed2017analysis,liu2009fault}.

In \cite{jiang2011sensor}, the faulty node can be detected using redundant node measurements. Thus, the faulty one is isolated based on its reputation obtained by as a minimum of three neighbor voting. Relying on the neighboring nodes was used to adapt time correlation information between these nodes to detect faulty node/(s) \cite{jia2018fault}. An ineffective solution that can cause more delay and cost that rely on using an extra HW (testbed) to check the faulty node \cite{khalastchi2013sensor}. In \cite{muhammed2017analysis}, three statistical algorithms were studied for fault detection called time-series analysis, descriptive statistics, and Bayesian statistics. The time-series mechanism is utilized to detect packets similarities and to measure the amount of data deviation. Descriptive statistics use the mean or median of neighboring nodes to vote for determining the faulty node. Bayesian techniques were employed to determine the likelihood of a faulty sensor based on Bayes theorem. In \cite{liu2009fault}, the authors mentioned that the node could detect the failure by self-diagnosis, such as the faults caused by battery depletion, which is measured by the battery current or voltage. Accordingly, if a node dropped or lost packets, an extra memory should be embedded in the nodes to retrieve those packets and resend again-they said. The authors also respite the lost packet to the environment condition that is why we study the proposed paradigm over six different environments.

On the other hand, uncontrolled WSNs security can deteriorate the DT, data privacy, and power consumption. In this trajectory, game theory has introduced several approaches \cite{abdalzaher2016game,salim2016energy,abdalzaher2016using,abdalzaher2019non,abdalzaher2017effective,abdalzaher2017usingiet,abdalzaher2017using,sfar2019game}. In \cite{abdalzaher2016game}, the authors extensively studied various WSN attacks and the suitable game defense models. In \cite{sfar2019game} Markovian chain was utilized to model the game transitions for preserving the data privacy. In \cite{abdalzaher2016using,abdalzaher2017usingiet}, Stackelberg games have been developed to mitigate the external attacks manipulations using energy defense to avoid the delivered data disruption in a clustered WSN. Stackelberg game has also been extended to confront the false injected data from intelligent attacks in WSNs to enhance the DT \cite{abdalzaher2017effective}. The Stackelberg game was also utilized to confront the false injected noise power in WSNs-based cognitive radio (CR) due to the spectrum sensing data falsification (SSDF) attack, where the HW failure problem was considered \cite{abdalzaher2019access}. The work in \cite{abdalzaher2019access} aims to mitigate the disrupted observed signal-to-noise ratio due to the SSDF attack to make the fusion center in CR capable of achieving accurate decision about the spectrum status. Interestingly, in \cite{abdalzaher2019non}, a nonzero-sum game was proposed to mitigate DoS attack and ON-OFF attack impact and to detect the HW failure in WSNs. The SF attack was handled by game theory in \cite{abdalzaher2016using}. In \cite{abdalzaher2017using}, a repeated game model has been utilized to enhance WSNs DT against the SF attack. More particularly, the most effective parameter in that game was the distance between the communicating nodes, which was criticized by \cite{zhou2004impact}. Moreover, the model in \cite{abdalzaher2017using} omitted the harmful effect of HW failure and did not utilize the TDMA protocol as well. To solve this issue, a more intelligent game model needs to be designed along with a robust detection scheme against the SF attack at the HW failure existence.

Unlike the previous related works, this paper presents an efficient repeated game-theoretic approach along with TDMA protocol to classify between the cause of packet dropping in WSNs-based IoT whether a reason of malicious effect due to SF attack or a result of HW failure to manage the consequent power waste and achieve the optimal DT. The repeated game is considered the best among the cooperative games to support the adequate incentive to guarantee collaborative interaction between the participant players at the price of elapsed time till reaching the equilibrium point, which meets the flexibility of IoT applications time constraint. The proposed model presents the adequate incentive to the malicious CMs due to SF attack to react benevolently and then, uncomplicatedly at the equilibrium point, detects the CMs suffering from HW failure. \vspace{-.1in}

\section{System model}\label{system model}

Figure \ref{disaster_1} illustrates system model using IoT based WSN. In this model, WSN consists of a set of CMs, $\mathcal{N}$, where the number of CMs in the cluster is given by the cardinality of the set $\mathcal{N}$ which is represented by $\mathcal{|N|}$. Table \ref{list} lists the utilized notations and variables. For managing synchronization and packet transmission between the CMs and CH in the clustered WSN, TDMA protocol is utilized as shown in Fig. {\ref{Time}}. In fact, the proposed model is applicable to work with different MAC protocols such as OFDM based protocols \cite{abdalzaher2017using} but we utilize TDMA due to its features supporting the power conservation. As extensively studied in the literature, TDMA is effective for prolonging the network lifetime \cite{van2004advantages}. Moreover, dynamic TDMA, which is a MAC protocol based on scheduled time (DMAC), is efficient for WSNs energy conservation, prolonging network lifetime, and avoiding overhearing \cite{lu2004adaptive}. Consequently, it is an adequate intensive to employ TDMA protocol with the proposed approach.

This paper considers a game-theoretic model where each game player has two actions status. First, every $i$-th CM has to execute either benevolent action by not dropping packets, no drop ($ND$); or malicious action by dropping packets, drop ($D$). The $D$ action is an incentive of the CM to save battery power. Second, the CH performs Beacon ($B$) or no Beacon ($NB$) action status. The $B$ action means that permission is given to the benevolent CM, does not drop packets, to send their observed data. In addition, $B$ is used to permit the $i$-th benevolent CM to go to the sleep mode, to take a rest of packet transmission to save its battery lifetime, or to get power recovery when recharging power is available. Conversely, the $NB$ action is fundamentally used when the $i$-th CM action is $D$. Moreover, a controversial CM performance occurs when it has a random HW failure at the same time of SF attack exist; specifically, the ones suffering from dropping packets and over packets transmissions which are precisely considered through the proposed model. In other words, the model can effectively classify between the infected CMs by the SF attack and the ones suffering from HW failure. The TDMA is also utilized to gradually send the $B$ to the benevolent CM when its turn comes to transmit its data.

\begin{table}[h!]
\centering
\caption{Notations of parameters and variables.}
\label{list}
\begin{tabular}{|c | l |}
\hline
 Symbol & Description \\
  \hline \hline
   $\mathcal{N}$ and $|\mathcal{N}|$ & The set of CMs and the total number of CMs\\
    \hline
    $A_{i}$ & An individual action of $i$-th CM \\
    \hline
    $A_{i}^*$ & The optimal action of $i$-th CM \\
    \hline
    $\mathcal{\textbf{A}}_i$ & Set of action done by the $i$-th CM \\
    \hline
        $A_{CH}$ & An individual action of the CH \\
    \hline
    $A_{CH}^*$ & The optimal action of the CH \\
    \hline
    $\mathcal{\textbf{A}}_{CH}$ & Set of action done by the CH\\
    \hline
    $\textbf{A}$ & The action matrix  \\
    \hline
    $B$ and $NB$ & \begin{tabular}[c]{@{}l@{}}Beacon and No Beacon actions done by \\the CH, respectively\end{tabular}  \\
    \hline
    $D$ and $ND$ & Drop and No drop actions done by the CM, respectively  \\
    \hline
    $RSSI$ & Received signal strength indicator  \\
    \hline
    $TC$ & Transmission cost \\
    \hline
    $TC_0$ & Start up initial cost \\
    \hline
    $TC_A$ & Amplification cost  \\
    \hline
    $V$ & Battery voltage  \\
    \hline
     $T_0$ & Offset (initial) start up time  \\
    \hline

     $I_0$ & Consumed current when radio is ON\\
    \hline

    $I_c$ & Current supported by the battery at transmission level $c$  \\
    \hline
    $DR$ & The transmission data rate  \\
    \hline
    $L$ & The packet length in bits\\
    \hline
    $PL$ & \begin{tabular}[c]{@{}l@{}} The path loss of the link between every $i$-th CM\\ and CH\end{tabular} \\
    \hline
    $PL_{f}$ & \begin{tabular}[c]{@{}l@{}} The free space path loss at the reference distance of the \\antenna far field \end{tabular}\\
    \hline
    $d_{iCH}$ & The distance between the communicating CM $i$ and CH  \\
    \hline
    $d_{0}$ & The reference distance of the antenna far field   \\
    \hline
    $h$ & Transmission power level  \\
    \hline
    $n$ & The path loss exponent  \\
    \hline
    $\sigma$ & The standard deviation of the shadow fading  \\
    \hline
    $\eta$ & The path loss direction coefficient\\
    \hline
$\theta$ & The radiation coefficient angle
      \\
      \hline
      $R$ & A random value $\in ]0,1[$\\
    \hline
     $DOI$ & Degree of irregularity\\
    \hline
    $RL$ & The reliability level\\
    \hline
    $TP$ & \begin{tabular}[c]{@{}l@{}}The total number of packets per message\\ (a given window size) \end{tabular}\\
    \hline
    $pkt$ & Data packet   \\
    \hline
    $U_i$ & The The utility function of the $i$-th CM\\
    \hline
    $\xi_i$ & \begin{tabular}[c]{@{}l@{}}A punishment (loss) parameter deducted \\from the $i$-th CM utility \end{tabular}\\
    \hline
    $\alpha \; \text{and} \; \beta$ & Application dependent weighting factors\\
    \hline
    $eb$ & Transmission energy per bit\\
    \hline
     $DT$ & The data trustworthiness\\
    \hline
    $\overline{DT}$ & The optimal data trustworthiness\\
    \hline
     $rd$ & The round number\\
    \hline
     $N_{rd}$ & The total number of rounds\\
    \hline
\end{tabular}
\end{table}

\begin{figure}[h]
\begin{center}
\includegraphics[width =\columnwidth]{disaster.eps}
\caption{Disaster management using WSNs-based IoT system.}
\label{disaster_1}
\end{center}
\end{figure}

Figure {\ref{beacon}} shows the Beacon ($B$) action/message distribution after checking the CM behavior. At the beginning (Round $\#$ 0), all CMs are supposed to be benevolent. Accordingly, the CH action for all CMs is $B$. After calculating ($U_i$)s for all CMs (at Round $\#$ z), the CH can determine which CM has the right to be supported by the Beacon or not. Therefore, if the $i$-th CM is benevolent and it is its turn using TDMA, it will receive the Beacon. On the contrary, if this $i$-th CM is malicious (drops packets), the Beacon will not be sent to this $i$-th CM. Accordingly, this malicious CM will keep re-transmission of the packets that will not receive acknowledgments on from the CH. Therefore, this approach can deteriorate the battery power of the CM that keeps on malicious behavior, and hence, this CM is prone to going to die. To this end at (Round $\# \; N_{rd}$), $N_{rd}$ is the given period representing the total number of rounds, all CMs are benevolent, and no one will be changed after that unless some of them have HW failure. Indeed, the CH communicates with the CMs throughout a star topology, in which the communication link between each CM and the CH is dedicated, to facilitate the check procedure of the received packets from every $i$-th CM. Therefore, it will be a conventional topology to determine the benevolent CM that does not drop. To this end, there are four scenarios in order due to the CH action ($A^i_{CH}$) and the $i$-th CM action ($A_{i}$). Three scenarios out of these four represent the one-shot games at which both the CH and CM perform the same action regardless of the other player's action. The last scenario introduces the rational interaction between the CH and the $i$-th CM as a reward and punishment defense mechanism according to the action done by every CM. Based on this scenario, all the malicious rational CMs will re-behave benevolently. Finally, the four actions status of the two players (i.e., CH and the $i$-th CM) are given by

\begin{itemize}
\item
$A^i_{CH} =$ $NB$ and $A_i =$ $D$
\item
$A^i_{CH} =$ $NB$ and $A_i =$ $ND$
\item
$A^i_{CH} =$ $B$ and $A_i =$ $D$
\item
$A^i_{CH} =$ $B$ and $A_i =$ $ND$
\end{itemize}

\begin{figure}[h!]
\begin{center}
\includegraphics[width =\columnwidth ]{Time.eps}
\caption{Packet transmission sequence using TDMA protocol.}
\label{Time}
\end{center}
\end{figure}
\begin{figure}[t!]
\begin{center}
\includegraphics[width =\columnwidth]{beacon.eps}
\caption{CH Beacon distribution for the CMs with TDMA.}
\label{beacon}
\end{center}
\end{figure}

\section{Proposed Repeated Game Approach}\label{game approach}

The proposed game confirms a cooperative attitude between the CH (the defender) and the participant CMs. Indeed, the CMs are assumed to act as rational players. The model is used to mitigate the potential malicious CMs that drop the observed packets due to the effect of an intelligent SF attack. The proposed model provides an adequate incentive for the CMs to react benevolently and not drop packets. Conversely, if a CM persists to behave maliciously, this CM will not be given a permission to go to the sleep mode leading to shortly exhausting its battery.

Consequently, rational CMs will prefer to react benevolently because it is more profitable based on the proposed game. This game leads to the Pareto optimality and nash equilibrium (NE) at which both players reach their optimal utility. The utility function of every $i$-th CM per every iteration is computed using three main parameters, namely, received signal strength indicator ($RSSI_{i}$), reliability level ($RL_{i}$), and a punishment parameter ($\xi_i$) between the CH and the $i$-th CM, which is given by
\begin{equation}\label{utility}
U_{i} = \alpha RSSI_{i} + \beta  RL_{i} - \xi_i,
\end{equation}\vspace{-.2in}
\begin{equation}\label{eq2.9}
 \alpha + \beta   = 1,
\end{equation}
where $\alpha$ and $ \beta$ are ''application dependent'' weighting factors \cite{abdalzaher2017using}.

\subsection{Transmission Cost based Received Signal Strength Indicator ($RSSI$)}
First, this parameter concentrates on the main effective factors of the transmission cost that are described as follows.
\begin{equation}\label{rssi}
RSSI = TC - PL - P_n,
\end{equation}
where $TC$ is the transmission cost while $PL$ is the path loss and $P_n$ is the noise power that are obtained from the six exploited environments representing the link quality indicator (LQI) that the CM is deployed over. $P_n$ and $PL$ parameters measurements are indicated in Table {\ref{pathloss}} \cite{gungor2010opportunities}. Then, the transmission cost is expressed by
\begin{equation}
TC = TC_0 + TC_A,
\end{equation}
where $TC_0$ is the initial cost that the CM starts up with, while $TC_A$ denotes the amplification cost for packet transmission. The initial cost can be given by
\begin{equation}
TC_0 = V \times I_0 \times T_0,
\end{equation}
where $V$ is the battery voltage exploited for transmission, $I_0$ represents the current in Amperes when the radio is in (ON state), and $T_0$ is the initial start up time.
\begin{equation}
TC_A = V \times I_c \times \frac{L}{DR},
\end{equation}
where $I_c$ is the current in Amperes with a transmission power level $c$, $L$ represents the packet length, and $DR$ is the transmission data rate. Table \ref{tmote} shows the eight transmission levels along with the corresponding consumed electric current using Tmote Sky mote \cite{corporaton2006tmote}. The adopted path loss between every $i$-th CM and the CH ($i,CH$) is given by

\begin{table}[]
\centering
\caption{Path loss parameters \cite{gungor2010opportunities}.}
\label{pathloss}
\begin{tabular}{|l|l|l|l|}
\hline
Environment                        & $n$  & $\sigma$ (dB) & $P_n$ (dBm) \\ \hline
Outdoor line-of-sight (OL)         & 2.42 & 3.12 &   -93      \\ \hline
Outdoor non-line-of-sight (ON)     & 3.51 & 2.95  &    -93         \\ \hline
Underground line-of-sight (UL)     & 1.45 & 2.45   &   -92         \\ \hline
Underground non-line-of-sight (UN) & 3.15 & 3.19   &   -92         \\ \hline
Indoor line-of-sight (IL)          & 1.64 & 3.29   &   -88         \\ \hline
Indoor Non-line-of-sight (IN)      & 2.38 & 2.25  &    -88         \\ \hline
\end{tabular}
\end{table}

\begin{table}[]
\centering
\caption{Tmote Sky transmission levels and consumed electric current.}
\label{tmote}
\begin{tabular}{|l|l|}
\hline
$h$ & Electric current consumed (mA)  \\ \hline
3   & 8.5                            \\ \hline
7   & 9.9                           \\ \hline
11  & 11.2                           \\ \hline
15  & 12.5                               \\ \hline
19  & 13.9                            \\ \hline
23  & 15.2                          \\ \hline
27  & 16.5                          \\ \hline
31  & 17.4                            \\ \hline
\end{tabular}
\end{table}

\begin{equation}
PL[\texttt{dB}] = \bigg(PL_f[\texttt{dB}] + 10n \log10 \frac{d_{iCH}
}{d_0} \bigg) \times \eta_{\theta} + \sigma[\texttt{dB}],
\end{equation}
where $PL_{f}$ is the free space path loss at the reference distance $d_0$ of the antenna far-field, $n$ denotes the path loss exponent, $d_{iCH}$ is the distance between the transmitting $i$-th CM and the CH, $\sigma$ is the standard deviation in dB of the shadow fading (log-normal distribution) measurements as indicated in Table {\ref{pathloss}}, $\eta_{\theta} \in ]0,1]$ is the path loss direction coefficient when non-isotropic radiation is used, and ${\theta}$ represents the  radiation coefficient angle which is depicted in Fig. \ref{isotropic}.

\begin{figure}[t!]
\begin{center}
\includegraphics[width =\columnwidth]{isotropic.eps}
\caption{Isotropic and Non-isotropic radiation.}
\label{isotropic}
\end{center}
\end{figure}

If the radiation is isotropic, $\eta_{\theta} = 1$. On the other hand, when the radiation is non-isotropic $\eta_{\theta}$ is expressed by
\begin{equation}\label{eq2.4}
\hskip-10pt \eta_{\theta}=
\begin{cases}
 1, & \text{if}\ \ \theta = 0 \\
R \times DOI, & \text{if}\ \ 0^{\circ} < \theta < 360^{\circ},
\end{cases}
\end{equation}
where $R$ is a random value $\in ]0,1[$ and the experienced values of degree of irregularity (DOI) are obtained from the experiments presented in \cite{zhou2004impact}.

\subsection{Reliability Level ($RL$)}

Reliability level for the $i$-th CM ($RL_{i}$) represents the percentage of transmitted packets from the total number of packets ($TP$) per message (i.e., window size) during a given period, which is given by the CH as
\begin{equation}\label{RL}
RL_{i} = \frac{\sum_{j=1}^{TP} f(pkt^{j}_{i})}{TP},
\end{equation}
\begin{equation}\label{eq2.4}
f(pkt^{j}_{i})=
\begin{cases}
1, & \text{if}\ \ \textit{j}\text{-th} \   \text{pkt is forwarded from \textit{i}\text{-th}} \\ & \text{CM to CH}\\
0, & \text{if}\ \ \textit{j}\text{-th} \   \text{pkt at \textit{i}-th CM is dropped} \\ & \text{(not forwarded to CH)},
\end{cases}
\end{equation}
where $pkt_i^{j}$ corresponds to the $j$-th forwarded packet (pkt) from $i$-th CM to the CH, and $RL_{i}$ $\in ]0,1]$.

\subsection{Punishment Parameter ($\xi$)}

The punishment parameter for the $i$-th CM $\xi_i$ in Eq. {\ref{utility}} is utilized to enhance the cooperation between the CH and the participant CMs, which is calculated by
\begin{equation}\label{xi}
\hskip-10pt \xi_i=
\begin{cases}
x1, & \text{if}\ \  A^i_{CH} = NB \ and \ A_i = ND\\
x2, & \text{if}\ \ A^i_{CH} = B \ and \ A_{i} = D\\
x3, & \text{if}\ \ A^i_{CH} = NB \ and \ A_i = D\\
0, & \text{if}\ \ A^i_{CH} = B \ and \ A_i = ND,
\end{cases}
\end{equation}
where $x1$, $x2$, and $x3$ are given by
\begin{equation}\label{x1}
x1 = \sum^{TP}_{j=1} f(pkt^{j}_i) \times \text{L} \times eb,
\end{equation}
\begin{equation}\label{x2}
x2 = \bigg(TP - \sum^{TP}_{j=1} f(pkt^{j}_i)\bigg) \times \text{L} \times eb,
\end{equation}
\begin{equation}\label{x3}
x3 = x1 + x2,
\end{equation}
where $eb$ denotes the transmission energy per bit, and $TP$ is the total number of packets to be transmitted to the CH.

In fact, the term $\xi_{i}$ in Eq. (\ref{utility}) is a loss parameter used to stimulate both CMs and CH to establish a cooperative connection leading to prolonging the network lifetime where three main $\xi_{i}$ cases are used for. First, the CH does not send Beacon message to the $i$-th CM; however, the CM is benevolent by keeping packets transmission to the CH. Therefore, this CM cannot take a rest of packet transmission or go to the sleep mode for saving the battery lifetime at which $\xi_{i} = x1$ due to the non-cooperative behavior of CH. Second, $\xi_i$ equals $x2$ when the CM behaves maliciously by dropping packets; however, the CH cooperates with it by sending it the Beacon. Third, the worst-case at which both the CH and CM choose to be non-cooperative players for which $\xi_i$ equals $x3 = x1 + x2$.

\subsection{Data Trustworthiness (DT)}
According to the above-mentioned subsections, the DT calculated by the CH is defined as the average utility function \cite{abdalzaher2017using} of all CMs during the given time period as
\begin{equation}\label{DT}
DT = \frac{\sum^{N_{rd}}_{rd=1} \sum_{i=1}^{\mathcal{|N|}}U_{i}^{rd}}{N_{rd}}.
\end{equation}
It is worth mentioning that the relationship of the packet drop rate and the DT is inversely proportional.

\subsection{The Proposed Model and Corresponding One Shot Games}

The proposed repeated game is utilized to resolve the equivalent \textit{prisoner-dilemma} \cite{ref_5} using the available four scenarios based on the players' actions. The game is developed to fulfill the Pareto optimal point and NE point at the same state. The first three scenarios represent a one-shot game of \textit{prisoner-dilemma} between the CH and the $i$-th CM in which the DT does not reach to its optimal value. The last scenario presents the proposed repeated game versus the other one-shot games, which are discussed as follows:

\begin{itemize

\item  In the first scenario, all CMs actions are to cooperate with the CH by not dropping any packet ($ND$). In other words, they behave benevolently with the CH. On the other hand, the CH action is $NB$ to be sent to the CMs even they are benevolent. Accordingly, the utility function is affected by Eq. (\ref{x1}) of the punishment parameter.

\item  In the second scenario, the CH chooses to exert $B$ action for all CMs. Conversely, the CM action is to drop ($D$) packets aiming at saving battery lifetime. Therefore, the punishment parameter here is represented by Eq. (\ref{x2}).

\item The third scenario is the worst one at which the minimal utility is obtained due to the CH and CM actions, $NB$ and $D$, respectively. It means that the CH does not provide the CM by the Beacon, and this CM action is to drop packets. Consequently, the punishment parameter ($\xi$) is calculated based on Eq. (\ref{x3}). Therefore, these malicious CMs will not be permitted to go to sleep mode, and hence, they are not capable of preserving their battery lifetime.

\item  The fourth scenario represents the proposed repeated game model for handling the behavior of the $i$-th malicious CM. At the equilibrium point, the CH and all $i$-th CM choose to cooperate by exerting $B$ and $ND$ actions, respectively. More particularly, both RL and utility functions are maximized. Generally speaking, the process of permitting or preventing a CM from the Beacon message until reaching the optimal DT is based on (\textbf{Algorithm 1}). In this algorithm, if a CM drops packets, it will be designated as malicious or suffers from HW failure. In other words, the dropping packets CM will be designated as malicious or labeled in the HW failure list (HWL). Then, this $i$-th CM will go through a punishment cycle till reacting benevolently. At satisfying two constraints, the round number $ rd = i + i\mathcal{|N|}$ comes and this $i$-th CM reacts benevolently again, this $i$-th CM will be given the Beacon. For instance, if $\mathcal{|N|}$ equals 10 and CM 3 is malicious, the Beacon will be supplied to this CM only when it re-behaves benevolently at $rd = 33$. This scheme is recursively executed $N_{rd} = c \mathcal{|N|}$ times till achieving the optimal DT, where $c \in \mathbb{R}_{+}>\mathcal{|N|}$. Consequently, when the CM action is $ND$, its gain is much higher than when its action is $D$ for its utility function. Similarly, when the CH action is $B$ to the CMs, their utility functions are enhanced, which yields to the optimal DT. Therefore, this process is called the punish and forgive strategy. Finally, both the CH and the designated rational malicious CM based on this game will prefer to cooperate due to the gain they can earn. In other words, the cooperative interaction between CH and CMs leads the Pareto optimality and NE at the same state by reaching the optimum DT. After that, any CM drops packets or does over packet transmission is a result of HW failure, which is listed in HWL and quietly detected by the CH.
\end{itemize}

\begin{algorithm}[t]
\caption{Proposed Repeated Game Algorithm for SF attack.
}
\SetAlgoLined
 \textbf{Input} $A^i_{CH} = \{B, NB\}$, $A_i = \{D,ND\} $ \;

 \While{$ d \leq c\mathcal{|N|}$}{
  Compute $RSSI_i$, $RL_i$, $\xi_i$, and $U_{i}$ by Eqs. (\ref{rssi}), (\ref{RL}), (\ref{xi}) and (\ref{utility}) $\forall i \in |\mathcal{N}|$\;

  Determine the malicious CMs or the ones have HW failure\;

	{\eIf{ CM$_i$ drops pkt $\rightarrow$ A$_i$ is $D$}
	{This $i$-th CM $\rightarrow$ malicious/HWL\;}
	{This $i$-th CM is designated as benevolent and No HW failure;}}

   {\eIf {$A_i$ of this $i$-th CM is  $ND$ and $rd = i + i\mathcal{|N|}$}
   {This $i$-th CM will receive $B$ message ($A^i_{CH}$ $\rightarrow B$)\;}
   {This $i$-th CM will be listed in HWL;}}
{\eIf{DT is calculated using Eq. (\ref{DT}) and ($A^i_{CH},A_i$) $\rightarrow$ ($A_{CH}^*,A_i^*$) $\forall i$}
{DT is optimal and $NE$ exists\;}{Continue\;}}

}
 \textbf{Output} Optimal DT is attained and $(A^*_{CH}, A^*_i), \forall i$ $\rightarrow$ NE exists\;
\If{$A_i = D$}
{This $i$-th CM suffers from a HW failure\;}
\end{algorithm

\section{Pareto Optimality and Game Formulations}\label{proof}

The proposed repeated game is between the CH (defender) and every $i$-th CM, which is denoted by
\begin{equation}
G=\langle \{CH, i\}, \textbf{A}, U_{i}\rangle.
\end{equation}

The CH set of actions $\mathcal{\textbf{A}}_{CH}$ represent the CH defense strategy $DS_{CH}(\xi_i, DT)$ against the designated malicious CM. Conversely, $\mathcal{\textbf{A}}_{i}$ denotes the $i$-th CM malicious strategy $MS_{CM}(f(pkt^{j}_i), DT)$ at which the $j$-th packet is dropped by the $i$-th CM.

The best strategy is achieved using the proposed game represented by the fourth scenario in which the optimal action of the $i$-th CM $A^*_i \in \mathcal{\textbf{A}}_i$ is given by
\begin{equation}\label{eq2.11}
A^*_i = \underset{\xi_i=0}{\operatorname{arg\,max}} (U_i).
\end{equation

More concretely, the optimal action of the $i$-th CM and CH are given by
\begin{equation}\label{eq2.12}
A^*_i = ND \rightarrow f(pkt^{j}_i)= 1, \forall j \in TP,
\end{equation}

\begin{equation}\label{eq2.13}
A^*_{CH} = \underset{f(pkt^{j}_i)= 1, \forall j \in TP, \forall i \in \mathcal{N}, j \neq i}{\operatorname{arg\,max}} (DT).
\end{equation}

\noindent Taking into consideration the rationality principle of the participant players, the CH will choose to cooperate and use $B$ action. Consequently, $A^*_{CH}$ can be simplified as
\begin{equation}\label{eq2.14}
A^*_{CH} = B \rightarrow  \xi_{i} = 0, \forall i.
\end{equation}

Consequently, the NE is achieved, which is given here by
\begin{equation}\label{eq2.15}
U_i(A^*_{CH},A^*_i) \geq U_i(A^i_{CH},A^*_i), \forall i \in \mathcal{N}.
\end{equation

Then, we prove that both the Pareto optimal and NE point are achieved in the same state as follows:

Let the Pareto optimality is attained at optimal DT ($\overline{DT}$). Consequently, any other value of DT is less than this optimal value as

\begin{equation}\label{eq8.16}
\overline{DT} \geq DT.
\end{equation}

$\overline{DT}$ is attained using the punish-and-forgive strategy that is presented in the fourth scenario, which is derived by

\begin{equation}\label{eq8.17}
\overline{DT} = \quad \min_{A_{CH}} \max_{A_{i , \forall i \in \mathcal{N}}} DT,\
\end{equation}

\begin{equation}\label{eq8.18}
\quad \min_{A_{CH}=B} \xi_i = 0\, \; \forall i \in \mathcal{N},\
\end{equation}

\begin{equation}\label{eq8.19}
\therefore U_{i} = \alpha RSSI_i + \beta RL_i, \forall i.
\end{equation}

\begin{equation}\label{eq8.20}
 \quad \max_{A_{i, \forall i \in \mathcal{N}}}  f(pkt_i^{j}), \forall j \in TP, \; \forall i \in \mathcal{N}, j \neq i,\
\end{equation}

\hspace{-15pt} Accordingly, $A^*_i = ND \rightarrow f(pkt_i^{j}) = 1, \forall i \in \mathcal{N},  j \neq i,$ and $ A^*_{CH} = B \rightarrow \xi_i = 0, \forall i \in \mathcal{N}$

\begin{equation}\label{eq8.21}
\therefore RL_i = 1, \forall i \in \mathcal{N},
\end{equation}

\begin{equation}\label{eq8.22}
\therefore \overline{DT} > DT.
\end{equation}

Consequently, the NE and Pareto optimality are achieved at the same state when $\overline{DT}$ exists at $(A^*_{CH},A^*_i), \forall i \in \mathcal{N}$.

\section{Simulation results and Discussion}\label{results}

This section shows the simulation results. The simulation parameters are depicted in Table \ref{parameters}. We use Tmote Sky mote as a realistic node model among the most usable nodes with standard of IEEE 802.15.4 supporting precise locations and scalability for IoT platforms \cite{raza2011securing} that equipped by the Texas Instruments MSP430 microcontroller with a Chipcon CC2420 radio, and utilize the parameters from its datasheet in \cite{corporaton2006tmote}.
We also assumed that 20\% of CMs suffer from a random HW failure, and all CMs use power level $h=31$ as an empirically selected optimum value. The utilized DOI measurement values are $\{0.0055, 0.0035,0.004,0.0045,0.006,0.0085\}$ \cite{zhou2004impact}.
All CMs are located at the maximum coverage range between the CH and every Tmote Sky CM (125 m) to show the effectiveness of the proposed model. Besides, the DT of the received signal is affected by $P_n$, path loss, and shadowing fading (log-normal distribution with standard deviation $\sigma$). We assume six environment scenarios (i.e., OL, ON, UL, UN, IL, and IN), where their path loss parameters are given in Table {\ref{pathloss}} \cite{gungor2010opportunities}. Rayleigh fading is not taken into consideration.

\begin{table}[b]
\caption{Simulation parameters.}
\label{parameters}
\centering
\begin{tabular}{|l|l|l |l|}
\hline
Parameter       & Value     & Parameter   & Value                                                                                \\ \hline \hline
$\mathcal{|N|}$ & 10        & \begin{tabular}[c]{@{}l@{}} No. of randomly assumed \\malicious CM \end{tabular} & 1 and 2                                                 \\ \hline
$L$        & 1024 bits     & $T_0$       & 580 $\mu$s                                                                                \\ \hline
$I_0$        & $\mu$A   & $DR$   & 250 Kb/s                                                                                \\ \hline
$I_c$        & 17.4 mA      & $V$   & 3 Volts \\ \hline
$\alpha$ and $\beta$        & 0.6 and 0.4    & $eb$   & 50 nJ \\ \hline
 $d_0$      & 10 m \cite{corporaton2006tmote} & $d_{iCH}$  & 125 m \cite{corporaton2006tmote}  \\ \hline
$PL_f$             & 55 dB   & $h$             & 31 \\ \hline
$TP  $           & 100  & $c$   & 11 \\ \hline
\end{tabular}
\end{table}

Figure \ref{comp_old} illustrates the improved performance using the proposed game as compared to the work in \cite{abdalzaher2017using}. It is clear that the normalized DT of the proposed game reaches the equilibrium state much faster than the corresponding game model in \cite{abdalzaher2017using}. Moreover, the obtained normalized DT of the three one-shot games involved in this paper gets worse as compared to the proposed repeated game and corresponding results in \cite{abdalzaher2017using}. It means that the proposed repeated game is more effective than the work in \cite{abdalzaher2017using} for stimulating the CH and CM to cooperate using $B$ and $ND$ actions, respectively.

Figure \ref{model_3shotG} shows the obtained results of the proposed repeated game model as compared to the three one-shot games. It is clear that after the equilibrium point, the model maximizes the normalized DT leading to the optimal DT whether the number of malicious CMs equals 1 or 2. We succeeded to prove that in both the isotropic and non-isotropic packet transmission. The minimum normalized DT is achieved by the third scenario when the CH and CM actions are $NB$ and $D$, respectively. This is because the punishment parameter is considered doubled using Eq. (\ref{x3}). The normalized DT of the first and second one-shot games (first and second scenarios) get better performance than the third one but are still less than the proposed game results.

Figure \ref{DOI} shows a comparison between the obtained normalized utility functions of the isotropic and non-isotropic packet transmission using the proposed repeated game model over the six environments (OL, ON, UL, UN, IL, and IN) with each DOI measurements. Generally speaking, all the obtained results with any environment are close to their corresponding ones regardless of the DOI value. It is clear from Fig. \ref{DOI}a-d, with IN environment type, at which the values of $\sigma$ and $n$ are very close, the change of DOI does not affect the model performance as both the normalized utility of the isotropic and non-isotropic transmission are overlapped.  Interestingly, we can observe that the non-isotropic exceeds the isotropic packet transmission by only 1\% - 4\% that reflects the efficiency of the proposed model.

Detecting HW failure is discussed using both Fig. {\ref{HW_UL}}(a) and Fig. {\ref{HW_UL}}(b). At the equilibrium point, all the rational malicious attempts are refrained whether with isotropic or non-isotropic packet transmission. Afterward, any dropping packet or over packet transmission will be due to the HW failure not the SF attack.
Figure {\ref{HW_UL}}(a) shows the normalized utilities of the 10 CMs in which the values that exceed 100\% are due to the over packet transmission of the CMs that suffer from HW failure such as CM 4 and 8. The UL environment has the least path loss exponent that reflects the minimum effect on the isotropic radiation of packets. Therefore, the best-normalized utilities of using the proposed model with the isotropic packet transmission among the six environments are in the UL environment in which the utilities reach 96.8\%. Conversely, the ON environment represents the worse effect on the optimal isotropic normalized utilities, which reach only 93.5\%, as shown in Fig. {\ref{HW_UL}}(b).

Afterward, the enhanced performance and model efficiency using the number of successfully transmitted packets have been depicted in Fig. \ref{pkt} using isotropic transmission over the ON environment representing the worst constraints. The number of transmitted packets counted at the equilibrium state based on the proposed repeated game is quite higher than the other three one-shot games as a result of the attack presence. In this regard, based on the proposed model along with the TDMA protocol, the CH can receive a much higher number of trusted packets from the CMs leading to the optimum DT in the six environments and DOIs. In other words, the model effectiveness has been achieved against the SF attack regardless of the environment and DOI types and whether the packet transmission is isotropic or non-isotropic.

Moreover, the comparison between the lost power using the proposed model and without detection mechanism against the SF attack is shown in Fig. \ref{power} over ON environment representing the worst constraints. If the proposed model has not been used, the network will be prone to lose a valuable amount of power due to the SF attack and the undiscovered CMs that suffer from HW failure, leading to battery power deterioration that increases with the increase of the number CMs as shown in Fig. \ref{power}. More particularly, the intensive power degradation is a result of giving negative acknowledgment by the CH to the malicious CMs and hence, they recursively transmit those packets that do not receive acknowledgments. Moreover, these CMs will not receive the Beacon to take a rest from the transmission or to go to the sleep mode. Therefore, the fraudulent behavior of the CMs will aggravatingly contribute to exhaust their battery lifetime.

Figure {\ref{elapsed_time}} shows the relationship between the elapsed time and the number of CMs over the ON environment representing the worst constraints. The obtained results compare between the obtained results based on the proposed model and the corresponding work in \cite{abdalzaher2017using}. It is clearly shown that the time consumption using the proposed model is much less than the work in \cite{abdalzaher2017using} regardless of the number of CMs. Moreover, the proposed model presents an enhanced performance result regardless of increasing the number of CMs.

\begin{figure}[t]
\begin{center}
\includegraphics[width =.65\columnwidth]{fig2_comp_old_new.eps
\caption{Normalized DT comparison between the proposed model and the corresponding in the literature using Non-isotropic transmission over UL environment, number of malicious CMs equals 2.}\vspace{.3in}
\label{comp_old}
\end{center}
\end{figure}

\begin{figure}[h!]
\begin{center}
\includegraphics[width =.65\columnwidth]{fig1_comp_2mal_wanted.eps
\caption{Normalized DT based on the proposed repeated game compared to the three one shot games using Isotropic and Non-isotropic transmission and over ON environment, when number of malicious CMs equals 1 and 2.}\vspace{.2in}
\label{model_3shotG}
\end{center}
\end{figure}

\begin{figure*}[!ht]
    \centering
\begin{subfigure}{0.3\textwidth}
  \includegraphics[width=\linewidth]{U_all_env_doi_1_wanted.eps}\vspace{-.05in}
  \caption{DOI 1}
  \label{fig:1}
\end{subfigure}\hfil
\begin{subfigure}{0.3\textwidth}
  \includegraphics[width=\linewidth]{U_all_env_doi_2_wanted.eps}\vspace{-.05in
  \caption{DOI 2}
  \label{fig:2}
\end{subfigure}\hfil
\begin{subfigure}{0.3\textwidth}
  \includegraphics[width=\linewidth]{U_all_env_doi_3_wanted.eps}\vspace{-.05in}
  \caption{DOI 3}
  \label{fig:3}
\end{subfigure}

\medskip
\begin{subfigure}{0.3\textwidth}
  \includegraphics[width=\linewidth]{U_all_env_doi_4_wanted.eps}\vspace{-.05in}
  \caption{DOI 4}
  \label{fig:4}
\end{subfigure}\hfil
\begin{subfigure}{0.3\textwidth}
  \includegraphics[width=\linewidth]{U_all_env_doi_5_wanted.eps}\vspace{-.05in}
  \caption{DOI 4}
  \label{fig:5}
\end{subfigure}\hfil
\begin{subfigure}{0.3\textwidth}
  \includegraphics[width=\linewidth]{U_all_env_doi_6_wanted.eps}\vspace{-.05in}
  \caption{DOI 6}
  \label{fig:6}
\end{subfigure}\vspace{-.1in}
\caption{Utility comparison of isotropic and non-isotropic packet transmission based on only the proposed repeated game over the six environments at every DOI, when number of malicious CMs equals 2.}
\label{DOI}
\end{figure*}

\begin{figure*}[!ht]
    \centering
\begin{subfigure}{0.45\textwidth}
  \includegraphics[width=\linewidth]{HW_UL_iso_noniso_up.eps}
  \caption{UL}
  \label{fig:1}
\end{subfigure}\hfil
\begin{subfigure}{0.45\textwidth}
  \includegraphics[width=\linewidth]{HW_ON_iso_noniso_up.eps}
  \caption{ON}
  \label{fig:2}
\end{subfigure
\caption{HW failure based on utility representation of isotropic and non-isotropic throughout (a) UL and (b) ON environments, 20\% of CMs suffer from HW failure.
\label{HW_UL}
\end{figure*}

\begin{figure}[h!]
\begin{center}
\includegraphics[width =.7\columnwidth]{pkt.eps}\vspace{-.1in}
\caption{Number of transmitted packets without and with attack presence using isotropic transmission over ON environment.
\label{pkt}
\end{center}
\end{figure}

\begin{figure}[h!]
\begin{center}
\includegraphics[width =.7\columnwidth, height=7cm]{power.eps
\caption{Lost power for the selfish CMs due to the SF attack impact using isotropic transmission over ON environment.
\label{power}
\end{center}
\end{figure}

\begin{figure}[h!]
\begin{center}
\includegraphics[width =.6\columnwidth, height=6.5cm]{elapsed_time.eps
\caption{Elapsed time comparison using isotropic transmission over ON environment.
\label{elapsed_time}
\end{center}
\end{figure}

\section{Conclusion}\label{conclusion}
In this paper, we have proposed an efficient repeated game defense model along with the TDMA protocol to effectively detect the SF attack and HW failure in clustered WSNs-based IoT systems. The developed model can stimulate the malicious CMs that drop packets to react benevolently and hence, facilitate the HW failure detection to achieve the optimal DT. Consequently, the model solves a \textit{prisoner-dilemma} problem and is capable of attaining both the Pareto optimality and NE at the same state when the maximum DT exists. Moreover, the model proves beneficial in security enhancement, maximizing DT, and managing the consequently lost power leading to robust IoT networks. Simulation results demonstrate the effectiveness of the proposed model regardless of the environment, DOI, and isotropic and non-isotropic transmissions achieving robust WSNs-based IoT by preventing the packet drop due to the SF attack. Furthermore, the model can maximize the number of successfully transmitted packets. One of the future works is to evaluate our approach using testbed.  \vspace{-.05in}

\bibliographystyle{IEEEtran}


\section{Extra Text}
very small numbers of supervised training examples, and make use of unlabelled data.
\end{comment}

\section{Introduction}

The field of question answering has been dominated by supervised methods
for competitive tasks such as the Stanford question answering dataset
(SQuAD) \cite{rajpurkar2016squad}.
However, as discussed in \citet{yogatama2019learning},
some of these datasets are becoming over-optimised for,
making the architectures less generally applicable.

At the other extreme,
the ability of the GPT-2 \cite{radford2019language} model to answer factoid questions,
based purely on unsupervised training directed
at improving its Language Model (LM) performance, was striking.
But further reflection highlights the following issues :
\begin{itemize}
\item Questions correctly (and confidently) answered were a small fraction ($\sim$1\%) of the questions asked
\item Huge model size and long training periods were required before such behaviour was manifested
\item This does not appear to be a practical approach to adsorbing an extensive knowledgebase
\end{itemize}

This work describes early work in aiding generalised models such as GPT-2
to answer questions, without having to embed
facts directly in the model's weights.
The overall direction of work is towards encouraging such generalised
models to make use of external datasources (and other resources)
without having to internalise all the data in models of exponentially
increasing size (e.g. GPT-2-1.5B is more than 10x the size of GPT-2-117M).

\section{Natural Questions Dataset}

The Natural Questions (NQ) dataset \cite{natural_questions_47761}
is a question answering dataset containing
307,373 training examples, 7,830 development examples, and 7,842 test examples.
Each example is comprised of a google.com query and a corresponding Wikipedia page.
Each Wikipedia page has a passage (or long answer)
annotated on the page that answers the question
and one or more short spans from the annotated passage
containing the actual answer.
The long and the short answer annotations can however be empty.
If they are both empty, then there is no answer on the page at all.
If the long answer annotation is non-empty,
but the short answer annotation is empty,
then the annotated passage answers the question
but no explicit short answer could be found.
Finally, 1\% of the documents have a passage annotated with a short
answer that is `yes' or `no', instead of a list of short spans.

As reported in \citet{radford2019language},
GPT-2-1.5B answers 4.1\% of NQ questions correctly when evaluated
by the exact match metric commonly used on reading
comprehension datasets like SQuAD.
In contrast, the smallest GPT-2-117M model
(used as the basis for the model proposed in this work)
is reported as not being capable of exceeding the 1.0\% accuracy of
the simple baseline which returns the most
common answer for each question type (who, what, where, etc...).
The fact that GPT-2-1.5B answered 5.3 times more questions correctly
suggests that model capacity has been a major factor in
the poor performance of neural systems on this kind of task
as of yet.

\section{Model Architecture}

The model proposed here is built from several components which
include (a) 876k Wikipedia sentences,
addressible via embeddings;
(b) a pretrained GPT-2-117M language model which was noted to be incapable of
answering questions successfully in \citet{radford2019language}; and
(c) a scheme for incorporating `sentence hints'
into the language generation context.

\subsection{Embeddings for Sentence Lookup}

Three different
embedding methods were used :

(i) pre-trained BERT-base (L=12, H=768, A=12, Total Parameters=110M) \cite{devlin2018bert},
using the the $\mathtt{bert-as-service}$ Python tool\footnote{\url{https://bert-as-service.readthedocs.io/}}.
For a given input sentence this returns a 768-d embedding,
calculated as the GlobalAveragePooling of the top-but-one
layer of the pretrained BERT model;

(ii) Smooth Inverse Frequency (SIF) \cite{arora2017asimple} embeddings,
calculated by inverse-frequency weighting the BPE embeddings
(from the GPE-2-117M model being used for the text generation task)
followed by removal of the first PCA component; and

(iii) Universal Sentence Encoder \cite{cer2018universal},
the training details not clear in the
paper, but USE is not a purely unsupervised model :
``We augment unsupervised learning with training on supervised data
from the Stanford Natural Language Inference (SNLI) corpus'' \cite{snli:emnlp2015}.

Methods (i) and (ii) were not fine-tuned on the question answering task
(since this would violate the spirit of this unsupervised-only system),
whereas method (iii) was included to judge the benefits of adding some supervised
training to the embedding stage.

\begin{table*}[th]
\caption{Sample question answers with filter examples,
and examples of answers where pure SQuAD accuracy did not make sense
when the base data included far more information than the original (single)
wiki article targetted by the Natural Questions dataset.}
\label{qanda-table}
\vskip 0.15in
\begin{center}
\begin{small}

\begin{tabular}{llll}
\hline
Question & Target & GPT-2-117M & Reject reason \\
\hline
Who is the richest club in the championship?  &
`Aston Villa', &
The richest club in  &
{\sc Smart Alec}
\\
& `Manchester City' & the championship & \\
\hline
Are all firestone tires made in the usa? &
`NO' &
No &
{\sc Y/N question}
\\
\hline
What is the name of manchester united stadium? &
`Old Trafford' &
Manchester United &
{\sc Within question}
\\
\hline
Who cracked the enigma code in world war 2? &
`Turing' &
Alan Turing &
{\sc N/a : Accepted}
\\
\hline
How many inches is the iphone 5s screen?	&
`4 - inch screen size', &
4 inches &
{\sc N/a : Accepted}
\\
&`4 in', `4 in ( 10 cm )' &  &
\\
\hline
\end{tabular}

\end{small}
\end{center}
\vskip -0.1in
\end{table*}

\subsection{Embeddings for Questions}

In order that facts might be supplied by external text,
embeddings $e(s_n)$ were produced
for each sentence $s_n$ of the $N(=876,645)$ wikitext sentences,
and also $e(q_j)$ was calculated for each $q_j$ of the $J$ questions.

The search term was calculated by adding a `question to sentence' vector,
set to the mean difference between the embeddings for question phrases
and those of wikitext sentences to the original question $q_j$  :
\[
search_j = e(q_j) + \frac{1}{N}\sum{e(s_\cdot)} - \frac{1}{J}\sum{e(q_\cdot)}
\]

\subsection{Knowledge Look-up}

In order to aid the LM in retrieving factoid answers,
`hint sentences' sufficient to fill half of the LM context window
were retrieved
from the list of the $N$ wikitext sentences, using
a cosine distance ranking of the $s_n$ vs $search_j$

\begin{figure}[t]
  \vskip 0.0in
  \begin{center}
    \centerline{\includegraphics[width=\columnwidth]{model-diagram.pdf}}
    \caption{
    Proposed information flow : (a) Initial question; (b) Wiki sentence ranking; (c) hinting in preamble; (d) GPT2 output.
    }
    \label{model-diagram}
  \end{center}
  \vskip -0.2in
\end{figure}

\subsection{LM Context Seeding}

In order to obtain the results in \citet{radford2019language}
for the NQ task, their GPT-2-1.5B model context was seeded with
example question/answer pairs which helped the model
infer the short answer style of the dataset.

Rather than expect the smaller GPT model to extrapolate from
the Q \& A format,
both the `hint sentences' and the question $q_i$
were incorporated into the context seen by the model directly:

\begin{quote}
Information :

$\mathtt{HintSentence{[}~{]}}$ {\it or} $\mathtt{None}$

The best short answer to ``$q_i$?'' from the
information above is `` \ldots
\end{quote}

The GPT-2-117M output is then recorded up until the closing double-quote
(closing quotes appears to be strongly favoured by the LM).

\subsection{Sampling from the Language Model}

A number of approaches to sampling from the model were tried
(including Beam search, which performed poorly),
and the following were found to work satisfactorially :

\begin{enumerate}
\item  SoftMax temperature was kept at 1.0 (i.e. as trained);

\item  Nucleus Sampling \cite{holtzman2019curious} was used,
with only tokens that cover the first 90\% of probability space
being considered as choices at each step.  This appears to give
a good mix of diversity without `going off the rails' - which is
desirable for human-like communication \cite{grice1975logic};

\item   A probability bias term \cite{murray2018correcting} was added to the
log-probabilities of each sequence, whereby each token was `awarded' a bonus of $\alpha$,
which was found empirically to create a more balanced spread of long and short outputs;

\item   After a sorted list of 100 different sequences was created, this was
further filtered (as illustrated in Table \ref{qanda-table}) to reject answers that were very unlikely to be correct:

     \begin{itemize}
\item answers that simply repeat the question (determined as whether
the answer's bigram Jaccard similarity with the question exceeds 0.5);
\item answers that are contained within the question verbatim;
\item answers such as `yes/no', `i don't know', `none', `no one', `it depends' -
which may have been safe choices,
but could not score positively on the filtered list of questions.
     \end{itemize}
\end{enumerate}

Further details can be found in the Supplimental Materials.

\section{Experiments}

The model architecture was applied to the NQ task,
and results are reported for performance on the validation set
(the training set was unused).
Only questions that were (a) not Yes/No; and (b) had a `short answer' were considered,
resulting in 3975 triples of \{question, wikitext, answer list\}.

The list of `hint sentence' candidates was set to be
the aggregate of all the sentences across the 3975 wikitext pages,
totalling $\sim$876k sentences.
Importantly, the hint sentence choices weren't restricted to
the wikitext corresponding to the specific question -
which makes the task significantly more difficult that the
BERT baseline for Natural Questions task \cite{alberti2019bert}, which
works on an article-by-article basis.

In the results reported, to reduce noise, the `Yes/No' questions
were removed from consideration
(since scoring positively on these examples may the result of a coin-flip).

\section{Results}

This work is in its early stages, and the results obtained so far are encouraging,
despite being low in number.

For the 3975 useful NQ development set questions,
we found that the poor results of using GPT-2-117M unaided reported
in \citet{radford2019language} were born out.

However, when using each question to select `hint sentences'
from the whole list of 876k wikitext sentences,
the GPT-2-117M was able to make use of the extra information
(without having been explicitly training to do so).

\begin{table}[h]
\caption{Question answering accuracy.}
\label{results-table}
\vskip 0.15in
\begin{center}
\begin{small}
\begin{sc}

\begin{tabular}{lrrr}
\hline
Embedding & dim & $\alpha$ & Score \\
\hline
No Hints  & - & 0.0   &  0.84\% \\
\hline
BERT-REST & 768 & 0.0   &  1.08\% \\
SIF       & 768 & 0.7   &  3.14\% \\
SIF       & 768 & 0.2   &  3.29\% \\
\hline
USE       & 512 & 0.0   &  4.45\% \\
\hline
\end{tabular}

\end{sc}
\end{small}
\end{center}
\vskip -0.1in
\end{table}

Note that the results in Table \ref{results-table} are not directly comparable with the
reported accuracy of the 1.5 billion parameter GPT-2-1.5B (4.1\%),
since the ``Yes/No'' questions have been deliberately excluded in the experimental results above,
since random chance would then add approximately 1.8\% (of pure noise)
to the results presented here.  Adjusting the reported GPT-2 figures
(downward) for this effect shows that the proposed model has higher performance
for a much lower parameter count, even when using purely unsupervised training methods.

\section{Discussion}

As mentioned in \citet{sutskever-openai-video},
an online video in which \citet{radford2017learning} is discussed,
`higher order' capabilities seem to appear in language-related models
only if the size of the model is sufficient to have captured
many the basic features of the underlying language,
since knowing the basic words and structures is more important to a Language Modeling
objective than higher order features like sentiment and story arc (for instance).

Being able to capture such higher order features
provides a natural incentive to want to scale the training of language models
to as large a number of parameters as possible.
And undoubtedly there will be important and interesting results to come out of these efforts.

However, it is not at all clear that embedding factoids
in neural network weights is a practical way of building intelligent systems.
Even humans (built on a biological neural substrate)
seem to reason about facts symbolically \textit{despite} the processing being
based in neurons.

The goal of this research is to explore how to interface
the extremely effective aspects of models such as GPT-2
with more accessible sources of knowledge and planning.

By using the \textit{human readable} output of a Language Model
component to direct further information gathering (or, potentially, other activities),
one might imagine the system would not only become more capable (without exponentially long training),
but would also have an \textit{internal dialogue} that would be human interpretable.

\subsection{Further Work}

Clearly, more experimentation is needed to understand how to improve the current
system.  Fortunately, that can be accomplished without a huge investment in hardware.

In terms of sentence embedding techniques,
one additional method was investigated, so far without encouraging results :
the generation of sentence embeddings from
using an additional layer for the GPT-2-117M model
it its initially untrained state.  This deserves further work,
given the findings of \citet{wieting2019training}.

Also interesting is the potential for training a more specific retrieval/utilisation
engine in a supervised manner, such as in \citet{Bapna_2019}, and then expanding the domain across which retrieval
is performed to encompass a much broader range of accessible facts without further training the model.
However, this is slightly contrary to the goal herein of using purely unsupervised techniques.

Beyond these initial phases, though, there is the potential for the
system to achieve some level of self-improvement.
As was discussed in \citet{radford2019language}, the GPT-2-1.5B model
could not only answer some factoid questions, but it also had a
good (self-) model of confidence in its answers\footnote{
``The probability GPT-2 assigns to its generated
answers is well calibrated and GPT-2 has an accuracy of
63.1\% on the 1\% of questions it is most confident in.''}.
This implies that if a trainable embedding component
were included in \textit{this} paper's architecture it might be trainable
(in a fully self-supervised way) to improve its self-hinting,
and thereby achieve a self-improving positive feedback loop.

\section*{Acknowledgments}
The authors would like to thank Google for access to the TFRC TPU program which
was used in training and fine-tuning models during experimentation for this paper.

\bibliographystyle{acl_natbib}


\section{Introduction}

In topological dynamics, the topological entropy of a dynamical system measures the information in orbits, by counting the exponential growth rate of different partial orbits with a certain of accuracy. One example of a dynamical system is a \emph{subshift}, a dynamical system whose points are infinite words over a finite alphabet $A$, and the dynamics is the left shift. One-way entropy can arise in a subshift when, somewhere in partial orbits, we literally see all distinct words $A^n$ up to $n$. One may ask to what extent entropy always arises from such ``free choices''.

Two formal notions that most directly capture this idea are the \emph{independence entropy} of a subshift and \emph{independence sets}. The former measures how much entropy comes from ``set-theoretic hyperrectangles'', namely sets of the form $A_1 \times A_2 \times \cdots A_n$ which are contained in the language of the subshift as $n \rightarrow \infty$, where $A_i \subseteq A$ are any subsets of the alphabet and we consider consecutive letters only, see \cite{LoMaPa13}, (p.~303) for the precise definition. Positive entropy does not imply positive independence entropy (see Proposition~\ref{prop:NoIndependenceEntropy}).

Independence sets, on the other hand, are defined similarly in \cite{KuKwLi14a,FaKuKwLi15}, but we allow gaps between the positions where the prescribed letters appear, and there is no constraint on the words seen in the gaps between the positions. More precisely, in the case of a subshift $X$ with a binary alphabet $A = \{0,1\}$, an \emph{independence set} is a set $N \subseteq \mathbb{N}$ such that $X|_N = \{0,1\}^N$. It turns out that the existence of an independence set of positive lower asymptotic density does capture positive entropy, see \cite{KuKwLi14a,FaKuKwLi15} for a proof in this binary subshift case, and \cite{GlWe95,HuYe06,KeLi07} for analogous results in more general settings.

The following theorem gives a new proof of this result (see Corollary~\ref{cor:IndependenceSet}), but it is stronger, as there is an additional constraint on how the independent choices must be realized. It also applies in the case of a general alphabet.

\begin{theorem}
\label{thm:Main}
A subshift $X \subseteq A^\mathbb{N}$ has positive entropy if and only if it contains a steadily branching binary tree.
\end{theorem}

We can interpret $A^\mathbb{N}$ as the boundary of an $|A|$-ary tree and $X$ a closed subset of this boundary. A closed subset of the boundary of a tree is determined by finite subpaths in the tree, and it is in this sense that $X$ contains the binary tree. Steadily branching means that the embedded binary tree branches at a uniform sequence of times which form a set of positive lower asymptotic density. A formal definition is given in Section~\ref{sec:Winning}.

Positive entropy refers to topological entropy, and in the context of subshifts, means the exponential growth of the number of words. Countable subshifts can have a growth rate arbitrarily close to exponential (see Proposition~\ref{prop:Countable}), but clearly contain trees with only finitely many branchings. Thus, if we weaken the assumption of positive entropy, the existence of a steadily branching binary tree can fail in a very strong sense.

It is also easy to find examples with positive entropy where it is not possible to find a tree where branchings happen a syndetic set of times (see Proposition~\ref{prop:NoSyndetic}). There are also examples where no individual tree which branches at a uniform sequence of times ``captures'' all of the entropy, as can be seen from \cite{LoMaPa13}, (Example~2). These remarks show that we cannot expect to essentially improve the conclusion about the tree under the assumption of positive entropy.

The proof of Theorem~\ref{thm:Main} is straightforward using the standard results about the winning shift, which is the set of winning turn orders in a certain word-building game associated to $X$. The winning shift is known to have the same entropy as $X$. This implies it has a point with positive density, and this point is the branching structure of a steadily branching tree in~$X$. This note is simply a self-contained elaboration of this deduction. I give a combinatorial proof directly from the definitions, and also include an ergodic theoretic proof.

It is easy to deduce a two-sided version of the result as well. For $x \in A^{-\mathbb{N}}$ and $y \in A^\mathbb{N}$, write $x \cdot y \in A^\mathbb{Z}$ for the configuration with $x$ and $y$ back to back.

\begin{theorem}
\label{thm:Z}
A subshift $X \subseteq A^\mathbb{Z}$ has positive entropy if and only if for some $x \in A^{-\mathbb{N}}$, the set $\{y \in A^\mathbb{N} \;:\; x \cdot y \in X \}$ contains a steadily branching binary tree.
\end{theorem}

The winning shift was introduced in \cite{SaTo14c}, and has also been studied in \cite{PeSa19}. We found out while working on \cite{PeSa19} that a concept equivalent to the winning shift was discovered in the set systems setting already in 2002 \cite{AnRoSa02} (even if ostensibly only for binary words), and I found out while working on the present paper that \cite{AnRoSa02} has been applied by \mbox{dynamicists \cite{KuKwLi14a,FaKuKwLi15}} (this paper is independent from \cite{SaTo14c}, but almost contemporary), and their proof that this gives large independence sets essentially boils down to the same proof as I give here. Nevertheless, I feel that though Theorem~\ref{thm:Main} is an interesting statement about subshifts, to our knowledge the statement does not appear in the literature, and its proof through winning shifts is worth making explicit. Furthermore, unlike Theorem~\ref{thm:Main}, the statement about independence sets does not trivially generalize to non-binary alphabets.

As discussed, I obtain a new proof of the fact entropy implies the existence of certain types of independence sets in the case of a binary alphabet.

\begin{corollary}
\label{cor:IndependenceSet}
Let $X \subseteq \{0,1\}^\mathbb{N}$ be a subshift. Then, $X$ has positive entropy if and only if it has an independence set of positive lower asymptotic density.
\end{corollary}

Again, I mention that this result is proved in \cite{KuKwLi14a,FaKuKwLi15}, and that generalizations appear in \cite{GlWe95,HuYe06,KeLi07}. To our knowledge, the first reference where the Sauer-Shelah lemma appears in a dynamics context is \cite{GlWe95}. The most naive generalization of Corollary~\ref{cor:IndependenceSet}, the existence of a high density set $N$ with $X|_N = A^N$, fails for a non-binary alphabet $A$ (even for trivial reasons, by artificially increasing the alphabet of the subshift). However, one can state an equivalent condition for having higher entropy in this way \cite{Be00}, (Theorem~8.3), \cite{FaKuKwLi15}, (Theorem~2). (The non-trivial direction of this equivalence also appears in \cite{SaTo14c}, (Proposition~5.9).)

As I show in this note, winning shifts say something stronger than Corollary~\ref{cor:IndependenceSet} in the case of one-dimensional subshifts, but it is not clear how to generalize them to other settings, at least in a way that allows seeing them naturally as a dynamical system.

\begin{question}
Does every expansive system of positive entropy contain a steadily branching binary tree (and what does that even mean)? More generally, can the notion of winning shift be extended to general (expansive) systems? Group/monoid actions?
\end{question}

\section{Definitions}

Let $\mathbb{N} \ni 0$ be the natural numbers. An \emph{alphabet} is a finite set $A$. \emph{Words} are elements of the free monoid generated by $A$, denoted by $A^*$. Elements of $A$ are seen as belonging to $A^*$ when convenient, $u \cdot v$ denotes the multiplication in the free monoid (formal concatenation). The \emph{length} $|w|$ of a word is defined in the obvious way. Write $A^n = \{w \in A^* \;:\; |w| = n\}$.

The set $A^\mathbb{N}$, for a finite alphabet $A$ (or later $A^\mathbb{Z}$), always carries the product topology, and it is homeomorphic to Cantor space if $|A| \geq 2$. A \emph{subshift} is a closed subset of $A^\mathbb{N}$ for a finite alphabet $A$ (or later $A^\mathbb{Z}$) satisfying $\sigma(X) \subseteq X$ where $\sigma$ is the \emph{shift} $\sigma(x)_i = x_{i+1}$. The \emph{words of a subshift} $X \subseteq A^\mathbb{N}$ are the words $w \in A^*$ such that $x|_{[0,|w|-1]} = w$ for some $x \in X$. The words of a subshift form its \emph{language}. Writing $L_n$ for the intersection of the language of $X$ with $A^n$, the \emph{(topological) entropy} of a subshift $X$ is the exponential growth rate of the number of words, $h(X) = \lim_{n \rightarrow \infty} \frac{\log |L_n|}{n}$ (which exists by the subadditivity of $\log |L_n|$). The \emph{lower asymptotic density} of $N \subseteq \mathbb{N}$ is $\liminf_k \frac{|N \cap [0,k-1]|}{k}$.

Two subshifts $X \subset A^\mathbb{N}, Y \subset B^\mathbb{N}$ are \emph{topologically conjugate} if there is a shift-commuting homeomorphism $\phi : X \to Y$. A subshift is \emph{countable} if it countably has many points. A set $N \subseteq \mathbb{N}$ is \emph{syndetic} if $\mathbb{N} \subseteq N+[-n,n]$ where $+$ denotes the Minkowski sum.

\section{The Winning Shift}
\label{sec:Winning}

For $z, b \in \mathbb{N}^\mathbb{N}$, denote $z \leq b \iff \forall i: z_i \leq b_i$.

\begin{definition}
Let $A$ be a finite alphabet and let $X \subseteq A^\mathbb{N}$. A \emph{tree in $X$ with branching structure $b \in \mathbb{N}^\mathbb{N}$} is a set of sequences $(x^z)_{\mathbb{N}^\mathbb{N} \ni z \leq b}$ where each $x^z$ is an element of $X$, and:
\[ x^z_{[0,i)} = x^{z'}_{[0,i)} \iff z_{[0,i)} = {z'}_{[0,i)}. \]
A \emph{steadily branching binary tree} is a tree with branching structure $b \in \{0,1\}^\mathbb{N}$ satisfying $\liminf_{i \rightarrow \infty} \frac{\sum_{j = 0}^{i-1} b_j}{i} > 0$.
\end{definition}

In other words, for distinct sequences $z, z' \in \mathbb{N}^\mathbb{N}$, the first position where $x^z$ and $x^{z'}$ differ is the same as the first position where $z$ and $z'$ differ. For binary $b$, this means that the nonzero positions in $b$ are the positions where our tree must branch in two, and more generally, $b_i = n$ means the tree must branch $n$ times in position $i$, explaining why we call this sequence a branching structure. Note also that if $X \subseteq A^\mathbb{N}$ and $X$ contain a tree with branching structure $b \in \mathbb{N}^\mathbb{N}$, then necessarily $b_i \leq |A|-1$ for all $i \in \mathbb{N}$.

\begin{definition}
Let $X \subseteq A^\mathbb{N}$ be a subshift. Let $W(X)$, the \emph{winning shift} of $X$, be the set of all branching structures of trees in $X$.
\end{definition}

This is defined in a game-theoretic framework in \cite{SaTo14c}: a tree in $X$ with branching structure $z$ can be interpreted as a winning strategy for the first player in a word-building game where on the $i$th turn, the first player picks a set of $z_i+1$ symbols, then the second picks one of them, and the first player wins if the word obtained in the limit is in~$X$.

It is shown in \cite{SaTo14c} that the winning shift is indeed a subshift. A subshift $Y \subseteq \mathbb{N}^\mathbb{N}$ is \emph{hereditary} \cite{KeLi07} if for all $y' \in \mathbb{N}^\mathbb{N}$ we have:
\[ (y \in Y \wedge \forall i: y'_i \leq y_i) \implies y' \in Y. \]

The following fact is Proposition 5.7 of \cite{SaTo14c} (the hereditarity claim is trivial). The notation differs slightly, in the reference $\tilde W(X)$ is used for what we call $W(X)$, and their $W(X)$ is the same as ours in the binary case, but differs in general.

\begin{lemma}
The subshift $W(X)$ is hereditary and has the same number of words of each length as~$X$.
\end{lemma}

\begin{proof}[Proof sketch]
The hereditarity claim is trivial. For the claim about words, one can define $W(L)$ for $L \subseteq A^n$ analogously to the subshift case (using finite trees). Letting $L \subseteq A^n$ be the language of $X$ intersected with $A^n$, $W(L)$ is the language of $W(X)$ intersected with $A^n$. Now, we write $L = 0 L_0 \sqcup 1 L_1 \sqcup \cdots \sqcup (k-1) L_{k-1}$ and exchange a suitable sum:
\begin{align*}
|W(L)| &= \left|\{ i \cdot w \;:\; |\{j \;:\; w \in W(L_j)\}| > i\}\right| \\
&= \sum_i \sum_{{w \in A^{n-1}}\atop{|\{j \;:\; w \in W(L_j)\}| > i}} 1 \\
&= \sum_{w \in A^{n-1}} \sum_{i = 0}^{|\{j \;:\; w \in W(L_j)\}|-1} 1 \\
&= \sum_{w \in A^{n-1}} |\{j \;:\; w \in W(L_j)\}| \\
&= \sum_j |W(L_j)| = \sum_j |L_j| = |L|.
\end{align*}
The first equality is true by definition, and the penultimate one by induction.
\end{proof}

For a finite word $w \in \mathbb{N}^*$, write $\sum w = \sum_i w_i$ for the sum of the symbols in $w$, and $|w|$ for the length of $w$ as a word. The key to finding steadily branching trees is to study the \emph{density} $\sum w/|w|$ of a word $w$. If $Y \subseteq \{0,1\}^\mathbb{N}$ is a subshift, by $Y^k$ we mean the Cartesian power with the diagonal action, interpreted in an obvious way as an alphabet over the alphabet $\{0,1\}^k$.

We observe a simple combinatorial lemma.

\begin{lemma}
\label{lem:Density}
If a subshift $Y$ has positive entropy and is hereditary, then for some $\beta > 0$ there exist arbitrarily long words $w$ of $Y \cap \{0,1\}^\mathbb{N}$ with $\sum w/|w| \geq \beta$.
\end{lemma}

\begin{proof}
Let $\{0,1,...,k-1\}$ be the alphabet of $Y$. Let:
\[ b(Y) = \{x \in \{0,1\}^\mathbb{N} \;:\; \exists y \in Y: \forall i: y_i \neq 0 \iff x_i \neq 0 \}. \]
Since $Y$ is hereditary, it is easy to see that the number of words in $Y$ of length $n$ is at most the number of words in $b(Y)^k$ of length $n$. Thus, if $Y$ has positive entropy, so does $b(Y)^k$, and thus so does $b(Y)$. Suppose thus that the number of words in $b(Y)$ of every length $n$ is at least $\alpha^n$ for some $\alpha > 0$, as is clearly implied by positive entropy.

The number of words of length $n$ with at most $k$ many $1$s is at most:
\[ \binom{n}{k} 2^k < \left(\frac{n \cdot e}{k}\right)^k 2^k. \]

Setting $k = \beta n$, this becomes $((\frac{n \cdot e}{\beta n})^\beta 2^\beta)^n$ and we observe that
as $\beta \rightarrow 0$, we have $2^\beta \rightarrow 1$ and $(\frac{n \cdot e}{\beta n})^\beta = (\frac{e}{\beta})^\beta \rightarrow 1$, so for small enough $\beta > 0$, we have $(\frac{n \cdot e}{\beta n})^\beta 2^\beta < \alpha$, and thus there must be words of length $n$ in $b(Y)$ with at least $\beta n$ many $1$s, for arbitrarily large $n$. These are words of $Y \cap \{0,1\}^\mathbb{N}$ since $Y$ is hereditary.
\end{proof}

This argument appears also in \cite{Kw13} (Theorem~4.8) (this theorem already includes the statement about lower asymptotic density, which we deduce in the next section).

\section{The Proofs}

\begin{proof}[Proof of Theorem~\ref{thm:Main}]
Obviously, a steadily branching tree implies positive entropy.

For the other direction, let $A \subseteq \mathbb{N}$ be a finite alphabet and $Y \subseteq A^\mathbb{N}$ a subshift. Write $s_n$ for the maximal sum $\sum w$ of a word $w$ of length $n$ in $Y$. This sequence is clearly subadditive, so $\lim_{n \rightarrow \infty} s_n/n$ exists, say $\lim_n s_n/n = \alpha$.

We outline the usual addendum that there must be a configuration $y \in Y$ such that every prefix $w$ of $y$ satisfies $\sum w/|w| \geq \alpha$. Supposing that this is not the case, then every point $X$ has a prefix $w$ such that $\sum w/|w| < \alpha$, and this must happen after a bounded number of steps by compactness, thus there exists $\epsilon > 0$ such that for some $m$, we always find a prefix $w$ of length at most $m$ in any point $y \in Y$, such that $\sum w/|w| < \alpha - \epsilon$. Now, given any long word $w$ of $Y$, we can split it as $w = w^0 w^1 \cdots w^k$ (where $i$ in $w^i$ denotes a superscript, not a power) with $|w^k| \leq m$ and $\sum w^i/|w^i| < \alpha - \epsilon$ for all $i < k$. If $w$ is long enough, then since $\sum uv/|uv| \leq \max(\sum u/|u|, \sum v/|v|)$ for all words $u, v$, we have:
\[ \sum w/|w| < \alpha - \epsilon/2 \]
for all long enough words, a contradiction to $\lim_n s_n/n = \alpha$.

Now, we set $Y = W(X)$ and apply Lemma~\ref{lem:Density}. The lemma implies that $\alpha > 0$ in the above. The point $y \in W(X)$ whose density stays above $\alpha$ gives the branching structure of a steadily branching tree in $X$.
\end{proof}

The ``usual addendum'' is well known. The author learned it from \cite{KaKe97,Je14} and P.\ Guillon; Jeandel attributes it to \cite{Ma99,FeHu10}, and it also appears in \cite{Kw13,FaKuKwLi15} where it is attributed to \cite{Pe88,Ru78}.

The point of this note was to provide a combinatorial proof of Theorem~\ref{thm:Main} from the first principles, as this is easy to do. However, I have included also the proof using ergodic theory (see \cite{DeGrSi76} for a basic reference).

\begin{proof}[Ergodic theoretic proof of Theorem~\ref{thm:Main}]
Obviously a steadily branching tree implies positive entropy. For the other direction, since the winning shift has positive entropy, it admits an invariant measure $\mu$ with positive entropy, thus $\mu([a]) > 0$ for some $a > 0$. By the ergodic decomposition there exists such an ergodic measure, and by the pointwise ergodic theorem, there is a point $y \in W(X)$ where the lower asymptotic density of $a$s is positive, giving the result.
\end{proof}

We conclude with the proofs of Theorem~\ref{thm:Z} and Corollary~\ref{cor:IndependenceSet}.

\begin{proof}[Proof of Theorem~\ref{thm:Z}]
Let $X_R \subseteq A^\mathbb{N}$ be the subshift of the right tails of points in $X$ and apply Theorem~\ref{thm:Main}. Let $y \in \{0,1\}^\mathbb{N}$ be the branching structure of some steadily branching tree and $\alpha$ the lower asymptotic density. It is easy to see that for any $n$, we can find a finite prefix $w$ of $y = wx$ of a length of at least $n$ such that for all prefixes $u$ of $x$ of length at most $n$, $\sum u/|u| \geq \alpha$. Otherwise, by cutting long words into ones of length at most $n$, as in the previous argument, we see that the lower asymptotic density is less than $\alpha$.

The fact we can find such $wx$ as a branching structure implies that the tree corresponding to $x$ can follow at least one word of length $|w|$. Letting $n$ tend to infinity, by compactness, we obtain a steadily branching tree that can follow some left tail.
\end{proof}

\begin{proof}[Proof of Corollary~\ref{cor:IndependenceSet}]
Supposing $X$ has positive entropy, let $y \in W(X) \cap \{0,1\}^\mathbb{N}$ have positive lower asymptotic density. The set $N = \{n \;:\; y_n = 1\}$ is an independence set (which by assumption has positive lower asymptotic density): Suppose $(x^z)_{\mathbb{N}^\mathbb{N} \ni z \leq y}$ form a tree with branching structure $y$, i.e.,\ we have:
\[ x^z_{[0,i)} = x^{z'}_{[0,i)} \iff z_{[0,i)} = {z'}_{[0,i)}. \]
Supposing that $(m_i)_{i \in \mathbb{N}}$ enumerates $N$ in order, let $N_n = \{m_0,...,m_{n-1}\}$, and for $w \in \{0,1\}^n$ let $z^w \in \{0,1\}^\mathbb{N}$ be the characteristic sequence of $\{m_i \;:\; i < |w|, w_i = 1\}$. Clearly $z^w \leq y$ for all $w \in \{0,1\}^n$. The map:
\[ \phi : 2^n \to \{x^z|_{N_n} \;:\; z \leq b\} \]
defined by $\phi(w) = x^{z^w}|_{N_n}$ is injective, because $\phi(u0v)_{m_{|u|}} \neq \phi(u1v)_{m_{|u|}}$. Thus, this map is surjective, giving $X|_{N_n} = \{0,1\}^{N_n}$. By compactness, we have $X|_N = \{0,1\}^N$.
\end{proof}

\section{Proofs of supplementary claims}

In this section, I provide brief proofs for the claims made in the introduction.

\begin{proposition}
\label{prop:NoIndependenceEntropy}
There exists a subshift $X \subset \{0,1\}^\mathbb{N}$ with positive entropy, such that every topologically conjugate subshift $Y \cong X$ has zero independence entropy.
\end{proposition}

\begin{proof}
By a compactness argument, any subshift $X$ with positive independence entropy must contain two points which differ in only one position, i.e.,\ $\exists x, y \in X: x_0 \neq y_0 \wedge \forall i \neq 0: x_i = y_i$. Positive entropy does not imply the existence of a pair of points with finitely many differences, see \cite{Me19}, (Theorem~1.3), and clearly this property is preserved under conjugacy.
\end{proof}

\begin{proposition}
\label{prop:Countable}
For any function $f : \mathbb{N} \to \mathbb{N}$ satisfying $f(n) = o(a^n)$ for all $a > 1$, there exists a countable subshift $X \subset \{0,1\}^\mathbb{N}$ such that for all large enough $n$, the number of words of length $n$ in $X$ is at least $f(n)$.
\end{proposition}

\begin{proof}
The forbidden patterns of $X$ are described as follows: if a finite subword contains $n$ many $1$s, they must be pairwise separated by a distance of at least $m_n$. Here, $(m_n)_n$ is some nondecreasing sequence. The number of words of $X$ of length $n$ is at least $2^{\lfloor n/m_n \rfloor}$, and if $m_n$ grows slowly enough this stays above $f$. By the assumption on $f$ we can have $m_n \rightarrow \infty$, and it is easy to see that $X$ is then countable, since all its points have finite sum and finite subsets of $\mathbb{N}$ form a countable set.
\end{proof}

\begin{proposition}
\label{prop:NoSyndetic}
There exists a subshift $X \subset \{0,1\}^\mathbb{N}$ with positive entropy such that every point in $W(X)$ contains arbitrarily long subwords of the form $0^n$.
\end{proposition}

\begin{proof}
If $X$ itself is hereditary, then $W(W(X)) = W(X)$, so it suffices to find a hereditary $X$ with positive entropy such that every point $x \in X$ contains arbitrarily long subwords of the form $0^n$. For this, it clearly suffices to find a binary subshift $Y$ where every point contains the subword $0^n$ for arbitrarily large $n$, but some configuration contains $1$s with positive lower asymptotic density, as the smallest hereditary subshift containing $Y$ then has the claimed property: entropy comes from independently flipping the positive density sequence of $1$s, and taking the hereditary closure can clearly only add $0^n$-subwords to points. The existence of such $Y$ is folklore, see e.g.\ \cite{Sa20}, (Example~7.3), for an explicit construction.
\end{proof}

\bibliographystyle{plain}