TITLE: Finding $\lim \frac{3^n}{4^n}$
QUESTION [1 upvotes]: $$\lim_{n \to \infty} \frac{3^n}{4^n}$$

I know the limit is zero because the denominator grows faster than the numerator in this case... although I still get infinity over infinity.
How do I "show" that the limit is zero? L'Hopital's rule is redundant in this case and doing $\lim e^{n\ln(3/4)}$ doesn't help.

REPLY [1 votes]: I don't think Lhopital's rule is redundant.
Call the limit $L$, which exists because the sequence is bounded and decreasing.
The derivative of $b^x$ is $\ln bb^x$.
We get $L=\ln3/\ln4L\implies L=0$.

Also, $e^{n\ln(3/4)}\to0$, since $\ln(3/4)$ is
negative.


text:
\begin{document}

\title{On the Decoding of Polar Codes on Permuted Factor Graphs}

\author{\IEEEauthorblockN{Nghia Doan\IEEEauthorrefmark{1}, Seyyed Ali Hashemi\IEEEauthorrefmark{1}, Marco Mondelli\IEEEauthorrefmark{2}, Warren J. Gross\IEEEauthorrefmark{1}}
\IEEEauthorblockA{
\IEEEauthorrefmark{1}Department of Electrical and Computer Engineering, McGill University, Montr\'eal, Qu\'ebec, Canada\\
\IEEEauthorrefmark{2}Department of Electrical Engineering, Stanford University, California, USA\\
Email: nghia.doan@mail.mcgill.ca, seyyed.hashemi@mail.mcgill.ca, mondelli@stanford.edu, warren.gross@mcgill.ca}}

\maketitle
\begin{abstract}
Polar codes are a channel coding scheme for the next generation of wireless communications standard (5G). The belief propagation (BP) decoder allows for parallel decoding of polar codes, making it suitable for high throughput applications. However, the error-correction performance of polar codes under BP decoding is far from the requirements of 5G. It has been shown that the error-correction performance of BP can be improved if the decoding is performed on multiple permuted factor graphs of polar codes. However, a different BP decoding scheduling is required for each factor graph permutation which results in the design of a different decoder for each permutation. Moreover, the selection of the different factor graph permutations is at random, which prevents the decoder to achieve a desirable error-correction performance with a small number of permutations. In this paper, we first show that the permutations on the factor graph can be mapped into suitable permutations on the codeword positions. As a result, we can make use of a single decoder for all the permutations. In addition, we introduce a method to construct a set of predetermined permutations which can provide the correct codeword if the decoding fails on the original permutation. We show that for the 5G polar code of length $1024$, the error-correction performance of the proposed decoder is more than $0.25$~dB better than that of the BP decoder with the same number of random permutations at the frame error rate of $10^{-4}$.
\end{abstract}

\begin{IEEEkeywords}
polar codes, belief propagation decoding, permuted factor graph.
\end{IEEEkeywords}

\IEEEpeerreviewmaketitle
\section{Introduction} \label{sec:intro}
Polar codes \cite{arikan} are the first class of error-correcting codes that was proved to achieve channel capacity with efficient encoding and decoding algorithms. As such, they have been adopted for the enhanced mobile broadband (eMBB) control channel of the fifth generation (5G) wireless communications standard. Successive cancellation (SC) and belief propagation (BP) decoding algorithms are two methods introduced in \cite{arikan} to decode polar codes. Although SC decoding can provide a low-complexity solution, its serial nature prevents the decoding to reach high throughput. Furthermore, the polarization phenomenon of polar codes under SC decoding requires large block lengths. Thus, for short to moderate code lengths, the error-correction performance of SC decoding is insufficient for many practical applications. To improve the performance of SC decoding, SC list (SCL) decoding was proposed in \cite{tal_list}. SCL decoding maintains a list of most likely codewords by running a list of coupled SC decoders in parallel. An enormous improvement in the error probability of SCL decoder is obtained if a cyclic redundancy check (CRC) is used to select the correct codeword \cite{tal_list}. However, SCL decoding still suffers from the serial nature and low throughput \cite{Alexios_LLR_SCLD}, which scales with list size. Several attempts have been made to reduce the computational complexity and increase the throughput of polar code SCL decoders \cite{PSCL_GLOBECOM,Ali_mem_effic_PC,Ali_FSSCL}.

Unlike SC and SCL decoding, the message passing process of BP decoding can be executed in parallel, which allows this decoder to obtain high throughput. However, BP decoding cannot achieve low error probability with a limited number of iterations. One of the methods used to improve the error-correction performance of BP decoding for polar codes is to utilize the redundant factor graph representations \cite{Kor09thesis, hussami2009performance}. It was shown in \cite{Kor09thesis, hussami2009performance} that for a polar code of length $N$, there are $(\log_{2}N)!$ redundant representations which can be constructed by different permutations of the layers in the factor graph of polar codes. \cite{Kor09thesis, hussami2009performance} also suggested to use only the $\log_2 N$ cyclic permutations in the factor graph layers, in order to limit the large number of factor graph permutations. In \cite{elkelesh2018belief}, it was shown that if the permutations in the factor graph of polar codes are selected randomly and a CRC is concatenated to the polar code, the error probability of decoding a polar code on the permuted factor graph outperforms the performance of a non CRC-aided SCL decoder. However, the number of randomly selected permutations and therefore the number of parallel BP decoders required to achieve a reasonable error probability in \cite{elkelesh2018belief} is too high. Moreover, the BP decoder scheduling has to be changed for each permutation of the factor graph layers. Therefore, a different decoder has to be designed for each permutation in practical applications.

In this paper, we first show that the permutations on the polar code factor graph can be mapped into permutations on the codeword positions, therefore allowing the use of the same decoder structure for all the permutations. Second, based on the observation that the decoding on the original permutation only fails with a small error probability, we propose a novel empirical approach to construct a set of good permutations. Our experimental results show that for the polar code selected for the eMBB control channel of 5G, with length $1024$, rate $0.5$, and by using a $24$-bit CRC, the error-correction performance is more than $0.25$ dB better than that of the BP decoder when the same number of random permutations are employed, at the frame error rate (FER) of $10^{-4}$.

The remainder of this paper is organized as follows. Section~\ref{sec:polar} briefly introduces a background on polar codes and BP decoding. Section~\ref{sec:pcbp} and Section~\ref{sec:results} present the proposed decoder and the experimental results, respectively. Finally, concluding remarks are provided in Section~\ref{sec:conclude}.

\section{Preliminaries} \label{sec:polar}

\subsection{Polar Codes}
\label{sec:polar:polar}

A polar code $\mathcal{P}(N,K)$ of length $N$ with $K$ information bits is constructed by applying a liner transformation to the message word $\bm{u} = \{u_0,u_1,\ldots,u_{N-1}\}$ as $\bm{x} = \bm{u}\bm{G}^{\otimes n}$ where $\bm{x} = \{x_0,x_1,\ldots,x_{N-1}\}$ is the codeword, $\bm{G}^{\otimes n}$ is the $n$-th Kronecker power of the polarizing matrix $\bm{G}=\bigl[\begin{smallmatrix} 1&0\\ 1&1 \end{smallmatrix} \bigr]$, and $n = \log_2 N$. The vector $\bm{u}$ contains a set $\mathcal{A}$ of $K$ information bits and a set $\mathcal{F}$ of $N-K$ frozen bits. The positions and the value of the frozen bits are known to the encoder and the decoder. The codeword $\bm{x}$ is then modulated and sent through the channel. In this paper, binary phase-shift keying (BPSK) modulation and additive white Gaussian noise (AWGN) channel model are considered, therefore the soft vector of the transmitted codeword received by the decoder is
\begin{equation}
\bm{y}=(\mathbf{1}-2\bm{x})+\bm{z}\text{,}
\end{equation}
where $\mathbf{1}$ is an all-one vector with size $N$, and $\bm{z} \in \mathbbm{R}^N$ is the AWGN noise vector with variance $\sigma^2$ and zero mean. It is noteworthy that all the decoders presented in this paper work in the log-likelihood ratio (LLR) domain. The corresponding LLR vector of the transmitted codeword is
\begin{equation}
\text{LLR}(\bm{x})=\ln{\frac{\text{Pr}(\bm{x}=0|\bm{y})}{\text{Pr}(\bm{x}=1|\bm{y})}}=\frac{2\bm{y}}{\sigma^2}\text{.}
\end{equation}

\subsection{Belief Propagation Decoding}
\label{sec:polar:BPD}

\begin{figure}[t]
  \centering
  \label{figBPDec}
  \begin{subfigure}[b]{0.5\textwidth}
  	\centering
  	\includegraphics[width=0.7\linewidth]{Figures/BPDecoding.png}
  	\caption{}
  	\label{figBPDec:a}
  \end{subfigure}
  \begin{subfigure}[b]{0.5\textwidth}
  	\centering
  	\includegraphics[width=0.4\linewidth]{Figures/BPPE.png}
  	\caption{}
  	\label{figBPDec:b}
  \end{subfigure}
  \caption{(a) BP decoding on the factor graph of $\mathcal{P}(8,5)$ with $\{u_0,u_1,u_2\}\in \mathcal{F}$, (b) a processing element (PE).}
\end{figure}

BP decoding is an iterative message passing algorithm applied on the factor graph representation of a code. The received channel LLR values, $\text{LLR}({\bm{x}})$, are iteratively propagated through the graph until either the LLR values converge or the maximum number of iterations is reached. The decoder then makes a hard decision based on the resulting LLR values to maximize the \textit{a posteriori} probability $\text{Pr}(\bm{x}|\bm{y})$.

Fig.~\ref{figBPDec:a} illustrates BP decoding on a factor graph representation of $\mathcal{P}(8,5)$. The messages are propagated through the processing elements (PEs) \cite{arikan2010polar} located in each layer. An update iteration starts with a right-to-left message pass that propagates the LLR values from the channel (rightmost) layer, to the information bit (leftmost) layer, and ends with the left-to-right message pass which occurs in the reverse order. Fig.~\ref{figBPDec:b} shows a PE with its corresponding messages, where $R_{i,l}$ denotes a left-to-right message, and $L_{i,l}$ denotes a right-to-left message of the $i$-th bit index at layer $l$. The update rule \cite{arikan2010polar} of the messages in each PE is given as
\begin{align}
\begin{split}
L_{i,l} &= f(L_{i,l+1},R_{i+2^l,l}+L_{i+2^l,l+1}) \text{,}\\
L_{i+2^l,l} &= f(L_{i,l+1},R_{i,l}) + L_{i+2^l,l+1} \text{,}\\
R_{i,l+1} &= f(R_{i,l},L_{i+2^l,l+1}+R_{i+2^l,l})  \text{,}\\
R_{i+2^l,l+1} &= f(R_{i,l},L_{i,l+1}) + R_{i+2^l,l} \text{,}
\end{split}
\label{PEUpdate}
\end{align}
where $f(x,y)=\ln{\frac{1+xy}{x+y}}$ for any $x,y \in \mathbbm{R}$.

Initially, $L_{i,n-1}$ ($0 \leq i < N$) are set to the received channel LLR values, $R_{i,0}$ ($i \in \mathcal{F}$) are set to $+\infty$, and all the other left-to-right and right-to-left messages of the PEs are set to $0$. The BP decoding performs a predetermined $I_{\max}$ update iterations where the messages are propagated through all PEs in accordance with (\ref{PEUpdate}). The decoder then makes a hard decision on the LLR values of the $i$-th bit at the information bit layer to obtain the estimated message word as
\begin{equation}
\hat{u}_i=
  \begin{cases}
    0 \text{,} & \text{if } R_{i,0}+L_{i,0} \geq 0 \text{,}\\
    1 \text{,} & \text{otherwise.}
  \end{cases}
\end{equation}

In order to reduce the decoding latency, $G$-matrix-based \cite{yuan2014early} or CRC-based \cite{elkelesh2018belief} early termination conditions are checked after each update iteration. If the early termination condition is satisfied, the decoding is terminated with the assumption that the LLR values have converged to indicate the correct codeword.

\subsection{BP Decoding on Permuted Factor Graphs}
\label{sec:polar:PGBPD}

\begin{figure*}[t]
\centering
\includegraphics[width=0.65\linewidth]{Figures/FactorgraphPermutations.png}
\caption{Permuted factor graph representations for $\mathcal{P}(8,5)$.}
\label{PerTG}
\end{figure*}

\begin{figure*}[t]
\centering
\includegraphics[width=0.65\linewidth]{Figures/BitRealization.png}
\caption{The proposed mapping from factor graph permutation to bit-index permutation for $\mathcal{P}(8,5)$.}
\label{BitRelization}
\end{figure*}

Factor graph permutations are a way to provide multiple representations of a single code. It was observed in \cite{Kor09thesis, hussami2009performance} that there exists $n!$ different ways to represent a polar code by permuting the layers in its factor graph. Fig.~\ref{PerTG} illustrates such permutations for $\mathcal{P}(8,5)$, where $3$ out of $3!=6$ permutations are shown. Note that the two leftmost factor graphs in Fig.~\ref{PerTG} are formed by applying cyclic shifts to the original factor graph depicted in Fig.~\ref{figBPDec:a}. In \cite{elkelesh2018belief}, parallel BP decoders are applied on a set of randomly selected factor graphs of a polar code concatenated with a CRC. Although this decoding scheme shows improvement in error probability when compared to a non CRC-aided SCL decoder, permuting layers results in different BP scheduling which consequently requires the design of a different BP decoder for each permutation. Moreover, a large number of random permutations are required to achieve a reasonable error-correction performance, which makes this decoding scheme too complex for practical applications.

\section{Improved BP Decoding on Permuted Factor Graphs} \label{sec:pcbp}

In this section, we first show that there is a one-to-one mapping between the permutations on the factor graph layers and the permutations on the codeword positions. We then propose a method to select the factor graph permutations that improves the error-correction performance of polar codes when decoding is performed on the permuted factor graphs.

\subsection{From Permutations on Factor Graph Layers to Permutations on Codeword Positions}

We denote by $\{l_{n-1},\ldots,l_0\}$ the layers of the original factor graph of polar codes (the one represented in the right part of Fig. \ref{BitRelization}) and by $\{b^{(i)}_{n-1},\ldots,b^{(i)}_0\}$ the binary expansion of the integer $i$.

\begin{theorem} \label{th:perm}
Let $\pi : \{0, \ldots, n-1\} \to \{0, \ldots, n-1\}$ be a permutation. Then, the synthetic channel associated to the position with binary expansion $\{b^{(i)}_{n-1},\ldots,b^{(i)}_0\}$ on the factor graph with layers $\{l_{n-1},\ldots,l_{0}\}$ is the same as the synthetic channel associated to the position with binary expansion $\{b^{(i)}_{\pi(n-1)},\ldots,b^{(i)}_{\pi(0)}\}$ on the factor graph with layers $\{l_{\pi(n-1)},\ldots,l_{\pi(0)}\}$.
\end{theorem}

\begin{proof}
Consider the original factor graph of polar codes. Then, the synthetic channel associated to the position with binary expansion $\{b^{(i)}_{n-1},\ldots,b^{(i)}_0\}$ is given by
$$
(((W^{(b^{(i)}_{n-1})})^{(b^{(i)}_{n-2})})^{\cdots})^{(b^{(i)}_0)},
$$
where $W$ is the transmission channel and the transformations $W\to W^{(0)}$ and $W\to W^{(1)}$ are the ``minus'' and ``plus'' polar transforms formally defined in (2.3) and (2.4) of \cite{Kor09thesis}. Note that the $i$-th component of the message word $u_i$ is connected to the $i$-th component of the codeword $x_i$ by associating a ``XOR'' to a $0$ and a ``dot'' to a $1$ in the binary expansion of the integer $i$. Note also that, by permuting the layers of the factor graph, we simply permute the order of those ``XOR''s and ``dot''s operations. Hence, the effect of applying a permutation $\pi$ to the binary expansion of $i$ is the same as the effect of applying the same permutation on the layers of the factor graph.
\end{proof}

Fig.~\ref{BitRelization} shows an example of the proposed mapping applied to a permuted factor graph of $\mathcal{P}(8,5)$. It can be seen that, by using the permuted bit indices, the structure of the factor graph is unchanged. Therefore, the original decoder can be used to perform decoding on all the required permutations. In addition, the proposed mapping allows to use other decoding algorithms, such as SC and SCL, on the permuted factor graphs without changing the decoder structure. This is particularly useful for hardware implementation.

\subsection{Selection of Good Permutations}
\label{sec:proposed:b}

First, we observe that BP decoding only fails to decode with a small probability on the original factor graph of polar codes. Therefore, we keep the original factor graph in the set of good permutations and create a set of permutations that provides the correct codeword when the decoder fails on the original factor graph. To this end, we first provide an approach to construct the permutation set $\mathbbm{P}$ of a polar code with $n$ factor graph layers which represents a search space for the good factor graph permutations. This approach is summarized in Algorithm~\ref{alg1}, which uses the recursive function \texttt{FormPermutation} described in Algorithm~\ref{alg2}. The main idea is to recursively create $\mathbbm{P}$ by permuting only some of the layers on the right-most side of the graph (see Fig.~\ref{figBPDec:a}), in order to limit the size of the search space. In other words, we fix the layers $\{l_0, \ldots, l_{n-k-1}\}$, with $0 \leq k < n$, and we consider permutations only of the remaining layers $\{l_{n-k},\ldots,l_{n-1}\}$. Note that the size of the search space $\mathbbm{P}$ is $|\mathbbm{P}| = k!$.

\begin{algorithm}[t]
\DontPrintSemicolon
\caption{Forming the permutation set }
\label{alg1}
\SetKwInOut{Input}{Input}
\SetKwInOut{Output}{Output}
\SetKwInOut{Initialization}{Initialization}
\SetKwFunction{FormPermutation}{FormPermutation}
\SetKwFunction{Main}{Main}

\Input{$n,k$}
\Output{$\mathbbm{P}$}

\tcp{Fixed layers}
$p_{fix} \leftarrow \{l_0,l_1,\ldots,l_{n-k-1}\}$ \\
\tcp{Permuted layers}
$p_{per} \leftarrow \{l_{n-k},l_{n-k+1},\ldots,l_{n-1}\}$\\
\tcc{Recursively form the permutation set}
$\mathbbm{P}_{per} \leftarrow$ \FormPermutation{$p_{per}$}\\
\tcc{Concatenate $p_{fix}$ to each element of $\mathbbm{P}_{per}$}
$\mathbbm{P} \leftarrow \emptyset$\\
\For{$j \leftarrow 0$ \KwTo $|\mathbbm{P}_{per}|-1$}{
	$\mathbbm{P} \leftarrow \mathbbm{P} \cup [p_{fix},\mathbbm{P}_{per}[j]]$
}
\Return{$\mathbbm{P}$}
\end{algorithm}

\begin{algorithm}[t]
\DontPrintSemicolon
\caption{\texttt{FormPermutation($p_{per}$)}}
\label{alg2}
\SetKwFunction{FormPermutation}{FormPermutation}
\SetKwInOut{Input}{Input}
\SetKwInOut{Output}{Output}
\Input{$p_{per}$ \tcc*{Factor graph layer order}}
\Output{$\mathbbm{P}_{per}$ \tcc*{Set of all permutations}}
$\mathbbm{P}_{per} \leftarrow \emptyset$ \\
\eIf{$length(p_{per})=2$}{
		$\mathbbm{P}_{per}[0] \leftarrow [p_{per}[0],p_{per}[1]]$\\
		$\mathbbm{P}_{per}[1] \leftarrow [p_{per}[1],p_{per}[0]]$
}{
		\For{$i\leftarrow 0$ \KwTo $length(p_{per})-1$}{
		$p^{'}_{per} \leftarrow p_{per}$ \\
		$l_{i} \leftarrow p^{'}_{per}[i]$  \\
		$p^{'}_{per} \leftarrow p^{'}_{per}\setminus l_{i}$\\

	      $\mathbbm{P}^{'}_{per} \leftarrow$ \FormPermutation{$p^{'}_{per}$} \\
		\For{$j \leftarrow 0$ \KwTo $|\mathbbm{P}^{'}_{per}|-1$}{
		$\mathbbm{P}_{per} \leftarrow \mathbbm{P}_{per} \cup [l_{i},\mathbbm{P}^{'}_{per}[j]]$\\
		}
	}
}
\Return{$\mathbbm{P}_{per}$}
\end{algorithm}

At this point, we evaluate numerically the probability of correct decoding for each element in $\mathbbm{P}$, when the decoding fails on the original factor graph of polar codes. Then, we select the $M$ elements in $\mathbbm{P}$ with the highest probability of successful decoding and form the subset $\mathbbm{P}_b$ of $\mathbbm{P}$. Note that $|\mathbbm{P}_b| = M$. At the decoder, we consider only the $M$ permutations in $\mathbbm{P}_b$. This is described in Algorithm~\ref{alg3}. Note that Theorem~\ref{th:perm} is used to perform decoding on the permuted bit indices instead of the permuted factor graph layers. In addition, all the BP decoders run a maximum of $I_{\max}$ iterations and an early stopping criteria is used to terminate the BP decoding process if one of the BP decoders satisfies the termination condition. If none of the BP decoders satisfy the early stopping criteria or the maximum number of iterations is reached, the message word given by the original permutation is selected as the final decoding result.

\begin{algorithm}[t]
\DontPrintSemicolon
\caption{BP decoding on predetermined bit-index permutations}
\label{alg3}
\SetKwInOut{Input}{Input}
\SetKwInOut{Output}{Output}
\SetKwFunction{BPDecoding}{BPDecoding}
\Input{$\bm{y},\mathbbm{P}_b$}
\Output{$\bm{\hat{u}}$}
\tcc{Initilize early termination flag}
$isTerm \leftarrow False$\\
\For{all permutations in $\mathbbm{P}_b$}{
	\tcc{Permute $\bm{y}$ using Theorem~\ref{th:perm}}
	\For{$i \leftarrow 0$ \KwTo $N-1$}{
	$\bm{y_{\pi}}[\pi(i)] \leftarrow \bm{y}[i]$ \\
	}
	\tcc{Apply BP decoding on $\bm{y_{\pi}}$}
	$[\bm{\hat{u}_{\pi}},isTerm] \leftarrow$ \BPDecoding{$\bm{y_{\pi}}$}\\
	\tcc{Obtain $\hat{u}$ if early termination}
	\If{$(isTerm=True)$}{
		\For{$i \leftarrow 0$ \KwTo $N-1$}{
		$\bm{\hat{u}}[i] \leftarrow \bm{\hat{u}_\pi}[\pi(i)]$\\
		}
		\Return{$\bm{\hat{u}}$}
	}
}
\tcc{If no early termination}
\If{$(isTerm=False)$}{
	$\bm{\hat{u}} \leftarrow$ \BPDecoding{$\bm{y}$}\\
	\Return{$\bm{\hat{u}}$}
}
\end{algorithm}

\begin{figure}[t]
\centering
\input{Figures/fer_PBP_CRC_k.tikz}
\centering
\caption{FER performance of BP decoding on $16$ best permuted factor graphs of $\mathcal{P}(1024,512)$ with a $24$-bit CRC for various sizes of $\mathbbm{P}$, where $|\mathbbm{P}|=k!$.}
\label{perf:k}
\end{figure}

It should be noted that the computational complexity of forming $\mathbbm{P}_b$ is directly proportional to the size of $\mathbbm{P}$, since all the elements in $\mathbbm{P}$ are evaluated numerically. However, this operation is performed only once and is done off-line so there is no complexity overhead in the decoding process. In addition, the error-correction performance of BP decoding on permuted factor graphs selected from $\mathbbm{P}_b$ does not change significantly even for small values of $k$. Fig.~\ref{perf:k} illustrates the FER curves of applying BP decoding on permuted factor graphs in $\mathbbm{P}_b$ to decode $\mathcal{P}(1024,512)$ with a $24$-bit CRC. We set $M=16$ and we consider different values of $k$ ($k \in \{4,5,6,7\}$) corresponding to different sizes of $\mathbbm{P}$ ($|\mathbbm{P}| \in \{24,120,720,5040\}$). It can be seen that the FER performance of BP decoding on permuted factor graphs for all cases is similar, showing that the good permutations are those obtained by permuting only the layers on the right-most side of the polar codes factor graph. Therefore, the size of the search space $\mathbbm{P}$ can be significantly reduced, in order to form $\mathbbm{P}_b$ with low computational complexity.

\section{Experimental Results} \label{sec:results}

In this section, we evaluate applying the proposed technique on the decoding of the polar code $\mathcal{P}(1024,512)$, which is selected for the 5G eMBB control channel \cite{3gpp_report}, in terms of FER performance and average decoding latency. All the BP decoders considered in this section has the same number of $I_{\max} = 200$ maximum iterations.

\begin{figure}[t]
\centering
  \input{Figures/fer_PBP_Gmatrix_Compare.tikz}
  \centering
  \hspace{10pt}\ref{perf-legend-crc0}\vspace{2pt}
  \caption{FER performance of decoding $\mathcal{P}(1024,512)$ on permuted factor graphs considering $M=10$ best permutations, in comparison with considering $10$ random and cyclic shift permutations, when no CRC is used.}
  \label{perf:a}
\end{figure}

Fig.~\ref{perf:a} shows the FER performance of decoding $\mathcal{P}(1024,512)$ on permuted factor graphs (permuted bit indices) when no CRC is used. Since there are $10$ cyclic shift permutations for $\mathcal{P}(1024,512)$, we used $M = 10$ in order to have a fair comparison with other decoders. In Fig.~\ref{perf:a}, PBP-CS denotes BP decoding on permuted factor graphs with $n$ cyclic shift permutations \cite{Kor09thesis, hussami2009performance}, PBP-R$M$ denotes BP decoding on permuted factor graphs with $M$ random permutations \cite{elkelesh2018belief}, and PBP-B$M$ denotes the proposed BP decoding on permuted factor graphs with $M$ predetermined permutations in $\mathbbm{P}_b$. The results are also compared with SC, BP, and SCL decoding with list size $32$ (SCL$32$). It can be seen that while the FER performance of PBP-CS and PBP-R$10$ are similar, our proposed decoder results in $0.15$~dB improvement in comparison with both PBP-CS and PBP-R$10$ at FER$=10^{-3}$. However, there is still a $0.25$~dB gap between the FER performance of the proposed BP decoding on permuted factor graphs and that of SCL$32$. Using the result of Theorem~\ref{th:perm}, we performed SC decoding on permuted factor graphs and it can be seen in Fig.~\ref{perf:a} that the FER performance gap between using $M=10$ best permutations for SC decoding (denoted by PSC-B$M$) and that of SCL$32$ is less than $0.05$~dB in the high $E_b/N_0$ region. It should be noted that in order to select the correct codeword among the $M$ SC decoders, we used the absolute LLR value of the last decoded bit as a reliability measure of the decoding process, which is also used in \cite{Condo_BD}.

\begin{figure}[t]
  \centering
  \input{Figures/fer_PBP_CRC24_Compare.tikz}
  \hspace{10pt}\ref{perf-legend-crc24}\vspace{2pt}
  \caption{FER performance of decoding $\mathcal{P}(1024,512)$ on permuted factor graphs considering $M \in \{10,32,128\}$ best permutations, in comparison with considering the same number of random permutations, when a $24$-bit CRC is used.}
  \label{perf:b}
\end{figure}

Fig.~\ref{perf:b} presents the FER performance of decoding $\mathcal{P}(1024,512)$ when a CRC of length $24$ is used to aid the decoding process. We use the CRC which is selected to be used in 5G together with polar codes with the CRC polynomial
\begin{align}
\text{CRC}24 = &x^{24} + x^{23} + x^{21} + x^{20} + x^{17} + x^{15} + x^{13} + x^{12} \nonumber \\
               &+ x^{8} + x^{4} + x^{2} + x + 1 \text{.}
\end{align}
The curves in Fig.~\ref{perf:b} are obtained by considering $M \in \{10,32,128\}$ and the suffix -CRC$24$ is used to denote that the decoding is performed with the CRC. It can be seen that when $M=10$, BP decoding with cyclic shift permutations results in a better error-correction performance than when the permutations are selected randomly. Our proposed method results in an additional $0.2$~dB performance improvement over cyclic shift permutations when $M=10$, at FER$=10^{-4}$. When $M=32$ and $M=128$, BP decoding with the proposed selection of permutations results in around $0.3$~dB improvement in comparison with BP decoding on randomly selected factor graphs. We have also performed SC decoding on the permuted factor graphs by using CRC and it can be seen in Fig.~\ref{perf:b} that when adding a CRC, the FER performance of the BP decoder is superior to that of the SC decoder. This is in contrast to the results in Fig.~\ref{perf:a} where no CRC is used.

Although the FER performance of the BP decoder on permuted factor graphs can be improved significantly by using the proposed method to select the best permutations, it is still far from that of SCL$32$-CRC$24$ for practical values of $M$ as depicted in Fig.~\ref{perf:b}. However, the parallel nature of BP decoding makes this decoder interesting for applications with stringent latency requirements. It should be noted that we can evaluate the latency of a decoder by the number of time steps required to finish the decoding process \cite{arikan}. For BP decoding, the average decoding latency can be given as
\begin{equation}
\mathcal{T}_{\text{BP}}=2nI_{\text{avg}}\text{,} \label{T_BP}
\end{equation}
where $I_{\text{avg}}$ is the average number of iterations required to finish the decoding process. We now evaluate the average decoding latency of BP decoding on permuted factor graphs of $\mathcal{P}(1024,512)$ as shown in Fig.~\ref{latency}, when the permutations are selected based on the method in this paper, in comparison with cyclic shift \cite{Kor09thesis, hussami2009performance} and random \cite{elkelesh2018belief} permutations. Note that CRC$24$ is used to early terminate the decoding when one of the decoders passes the CRC test. It can be seen that the average decoding latency of the proposed method $\mathcal{T}_{\text{PBP-B$M$-CRC$24$}}$, is less than $330$ time steps for $2 \leq E_b/N_0 \leq 3.5$, and it is always less than the average decoding latency requirements of \cite{Kor09thesis, hussami2009performance} ($\mathcal{T}_{\text{PBP-CS-CRC$24$}}$) and \cite{elkelesh2018belief} ($\mathcal{T}_{\text{PBP-R$M$-CRC$24$}}$) when $M\in\{10,32\}$. This latency saving is more significant in the low $E_b/N_0$ region. At $E_b/N_0=3$~dB, the average decoding latency of the proposed decoder with $M=32$ and CRC$24$ in accordance with (\ref{T_BP}) is around $100$ time steps. In comparison, the SCL$32$ decoder in \cite{Alexios_LLR_SCLD} requires $2582$ time steps to decode $\mathcal{P}(1024,512)$ with CRC$24$, and the Fast-SSCL-SPC decoder in \cite{Ali_FSSCL} requires $673$ time steps to decode the same code.

\begin{figure}[t]
  \centering
  \input{Figures/latency_PBP_Compare_CRC24.tikz}
  \caption{Comparison between average decoding latency requirements of BP decoding on permuted factor graphs of $\mathcal{P}(1024,512)$ when the permutations are selected based on the proposed method in this paper and the methods in \cite{Kor09thesis, hussami2009performance} and \cite{elkelesh2018belief}. A $24$-bit CRC is used for early termination.}
  \label{latency}
\end{figure}

\section{Conclusion} \label{sec:conclude}
In this paper, we first introduced a mapping to represent a polar code factor graph permutation with an equivalent bit-index permutation. This scheme enables a single decoding scheduling that can be applied on different factor graph permutations, which is particularly interesting for hardware implementations. Second, we provided an empirical method to construct the good permutations of polar codes, in order to use only a small number of predetermined permutations to obtain a reasonable error-correction performance. We demonstrated that the error-correction performance of the proposed method applied to belief propagation (BP) decoding can obtain more than $0.25$~dB improvement at the frame error rate of $10^{-4}$, in comparison with BP decoding applied to the same number of randomly-selected permuted factor graphs for the 5G polar code of length $1024$ and rate $0.5$, concatenated with a $24$-bit cyclic redundancy check.

config: arxiv


TITLE: Physics Equivalent of Physical Chemistry (P-Chem)
QUESTION [1 upvotes]: Before I take P-Chem I would like to understand how physicists view the same material. What Physics course(s) should I take and/or books should I read to learn the same material from a physicist's perspective? Would thermodynamics be equivalent?
Background: I have done the math: Calculus 1-3 and differential equations and have already taken general physics 1+2 and 2 semesters of modern physics (relativity, QM...).

REPLY [0 votes]: This really depends on the faculty of your institution - some physical chemistry curricula are heavy on molecular orbital theory and spectroscopy rather than macroscopic phenomena like thermodynamics.  In that case, the toolset and language build off what you see in a quantum mechanics class, but the increased complexity of the systems makes the reasoning necessarily a bit less rigorous.  It's hard to say what the physics equivalent is, because to a reductionist, it is a system of approximation tools that allow one to apply quantum mechanical principles to non-homogeneous many-body systems like molecules.


TITLE: A calculus/probability problem
QUESTION [1 upvotes]: Let $p_1,\ldots,p_n$ be numbers such that $0 < p_i < 1$ and $\sum p_i = 1$.
Let also $x_1,\ldots,x_n$ be numbers such that $x_i \ge -1$.
Define the function (for $0<y<1$)
$$f(y) = \sum_{i=1}^n \log\left(1+x_iy\right)p_i.$$
Now let $p_{n+1}$ be a new number such that $0 < p_{n+1} < 1$, and let $x_{n+1}$ be a new number such that $x_{n+1} > x_i$ for all $i=1,\ldots,n$. Define the new function (for $0<y<1$)
$$f^*(y) = \sum_{i=1}^n \log\left(1+x_iy\right)\left(p_i - \frac{p_{n+1}}{n}\right) + \log\left(1+x_{n+1}y\right)p_{n+1}.$$
I believe I have already managed to show, with just basic algebra and some calculus, that $f^*(y) > f(y)$ for all $y$.
Problem: However, can someone help me show also that the maximum value of $f^*(y)$ lies to the right of the maximum value of $f(y)$? (In other words, that the $y$ that maximizes $f^*$ is greater than the $y$ that maximizes $f$.)

REPLY [1 votes]: Note that
$$
f^\prime(y)=\sum_{i=1}^n\frac{p_ix_i}{1+x_iy}\tag{1}
$$
and
$$
\begin{align}
f^{\ast\prime}(y)
&=\sum_{i=1}^n\frac{\left(p_i-\frac{p_{n+1}}{n}\right)x_i}{1+x_iy}\;+\;\frac{p_{n+1}x_{n+1}}{1+x_{n+1}y}\\
&=f^\prime(y)+\frac{p_{n+1}}{n}\sum_{i=1}^n\left(\frac{x_{n+1}}{1+x_{n+1}y}-\frac{x_i}{1+x_iy}\right)\\
&\ge f^\prime(y)\tag{2}
\end{align}
$$
Since $y\ge0$, $\frac{x}{1+xy}$ is an increasing function of $x$, so $\frac{x_{n+1}}{1+x_{n+1}y}\ge\frac{x_i}{1+x_iy}$.
Both $f^{\prime}$ and $f^{\ast\prime}$ are obviously decreasing functions.
When $f^\prime(y)=0$, we have $f^{\ast\prime}(y)\ge0$. Since $f^{\ast\prime}$ is a decreasing function, if $f^{\ast\prime}(y^\ast)=0$, we must have $y^\ast\ge y$.


TITLE: how can I solve the following equation (without complex numbers)?
QUESTION [1 upvotes]: $$
\sqrt{45-x^2} = 3- x^2
$$
$$
\sqrt{13-x^2} = 7 - x^2
$$
I have tried the Quadratic formula.  I always came up with the solution of $\{-3, 3\}$ by the first one and $\{-3, 3\}$ by the second one which is both wrong. Does this happen because I have to pay attention to a rule when substituting in a root, which I don't know, or how should I arrive at the solution that the first has none according to the graph and the second has the solution set according to the graph $\{-2,2\}$? I search a lot in the internet but there was no solution.

REPLY [0 votes]: Define $u=3-x^2$. We have
$$\sqrt{42+u}=u$$
$$u^2=42+u$$
$$(u-7)(u+6)=0$$
$u=-6$ is extranneous. So $u=7$ is the only potential solution. This means that $x^2=-4$, which clearly has no real solutions.
For the other system, define $u=7-x^2$. We have
$$\sqrt{6+u}=u$$
$$u^2-u-6=0$$
$$(u-3)(u+2)=0$$
$u=-2$ is extranneous. So $u=3$ is the only potential solution. This means that $x^2=4$, so the only solutions are $x=\pm 2$.


text:
\begin{document}
\maketitle

\begin{abstract}
  We investigate the sharp asymptotic behavior at criticality of the
  large fluctuations of extensive observables in renewal models of
  statistical mechanics, such as the Poland-Scheraga model of DNA
  denaturation, the Fisher-Felderhof model of fluids, the
  Wako-Sait\^o-Mu\~noz-Eaton model of protein folding, and the
  Tokar-Dreyss\'e model of strained epitaxy. These models amount to
  Gibbs changes of measure of a classical renewal process and can be
  identified with a constrained pinning model of polymers.  The
  extensive observables that enter the thermodynamic description turn
  out to be cumulative rewards corresponding to deterministic rewards
  that are uniquely determined by the waiting time and grow no faster
  than it. The probability decay with the system size of their
  fluctuations switches from exponential to subexponential at
  criticality, which is a regime corresponding to a discontinuous
  pinning-depinning phase transition. We describe such decay by
  proposing a precise large deviation principle under the assumption
  that the subexponential correction term to the waiting time
  distribution is regularly varying. This principle is in particular
  used to characterize the fluctuations of the number of renewals,
  which measures the DNA-bound monomers in the Poland-Scheraga model,
  the particles in the Fisher-Felderhof model and the Tokar-Dreyss\'e
  model, and the native peptide bonds in the
  Wako-Sait\^o-Mu\~noz-Eaton model.\\

\noindent Keywords: Renewal processes; Polymer pinning models;
Critical phenomena; Renewal-reward processes; Precise large
deviations; Regular varying tails\\

\noindent Mathematics Subject Classification 2020: Primary 60F10;
60K05; 60G50, Secondary 62E20; 60K35; 82B20; 82B23
\end{abstract}

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

The Poland-Scheraga model of DNA denaturation \cite{PolSch1,PolSch2},
the Fisher-Felderhof model of fluids
\cite{FisFel1,FisFel2,FisFel3,FisFel4,Roepstorff}, the model of
protein folding introduced independently by Wako and Sait\^o first
\cite{WaSa1,WaSa2} and Mu\~noz and Eaton later
\cite{MuEa1,MuEa2,MuEa3}, and the Tokar-Dreyss\'e model of strained
epitaxy \cite{TokDre1,TokDre2,TokDre3} have been proved to share a
common regenerative structure in Ref.\ \cite{MarcoStat}, where they
have been named {\it renewal models of statistical mechanics}. In fact,
these models can be related to the pinning model of polymers
\cite{Giacomin,Frank}, which amounts to a Gibbs change of measure of a
classical discrete-time renewal process. Precisely, in
Ref.\ \cite{MarcoStat} they have been mathematically mapped into a
constrained pinning model obtained by the pinning model under the
condition that one of the renewals occurs at a predetermined time
corresponding to the system size. This constrained pinning model is
the prototype of renewal models of statistical mechanics and
introduces the language of renewal theory in the above lattice-gas
models of equilibrium statistical physics that apparently have nothing
to do with renewal theory.

The extensive variables that enter the thermodynamic description of
renewal models of statistical mechanics have been shown in
Ref.\ \cite{MarcoStat} to be cumulative rewards, supposing that each
renewal involves a deterministic reward that is uniquely determined by
the waiting time and grows no faster than it. Examples are the number
of DNA-bound monomers in the Poland-Scheraga model and the total
contact energy of a protein in the Wako-Sait\^o-Mu\~noz-Eaton model
\cite{MarcoStat}. The fluctuations of extensive variables in small
systems such as DNA molecules and proteins have become observable by
the recent advent of micromanipulation techniques \cite{Ritort},
motivating the development of a theoretical framework. A sharp large
deviation principle for multivariate extensive observables in renewal
models of statistical mechanics has been proposed in
Ref.\ \cite{MarcoStat}. This principle comes from more general sharp
large deviation principles established in Ref.\ \cite{MarcoProb} for
cumulative rewards in constrained and non-constrained pinning models
of polymers with broad-sense rewards taking values in a separable
Banach space.

Large deviation principles represent a general tool for describing the
exponential decay of probabilities of fluctuations in terms of a rate
function. A thorough study of the rate functions associated with
extensive observables in renewal models of statistical mechanics has
been provided in Ref.\ \cite{MarcoStat}.  There are however systems
for which the decay of probabilities is slower than exponential and
large deviation principles lose effectiveness due to a rate function
that displays a wide region of zeros. Such systems generalize a
polymer at the discontinuous pinning-depinning phase transition and
have been identified and named {\it critical} in
Ref.\ \cite{MarcoStat}.  Critical renewal models are found in the
theory of DNA and proteins since the DNA denaturation transition is
generally believed to be discontinuous \cite{Kafri1,Blossey1} and the
protein folding process is regarded as an ``all-or-none'' transition
\cite{Finkelstein1}, which is a microscopic analog of a discontinuous
phase transition.  Phase transitions are investigated by changing a
control parameter, such as the temperature or the denaturant
concentration, and the hallmark of discontinuous phase transitions is
a discontinuity in the graph of the expected value of some extensive
observable as a function of the control parameter. The number of
renewals, which counts for instance the pinned monomers in pinning
models of polymers and the DNA-bound monomers in the Poland-Scheraga
model, is the extensive observable commonly considered to characterize
the phase transition in renewal models of statistical mechanics
\cite{MarcoStat,Giacomin,Frank}. Criticality as defined in
Ref.\ \cite{MarcoStat} however does not require to introduce and
change a control parameter since the focus is on persistent
fluctuations that lead to subexponential decay of probabilities,
rather than on a comparison of the system in different
conditions. Despite the large amount of work devoted to pinning models
of polymers \cite{Giacomin,Frank}, which among others has elucidated
the sharp asymptotic behavior of partition functions by means of
methods from renewal theory, to the best of our knowledge criticality
in renewal models of statistical mechanics has never been investigated
in terms of fluctuations.

While a large deviation principle for extensive observables in renewal
models of statistical mechanics has been proposed in
Ref.\ \cite{MarcoStat} with no assumption on the waiting time
distribution, the study of critical fluctuations requires that some
hypothesis is made. This paper aims to describe the sharp asymptotics
of critical fluctuations, proposing a so-called precise large
deviation principle, under the assumption that the subexponential
correction term to the waiting time distribution is regularly
varying. This case covers pinning models of polymers and the
Poland-Scheraga model, for which the literature has mostly considered
polynomial-tailed corrections \cite{MarcoStat,Giacomin,Frank}.  The
paper is organized as follows.  Section \ref{sec:intro} introduces
pinning models and critical systems.  Section \ref{Results} presents
and discusses the main result of the paper and its application to the
number of renewals. The proof of this result is reported in section
\ref{proof}, which resorts to three appendices for the most technical
details.

\subsection{Pinning models}
\label{Models}

Let on a probability space $(\Omega,\mathcal{F},\probab)$ be given
independent and identically distributed random variables
$S_1,S_2,\ldots$ taking values in $\{1,2,\ldots\}\cup\{\infty\}$.  The
variable $S_i$ can be regarded as the \textit{waiting time} for the
$i$th occurrence at the \textit{renewal time} $T_i:=S_1+\cdots+S_i$ of
some event that is continuously renewed over time. The pinning model
considered in Refs.\ \cite{MarcoStat} and \cite{MarcoProb} makes use
of this formalism to describe a polymer that is pinned by a substrate
at the monomers $T_1,T_2,\ldots$. The polymer is supposed to consist
of $t\ge 1$ monomers so that the monomer $T_i$ contributes an energy
$-v(S_i)$ provided that $T_i\le t$, the real function $v$ defined on
$\{1,2,\ldots\}\cup\{\infty\}$ being called the
\textit{potential}. The state of the polymer is described by the law
$\probab_t$ on the measurable space $(\Omega,\mathcal{F})$ given by
the Gibbs change of measure
\begin{equation*}
\frac{d\probab_t}{d\probab}:=\frac{e^{H_t}}{Z_t},
\end{equation*}
where $H_t:=\sum_{i\ge 1}v(S_i)\mathds{1}_{\{T_i\le t\}}$ is the
\textit{Hamiltonian} and $Z_t:=\Ex[e^{H_t}]$ is the {\it partition
  function} ensuring normalization. The \textit{pinning model} is the
probabilistic model $(\Omega,\mathcal{F},\probab_t)$ supplied with the
hypotheses of aperiodicity and extensivity.  We say that the
\textit{waiting time distribution} $p:=\probab[S_1=\cdot\,]$ is
\textit{aperiodic} if its support $\mathcal{S}:=\{s\ge 1:p(s)>0\}$ is
nonempty and there does not exist an integer $\tau>1$ with the
property that $\mathcal{S}$ includes only some multiples of $\tau$. It
is worth observing that aperiodicity of $p$ can be obtained by simply
changing the time unit whenever $\probab[S_1<\infty]>0$.
\begin{assum}
\label{ass1}
The waiting time distribution $p$ is aperiodic.
\end{assum}
We say that the potential $v$ is \textit{extensive} if
$\limsup_{s\uparrow\infty}(1/s)\ln e^{v(s)}p(s)<+\infty$. Extensivity
is necessary to make the thermodynamic limit, as $t$ goes to infinity,
of the pinning model meaningful since
$Z_t\ge\Ex[e^{H_t}\mathds{1}_{\{S_1=t\}}]=e^{v(t)}p(t)$.
\begin{assum}
\label{ass2}
The potential $v$ is extensive.
\end{assum}

The \textit{constrained pinning model} where the last monomer is
forced to be always pinned by the substrate is the mathematical
skeleton of the Poland-Scheraga model, the Fisher-Felderhof model, the
Wako-Sait\^o-Mu\~noz-Eaton model, and the Tokar-Dreyss\'e model.
According to Refs.\ \cite{MarcoStat} and \cite{MarcoProb}, it
corresponds to the law $\probab_t^c$ on the measurable space
$(\Omega,\mathcal{F})$ defined through the change of measure
\begin{equation*}
\frac{d\probab_t^c}{d\probab}:=\frac{U_t e^{H_t}}{Z_t^c},
\end{equation*}
where $U_t:=\sum_{i\ge 1}\mathds{1}_{\{T_i=t\}}$ is the renewal
indicator taking value $1$ if and only if $t$ is a renewal and
$Z_t^c:=\Ex[U_te^{H_t}]$ is the partition function. As explained in
Ref.\ \cite{MarcoStat}, the constraint that $t$ is a renewal is needed
to set the system size, that is the number of monomers per strand for
the Poland-Scheraga model, the number of lattice sites for the
Fisher-Felderhof model and the Tokar-Dreyss\'e model, and the number
of peptide bonds for the Wako-Sait\^o-Mu\~noz-Eaton model, which turn
out to be $t$ (see \cite{MarcoStat}, section 3).  Aperiodicity of the
waiting time distribution gives $Z_t^c>0$ for all sufficiently large
$t$ (see \cite{MarcoProb}, section 1.1), thus ensuring that the
constrained pinning model is well-defined at least for such $t$.

\subsection{Deterministic rewards and critical systems}
\label{Known}

Let us suppose that the $i$th renewal involves a \textit{deterministic
  reward} $f(S_i)$, where $f$ is a function that maps
$\{1,2,\ldots\}\cup\{\infty\}$ in the Euclidean $d$-space $\Rl^d$.
The extensive observables of renewal models of statistical mechanics
are \textit{cumulative reward} by the time $t$ of the form
$W_t:=\sum_{i\ge 1}f(S_i)\mathds{1}_{\{T_i\le t\}}$ with $f(s)$ at
most of the order of magnitude of $s$ (see \cite{MarcoStat}, section
3). The number $N_t:=\sum_{i\ge 1}\mathds{1}_{\{T_i\le t\}}$ of
renewals by $t$ is the cumulative reward associated with the function
$f$ identically equal to 1. We aim to characterize the large
fluctuations of $W_t$ under the following hypothesis inherited from
Ref.\ \cite{MarcoStat}.
\begin{assum}
  \label{ass3}
If the support $\mathcal{S}$ of the waiting time distribution is
infinite, then $f(s)/s$ has a limit $r\in\Rl^d$ when $s$ goes to
infinity through $\mathcal{S}$.
\end{assum}

The study of the large fluctuations of $W_t$ on the exponential scale
has been carried out in Ref.\ \cite{MarcoStat}. This section collects
those results of Ref.\ \cite{MarcoStat} that introduce the problem of
critical fluctuations in renewal models of statistical mechanics and
that will serve the proof of the main contribution of the present
paper. In the thermodynamic limit, the scaled cumulative reward
$W_t/t$ converges in probability to a constant vector $\rho\in\Rl^d$
under assumptions \ref{ass1}, \ref{ass2}, and \ref{ass3}, which are
tacitly supposed to be satisfied in the sequel. In order to introduce
$\rho$, let us set $\ell:=\limsup_{s\uparrow\infty}(1/s)\ln
e^{v(s)}p(s)$, which fulfills $-\infty\le\ell<+\infty$ by assumption
\ref{ass2}, and if $\ell>-\infty$, then let us consider an ``effective
statistical weight'' $p_o$ for waiting times defined for all $s\ge 1$
by
\begin{equation}
  p_o(s):=e^{v(s)-\ell s}\,p(s).
\label{defpo}
\end{equation}
If $\ell=-\infty$ or $\ell>-\infty$ and $\sum_{s\ge 1}p_o(s)>1$, then
let $\zeta$ denote that unique real number larger than $\ell$ that
satisfies $\sum_{s\ge 1}e^{v(s)-\zeta s}\,p(s)=1$. Bearing in mind
that $\mathcal{S}$ is necessarily infinite when $\ell>-\infty$ and
letting $r$ be given by assumption \ref{ass3}, the vector $\rho$ turns
out to be
\begin{equation*}
  \rho:=\begin{cases}
  \frac{\sum_{s\ge 1} f(s)\,e^{v(s)-\zeta s}\,p(s)}{\sum_{s\ge 1} s\,e^{v(s)-\zeta s}\,p(s)} & \mbox{if } \ell=-\infty
  \mbox{ or }\ell>-\infty \mbox{ and } \sum_{s\ge 1}p_o(s)>1;\\
  \frac{\sum_{s\ge 1} f(s)\,p_o(s)}{\sum_{s\ge 1} s\,p_o(s)} & \mbox{if } \ell>-\infty, \mbox{ } \sum_{s\ge 1}p_o(s)=1,
  \mbox{ and } \sum_{s\ge 1}s\,p_o(s)<+\infty;\\
  r & \mbox{otherwise}.
  \end{cases}
\end{equation*}
We stress that $\sum_{s\ge 1} s\,e^{v(s)-\zeta s}\,p(s)$ is finite and
$\sum_{s\ge 1} f(s)\,e^{v(s)-\zeta s}\,p(s)$ exists due to assumption
\ref{ass3} whenever $\zeta$ is a real number larger than $\ell$.  The
following proposition states that $W_t/t$ convergences in probability
to $\rho$ as $t$ is sent to infinity (see \cite{MarcoStat}, theorem
4). It follows that $W_t/t$ convergences to $\rho$ also in mean since
$W_t/t$ takes bounded values with probability 1. Indeed, assumption
\ref{ass3} implies that there exists a positive constant $M<+\infty$
such that $\|f(s)\|\le Ms$ for all $s\in\mathcal{S}$, which gives
$\|W_t\|\le M\sum_{i\ge 1}S_i\mathds{1}_{\{T_i\le t\}}\le Mt$ with
probability 1.  Hereafter, $u\cdot v$ denotes the usual dot product
between $u$ and $v$ in $\Rl^d$ and $\|u\|:=\sqrt{u\cdot u}$ is the
Euclidean norm of $u$.
\begin{proposition}
\label{conv}
$\lim_{t\uparrow\infty}\probab_t^c[\|W_t/t-\rho\|\ge \delta]=0$ for any
$\delta>0$.
\end{proposition}
According to Ellis \cite{Ellisbook}, we say that $W_t/t$ {\it
  converges exponentially} to $\rho$ if for any $\delta>0$ there
exists a real number $\lambda>0$ such that
$\probab_t^c[\|W_t/t-\rho\|\ge\delta]\le e^{-\lambda t}$ for all
sufficiently large $t$. The following result improves proposition
\ref{conv} by identifying exponential convergence (see
\cite{MarcoStat}, theorem 4).
\begin{proposition}
\label{prop:conv}
$W_t/t$ converges exponentially to $\rho$ if and only if the conditions
  $\ell>-\infty$, $\sum_{s\ge 1}p_o(s)=1$, $\sum_{s\ge
    1}s\,p_o(s)<+\infty$, and $\rho\ne r$ are not simultaneously
  satisfied.
\end{proposition}
Proposition \ref{prop:conv} tells us that the convergence in
probability to $\rho$ of the scaled cumulative reward $W_t/t$ is
slower than exponential if $\ell>-\infty$, $\sum_{s\ge 1}p_o(s)=1$,
$\sum_{s\ge 1}s\,p_o(s)<+\infty$, and $\rho\ne r$. The facts that only
the condition $\rho\ne r$ involves the function $f$ and that such
condition is verified by most of $f$ justify the following definition
of critical model, which was originally proposed in
Ref.\ \cite{MarcoStat}. We stress that the condition $\sum_{s\ge
  1}p_o(s)=1$, if fulfilled, promotes $p_o$ to a probability
distribution on $\{1,2,\ldots\}$, which we call {\em effective waiting
  time distribution}.
\begin{definition}
The constrained pinning model is critical if $\ell>-\infty$,
$\sum_{s\ge 1}p_o(s)=1$, and $\sum_{s\ge 1}s\,p_o(s)<+\infty$.
\end{definition}
We point out that this notion of criticality is borrowed from the
literature on large deviation principles in statistical mechanics
\cite{El,Phys1}, where the focus is on the breaking of exponential
convergence. A different broader definition of critical system comes
from the theory of random polymers \cite{Giacomin,Frank}, where a
control parameter $\beta$ that plays the role of a binding energy can
drive a pinning-depinning phase transition. We recover the standard
framework of polymers by taking $v(s)=\beta$ for every $s$, and in
this framework our critical scenario corresponds to the conditions
$\ell=\limsup_{s\uparrow\infty}(1/s)\ln p(s)>-\infty$, $\sum_{s\ge
  1}s\,e^{-\ell s}\,p(s)<+\infty$, and $\beta=\beta_c$ with
$\beta_c:=-\ln\sum_{s\ge 1}e^{-\ell s}\,p(s)$. Clearly, $\beta_c$ is
finite if $\sum_{s\ge 1}s\,e^{-\ell s}\,p(s)<+\infty$.  These
conditions identify a discontinuous pinning-depinning phase transition
(see \cite{Giacomin}, theorem 2.1, or \cite{Frank}, theorem 7.4),
leaving out continuous phase transitions which preserve exponential
convergence. In order to clarify the point and make contact with the
literature \cite{MarcoStat,Giacomin,Frank} that looks at the expected
value of the number $N_t$ of renewals by $t$ to characterize the phase
transition, let us recall that $N_t$ is $W_t$ when the function $f$ is
identically equal to 1 and let us observe that this function satisfies
assumption \ref{ass3} with $r=0$. Then, $N_t/t$ converges in
probability and in mean to $\rho$ by proposition \ref{conv}. One can
verify (see \cite{MarcoStat}, section 4.4.1) that $\rho$ as a function
of $\beta$ is analytic on $(-\infty,+\infty)$ if $\ell=-\infty$ or
$\ell>-\infty$ and $\beta_c=-\infty$. If instead $\ell>-\infty$ and
$\beta_c>-\infty$, then $\rho$ is positive and analytic on the open
interval $(\beta_c,+\infty)$, continuous on the closed interval
$[\beta_c,+\infty)$, and equal to 0 for all $\beta<\beta_c$. In this
  case there is a phase transition for $\beta=\beta_c$. The phase
  transition is continuous, namely $\rho$ as a function of $\beta$ is
  continuous at $\beta_c$, if $\sum_{s\ge 1} s\,e^{-\ell
    s}\,p(s)=+\infty$. On the contrary, if $\sum_{s\ge 1} s\,e^{-\ell
    s}\,p(s)<+\infty$, then $\rho$ jumps from the value
  $w_c:=\frac{\sum_{s\ge 1} e^{-\ell s}\,p(s)}{\sum_{s\ge 1}
    s\,e^{-\ell s}\,p(s)}>0$ at $\beta_c$ to the value $0$ when
  $\beta$ is let to decrease and the phase transition is
  discontinuous.

Precise exponential rates for probability decays are provided by large
deviation principles. The cumulative reward $W_t$ satisfies a {\it
  large deviation principle} with {\it good rate function} according
to the following theorem (see \cite{MarcoStat}, theorem 1).
\begin{theorem}
\label{LDP}
There exists a proper convex lower semicontinuous function $I$ from
$\Rl^d$ to $[0,\infty]$ with compact level sets such that
\begin{enumerate}[{\upshape(a)}]
    \item $\liminf_{t\uparrow\infty}\frac{1}{t}\ln\probab_t^c\big[\frac{W_t}{t}\in G\big]\ge -\inf_{w\in G}\{I(w)\}$
    for each open set $G\subseteq\Rl^d$;
  \item $\limsup_{t\uparrow\infty}\frac{1}{t}\ln\probab_t^c\big[\frac{W_t}{t}\in F\big]\le-\inf_{w\in F}\{I(w)\}$
    for each Borel convex set $F\subseteq\Rl^d$ or closed set  $F\subseteq\Rl^d$.
\end{enumerate}
\end{theorem}
The function $I$ is the rate function and the compactness of its level
sets entails that $\inf_{w\in F}\{I(w)\}>0$ whenever $F$ is a closed
set that does not contain a zero of $I$ (see \cite{MarcoStat}, section
4.3).  The explicit expression of $I$ as the convex conjugate of the
scaled cumulant generating function has been given in
Ref.\ \cite{MarcoStat}, where the zeros of $I$ have in particular been
determined (see \cite{MarcoStat}, section 4.3) and the following
proposition has been deduced, $r$ being the vector of assumption
\ref{ass3}.
\begin{proposition}
Let $\mathcal{Z}$ be the set of zeroes of $I$. Then
\begin{enumerate}[{\upshape(a)}]
  \item $\mathcal{Z}=\{\rho\}$ if the model is not critical;
  \item $\mathcal{Z}=\{(1-\alpha)r+\alpha \rho:\alpha\in[0,1]\}$ if the model is critical.
\end{enumerate}
\end{proposition}
The closed line segment $\mathcal{Z}$ is not a singleton at
criticality if $\rho\ne r$ and, according to the literature on large
deviation principles in statistical mechanics \cite{El,Phys1}, we call
it the {\it phase transition segment}.  Thus, whatever $f$ is, the
scaled cumulative reward $W_t/t$ converges exponentially to $\rho$ in
the non-critical scenario with exponential rate $\inf_{w\in
  F}\{I(w)\}>0$ for the probability of a fluctuation over a closed set
$F$ that does not contain $\rho$. On the contrary, convergence in
probability of $W_t/t$ to $\rho$ is slower than exponential in the
critical constrained pinning model provided that $f$ obeys $\rho\ne
r$. In this case, the above large deviation principle tells us that
the probability that $W_t/t$ fluctuates over a closed set $F$ that
does not intersect the phase transition segment $\mathcal{Z}$ decays
exponentially with rate $\inf_{w\in F}\{I(w)\}>0$, whereas it says
nothing about the fluctuations that reach $\mathcal{Z}$ and that
prevent exponential convergence. The situation $\rho=r$ constitutes an
exception because convergence is exponential even in the critical
scenario.

\section{Main results}
\label{Results}

The present paper describes, in a critical scenario with regularly
varying corrections to the waiting time distribution, the fluctuations
of the scaled cumulative reward $W_t/t$ that reach the phase
transition segment $\mathcal{Z}$.  Let us suppose that the constrained
pinning model is critical and that $\rho\ne r$.  We tackle the issue
by studying the fluctuations in the closed half-space
$\mathcal{H}_\alpha$ that contains the fraction $\alpha\in[0,1)$
  starting from $r$ of the segment $\mathcal{Z}$ and that is delimited
  by the hyperplane normal to it:
  \begin{equation*}
    \mathcal{H}_\alpha:=\Big\{w\in\Rl^d:[\rho-r]\cdot[w-(1-\alpha)r-\alpha\rho]\le 0\Big\}.
\end{equation*}
At large $t$, the probability
$\probab_t^c[W_t/t\in\mathcal{H}_\alpha]$ is dominated by the
fluctuations of $W_t/t$ over the phase transition segment that prevent
exponential convergence because we know that
$\probab_t^c[W_t/t\in\mathcal{H}_\alpha\cap F]$ decays exponentially
fast for every closed set $F$ that does not intersect $\mathcal{Z}$.

\subsection{A precise large deviation principle}

We determine the large-$t$ behavior of the probability
$\probab_t^c[W_t/t\in\mathcal{H}_\alpha]$ under the assumption that
there exist a real number $\kappa\ge 1$ and a slowly varying function
$\mathcal{L}$ such that for each $s\ge 1$
\begin{equation}
  p_o(s)=\frac{\mathcal{L}(s)}{s^{\kappa+1}},
\label{ass4}
\end{equation}
$p_o$ being the effective waiting time distribution defined by
(\ref{defpo}).  A measurable function $\mathcal{L}$ on the positive
semi-axis is {\it slowly varying} if it is positive on some
neighborhood of infinity and satisfies the scale-invariance property
$\lim_{x\uparrow+\infty}\mathcal{L}(\gamma x)/\mathcal{L}(x)=1$ for
any number $\gamma>0$. Trivially, a measurable function $\mathcal{L}$
with a positive limit at infinity is slowly varying. The simplest
non-trivial example is represented by the logarithm.  Due to slow
variation of $\mathcal{L}$, the sequence whose $s$th term is $p_o(s)$
is {\it regularly varying with index $-\kappa-1$}.  We refer to
\cite{RV} for the theory of slow and regular variation.  We point out
that the constraint $\kappa\ge 1$ reflects our focus on critical
models, which fulfill $\sum_{s\ge 1}s\,p_o(s)<+\infty$. Indeed, since
$\mathcal{L}(x)\ge x^{-\delta}$ for any fixed $\delta>0$ and all
sufficiently large $x$ (see \cite{RV}, proposition 1.3.6), $\kappa<1$
would entail $\sum_{s\ge 1}s\,p_o(s)=+\infty$.  The following theorem
is the main result of the paper.
\begin{theorem}
  \label{mainth}
Suppose that assumptions \ref{ass1}, \ref{ass2}, and \ref{ass3} are
satisfied, that the model is critical, and that $\rho\ne r$. If there
exist a real number $\kappa\ge 1$ and a slowly varying function
$\mathcal{L}$ such that (\ref{ass4}) holds, then for every
$\alpha\in[0,1)$
\begin{equation*}
  \lim_{t\uparrow\infty}\frac{\probab_t^c[W_t/t\in\mathcal{H}_\alpha]}{t^{1-\kappa}\mathcal{L}(t)}=\frac{1}{\sum_{s\ge 1}s\,p_o(s)}
  \begin{cases}
    \frac{\alpha}{1-\alpha}+\ln(1-\alpha) & \mbox{if } \kappa=1; \\
    \frac{1+(\alpha\kappa-1)(1-\alpha)^{-\kappa}}{\kappa(\kappa-1)} & \mbox{if } \kappa>1.
  \end{cases}
\end{equation*}
\end{theorem}

Theorem \ref{mainth} states a precise large deviation principle for
the cumulative reward $W_t$. It completes the picture of the large
fluctuations of extensive variables in renewal models of statistical
mechanics by supplying the leading order of probabilities at
criticality, where a large deviation principle loses effectiveness.
It is worth noting that the function $f$ of rewards enters only the
shape of the half-space $\mathcal{H}_\alpha$ through $\rho$ and $r$,
so that, basically, all extensive observables in critical models
display the same fluctuations, whose probability decays polynomially
in the system size under our assumption of regular variation.

The proof of theorem \ref{mainth} is provided in section \ref{proof}.
We stress that the cumulative reward is a random sum of random
variables, which can be written down explicitly by introducing the
number $N_t$ of renewals by $t$ as $W_t=\sum_{i=1}^{N_t}X_i$ with
$X_i:=f(S_i)$ for any $i$. Precise large deviations for random sums of
random variables with several types of subexponential distributions
have been investigated by many researchers
\cite{L1,L2,L3,L4,L5,L6,L7}. However, their work does not cover our
case in two respects. First, the hypothesis they have made is that the
random variables $X_1,X_2,\ldots$ are independent of the counting
process $N_t$, but this hypothesis is not satisfied by our
problem. Second, we had to implement the constraint that $t$ is a
renewal in order to set the system size of renewal models of
statistical mechanics at $t$, whereas they did not have such a special
need.  For these reasons, theorem \ref{mainth} is a new result that
requires a new proof, which is guided by the idea that the only
significant way in which a large fluctuation of $W_t$ occurs at
criticality is that one and only one of the waiting times takes a
large value. This idea underlies many heavy-tailed problems and is
known with the folklore name of {\em principle of a single big jump}
\cite{Foss}, whose a detailed picture can be given for sums of
independent and identically distributed random variables
\cite{Bigjump1,Bigjump2}.

\subsection{Critical fluctuations of $\boldsymbol{N_t}$}

As shown in Ref.\ \cite{MarcoStat}, renewal models of statistical
mechanics can be mapped in a standard constrained pinning model where
$v(s)=\beta$ for any $s$, $\beta$ being a real number that acts as a
control parameter. Precisely, $\beta$ is the binding energy for the
Poland-Scheraga model, the chemical potential for the Fisher-Felderhof
model and the Tokar-Dreyss\'e model, and an entropic loss for the
Wako-Sait\^o-Mu\~noz-Eaton model (see \cite{MarcoStat}, section
3). From section \ref{Known} we know that criticality is achieved if
$\ell=\limsup_{s\uparrow\infty}(1/s)\ln p(s)>-\infty$, $\sum_{s\ge
  1}s\,e^{-\ell s}\,p(s)<+\infty$, and $\beta=\beta_c$ with
$\beta_c:=-\ln\sum_{s\ge 1}e^{-\ell s}\,p(s)$. Let us suppose here
that $\ell>-\infty$ and that $\sum_{s\ge 1}s\,e^{-\ell
  s}\,p(s)<+\infty$ and let us investigate the fluctuations of the
number $N_t$ of renewals by $t$ for different values of $\beta$. The
extensive observable $N_t$ measures the DNA-bound monomers in the
Poland-Scheraga model, the particles in the Fisher-Felderhof model and
the Tokar-Dreyss\'e model, and the native peptide bonds in the
Wako-Sait\^o-Mu\~noz-Eaton model (see \cite{MarcoStat}, section 3).
By proposition \ref{conv}, $N_t/t$ converges in probability and in
mean to $\rho=\frac{\sum_{s\ge 1} e^{-\zeta s}\,p(s)}{\sum_{s\ge 1}
  s\,e^{-\zeta s}\,p(s)}$ for $\beta>\beta_c$ with $\zeta>\ell$
satisfying $\sum_{s\ge 1} e^{\beta-\zeta s}\,p(s)=1$, to
$\rho=w_c:=\frac{\sum_{s\ge 1} e^{-\ell s}\,p(s)}{\sum_{s\ge 1}
  s\,e^{-\ell s}\,p(s)}$ for $\beta=\beta_c$, and to $\rho=0$ for
$\beta<\beta_c$.  By combining parts (a) and (b) of theorem \ref{LDP}
we find for any $\beta$ and open interval $G$
\begin{equation*}
\lim_{t\uparrow\infty}\frac{1}{t}\ln\probab_t^c\bigg[\frac{N_t}{t}\in G\bigg]=-\inf_{w\in G}\big\{I(w)\big\}.
\end{equation*}
The rate function $I$ has been determined in Ref.\ \cite{MarcoStat} and
for each real $w$ takes the value (see \cite{MarcoStat}, section 4.4.2)
\begin{equation*}
  I(w):=\begin{cases}
  w(\beta_c-\beta)-\ell & \mbox{if } w\in[0,w_c];\\
  -w\ln\big[\sum_{s\ge 1}e^{\beta-\eta s}\,p(s)\big]-\eta & \mbox{if } w\in(w_c,1);\\
  -\ln\big[e^\beta p(1)\big] & \mbox{if } w=1;\\
  +\infty & \mbox{otherwise}
  \end{cases}
  +
  \begin{cases}
  \zeta & \mbox{if } \beta>\beta_c;\\
  \ell & \mbox{if } \beta\le\beta_c,
  \end{cases}
\end{equation*}
where $\eta$ is the unique number larger than $\ell$ that fulfills
$\frac{\sum_{s\ge 1} e^{-\eta s}\,p(s)}{\sum_{s\ge 1} s\,e^{-\eta
    s}\,p(s)}=w$.  The rate function $I$ has an affine stretch on
$[0,w_c]$, is analytic on $(w_c,1)$, and is continuously
differentiable at $w_c$ (see \cite{MarcoStat}, section 4.4.2). If
$\beta\ne\beta_c$, then the model is not critical and $I(w)=0$ only
for $w=\rho$. If instead $\beta=\beta_c$, then the model is critical
and $I(w)=0$ for all $w\in[0,w_c]$. The phase transition segment
$\mathcal{Z}$ is the closed interval $[0,w_c]$.

Theorem \ref{mainth} completes the study of the large fluctuations of
$N_t$ initiated in Ref.\ \cite{MarcoStat} by resolving for every
$\alpha\in[0,1)$ the subexponential decay at criticality of the
  probability $\probab_t^c[N_t\le\alpha w_c t]$. Indeed, under the
  assumption that there exist an index $\kappa\ge 1$ and a slowly
  varying function $\mathcal{L}$ such that $e^{-\ell
    s}\,p(s)=s^{-\kappa-1}\mathcal{L}(s)$ for all $s\ge 1$, as
  $\mathcal{H}_\alpha=(-\infty,\alpha w_c]$ theorem \ref{mainth} shows
that
\begin{equation*}
  \lim_{t\uparrow\infty}\frac{\probab_t^c[N_t\le\alpha w_c t]}{t^{1-\kappa}\mathcal{L}(t)}=\frac{1}{\sum_{s\ge 1}s\,e^{-\ell s}\,p(s)}
  \begin{cases}
    \frac{\alpha}{1-\alpha}+\ln(1-\alpha) & \mbox{if } \kappa=1; \\
    \frac{1+(\alpha\kappa-1)(1-\alpha)^{-\kappa}}{\kappa(\kappa-1)} & \mbox{if } \kappa>1.
  \end{cases}
\end{equation*}

\section{Proof of theorem \ref{mainth}}
\label{proof}

In this section we report the proof of theorem \ref{mainth},
postponing the most technical details in the appendices in order not
to interrupt the flow of the presentation. The proof is facilitated by
a natural change of measure. Regarding the effective waiting time
distribution $p_o$ as a new waiting time distribution, which is
non-defective because $\sum_{s\ge 1} p_o(s)=1$ by the hypothesis of
criticality, let us consider a new probability space
$(\Omega_o,\mathcal{F}_o,\probab_o)$ where a sequence $\{S_i\}_{i\ge
  1}$ of independent waiting times distributed according to $p_o$ is
given. Denoting by $\Ex_o$ the expectation with respect to
$\probab_o$, we have $\Ex_o[S_1]=\sum_{s\ge 1} s\,p_o(s)<+\infty$ and
$\Ex_o[f(S_1)]=\rho\,\Ex_o[S_1]$ again by criticality. The tail
probability $\mathcal{Q}$ of $S_1$ under the law $\probab_o$ is the
measurable function that maps each real number $x>0$ in
\begin{equation*}
\mathcal{Q}(x):=\probab_o[S_1>x]=\sum_{s\ge 1}\mathds{1}_{\{s>x\}} p_o(s).
\end{equation*}
The hypothesis that $p_o(s)=s^{-\kappa-1}\mathcal{L}(s)$ for all $s\ge
1$ with $\mathcal{L}$ a slowly varying function results in regular
variation with index $-\kappa$ for $\mathcal{Q}$, meaning that
$\lim_{x\uparrow+\infty}\mathcal{Q}(\gamma
x)/\mathcal{Q}(x)=\gamma^{-\kappa}$ for any number $\gamma>0$. Indeed,
the following lemma holds as demonstrated in appendix \ref{appendix1}.
\begin{lemma}
\label{lemmaQtail}
$\mathcal{Q}$ varies regularly with index $-\kappa$ and
$\lim_{x\uparrow+\infty}x^\kappa\mathcal{Q}(x)/\mathcal{L}(x)=1/\kappa$.
\end{lemma}

The transition to the new probabilistic model
$(\Omega_o,\mathcal{F}_o,\probab_o)$ proceeds as follows.  By
observing that $\prod_{i=1}^n e^{v(s_i)}p(s_i)=e^{\ell t}\prod_{i=1}^n
p_o(s_i)$ whenever $s_1+\cdots+s_n=t$, for every integer $t\ge 1$ and
Borel set $\mathcal{B}\subseteq\Rl^d$ we find
\begin{align}
\nonumber
Z_t^c\cdot\,\probab_t^c\bigg[\frac{W_t}{t}\in \mathcal{B}\bigg]&=\Ex\bigg[\mathds{1}_{\big\{\frac{W_t}{t}\in \mathcal{B}\big\}} U_te^{H_t}\bigg]\\
\nonumber
&=\sum_{n\ge 1}\Ex\bigg[\mathds{1}_{\big\{\frac{1}{t}\sum_{i=1}^n f(S_i)\in \mathcal{B}\big\}} \mathds{1}_{\{T_n=t\}}e^{\sum_{i=1}^n v(S_i)}\bigg]\\
\nonumber
&=\sum_{n\ge 1}\sum_{s_1\ge 1}\cdots\sum_{s_n\ge 1}\mathds{1}_{\big\{\frac{1}{t}\sum_{i=1}^n f(s_i)\in \mathcal{B}\big\}} \mathds{1}_{\{s_1+\cdots+s_n=t\}}
\prod_{i=1}^n e^{v(s_i)} p(s_i)\\
\nonumber
&=e^{\ell t}\sum_{n\ge 1}\sum_{s_1\ge 1}\cdots\sum_{s_n\ge 1}\mathds{1}_{\big\{\frac{1}{t}\sum_{i=1}^n f(s_i)\in \mathcal{B}\big\}} \mathds{1}_{\{s_1+\cdots+s_n=t\}}
\prod_{i=1}^n p_o(s_i)\\
&=e^{\ell t}\,\Ex_o\bigg[\mathds{1}_{\big\{\frac{W_t}{t}\in \mathcal{B}\big\}} U_t\bigg].
\label{primaident}
\end{align}
This identity with $\mathcal{B}=\Rl^d$ yields $Z_t^c=e^{\ell
  t}\,\Ex_o[U_t]$, which allows us to recast (\ref{primaident}) as
\begin{equation}
\label{mod2}
\Ex_o[U_t]\cdot\probab_t^c\bigg[\frac{W_t}{t}\in\mathcal{B}\bigg]=\Ex_o\bigg[\mathds{1}_{\big\{\frac{W_t}{t}\in \mathcal{B}\big\}} U_t\bigg].
\end{equation}
Formula (\ref{mod2}) is precisely the bridge between constrained
pinning models with respect to $(\Omega,\mathcal{F},\probab)$ and
$(\Omega_o,\mathcal{F}_o,\probab_o)$. We observe that
$\lim_{t\uparrow\infty}\Ex_o[U_t]=1/\Ex_o[S_1]$ since $p_o$ is
non-defective. This limit is due to an application of the renewal
theorem (see \cite{Feller1}, theorem 1 in chapter XIII.10) to the
renewal equation $\Ex_o[U_t]=\sum_{s=1}^tp_o(s)\,\Ex_o[U_{t-s}]$ valid
for every $t\ge 1$. The renewal equation is deduced by conditioning on
$T_1=S_1$ and then by using the fact that a renewal process starts
over at every renewal.

Fix $\alpha\in[0,1)$. If $t$ is a renewal, then $\sum_{i\ge
    1}S_i\mathds{1}_{\{T_i\le t\}}=t$ and the condition
  $W_t/t\in\mathcal{H}_\alpha$, namely
  $[\rho-r]\cdot[W_t/t-(1-\alpha)r-\alpha\rho]\le 0$, becomes
  $\sum_{i\ge 1}g(S_i)\mathds{1}_{\{T_i\le t\}}\le\alpha t$ with
  \begin{equation*}
    g(s):=\frac{[\rho-r]\cdot[f(s)-rs]}{\|\rho-r\|^2}.
\end{equation*}
This way, by setting $\mathcal{B}=\mathcal{H}_\alpha$ in (\ref{mod2})
we find for each $t\ge 1$
\begin{equation*}
  \Ex_o[U_t]\cdot\probab_t^c\bigg[\frac{W_t}{t}\in\mathcal{H}_\alpha\bigg]=
  \Ex_o\bigg[\mathds{1}_{\big\{\sum_{i\ge 1}g(S_i)\mathds{1}_{\{T_i\le t\}}\le\alpha t\big\}}U_t\bigg]=:\mathcal{E}(t).
\end{equation*}
Since $\lim_{t\uparrow\infty}\Ex_o[U_t]=1/\Ex_o[S_1]$ and
$\lim_{t\uparrow\infty}t^\kappa\mathcal{Q}(t)/\mathcal{L}(t)=1/\kappa$
by lemma \ref{lemmaQtail}, it follows that in order to prove theorem
\ref{mainth} it suffices to demonstrate that
\begin{align}
  \lim_{t\uparrow\infty}\frac{\mathcal{E}(t)}{t\,\mathcal{Q}(t)}
 \nonumber
  &=\frac{1}{\Ex_o[S_1]^2}\begin{cases}
    \frac{\alpha}{1-\alpha}+\ln(1-\alpha) & \mbox{if } \kappa=1;\\
    \frac{1+(\alpha\kappa-1)(1-\alpha)^{-\kappa}}{\kappa-1} & \mbox{if } \kappa>1
 \end{cases}\\
 &=\frac{1}{\Ex_o[S_1]^2}\bigg[\alpha(1-\alpha)^{-\kappa}-\int_{1-\alpha}^1\frac{dx}{x^\kappa}\bigg].
 \label{mod3}
\end{align}
We shall demonstrate (\ref{mod3}) by verifying a lower bound first and
an upper bound later. The features of the function $g$ we will use to
this aim are the equality $\Ex_o[g(S_1)]=\Ex_o[S_1]$ and the fact that
$g(s)/s$ goes to zero when $s$ is sent to infinity through
$\mathcal{S}$, which is the support of both $p$ and $p_o$. Since the
values $g(s)$ when $s\notin\mathcal{S}$ do not affect the problem, in
order to simplify the notations we redefine the function $g$ by
setting $g(s):=0$ for all $s\notin\mathcal{S}$ so that the limit
$\lim_{s\uparrow\infty}g(s)/s=0$ is valid.

\subsection{A lower bound}

In order to prove (\ref{mod3}) we show at first that
\begin{equation}
   \label{binf}
  \liminf_{t\uparrow\infty}\frac{\mathcal{E}(t)}{t\,\mathcal{Q}(t)}\ge
  \frac{1}{\Ex_o[S_1]^2}\bigg[\alpha(1-\alpha)^{-\kappa}-\int_{1-\alpha}^1\frac{dx}{x^\kappa}\bigg].
\end{equation}
This bound is trivial if $\alpha=0$ since the l.h.s.\ of (\ref{binf})
is not negative. In the case $\alpha>0$, it follows if we demonstrate
that for all real numbers $\gamma$, $\eta$, and $\epsilon$ such that
$1-\alpha<\gamma<\eta<1$ and $\epsilon>0$
\begin{equation}
\label{binf1}
  \liminf_{t\uparrow\infty}\frac{\mathcal{E}(t)}{t\,\mathcal{Q}(t)}\ge
  \frac{1-2\epsilon}{\Ex_o[S_1]^2}\bigg[(1-\gamma)\gamma^{-\kappa}-(1-\eta)\eta^{-\kappa}-\int_\gamma^\eta \frac{dx}{x^\kappa}\bigg].
\end{equation}
Indeed, (\ref{binf1}) gives (\ref{binf}) when $\gamma$ is sent to
$1-\alpha$, $\eta$ is sent to 1, and $\epsilon$ is sent to 0.

Let us assume $\alpha>0$ and let us pick $\gamma$, $\eta$, and
$\epsilon$ such that $1-\alpha<\gamma<\eta<1$ and $\epsilon>0$.  To
get at a proof of (\ref{binf1}) we observe that $3y/2-y^2/2\le 1$ for
any integer $y\in\mathbb{Z}$, so that for each $n\ge 2$ we find
\begin{equation*}
1\ge\frac{3}{2}\sum_{j=1}^n\mathds{1}_{\{S_j>\gamma t\}}-\frac{1}{2}\Bigg[\sum_{j=1}^n\mathds{1}_{\{S_j>\gamma t\}}\Bigg]^2
=\sum_{j=1}^n\mathds{1}_{\{S_j>\gamma t\}}-\sum_{j=1}^{n-1}\sum_{k=j+1}^n\mathds{1}_{\{S_j>\gamma t\}}\mathds{1}_{\{S_k>\gamma t\}}.
\end{equation*}
It follows that for all $t\ge 2$
\begin{align}
  \nonumber
  \mathcal{E}(t)&:=\Ex_o\bigg[\mathds{1}_{\big\{\sum_{i\ge 1}g(S_i)\mathds{1}_{\{T_i\le t\}}\le\alpha t\big\}}U_t\bigg]
  =\sum_{n=1}^t\Ex_o\bigg[\mathds{1}_{\big\{\sum_{i=1}^ng(S_i)\le\alpha t\big\}}\mathds{1}_{\{T_n=t\}}\bigg]\\
  \nonumber
  &\ge\sum_{n=1}^t\sum_{j=1}^n\Ex_o\bigg[\mathds{1}_{\big\{\sum_{i=1}^ng(S_i)\le\alpha t\big\}}\mathds{1}_{\{S_j>\gamma t\}}
    \mathds{1}_{\{S_1+\cdots + S_n=t\}}\bigg]+\\
  \nonumber
  &-\sum_{n=2}^t\sum_{j=1}^{n-1}\sum_{k=j+1}^n
  \Ex_o\bigg[\mathds{1}_{\big\{\sum_{i=1}^ng(S_i)\le\alpha t\big\}}\mathds{1}_{\{S_j>\gamma t\}}\mathds{1}_{\{S_k>\gamma t\}}
    \mathds{1}_{\{S_1+\cdots+S_n=t\}}\bigg]\\
  \nonumber
  &\ge\sum_{n=1}^tn\,\Ex_o\bigg[\mathds{1}_{\big\{\sum_{i=1}^ng(S_i)\le\alpha t\big\}}\mathds{1}_{\{S_n>\gamma t\}}\mathds{1}_{\{T_n=t\}}\bigg]
  -t^2\,\Ex_o\Big[\mathds{1}_{\{S_1>\gamma t\}}\mathds{1}_{\{S_2>\gamma t\}}U_t\Big]\\
  &\ge\sum_{n=1}^tn\,\Ex_o\bigg[\mathds{1}_{\big\{\sum_{i=1}^ng(S_i)\le\alpha t\big\}}\mathds{1}_{\{S_n>\gamma t\}}\mathds{1}_{\{T_n=t\}}\bigg]
  -\big[t\,\mathcal{Q}(\gamma t)\big]^2.
  \label{aux1}
\end{align}
Since $\alpha+\gamma-1>0$ by hypothesis, the limit
$\lim_{s\uparrow\infty}g(s)/s=0$ entails that there exists a positive
integer $t_1$ such that $g(s)\le (\alpha+\gamma-1)s$ whenever
$s>\gamma t_1$. If $t>t_1$, then the conditions $s>\gamma t$ and
$\sum_{i=1}^ng(S_i)<(\alpha+\gamma)(t-s)$ together imply
\begin{equation*}
\sum_{i=1}^ng(S_i)+g(s)\le(\alpha+\gamma)(t-s)+(\alpha+\gamma-1)s=(\alpha+\gamma)t-s\le\alpha t.
\end{equation*}
This way, from (\ref{aux1}) we get for every $t>t_1\ge 1$
\begin{align}
  \nonumber
  \mathcal{E}(t)&\ge\sum_{n=2}^t\sum_{s=1}^{t-n+1} n\,\Ex_o\bigg[\mathds{1}_{\big\{\sum_{i=1}^{n-1}g(S_i)+g(s)\le\alpha t\big\}}
    \mathds{1}_{\{T_{n-1}=t-s\}}\bigg]\,\mathds{1}_{\{s>\gamma t\}}\,p_o(s)-\big[t\,\mathcal{Q}(\gamma t)\big]^2\\
  \nonumber
  &\ge\sum_{s=1}^{t-1}\sum_{n=1}^{t-s} n\,\Ex_o\bigg[\mathds{1}_{\big\{\sum_{i=1}^ng(S_i)+g(s)\le\alpha t\big\}}
    \mathds{1}_{\{T_n=t-s\}}\bigg]\,\mathds{1}_{\{s>\gamma t\}}\,p_o(s)-\big[t\,\mathcal{Q}(\gamma t)\big]^2\\
  \nonumber
  &\ge\sum_{s=1}^{t-1}\sum_{n=1}^{t-s} n\,\Ex_o\bigg[\mathds{1}_{\big\{\sum_{i=1}^ng(S_i)< (\alpha+\gamma)(t-s)\big\}}
    \mathds{1}_{\{T_n=t-s\}}\bigg]\,\mathds{1}_{\{s>\gamma t\}}\,p_o(s)-\big[t\,\mathcal{Q}(\gamma t)\big]^2\\
  \nonumber
  &=\sum_{s=1}^{t-1}\Ex_o\bigg[N_{t-s}\mathds{1}_{\big\{\sum_{i\ge 1}g(S_i)\mathds{1}_{\{T_i\le t-s\}}< (\alpha+\gamma)(t-s)\big\}}U_{t-s}\bigg]\,
  \mathds{1}_{\{s>\gamma t\}}\,p_o(s)-\big[t\,\mathcal{Q}(\gamma t)\big]^2.
\end{align}
By introducing the restriction $s<\eta t$, for any $t>t_1$ we obtain
the further lower bound
\begin{align}
  \nonumber
 \mathcal{E}(t)&\ge\sum_{s\ge 1}\Ex_o\bigg[N_{t-s}\mathds{1}_{\big\{\sum_{i\ge 1}g(S_i)\mathds{1}_{\{T_i\le t-s\}}<(\alpha+\gamma)(t-s)\big\}}U_{t-s}\bigg]\,
  \mathds{1}_{\{\gamma t<s\le\eta t\}}\,p_o(s)-\big[t\,\mathcal{Q}(\gamma t)\big]^2\\
  \nonumber
  &\ge\sum_{s\ge 1}\Ex_o\big[N_{t-s}U_{t-s}\big]\,\mathds{1}_{\{\gamma t<s\le\eta t\}}\,p_o(s)-\big[t\,\mathcal{Q}(\gamma t)\big]^2+\\
  \label{aux2}
  &-\sum_{s\ge 1}(t-s)\,\Ex_o\bigg[\mathds{1}_{\big\{\sum_{i\ge 1}g(S_i)\mathds{1}_{\{T_i\le t-s\}}\ge(\alpha+\gamma)(t-s)\big\}}U_{t-s}\bigg]\,
  \mathds{1}_{\{\gamma t<s\le\eta t\}}\,p_o(s),
\end{align}
where the fact that $N_{t-s}\le t-s$ has been used in the last
equality.

To continue estimation we need the following lemma, which is proved in appendix \ref{appendix2}.
\begin{lemma}
\label{lemmaux}
$\lim_{t\uparrow\infty}\Ex_o[(N_t/t)U_t]=1/\Ex_o[S_1]^2$.
\end{lemma}
We also observe that
$\lim_{t\uparrow\infty}\Ex_o[\mathds{1}_{\{\sum_{i\ge
      1}g(S_i)\mathds{1}_{\{T_i\le
      \tau\}}\ge(\alpha+\gamma)\tau\}}U_\tau]=0$ since formula
(\ref{mod2}) and proposition \ref{conv} with $g$ in place of $f$ yield
respectively $\Ex_o[\mathds{1}_{\{\sum_{i\ge
      1}g(S_i)\mathds{1}_{\{T_i\le
      \tau\}}\ge(\alpha+\gamma)\tau\}}U_\tau]\le\probab_\tau^c[\sum_{i\ge
    1}g(S_i)\mathds{1}_{\{T_i\le\tau\}}\ge(\alpha+\gamma)\tau]$ and
$\lim_{\tau\uparrow\infty}\probab_\tau^c[\sum_{i\ge
    1}g(S_i)\mathds{1}_{\{T_i\le\tau\}}\ge(\alpha+\gamma)\tau]=0$ as
$\Ex_o[g(S_1)]/\Ex_o[S_1]=1$ and $\alpha+\gamma>1$.  Then, by these
arguments we deduce that there exists $t_2\ge t_1$ such that
$\tau>(1-\eta)t_2$ implies both $\Ex_o[N_\tau U_\tau]\ge
(1-\epsilon)\tau/\Ex_o[S_1]^2$ and $\Ex_o[\mathds{1}_{\{\sum_{i\ge
      1}g(S_i)\mathds{1}_{\{T_i\le
      \tau\}}\ge(\alpha+\gamma)\tau\}}U_\tau]\le
\epsilon/\Ex_o[S_1]^2$.  If $t>t_2$, then the condition $s\le\eta t$
giving $t-s>(1-\eta)t_2$ allows us to replace (\ref{aux2}) with
\begin{align}
  \nonumber
  \mathcal{E}(t)&\ge\frac{1-2\epsilon}{\Ex_o[S_1]^2}\sum_{s\ge 1}(t-s)\,\mathds{1}_{\{\gamma t<s\le\eta t\}}\,p_o(s)-\big[t\,\mathcal{Q}(\gamma t)\big]^2\\
  \nonumber
  &=\frac{1-2\epsilon}{\Ex_o[S_1]^2}\bigg[(1-\gamma)\,t\,\mathcal{Q}(\gamma t)-(1-\eta)\,t\,\mathcal{Q}(\eta t)
  -t\int_\gamma^\eta\mathcal{Q}(xt)dx\bigg]-\big[t\,\mathcal{Q}(\gamma t)\big]^2.
\end{align}
From here, we obtain (\ref{binf1}) by dividing by $t\,\mathcal{Q}(t)$
first and by sending $t$ to infinity later because on the one hand the
limit
$\lim_{t\uparrow\infty}\mathcal{Q}(xt)/\mathcal{Q}(t)=x^{-\kappa}$ is
uniform with respect to $x$ in the compact interval $[\gamma,\eta]$
(see \cite{RV}, theorem 1.5.2), and on the other hand
$\lim_{t\uparrow\infty}t\,\mathcal{Q}(t)=0$ as
$t\,\mathcal{Q}(t)\le\Ex_o[S_1\mathds{1}_{\{S_1>t\}}]$ and
$\Ex_o[S_1]<+\infty$.

\subsection{An upper bound}

Now we show that for all real numbers $\gamma$, $\eta$, and
$\epsilon$ such that $0<\gamma<1-\alpha$, $\gamma<\eta<1$, and
$\epsilon>0$
\begin{equation}
  \limsup_{t\uparrow\infty}\frac{\mathcal{E}(t)}{t\,\mathcal{Q}(t)}\le
  \frac{1+\epsilon}{\Ex_o[S_1]^2}\bigg[(1-\gamma)\gamma^{-\kappa}-(1-\eta)\eta^{-\kappa}-\int_\gamma^\eta \frac{dx}{x^\kappa}\bigg]
  +\eta^{-\kappa}-1.
  \label{primau}
\end{equation}
In the light of (\ref{binf}), this bound leads us to prove
(\ref{mod3}) because sending $\gamma$ to $1-\alpha$, $\eta$ to 1, and
$\epsilon$ to 0 we find
\begin{equation*}
  \limsup_{t\uparrow\infty}\frac{\mathcal{E}(t)}{t\,\mathcal{Q}(t)}\le
  \frac{1}{\Ex_o[S_1]^2}\bigg[\alpha(1-\alpha)^{-\kappa}-\int_{1-\alpha}^1\frac{dx}{x^\kappa}\bigg].
\end{equation*}

Pick $\gamma$, $\eta$, and $\epsilon$ such that $0<\gamma<1-\alpha$,
$\gamma<\eta<1$, and $\epsilon>0$. Obviously, for every $n\ge 1$ and
$t\ge 1$ we have
\begin{equation*}
  1\le\prod_{j=1}^n\mathds{1}_{\{S_j\le\gamma t\}}+\sum_{j=1}^n\mathds{1}_{\{S_j>\gamma t\}}
\end{equation*}
since either $S_j\le\gamma t$ for all $j\le n$ or $S_j>\gamma t$ for
at least one $j\le n$. It follows that for any $t\ge 1$
\begin{equation}
  \mathcal{E}(t)=\sum_{n=1}^t\Ex_o\bigg[\mathds{1}_{\big\{\sum_{i=1}^ng(S_i)\le\alpha t\big\}}\mathds{1}_{\{T_n=t\}}\bigg]\le
  \mathcal{E}_1(t)+\mathcal{E}_2(t)
  \label{auxu1}
\end{equation}
with
\begin{equation*}
\mathcal{E}_1(t):=\sum_{n=1}^t\Ex_o\Bigg[\mathds{1}_{\big\{\sum_{i=1}^ng(S_i)\le\alpha t\big\}}\prod_{j=1}^n\mathds{1}_{\{S_j\le\gamma
      t\}}\mathds{1}_{\{T_n=t\}}\Bigg]
\end{equation*}
and
\begin{equation*}
\mathcal{E}_2(t):=\sum_{n=1}^tn\,\Ex_o\Big[\mathds{1}_{\{S_n>\gamma t\}}\mathds{1}_{\{T_n=t\}}\Big].
\end{equation*}
The term $\mathcal{E}_1(t)$ can be estimated by means of the following
lemma which is proved in appendix \ref{appendix3}. Set $\xi_t:=-\ln
t\,\mathcal{Q}(\gamma t)$ for all $t$ for brevity and notice that
$\lim_{t\uparrow\infty}\xi_t=+\infty$ since
$x\,\mathcal{Q}(x)\le\Ex_o\big[S_1\mathds{1}_{\{S_1>x\}}\big]$ and
$\Ex_o\big[S_1\big]<+\infty$.
\begin{lemma}
  \label{lemmazl}
  For all sufficiently large $t$ there exist two positive real numbers
  $z_t$ and $\lambda_t$ such that $\Ex_o[\mathds{1}_{\{S_1\le\gamma
      t\}}\,e^{z_tS_1-\lambda_tg(S_1)}]\le 1$ and
  $(z_t-\alpha\lambda_t)t\ge\xi_t+\ln|\xi_t|$.
\end{lemma}
Let $z_t$ and $\lambda_t$ be the numbers introduced by lemma
\ref{lemmazl}, so that the inequalities
$0<\Ex_o[\mathds{1}_{\{S_1\le\gamma
    t\}}\,e^{z_tS_1-\lambda_tg(S_1)}]\le 1$ and
$(z_t-\alpha\lambda_t)t\ge\xi_t+\ln|\xi_t|$ hold for all $t>t_1$ with
some $t_1>0$. The fact that $\lambda_t\ge 0$ allows us to invoke the
inequality $\mathds{1}_{\{\sum_{i=1}^ng(S_i)\le\alpha t\}}\le
e^{\alpha\lambda_t t-\lambda_t\sum_{i=1}^ng(S_i)}$ to obtain
\begin{align}
\nonumber
  \mathcal{E}_1(t)&\le e^{\alpha\lambda_tt}\sum_{n=1}^t\Ex_o\Bigg[\prod_{j=1}^n \mathds{1}_{\{S_j\le\gamma
      t\}}\,e^{-\lambda_tg(S_j)}\,\mathds{1}_{\{T_n=t\}}\Bigg]\\
  \nonumber
  &=e^{(\alpha \lambda_t-z_t)t}\sum_{n=1}^t\Ex_o\Bigg[\prod_{j=1}^n \mathds{1}_{\{S_j\le\gamma
      t\}}\,e^{z_tS_j-\lambda_tg(S_j)}\,\mathds{1}_{\{T_n=t\}}\Bigg]\\
  \nonumber
  &=e^{(\alpha \lambda_t-z_t)t}\sum_{n=1}^t\frac{\Ex_o\big[\prod_{j=1}^t \mathds{1}_{\{S_j\le\gamma
      t\}}\,e^{z_tS_j-\lambda_tg(S_j)}\,\mathds{1}_{\{T_n=t\}}\big]}{\Ex_o\big[\mathds{1}_{\{S_1\le\gamma
        t\}}\,e^{z_tS_1-\lambda_tg(S_1)}\big]^{t-n}}.
\end{align}
At this point, we make use of $\Ex_o[\mathds{1}_{\{S_1\le\gamma
    t\}}\,e^{z_tS_1-\lambda_tg(S_1)}]\le 1$ and
$(z_t-\alpha\lambda_t)t\ge\xi_t+\ln|\xi_t|$ to get for any $t>t_1$ at
the upper bound
\begin{align}
\nonumber
  \mathcal{E}_1(t)&\le e^{-\xi_t-\ln|\xi_t|}\sum_{n=1}^t\frac{\Ex_o\big[\prod_{j=1}^t \mathds{1}_{\{S_j\le\gamma
      t\}}\,e^{z_tS_j-\lambda_tg(S_j)}\,\mathds{1}_{\{T_n=t\}}\big]}{\Ex_o\big[\mathds{1}_{\{S_1\le\gamma
        t\}}\,e^{z_tS_1-\lambda_tg(S_1)}\big]^t}\\
  \nonumber
  &=\frac{t\,\mathcal{Q}(\gamma t)}{|\xi_t|}\,\frac{\Ex_o\big[\prod_{j=1}^t \mathds{1}_{\{S_j\le\gamma
      t\}}\,e^{z_tS_j-\lambda_tg(S_j)}\,U_t\big]}{\Ex_o\big[\mathds{1}_{\{S_1\le\gamma
        t\}}\,e^{z_tS_1-\lambda_tg(S_1)}\big]^t}\\
  &\le\frac{t\,\mathcal{Q}(\gamma t)}{|\xi_t|}\,\frac{\Ex_o\big[\prod_{j=1}^t \mathds{1}_{\{S_j\le\gamma
      t\}}\,e^{z_tS_j-\lambda_tg(S_j)}\big]}{\Ex_o\big[\mathds{1}_{\{S_1\le\gamma
        t\}}\,e^{z_tS_1-\lambda_tg(S_1)}\big]^t}=\frac{t\,\mathcal{Q}(\gamma t)}{|\xi_t|}.
\label{uuu1}
\end{align}
As far as $\mathcal{E}_2(t)$ is concerned, we let $\eta$ come into
play by writing for all $t\ge 2$
\begin{align}
\nonumber
\mathcal{E}_2(t)&=\sum_{n=1}^tn\,\Ex_o\Big[\mathds{1}_{\{\gamma t<S_n\le\eta t\}}\mathds{1}_{\{T_n=t\}}\Big]
+\sum_{n=1}^tn\,\Ex_o\Big[\mathds{1}_{\{S_n>\eta t\}}\mathds{1}_{\{T_n=t\}}\Big]\\
\nonumber
&= \sum_{n=2}^t(n-1)\,\Ex_o\Big[\mathds{1}_{\{\gamma t<S_n\le\eta t\}}\mathds{1}_{\{T_{n-1}+S_n=t\}}\Big]
+ \Ex_o\Big[\mathds{1}_{\{\gamma t<S_1\le\eta t\}}U_t\Big]+\Ex_o\Big[\mathds{1}_{\{S_1>\eta t\}}N_tU_t\Big]\\
\nonumber
&=\sum_{s=1}^{t-1}\sum_{n=1}^{t-s}n\,\Ex_o\big[\mathds{1}_{\{T_n=t-s\}}\big]\,\mathds{1}_{\{\gamma t<s\le\eta t\}}\,p_o(s)
+ \Ex_o\big[\mathds{1}_{\{\gamma t<S_1\le\eta t\}}U_t\big]+\Ex_o\big[\mathds{1}_{\{S_1>\eta t\}}N_tU_t\big]\\
\nonumber
&=\sum_{s\ge 1}\Ex_o\big[N_{t-s}U_{t-s}\big]\,\mathds{1}_{\{\gamma t<s\le\eta t\}}\,p_o(s)
+ \Ex_o\big[\mathds{1}_{\{\gamma t<S_1\le\eta t\}}U_t\big]+\Ex_o\big[\mathds{1}_{\{S_1>\eta t\}}N_tU_t\big].
\end{align}
We notice that $\Ex_o[\mathds{1}_{\{\gamma t<S_1\le\eta
    t\}}U_t]\le\Ex_o[\mathds{1}_{\{S_1>\gamma t\}}]=\mathcal{Q}(\gamma
t)$. We also observe that the condition $U_t=1$ implies $S_1\le t$, so
that $\Ex_o[\mathds{1}_{\{S_1>\eta
    t\}}N_tU_t]=\Ex_o[\mathds{1}_{\{\eta t<S_1\le t\}}N_tU_t]$ and
hence $\Ex_o[\mathds{1}_{\{S_1>\eta t\}}N_tU_t]\le
t\,\Ex_o[\mathds{1}_{\{\eta t<S_1\le t\}}]=t\,\mathcal{Q}(\eta
t)-t\,\mathcal{Q}(t)$. Finally, we recall that
$\lim_{\tau\uparrow\infty}\Ex_o[(N_\tau/\tau) U_\tau]=1/\Ex_o[S_1]^2$
by lemma \ref{lemmaux}, which entails that there exists $t_2\ge t_1$
with the property that $\Ex_o[N_\tau U_\tau]\le
(1+\epsilon)\tau/\Ex_o[S_1]^2$ for all $\tau>(1-\eta)t_2$.  This way,
since $t-s\ge(1-\eta)t$ when $s\le\eta t$, for every $t>t_2$ we get
the bound
\begin{align}
\nonumber
\mathcal{E}_2(t)&\le \frac{1+\epsilon}{\Ex_o[S_1]^2}\sum_{s\ge 1}(t-s)\,\mathds{1}_{\{\gamma t<s\le\eta t\}}\,p_o(s)
+\mathcal{Q}(\gamma t)+t\,\mathcal{Q}(\eta t)-t\,\mathcal{Q}(t)\\
\nonumber
&=\frac{1+\epsilon}{\Ex_o[S_1]^2}\bigg[(1-\gamma)\,t\,\mathcal{Q}(\gamma t)-(1-\eta)\,t\,\mathcal{Q}(\eta t)-t\int_\gamma^\eta\mathcal{Q}(xt)dx\bigg]\\
&+\mathcal{Q}(\gamma t)+t\,\mathcal{Q}(\eta t)-t\,\mathcal{Q}(t).
\label{uuu2}
\end{align}

In conclusion, by combining (\ref{auxu1}) with (\ref{uuu1}) and
(\ref{uuu2}) we obtain
\begin{align}
  \nonumber
  \mathcal{E}(t)&\le\frac{1+\epsilon}{\Ex_o[S_1]^2}\bigg[(1-\gamma)\,t\,\mathcal{Q}(\gamma t)-(1-\eta)\,t\,\mathcal{Q}(\eta t)
    -t\int_\gamma^\eta\mathcal{Q}(xt)dx\bigg]\\
\nonumber
  &+\mathcal{Q}(\gamma t)+\frac{t\,\mathcal{Q}(\gamma t)}{|\xi_t|}+t\,\mathcal{Q}(\eta t)-t\,\mathcal{Q}(t)
\end{align}
for all $t>t_2$. Recalling that the limit
$\lim_{t\uparrow\infty}\mathcal{Q}(xt)/\mathcal{Q}(t)=x^{-\kappa}$ is
uniform with respect to $x$ in the compact interval $[\gamma,\eta]$
and that $\lim_{t\uparrow\infty}\xi_t=+\infty$, (\ref{primau}) follows
from here by dividing by $t\,\mathcal{Q}(t)$ first and by sending $t$
to infinity later.

\section*{Acknowledgments}
The author is grateful to Giambattista Giacomin for a critical reading
of the manuscript and valuable comments.

\appendix

\section{Proof of lemma \ref{lemmaQtail}}
\label{appendix1}

If $\mathcal{L}$ varies slowly and
\begin{equation}
\lim_{x\uparrow+\infty}\frac{\mathcal{Q}(x)}{x^{-\kappa}\mathcal{L}(x)}=\frac{1}{\kappa},
\label{A1}
\end{equation}
then $\mathcal{Q}$ varies regularly with index $-\kappa$.

Let us demonstrate the limit (\ref{A1}).  Pick two real numbers
$\delta\in(0,\kappa)$ and $K>1$ and observe that there exists $x_o>1$
such that $(x/y)^\delta\mathcal{L}(x)/K\le \mathcal{L}(y)\le
K(x/y)^{-\delta}\mathcal{L}(x)$ when $x_o\le x\le y$ (see \cite{RV},
theorem 1.5.6). Recalling that $p_o(s)=s^{-\kappa-1}\mathcal{L}(s)$,
it follows that $x^\delta\mathcal{L}(x) s^{-\kappa-\delta-1}/K\le
p_o(s)\le K x^{-\delta}\mathcal{L}(x)s^{-\kappa+\delta-1}$ if $x_o\le
x<s$. The upper bound gives for $x\ge x_o>1$
\begin{equation*}
  \mathcal{Q}(x)=\sum_{s\ge 1}\mathds{1}_{\{s>x\}}p_o(s)\le \sum_{s\ge 1}\mathds{1}_{\{s>x\}}K x^{-\delta}\mathcal{L}(x)s^{-\kappa+\delta-1}
\le\frac{K}{\kappa-\delta}\frac{x^{-\delta}}{(x-1)^{\kappa-\delta}}\mathcal{L}(x),
\end{equation*}
where the inequality
$(\kappa-\delta)s^{-\kappa+\delta-1}\le(s-1)^{-\kappa+\delta}-s^{-\kappa+\delta}$
valid for all $s>1$ has been used to change the second series with a
telescoping series. Similarly, the lower bound and the inequality
$s^{-\kappa-\delta}-(s+1)^{-\kappa-\delta}\le(\kappa+\delta)s^{-\kappa-\delta-1}$
valid for all $s\ge 1$ yield for $x\ge x_o$
\begin{equation*}
  \mathcal{Q}(x)\ge \sum_{s\ge 1}\mathds{1}_{\{s>x\}}x^\delta\mathcal{L}(x) s^{-\kappa-\delta-1}/K\
\ge\frac{1}{K(\kappa+\delta)}x^{-\kappa}\mathcal{L}(x).
\end{equation*}
This way, we find
\begin{equation*}
  \frac{1}{K(\kappa+\delta)}\le \liminf_{x\uparrow+\infty}\frac{\mathcal{Q}(x)}{x^{-\kappa}\mathcal{L}(x)}
  \le \limsup_{x\uparrow+\infty}\frac{\mathcal{Q}(x)}{x^{-\kappa}\mathcal{L}(x)}\le\frac{K}{\kappa-\delta}
\end{equation*}
and (\ref{A1}) follows from here by sending $\delta$ to 0 and $K$ to
1.

\section{Proof of lemma \ref{lemmaux}}
\label{appendix2}

Recall that $N_t$ is the cumulative reward corresponding to a function
$f$ identically equal to 1.  Since $0\le N_t/t\le 1$ and
$0<1/\Ex_o[S_1]<1$, for any $t\ge 1$ and $\delta>0$ we can write
\begin{align}
  \nonumber
  \Bigg|\Ex_o\bigg[\bigg(\frac{N_t}{t}-\frac{1}{\Ex_o[S_1]}\bigg)U_t\bigg]\Bigg|&\le
  \delta\,\Ex_o\bigg[\mathds{1}_{\big\{\big|\frac{N_t}{t}-\frac{1}{\Ex_o[S_1]}\big|<\delta\big\}}U_t\bigg]
  +2\,\Ex_o\bigg[\mathds{1}_{\big\{\big|\frac{N_t}{t}-\frac{1}{\Ex_o[S_1]}\big|\ge\delta\big\}}U_t\bigg]\\
  \nonumber
  &\le\delta+2\,\probab_t^c\bigg[\bigg|\frac{N_t}{t}-\frac{1}{\Ex_o[S_1]}\bigg|\ge\delta\bigg],
\end{align}
where the second bound is obtained by applying formula (\ref{mod2}) to
$N_t$. From here, we get at the proof of the lemma by combining the
limit $\lim_{t\uparrow\infty}\Ex_o[U_t]=1/\Ex_o[S_1]$ with the
convergence in probability stated by proposition \ref{conv}.

\section{Proof of lemma \ref{lemmazl}}
\label{appendix3}

Recall that $\xi_t:=-\ln t\,\mathcal{Q}(\gamma t)$ and for every $t\ge
1$ set
\begin{equation*}
\lambda_t:=\frac{(1-\gamma)\xi_t-4\kappa\ln|\xi_t|}{\gamma(1-\gamma)\,t}
\end{equation*}
and
\begin{equation*}
z_t:=\alpha\lambda_t+\frac{\xi_t+\ln|\xi_t|}{t}.
\end{equation*}

It is manifest that $(z_t-\alpha\lambda_t)t\ge\xi_t+\ln|\xi_t|$ for
each $t$ and, since $\xi_t$ goes to infinity when $t$ is sent to
infinity, there exists a positive integer $\tau_1$ such that $\xi_t>1$
and the real numbers $\lambda_t$ and $z_t$ are positive for any
$t>\tau_1$. We prove the lemma by showing that for all sufficiently
large $t>\tau_1$
\begin{equation}
\label{lemmazl_1}
  \sum_{s\ge 1}\mathds{1}_{\{s\le\gamma t/\xi_t^2\}}\,e^{z_ts-\lambda_tg(s)}\,p_o(s)\le 1-\frac{2}{t}
\end{equation}
and
\begin{equation}
  \label{lemmazl_2}
\sum_{s\ge 1}\mathds{1}_{\{\gamma t/\xi_t^2<s\le\gamma t\}}\,e^{z_ts-\lambda_tg(s)}\,p_o(s)\le\frac{2}{t}.
\end{equation}
We point out that $\lim_{t\uparrow\infty}\gamma t/\xi_t^2=+\infty$
since $\mathcal{Q}(x)\ge x^{-\kappa-\delta}$ for any $\delta>0$ and
all sufficiently large $x$ as $\mathcal{Q}$ varies regularly with
index $-\kappa$ (see \cite{RV}, proposition 1.3.6).

Let us verify (\ref{lemmazl_1}) at first. Let $M<+\infty$ be a
positive constant such that $|g(s)|\le Ms$ for all $s$, which
certainly exists because $\lim_{s\uparrow\infty}g(s)/s=0$. Then, let
$K<+\infty$ be a positive constant such that
$\gamma(tz_t+Mt\lambda_t)^2\xi_t^{-2}e^{\gamma(tz_t+Mt\lambda_t)\xi_t^{-2}}\le
K$ for all $t>\tau_1$, which exists because
$\lim_{t\uparrow\infty}\gamma(tz_t+Mt\lambda_t)^2\xi_t^{-2}e^{\gamma(tz_t+Mt\lambda_t)\xi_t^{-2}}=\gamma^{-1}(\alpha+\gamma+M)^2$.
Finally, let $\tau_2\ge\tau_1$ be an integer such that $z_ts-\lambda_t
g(s)\ge 0$ for all $t>\tau_2$ and $s>\gamma t/\xi_t^2$, which exists
because $\lim_{t\uparrow\infty}z_t/\lambda_t=\alpha+\gamma>0$,
$\lim_{s\uparrow\infty}g(s)/s=0$, and $\lim_{t\uparrow\infty}\gamma
t/\xi_t^2=+\infty$. Pick $t>\tau_2$. The bound $e^y\le 1+y+y^2e^{|y|}$
valid for all $y\in\Rl$ yields for any $s\le\gamma t/\xi_t^2$
\begin{align}
\nonumber
  e^{z_ts-\lambda_tg(s)}&\le 1+z_ts-\lambda_tg(s)+(z_t+M\lambda_t)^2s^2 e^{(z_t+M\lambda_t)s}\\
  \nonumber
  &\le 1+z_ts-\lambda_tg(s)+\frac{\gamma}{t}\bigg(\frac{tz_t+Mt\lambda_t}{\xi_t}\bigg)^2s\,e^{\gamma\frac{tz_t+Mt\lambda_t}{\xi_t^2}}\\
  \nonumber
  &\le 1+z_ts-\lambda_tg(s)+\frac{K}{t}s.
\end{align}
This bound, in combination with the facts that $z_ts-\lambda_tg(s)\ge
0$ for $s>\gamma t/\xi_t^2$ and that $\Ex_o[g(S_1)]=\Ex_o[S_1]$, gives
\begin{align}
\nonumber
\sum_{s\ge 1}\,\mathds{1}_{\{s\le\gamma t/\xi_t^2\}}\,e^{z_ts-\lambda_tg(s)}\,p_o(s)
&\le 1+\sum_{s\ge 1}\mathds{1}_{\{s\le\gamma t/\xi_t^2\}}\,\big[z_ts-\lambda_tg(s)\big]\,p_o(s)
+\frac{K}{t}\Ex_o[S_1]\\
\nonumber
&\le 1+\Ex_o[S_1]\Bigg\{\frac{tz_t-t\lambda_t}{\xi_t}+\frac{K}{\xi_t}+\frac{2}{\Ex_o[S_1]\xi_t}\Bigg\}\frac{\xi_t}{t}-\frac{2}{t}.
\end{align}
The term between braces goes to $-(1-\alpha-\gamma)/\gamma<0$ when $t$
is sent to infinity, so that it is non-positive for all $t$ larger
than some $\tau_3\ge\tau_2$. It follows that (\ref{lemmazl_1}) holds
for all $t>\tau_3$.

Let us now prove (\ref{lemmazl_2}). To begin with, we observe that for
any $\delta>0$ and $K>1$ there exists $x_o>0$ such that
$y^{\kappa+\delta}\mathcal{Q}(y)\le
K\,x^{\kappa+\delta}\mathcal{Q}(x)$ if $x_o\le y\le x$ (see \cite{RV},
theorem 1.5.6). Thus, taking $\delta=\kappa-\gamma/2$ and $K=2$,
$\delta$ being positive because $\kappa\ge 1$ and $\gamma<1-\alpha$ by
hypothesis, the fact that $\lim_{t\uparrow\infty}\gamma
t/\xi_t^2=+\infty$ implies that an integer $\tau_4\ge\tau_3$ can be
found in such a way that $\mathcal{Q}(\gamma t/\xi_t^2)\le
2\,\xi_t^{4\kappa-\gamma}\mathcal{Q}(\gamma t)$ for all
$t>\tau_4$. Then, since $1-\alpha-\gamma>0$, the limit
$\lim_{s\uparrow\infty}g(s)/s=0$ ensures us that there exists an
integer $\tau_5\ge\tau_4$ with the property that
$g(s)\ge-(1-\alpha-\gamma)s$ for all $s>\gamma t/\xi_t^2$ whenever
$t>\tau_5$. This way, for every $t>\tau_5$ we find the bound
\begin{align}
\nonumber
\sum_{s\ge 1}\mathds{1}_{\{\gamma t/\xi_t^2<s\le\gamma t\}}\,e^{z_ts-\lambda_tg(s)}\,p_o(s)&\le
e^{[z_t+(1-\alpha-\gamma)\lambda_t]\gamma t}\,\mathcal{Q}(\gamma t/\xi_t^2)\\
\nonumber
&=\xi_t^{\gamma-4\kappa}e^{\xi_t}\,\mathcal{Q}(\gamma t/\xi_t^2)=\frac{\xi_t^{\gamma-4\kappa}}{t}\,\frac{\mathcal{Q}(\gamma t/\xi_t^2)}{\mathcal{Q}(\gamma t)}
\le \frac{2}{t}.
\end{align}
In conclusion, we have that both (\ref{lemmazl_1}) and
(\ref{lemmazl_2}) are satisfied if $t>\tau_5$.


TITLE: Help with a proof that $\lim_{x \to 0} \frac{a^x-1}{x}$ exists
QUESTION [1 upvotes]: I have found that proof
"Let $\underline{a>1}.$ I assume $a^x$ is continuous, and that the basic exponent law $a^{x+y}=a^xa^y$ holds.
Claim: $a^x$ is convex on $[0,\infty).$ Proof: Because $a^x$ is continuous, it suffices to show $a^x$ is midpoint convex. Suppose $x,y\in [0,\infty).$ Using $(uv)^{1/2} \le (u+v)/2$ for nonnegative $u,v,$ we get $a^{(x+y)/2} = (a^{x} a^{y})^{1/2} \le (a^x+a^y)/2.$
Now if $f$ is convex on $[0,\infty),$ then $(f(x)-f(0))/x$ is an increasing function of $x$ for $x\in(0,\infty).$ This is a simple and easily proved property of convex functions.
Claim: $\lim_{x\to 0^+}(a^x-1)/x$ exists. Proof: All of these quotients are bounded below by $0.$ As $x$ decreases to $0,(a^x-1)/x$ decreases by the above. Because of the lower bound of $0,$ the limit exists.
It follows that $\lim_{x\to 0}(a^x-1)/x$ exists. This follows from the above and the fact that if $x>0,$ then  $a^{-x} = 1/a^{x}.$ To handle $0<a<1,$ look at $[(1/a)^x-1]/x$ to see $\lim_{x\to 0}(a^x-1)/x$ exists."
source: zhw, Show $\lim_{h\to 0} \frac{(a^h-1)}{h}$ exists without l'Hôpital or even referencing $e$ or natural log, URL (version: 2017-02-18)
Can someone please explain to me why in the first part a>1 is of relevance.
My second question is how can I use the last sentence to see that the special case delivers everything I want to have?

REPLY [1 votes]: you need $a >1$ for this part:

Proof: All of these quotients are bounded below by 0.

For the last sequence:
Note:
$$\lim_{h \to 0^-} \frac{a^h-1}{h}=-\lim_{t \to 0^+} \frac{a^{-t}-1}{t}=-\lim_{t \to 0^+} \frac{1-a^t}{t}\frac{1}{a^t}=\lim_{t \to 0^+} \frac{a^t-1}{t}\frac{1}{a^t}$$
Finaly, if $a<1$ write $a=\frac{1}{b}$. Then $b>1$ and
$$\lim_{h \to 0} \frac{b^h-1}{h}=-\lim_{h \to 0} \frac{b^t-1}{t}\frac{1}{b^t}$$


TITLE: Simplify an expression with a root $ \frac{\sqrt{-x+2}}{\sqrt{x-1}}$
QUESTION [2 upvotes]: Simplify an expression with a root
I don't understand a transformation.
For this, $f_n= \frac{n}{2}l_n\sqrt{1-l_n^2/4}$
And now I'd like to show that
$\frac{1}{1-l_{2n}^2/4}f_{2n}=\frac{2}{1+\sqrt{1-l_n^2/4}}\cdot\frac{n}{2}l_n$
holds
Can anyone help me?
According to my calculations
$f_{2n}=\frac{2n}{2}l_{2n}\sqrt{1-l_{2n}^{2}/4}$ and then
$\frac{1}{1-l_{2n}^2/4}\frac{2n}{2}l_{2n}\sqrt{1-l_{2n}^2/4}=n\frac{l_{2n}\sqrt{1-l_{2n}^2/4}}{1-l_{2n}^2/4}=n\cdot l_{2n}\cdot \frac{1}{\sqrt{1-l_{2n}^2/4}}=\frac{n}{2}\cdot l_{2n}\cdot \frac{2}{\sqrt{1-l_{2n}^2/4}}$
Also we have
$l_{2n}^2=l_n^2/4+\big(1-\sqrt{1-l_n^2/4}\big)^2=2\big(1-\sqrt{1-l_n^2/4}\big)$
So I substituted the expression $l_{2n}$, but I can't prove the desired formula.
After putting in $n\cdot l_{2n}\cdot \frac{1}{\sqrt{1-l_{2n}^2/4}}$ I got
$n\sqrt{2\big(1-\sqrt{1-l_n^2/4}\big)}\cdot \frac{1}{\sqrt{1-(2\big(1-\sqrt{1-l_n^2/4}\big))/4}}=n\frac{\sqrt{2\big(1-\sqrt{1-l_n^2/4}\big)}}=n\frac{\sqrt{2\big(1-\sqrt{1-l_n^2/4}\big)\sqrt{1-l_n^2/4}\big)}}{\sqrt{2\sqrt{1-l_n^2/4}-1}}=n\frac{\sqrt{-2\sqrt{1-l_n^2/4}+2}}{\sqrt{2\sqrt{1-l_n^2/4}-1}}$
Now I don't know how I can further simplify the Expression.

REPLY [1 votes]: Nothing will be changed if you bring both the numerator and denominator under a single radical and bring the twos inside the radical to obtain
$$ n\sqrt{\frac{2-\sqrt{4-l_n^2}}{\sqrt{{4-l_n^2}}-1}} $$
Then the fraction under the radical can be rationalized.
$$ n\sqrt{\frac{2-\sqrt{4-l_n^2}}{\sqrt{{4-l_n^2}}-1}\cdot\frac{\sqrt{{4-l_n^2}}+1}{\sqrt{{4-l_n^2}}+1}}=n\sqrt{\frac{l_n^2-2+\sqrt{4-l_n^2}}{3-l_n^2}} $$
Although you could rationalize the denominator, I would not take it any further.


TITLE: Martingale recursively defined on uniform random-variable
QUESTION [1 upvotes]: I am trying to solve the following exercise on martingale:
Let $X_n$ be the recursive process defined as follows:
$X_0 \sim \mathcal{U}([-1,+1]), X_n = \sim \mathcal{U}([-|X_{n-1}|,+|X_{n-1}|])$
is the process a martingale?
Honestly I think it is a martingale, but how do I compute
$E(X_{n+1}|\mathcal{F}_n) = E[\mathcal{U}([-|X_{n}|,+|X_{n}|])|\mathcal{F}_n]$?
$X_{n+1}$ should take any value in the interval $[-|X_n|,+|X_n|]$ with probability $\sim \frac{1}{2|X_n|}$ , but I wouldn't Know how to compute the conditional expectation in this case, what is the proper way to formalize this?

REPLY [1 votes]: $\newcommand{\E}{\mathbb E}\newcommand{\F}{\mathcal F}$It is not a martingale. We prove it by contradiction, asssume it is a martingale. I assume $\F_n = \sigma(X_1,...,X_n)$. Then one has:
\begin{align*}\tag{1}
\E[X_{n+1} \mid \F_n ] =X_n
\end{align*}
Notice that $\sigma(X_n)\subset \F_n$, so:
\begin{align}
\E[\E[X_{n+1}\mid \F_n ] \mid X_n]= \E[X_{n+1}\mid X_n]=0
\end{align}
Since the "smaller $\sigma$-algebra wins". Moreover: $$\E[X_n\mid X_n ] =X_n$$ Now condition on $\sigma(X_n)$ on both sides of $(1)$ to get:
\begin{align}
0 = X_n \ \ \text{ a.s.}
\end{align}
This is clearly wrong, hence a contradiction.