text:
# Long-range antiferromagnetic order in the S=1 chain compound LiVGe2O6

\[

## Abstract

The phase transition in the compound LiVGe2O6 has been proposed as a unique example of a spin-Peierls transition in an S=1 antiferromagnetic chain. We report neutron and x-ray diffraction measurements of LiVGe2O6 above and below the phase transition at T=24 K. No evidence is seen for any structural distortion associated with the transition. The neutron results indicate that the low temperature state is antiferromagnetic, driven by ferromagnetic interchain couplings.

\]

The physics of one-dimensional (1D) spin systems has been a field of considerable theoretical and experimental interest in recent years. The enhanced importance of quantum fluctuations in these systems manifests itself in many exotic phenomena, two of which are the Haldane gap in integer spin chains and the spin-Peierls transition in 1D half-integer spin systems. Haldane predicted in 1983 , based on field-theoretical models, that Heisenberg, antiferromagnetic (AF), integer spin chains possess a spectrum of magnetic excitations in which lowest lying excited states are separated by a finite energy gap from the ground state. This remarkable result contrasts the half-integer case where the excitation spectrum is gapless. However, in the presence of magnetoelastic coupling, the energy of 1D, AF, half-integer spin systems can be lowered by a dimerization of the uniform chains. The resulting alternating spin chains possess a gapped magnetic excitation spectrum separating a singlet ground state from the triplet of excited states. This structural phase transition, driven by gains in magnetic energy, from the uniform to dimerized spin chain is known as the spin-Peierls transition .

Experimentally, the Haldane gap has been observed in numerous S=1 chain systems including CsNiCl3 , AgVP2S6 , YBaNiO5 , Ni(C2H8N2)2NO2ClO4  and Ni(C3H10N2)2N3ClO4 . The spin-Peierls transition has fewer experimental realizations most of which are organic, such as Cu(Au)BDT  and MEM(TCNQ)2  with the only known inorganic example being CuGeO3 . Recently, results were published on a new S=1, chain material LiVGe2O6  which were interpreted as being a remarkable union of these two, seemingly unrelated, phenomena. Powder susceptibility measurements showed a rapid decrease on passing through a transition temperature of about 22 K reminiscent of the isotropic decrease in magnetization, associated with the opening of a singlet-triplet gap in the excitation spectrum, which accompanies a spin-Peierls transition . However, the pre-existing gapped excitation spectrum normally precludes the possibility of a spin-Peierls phase transition in integer spin chain systems. It was suggested  that the Haldane gap was closed in LiVGe2O6 due to a novel, anomalously large biquadratic exchange interaction and this now gapless integer spin chain system undergoes a spin-Peierls phase transition at T=22 K .

However, very recent 7Li nuclear magnetic resonance (NMR)  experiments produced results which seemed to contradict this interpretation. These measurements indicated that the observed phase transition was not a spin-Peierls transition and that the low temperature phase was antiferromagnetic in nature. Their results are also interpreted as being consistent with a discontinuous phase transition. In addition, these measurements suggest unusual behavior in the ordered phase including a gapped excitation spectrum with a gap $`\mathrm{\Delta }`$/$`k_B`$=83 K , roughly twice the observed coupling constant J/$`k_B`$$``$45 K , despite an anisotropy D/$`k_B`$ of less than 20 K . The authors of this  and a recent theory paper  discuss possible mechanisms for the low-temperature properties of LiVGe2O6 resulting from splitting of the three $`t_{2g}`$ orbitals which accomodate the two V3+ electrons. This splitting results from a small trigonal distortion  and separates the $`d_{xz}`$ orbital from the low-lying dxy, dyz doublet. Two scenarios are suggested, the first of which leads to a reduced intrachain coupling and subsequent enhancement of biquadratic and next near-neighbor interactions . The second scenario leads to increased importance of orbital degrees of freedom  and possible orbital ordering. However, until now, the precise nature of the ordered state was unclear.

To elucidate the nature of the low-temperature ordered state, we have performed temperature dependent neutron diffraction studies, and complimentary x-ray diffraction studies, above and below the transition temperature. These measurements indicate a commensurate, antiferromagnetic, long-range ordered low-temperature phase and provide no evidence for a structural distortion associated with the transition.

LiVGe2O6 crystallizes in a monoclinic unit cell with space group P21/c and room temperature lattice constants a=9.863(4) Å, b=8.763(2) Å, c=5.409 Å, and $`\beta `$=108.21(1) . The structure is composed of chains of edge sharing VO6 octahedra which are connected by GeO4 tetrahedra. Previous measurements  have indicated that the V-ions exist in a 3+ oxidation state with an effective S=1 magnetic moment.

Polycrystalline samples of LiVGe2O6 were prepared using a slightly different method than reported by Millet $`et`$ $`al`$.. Stoichiometric quantities of GeO2, Li2O, V2O5, and V metal were sealed in evacuated Pt tubes and heated for 2 days at 900 C. The samples were single phase according to powder x-ray diffraction. To reproduce the magnetization results reported previously, a small amount of powder was loaded in a Quantum Design SQUID magnetometer and the DC magnetization was measured as a function of temperature in an applied magnetic field of 2.5 kOe; the magnetization varied linearly with H for fields up to 65 kOe . The results are shown in Fig. 1(a) for temperatures up to 50 K and clearly demonstrate the same rapid decrease in magnetization, below a transition temperature of about 24 K, reported previously . The Curie tail below 10 K corresponds to less than 40 ppm of 3d impurity content. In addition, specific heat measurements were performed on a 13.7 mg cold-pressed pellet of LiVGe2O6 using a commercial heat-pulse, Quantum design calorimeter, the results of which are shown in Fig. 1(b). These results show a clear phase transition at a temperature of about 24 K, consistent with the magnetization results.

For the neutron diffraction measurements, approximately 10g of LiVGe2O6 powder was loaded in an aluminum sample can in the presence of He exchange gas and attached to the cold finger of a closed-cycle He refrigerator. The neutron diffraction measurements were performed on the HB1 triple-axis spectrometer at the High Flux Isotope Reactor, Oak Ridge National Laboratory. Neutrons of wavelength 2.44 Å were selected using a pyrolitic graphite (PG) (002) monochromator crystal and elastically scattered neutrons were measured using a second PG (002) analyzer crystal. To prevent higher-order contamination, a graphite filter was placed in the incident beam. The intensity of diffracted neutrons was measured for scattering angles between 5 and 100 for temperatures of 50 K and 11 K, well above and below the transition temperature, respectively.

The 50 K data was refined using Rietveld analysis and the observed pattern was found to be consistent with the previously determined crystal structure  with low temperature lattice constants of a=9.800 Å, b=8.709 Å, c=5.364 Å, and $`\beta `$=108.21.

A portion of the resulting diffraction pattern is shown in the two upper panels of Fig. 2 for temperatures of 11 K and 50 K. We see clear, excess scattering at positions which can be described by Miller indices (110) and (001). These two reflections were the most pronounced but other, weaker reflections were seen at (111) and (220) positions with possible reflections at (-1-11) and (020). No additional scattering was observed for reflections with scattering angles in excess of about 50. This enhacement of the scattering at low angles is consistent with it being magnetic in origin.

To further confirm the magnetic nature of the scattering, the measurements were repeated using x-ray diffraction techniques. Approximately 2g of LiVGe2O6 powder was pressed into a pellet and loaded in a Be can in the presence of He exchange gas. This can was then connected to the cold finger of a closed-cycle He refrigerator and mounted in a Huber four-circle diffractometer. The incident radiation was Cu-Kα x-rays from an 18 kW rotating anode x-ray generator which were further monochromatized by Bragg reflection from a PG monochromator crystal. To allow comparison with the neutron diffraction results, the intensity of diffracted x-rays was measured for scattering angles between 5 and 70 at temperatures of 33 K and 11 K, again above and below the transition temperature. The resulting data in the vicinity of the (110) and (001) reflections is shown in the lower two panels of Fig. 2. Clearly, no additional scattering is seen on passing through the transition temperature and, in fact, no excess scattering was observed at any angle. This further confirms the magnetic nature of the excess scattering observed in the neutron diffraction experiment. This coupled with the resolution limited nature of the excess neutron intensity, indicates that the low temperature phase is, in fact, a long-range ordered, commensurate magnetic state.

The temperature dependence of the (110) and (001) magnetic Bragg reflections was measured from 11 K to about 40 K and the resulting data are shown in the upper panel of Fig. 3. For reference, we have plotted the temperature derivative of the molar susceptibility and replotted the specific heat data in the lower panel of Fig. 3. The excess neutron intensity clearly disappears on passing through the transition temperature indicating its association with the phase transiton. The temperature dependence can be well described by a power law in the reduced temperature suggestive of a continuous phase transition. In addition, no hysteresis has been observed in either the magnetization or the specific heat and, thus, in contrast to the NMR results , we conclude that the transition is continuous in nature. While we can rule out the possibility of the transition being strongly first-order in nature, it is impossible to rule out a weakly first order phase transition from the existing data.

Despite the small number of observed reflections, we have sufficient information to determine the spin arrangement in the ordered state. As all reflections can be indexed with integer indices, the magnetic unit cell is identical in size to the nuclear unit cell and, hence, contains four magnetic V3+ sites. The observed magnetic peak intensities, coupled with the absence of (100) and (010) reflections, are most consistent with the arrangment of spins shown in Fig. 4 where we have superimposed the spins on the known crystal structure. In comparing various magnetic structures, an analytical approximation for the V3+ magnetic form factor was employed . The observed spin structure has spins aligned antiferromagnetically along the chain direction with ferromagnetic alignment between neighboring chains suggestive of ferromagnetic interchain coupling. Unfortunately, the limited amount of data makes it impossible to uniquely determine the spin direction but the strength of the (001) reflection indicates a small spin component along that direction. By considering several plausible spin directions an ordered moment ($`\mu `$=g$`\mu _B`$$`<`$S$`>`$) of 1.14(8) $`\mu _B`$ was extracted. This is reduced from the expected value of 1.79 $`\mu _B`$ (for g=1.79  and $`<`$S$`>`$=1) and this difference is likely due to the importance of quantum fluctuations in the low-dimensional system. In fact, the observed ordered moment is similar to that seen in other Haldane chain systems which order magnetically: CsNiCl3 is found to possess an ordered moment of 1.05 $`\mu _B`$  and the set of systems RBaNiO5, which if R $``$ Y order magnetically, display an ordered moment of about 1.1 $`\mu _B`$ .

The observed ordering in LiVGe2O6 is very simple and, as mentioned above, exhibits properties consistent with other Haldane chain systems which order magnetically due to significant interchain couplings. These interchain interactions are the likely cause of the phase transition in LiVGe2O6 and the parallel alignment of neighboring spin chains suggests that they are ferromagnetic in nature. The strength of the interchain coupling is estimated, using the Ginzberg-Landau theory of Scalapino, Imry, and Pinkus , to be $`J_{}`$ $``$ 1.4 K (assuming $`J_{}`$=45 K, four neighboring chains, and $`T_N`$=24 K). These interchain interactions suggest that LiVGe2O6 is a quasi-1D system with $`J_{}/J_{}`$ $``$ 0.03 (it is important to note that this this mean-field calculation results in an underestimated value of $`J_{}`$). This ratio of interchain to intrachain coupling may be slightly larger than expected given the 1D nature of the crystal structure, but is very similar to that observed in the quasi-1D Haldane system CsNiCl3  and certainly seems feasibile. Clearly, both quantum chemistry calculations and further experiments are needed to investigate the actual magnitude of the interchain couplings in LiVGe2O6.

We cannot rule out more exotic mechanisms for the ordering in this system and if the transition is discontinuous, as suggested by NMR studies, a simple ordering mediated by interchain coupling may be unlikely. However, of the theoretical ideas postulated to date, the notion of weakened intrachain coupling resulting from crystal-field splitting is particularly intriguing . Perhaps, in addition to enhancing novel interactions such as next near-neighbor coupling or biquadratic exchange , this reduction of intrachain coupling also increases the relative strength of the interchain interactions leading to a rather conventional ordering phase transition. In other words, the weakened intrachain interaction makes the system less one-dimensional. The mechanism involved in this phase transition clearly deserves further study and several properties, such as the large magnetic gap observed in the low temperature phase  remain unexplained.

In summary, we have performed neutron diffraction, and complimentary x-ray diffraction, measurements on LiVGe2O6 and see clear evidence for simple, commensurate long-range antiferromagnetic order below a temperature of 24 K. In addition, we see no evidence for structural changes at this temperature. These results contradict the complicated picture of a S=1 spin-Peierls system originally proposed  and seems to indicate surprisingly large interchain interactions.

We acknowledge fruitful discussions with D.A. Tennant, I. Affleck, and E. Sørenson. Oak Ridge National Laboratory is managed by UT-Battelle, LLC, for the U.S. Dept. of Energy under contract DE-AC05-00OR22725.


format: text

text:
# Correlation structure of extreme stock returns

## 1 Introduction

Understanding the relationship between the statistics of individual stock returns and that of the corresponding index is a major issue in several finance problems such as risk management  or market micro-structure modeling. It is also crucial for building optimized portfolios containing both index and stocks derivatives . Although the index return is the (weighted) sum of stock returns, it actually displays very different statistical properties from what would result if the stock returns were independent. In particular, the cumulants (that is, the volatility, the skewness and the kurtosis) of the index distribution, which should be suppressed by a power of the number of stocks $`N`$ for independent returns, are still very large, even for $`N=500`$. The negative skewness of the index, in particular, is actually larger than for individual stocks, and reflects a specific leverage effect .

It is a common belief that cross-correlations between stocks actually fluctuate in time, and increase substantially in a period of high market volatility. This has been discussed in many papers – see for example , with more recent discussions, including new indicators, in . Furthermore, this increase is thought to be larger for large downward moves than for large upward moves. The dynamics of these correlations themselves, and their asymmetry, should be estimated, leading to rather complex models . The view of ‘moving’ correlations has a direct consequence for risk management: the risk for a given portfolio is seen as resulting from both volatility fluctuations and correlation fluctuations.

An alternative point of view is provided by factor models with a fixed correlation structure. The simplest version contains a unique factor – the market itself. In this case, the time fluctuations of the measured cross-correlations between stocks is, as we show below, directly related to the fluctuations of the market volatility. The notion of “correlation” risk therefore reduces to market volatility risk, which considerably simplifies the problem. In this paper, we want to address to what extent a non-Gaussian one-factor model is able to capture the essential features of stocks cross-correlations, in particular in extreme market conditions. Our conclusion is that most of the extreme risk correlations, measured by different indicators, are actually captured by this simple fixed-correlation model. This model is able to reproduce quantitatively the observed exceedance correlations  without invoking the idea of ‘regime switching’ recently advocated in this context in .

However, a more detailed analysis shows that a refined model is needed to account for the dependence of the conditional volatility and skewness of the residuals on the market return.

## 2 A non-Gaussian one-factor model

We want to compare empirical measures of correlation with the prediction of a fixed-correlation model. However, for generic non-Gaussian probability distributions of returns, there is no unique way of building a multivariate process. A natural choice is to assume that the return of every stock is the sum of random independent (non-Gaussian) factors. While a multivariate Gaussian process can always be decomposed into independent factors, this is not true for generic non-Gaussian distributions. The existence of such a decomposition is thus part of the definition of our model.

### The model:

We will call market the dominant factor in this decomposition and write:

$$r_i(t)=\beta _ir_m(t)+ϵ_i(t).$$
(1)
The daily return is defined as $`r_i(t)=S_i(t)/S_i(t1)1`$, where $`S_i(t)`$ is the value of the stock $`i`$ on day $`t`$. The return is thus decomposed into a market part $`r_m(t)`$ and a residual part $`ϵ_i(t)`$. In a generic factor model, the residuals $`ϵ_i(t)`$ are combinations of all the factors except the market and are therefore independent of it. The one-factor model corresponds to the simple case where the $`ϵ_i(t)`$ are also independent of one another.

The market is defined as a weighted sum of the returns of all stocks. The weights can be those of a market index such as the S&P 500. These could also be the components of the eigenvector with the largest eigenvalue of the stocks cross-correlation matrix . We have chosen to work simply with uniform weights, leading to the following definition:

$$r_m=\frac{1}{N}\underset{i=1}{\overset{N}{}}r_i.$$
(2)
Had we chosen another weighting scheme for the definition of the market, the theoretical results below would still hold exactly provided that we replace averages over all stocks by the corresponding weighted averages. On our data set, the different weighted averages give essentially the same results. The coefficients $`\beta _i`$’s are then given by:

$$\beta _i=\frac{r_ir_mr_ir_m}{r_m^2r_m^2},$$
(3)
where the brackets refer to time averages. This model is meaningful in the case where $`\beta _i`$ is constant or slowly varying in time. Eq. (2) immediately implies $`(1/N)_{i=1}^N\beta _i=1`$.

An important qualitative assumption of this model is that although the market is built from the fluctuations of the stocks, it is a more fundamental quantity than the stocks themselves. Hence, one cannot expect to explain the statistical properties of the market from those of the stocks within this model.

### Real data and surrogate data:

The data set we considered is composed of the daily returns of 450 U.S. equities among the most liquid ones from 1993 up to 1999. In order to test the validity of a one-factor model, we also generated surrogate data compatible with this model. Very importantly, the one-factor model we consider is not based on Gaussian distributions, but rather on fat-tailed distributions that match the empirical observations for both the market and the stocks daily returns .

The procedure we used to generate the surrogate data is the following:

* Compute the $`\beta _i`$’s using Eq. (3) over the whole time period . These $`\beta _i`$’s are found to be rather narrowly distributed around $`1`$, with $`(1/N)_{i=1}^N\beta _i^2=1.05`$.
* Compute the variance of the residuals $`\sigma _{ϵ_i}^2=\sigma _i^2\beta _i^2\sigma _m^2`$. On the dataset we used $`\sigma _m`$ was 0.91% (per day) whereas the rms $`\sigma _{ϵ_i}`$ was 1.66%.
* Generate the residual $`ϵ_i(t)=\sigma _{ϵ_i}u_i(t)`$, where the $`u_i(t)`$ are independent random variables of unit variance with a leptokurtic (fat tailed) distribution — we have chosen here a Student distribution with an exponent $`\mu =4`$:

$$P(u)=\frac{3}{(2+u^2)^{5/2}},$$
(4)
which is known to represent adequately the empirical data .
* Compute the surrogate return as $`r_i^{\text{surr}}(t)=\beta _ir_m(t)+ϵ_i(t)`$, where $`r_m(t)`$ is the true market return at day $`t`$.

Therefore, within this method, both the empirical and surrogate returns are based on the very same realization of the market statistics. This allows us to compare meaningfully the results of the surrogate model with real data, without further averaging. It also short-cuts the precise parameterization of the distribution of market returns, in particular its correct negative skewness, which turns out to be crucial.

## 3 Conditioning on large returns

### Conditioning on absolute market return:

We have first studied a measure of correlations between stocks conditioned on an extreme market return. It is indeed commonly believed that cross-correlations between stocks increase in such “high-volatility” periods. A natural measure is given by the following coefficient:

$$\rho _>(\lambda )=\frac{\frac{1}{N^2}_{i,j}\left(r_ir_j_{>\lambda }r_i_{>\lambda }r_j_{>\lambda }\right)}{\frac{1}{N}_i\left(r_i^2_{>\lambda }r_i_{>\lambda }^2\right)},$$
(5)
where the subscript $`>\lambda `$ indicates that the averaging is restricted to market returns $`r_m`$ in absolute value larger than $`\lambda `$. For $`\lambda =0`$ the conditioning disappears. Note that the quantity $`\rho _>`$ is the average covariance divided by the average variance, and therefore differs from the average correlation coefficient. We have studied the latter quantity, and the following conclusions remain valid in this case also.

In a first approximation, the distribution of individual stocks returns can be taken to be symmetrical, leading $`r_i_{>\lambda }0`$. The above equation can therefore be transformed into:

$$\rho _>(\lambda )\frac{\sigma _m^2(\lambda )}{\frac{1}{N}_{i=1}^N\sigma _i^2(\lambda )},$$
(6)
where $`\sigma _m^2(\lambda )`$ is the market volatility conditioned to market returns in absolute value larger than $`\lambda `$, and $`\sigma _i^2(\lambda )=r_i^2_{>\lambda }r_i_{>\lambda }^2`$. In the context of a one-factor model, we therefore obtain:

$$\rho _>(\lambda )=\frac{\sigma _m^2(\lambda )}{\left(\frac{1}{N}_{i=1}^N\beta _i^2\right)\sigma _m^2(\lambda )+\frac{1}{N}_{i=1}^N\sigma _{ϵ_i}^2}.$$
(7)
The residual volatilities $`\sigma _{ϵ_i}^2`$ are independent of $`r_m`$ and therefore of $`\lambda `$ whereas $`\sigma _m^2(\lambda )`$ is obviously an increasing function of $`\lambda `$. Hence the coefficient $`\rho _>(\lambda )`$ is an increasing function of $`\lambda `$. The one-factor model therefore predicts an increase of the correlations (as measured by $`\rho _>(\lambda )`$) in high volatility periods. This conclusion is quite general, it holds in particular for any factor model, even with Gaussian statistics. Therefore, the very fact of conditioning the correlation on large market returns leads to an increase of the measured correlation. A similar discussion in the context of Gaussian models can be found in .

More precisely, we can now compare the coefficient $`\rho _>(\lambda )`$ measured empirically to one obtained within the one-factor model defined above. This is presented in Fig. 1. Interestingly, the surrogate and empirical correlations are similar, displaying qualitatively the same increase of the cross-correlation when conditioned to large market returns. This shows that a one-factor model does indeed account quantitatively for the apparent increase of cross-correlations in high volatility periods.

The one-factor model actually even overestimates the correlations for large $`\lambda `$. This overestimation can be understood qualitatively as a result of a positive correlation between the amplitude of the market return $`|r_m|`$ and the residual volatilities $`\sigma _{ϵ_i}`$, which we discuss in more details in Section 4 below (see in particular Fig. 5). For large values of $`\lambda `$, $`\sigma _{ϵ_i}`$ is found to be larger than its average value. From Eq. (7), this lowers the correlation $`\rho _>(\lambda )`$ as compared to the simplest one-factor model where the volatility fluctuations of the residuals are neglected.

### Conditional fraction of positive/negative returns:

Another quantity of interest is the fraction of stocks returns having the same sign as the market return, as a function of the market return itself. The empirical results are shown on Fig. 2. We observe that for the largest returns, $`90\%`$ of the stocks have the same return sign as that of the market. Therefore, the sign of the market appears to have a very strong influence on the sign of individual stock returns.

This fraction can be calculated exactly within the one-factor model. Focusing on positive market return (the case of negative returns can be treated similarly), a stock return $`r_i`$ is positive whenever $`ϵ_i>\beta _ir_m`$. Therefore the average fraction $`f(t)`$ of stocks having a positive return for a given market return $`r_m(t)`$ is

$$f(t)=\frac{1}{N}\underset{i=1}{\overset{N}{}}𝒫_<\left(\frac{\beta _ir_m(t)}{\sigma _{ϵ_i}}\right),$$
(8)
where $`𝒫_<`$ is the cumulative normalized distribution of the residual (chosen here to be a Student distribution with a exponent $`\mu =4`$). $`f(t)`$ is also plotted on Fig. 2 and fits well the empirical results. The theoretical estimate slightly overestimates the fraction $`f(t)`$ for positive market returns. As explained above, the correlations between $`\sigma _{ϵ_i}`$ and $`|r_m|`$ do lower $`f(t)`$ as needed for the positive side. However, the corresponding fraction for the negative side would then be underestimated.

### Conditioning on large individual stock returns – quantile correlations and exceedance correlations:

Since the volatility of the residuals is two times larger than the volatility of the market, the conditioning by extreme market events does not necessarily select extreme individual stock moves. The quantities studied in the previous section, namely return correlations and sign correlations, are therefore more related to the central part of the stocks distribution rather than to their extreme tails. We now study more specifically how extreme stock returns are correlated between themselves. A first possibility is to study quantile correlations, that we define as:

$$\rho (q)=\frac{\frac{1}{N^2}_{i,j}\left(r_ir_j_qr_i_qr_j_q\right)}{\frac{1}{N}_i\left(r_i^2_qr_i_q^2\right)},$$
(9)
where the subscript $`q`$ indicates that we only retain in the average days such that both $`|r_i|`$ and $`|r_j|`$ take their $`q`$quantile value, within a certain tolerance level (this tolerance is taken to be $`4\%`$ of the total interval for each quantile). In the limit $`q1`$, this selects extremes days for both stocks $`i`$ and $`j`$ simultaneously. The empirical results for $`\rho (q)`$ are compared with the prediction of the one-factor model in Fig. 3. The agreement is again very good, though the one-factor model still slightly overestimates the true correlations in the extremes.

Another interesting quantity that has been much studied in the econometric literature recently, is the so-called exceedance correlation function, introduced in . One first defines normalized centered returns $`\stackrel{~}{r}_i`$ with zero mean and unit variance. The positive exceedance correlation between $`i`$ and $`j`$ is defined as:

$$\rho _{ij}^+(\theta )=\frac{\stackrel{~}{r}_i\stackrel{~}{r}_j_{>\theta }\stackrel{~}{r}_i_{>\theta }\stackrel{~}{r}_j_{>\theta }}{\sqrt{(\stackrel{~}{r}_i^2_{>\theta }\stackrel{~}{r}_i_{>\theta }^2)(\stackrel{~}{r}_j^2_{>\theta }\stackrel{~}{r}_j_{>\theta }^2)}},$$
(10)
where the subscript $`>\theta `$ means that both normalized returns are larger than $`\theta `$. Large $`\theta `$’s correspond to extreme correlations. The negative exceedance correlation $`\rho _{ij}^{}(\theta )`$ is defined similarly, the conditioning being now on returns smaller than $`\theta `$. Fig. 4 shows the exceedance correlation function, averaged over the pairs $`i`$ and $`j`$, both for real data and for the surrogate one-factor model data. As in previous papers, we have shown $`\rho _{ij}^+(\theta )`$ for positive $`\theta `$ and $`\rho _{ij}^{}(\theta )`$ for negative $`\theta `$. As in previous studies , we find that $`\rho ^\pm (\pm \theta )`$ grows with $`|\theta |`$ and is larger for large negative moves than for large positive moves. This is in strong contrast with the prediction of a Gaussian model, which gives a symmetric tent-shaped graph that goes to zero for large $`|\theta |`$. Note however that previous studies have focused on fixed pairs of assets $`i`$ and $`j`$ (for example a few pairs of international markets). The result of Fig. 4 is interesting since it reveals a systematic effect over all pairs of a pool of 450 stocks.

Several models have been considered to explain the observed results . Simple GARCH or Jump models cannot account for the shape of the exceedance correlations. Qualitatively similar graphs can however be reproduced within a rather sophisticated ‘regime switching’ model, where the two assets switch between a positive, low volatility trend with small cross-correlations and a negative, high volatility trend with large cross-correlations. Note that by construction, this ‘regime switching’ model induces a strong skew in the ‘index’ (i.e. the average between the two assets). Fig. 4 however clearly shows that a fixed correlation non Gaussian one-factor model is enough to explain quantitatively the level and asymmetry of the exceedance correlation function. In particular, the asymmetry is induced by the large negative skewness in the distribution of index returns, and the growth of the exceedance correlation with $`|\theta |`$ is related to distribution tails fatter than exponential (in our case, these tails are indeed power-laws).

## 4 Conditional statistics of the residuals

We conclude from the above results that the observed fluctuations of the stock cross-correlations are mainly a consequence of the volatility fluctuations and skewness of the market return, and that a non Gaussian one-factor model does reproduce satisfactorily most of the observed effects. However, some small systematic discrepancies appear, and call for an extension of the one-factor model. The most obvious effect not captured by a one-factor model is the recently discovered ‘ensemble’ skewness in the daily distribution of stock returns, as discussed by Lillo and Mantegna . More precisely, they have shown that the histogram of all the stocks returns for a given day displays on average a positive skewness when the market return is positive, and a negative skewness when the market return is negative. The amplitude of this skewness furthermore grows with the absolute value of the market return. Note that this skewness is not related to the possible non zero skewness of individual stocks that has been recently discussed in several papers in relation with extended CAPM models .

Clearly, this ‘ensemble’ skewness that depends on the market return cannot be explained by the above one-factor model where the residuals have a time independent zero skewness. The one-factor model is certainly an oversimplification of the reality: although the market captures the largest part of the correlation between stocks, industrial sectors are also important, as can be seen from a diagonalization of the correlation matrix . Large moves of the market can be dominated by extreme moves of a single sector, while the other sectors are relatively unaffected. This effect does induce some skewness in the fixed-day histogram of stock returns distribution.

A way to account for this effect is to allow the distribution of the residual $`ϵ_i(t)`$ to depend on the market return $`r_m(t)`$. In order to test this idea, we have studied directly some moments of the distribution of the residuals for a given day as a function of the market return that particular day. We have studied the following quantities:

$$\mathrm{\Sigma }=[|ϵ_i[ϵ_i]|],$$
(11)
$$𝒮=\frac{[ϵ_i]\text{Med}(ϵ_i)}{\mathrm{\Sigma }},$$
(12)
$$𝒦=\frac{[ϵ_i^2][ϵ_i]^2}{\mathrm{\Sigma }^2},$$
(13)
where the square brackets $`[\mathrm{}]`$ means that we average over the different stocks for a given day and Med selects the median value of $`ϵ_i`$. These three quantities should be thought as robust alternatives to the standard variance, skewness and kurtosis, which are based on higher moments of the distribution.

The quantity $`\mathrm{\Sigma }`$ measures the ‘volatility’ of the residuals and is shown in Fig. 5 as a function of $`|r_m(t)|`$. A linear regression is also shown for comparison. It is clear that there is a positive correlation between the market volatility and the volatility of the residuals, not captured by the simplest one-factor model. As explained above, this effect actually allows one to account quantitatively for the systematic overestimation of the observed correlations.

In order to confirm the skewness effect of Lillo and Mantegna, we have then studied the quantity $`𝒮`$. This quantity is positive if the distribution is positively skewed. Fig. 6 shows a scatter plot of $`𝒮`$ as a function of $`r_m`$ . Again these two quantities are positively correlated, as emphasized by Lillo and Mantegna (although their analysis is different from ours).

Therefore, both the volatility and the skew of the residuals are quite strongly correlated with the market return. One could wonder if higher moments of the distribution are also sensitive to the value of $`r_m`$. We have therefore studied the quantity $`𝒦`$ as one possible refined measure of the shape of the distribution of residuals. This is shown in Fig. 7 and reveals a much weaker dependence than the previous two quantities.

## 5 Conclusion

We have thus shown that the apparent increase of correlation between stock returns in extreme conditions can be satisfactorily explained within a static one-factor model which accounts for fat-tail effects. In this model, conditioning on a high observed volatility naturally leads to an increase of the apparent correlations. The much discussed exceedance correlations can also be reproduced quantitatively and reflects both the non-Gaussian nature of the fluctuations and the negative skewness of the index, and not the fact that correlations themselves are time dependent.

This one-factor model is however only an approximation to the true correlations, and more subtle effects (such as the Lillo-Mantegna ‘ensemble’ skewness) require an extension of the one factor model, where the variance and skewness of the residuals themselves depend on the market return.

### Acknowledgments:

We wish to thank M. Meyer and J. Miller for many useful discussions.


text:
# A Decision-Theoretic Approach to Resource Allocation in Wireless Multimedia Networks

## I Introduction

When a user makes a call in a wireless network, the system must decide whether to admit the call or block it.111In this paper, we use the term “user” to refer to the actual user or the application running on the user’s mobile device; we use the generic term “call” to indicate an attempt to initiate a session, which could be of any medium type or types (e.g., voice, data, video, hybrid); we use the term “block” to mean rejecting new calls, the term “drop” to mean rejecting calls already in progress (e.g., during a handoff process), and the term “reject” to mean either block or drop. What makes the decision difficult is that, to achieve some sense of optimality, one needs to consider the future status of the network resources and the pattern of the future arrival requests. For example, even if the network currently has sufficient resources to handle the call, admitting the call may result in other, already in-progress calls being dropped in the future. This problem is aggravated by the trend to decreasing cell sizes coupled with an increased demand for multimedia services. The reduction in cell size leads to increased spectrum-utilization efficiency, but also increases the number of handoffs experienced during a typical connection. This means that the call requests at one cell will be more affected by decisions made in nearby cells. Furthermore, as the number of cells increases, the amount of resources per cell decreases. Thus, the trunking efficiency is reduced, leading to more severe fluctuations in the quality of service (QoS). The provision of connection-level QoS raises a distinct yet dependent set of issues. Guarantees made by one cell place future burdens, due to handoffs, on the resources of other cells.

This particular problem is but one of many in the general area of admission-control policies. The crafting of admission policies is generally approached by focusing on a subset of the design issues, while ignoring others. For example, several schemes for wireless networks  have been proposed to provide connection-level QoS by basing the call-admission decision on a requirement that the handoff-dropping probability be kept below a certain level. Clearly, however, lowering the handoff-dropping probability will, in general, mean increasing the probability of calls being blocked. A major issue remains unaddressed: is it worth decreasing the handoff-dropping probability from, say, 2% to 1% if it means increasing the probability of blocking from 5% to 10%? In other words, what is an acceptable tradeoff between call blocking and call dropping probabilities?

Tolerance to blocking and dropping among users is also not addressed by a simple minimization of handoff-dropping probability. For example, compare a typical voice call with a file transfer. A user making a voice call may be mildly frustrated if she cannot connect to the server, but would be much more annoyed if the call were dropped halfway through the conversation. On the other hand, a user attempting to do a number of FTP file transfers may prefer to be connected immediately, even if this means a higher probability of being dropped, since this increases the probability of at least some rapid file transfers. Should the network treat voice and file transfer connections uniformly and provide a single dropping probability for both?

We believe that sensible admission decisions should take both utilities and probabilities into account, and are best formulated in decision-theoretic terms. In this paper, we describe a general decision-theoretic approach to call admission. Although we use a specific example to demonstrate our approach, our approach gives a framework that can accommodate various QoS requirements in the multimedia resource-allocation process. Our focus is on wireless networks, but the generalization to other contexts is immediate. We show that even a simplistic decision-theoretic approach to wireless network admission policies produces substantial performance improvement over several well-known heuristics.

The key ingredients in decision theory are probability and utility. Probability is a measure of the likelihood of an event, while the utility (which can be interpreted as the reward) measures the event’s perceived importance. A decision-theoretic admission-control policy can take into account the relative utility of blocking and dropping, as well as other considerations, such as network utilization or service differentiation and delay requirements.

If we are to use a decision-theoretic approach, we must somehow determine the probabilities and utilities. We assume that the probabilities can be obtained by taking sufficient statistical measurements. Obtaining the utilities is somewhat more problematic. Utilities are subjective and different users may have different utilities for the same application. Moreover, there is the problem of what is known as inter-subjective utility: one user’s utility of 10 may not be equivalent to another user’s 10.

We sidestep these problems to some extent by assuming that we have only one user, which can be thought of as the system provider. Of course, it is in the system provider’s interest to keep users as happy as possible. So we can assume that, to some extent, the system provider’s utility is representative of a typical user’s utilities. This is particularly true if, as we would expect, the system provider gives higher utilities to calls for which users are prepared to pay more.

To use our approach, the system provider must decide what the relative utilities of blocking vs. dropping ought to be. Presumably this will be done by weighing the profits lost from blocking a call, compared to the profits lost due to customers switching to a different provider as a result of having calls dropped too frequently (and possibly refunds due to dropped calls). In this paper, we assume that we are simply given the relevant utilities, while recognizing that obtaining them may be a nontrivial problem.

Once we have the relevant probabilities and utilities, we can employ Markov Decision Processes (MDPs) . More specifically, we model the call-admission problem as an MDP, allowing us to use well-known techniques for finding the optimal call-admission policy. However, we must be careful in modeling the call-admission problem as an MDP. The standard techniques for finding the optimal policy in an MDP run in time polynomial in the size of the state space and the number of actions. A larger state space leads to a more accurate model of the system. But, if we are not careful, the state space can quickly become unmanageable. We discuss this issue in detail and show that under some simplifying and yet reasonably practical assumptions we can construct a manageable state space.

We are not the first to apply MDPs to the call-admission problem (see Section VI for other references). However, there are a number of subtleties that arise in using MDPs in this context that do not seem to have been considered earlier. For example, it is typically assumed that we are given the probabilities and utilities in an MDP, and that we must then construct an optimal admission policy. However, in a wireless network, the probabilities are themselves influenced by the admission policy we construct. For example, the probability that a call will be handed off from a neighboring cell depends on the probability that the neighboring cell will accept the call. This, in turn, depends on the admission policy, which was developed using assumptions about those probabilities. This is an issue that does not seem to have been considered in the literature on MDPs, perhaps because it was assumed that the probabilities of call blocking and dropping were so low that they could be ignored. Since we want our system to be able to deal with situations where the probability of blocking may be nonnegligible, we must address this problem as part of our solution. We do so by constructing a sequence of policies that converge to a limit. In the limit, we have a policy that is “locally” optimal with respect to a given probability measure and utility function, such that the probability measure is precisely that induced by the policy.

By finding a (locally) optimal policy using MDPs, we are able to make optimal tradeoffs between such concerns as providing the desired connection-level QoS and spectrum utilization. We show by an extensive series of simulations that our approach provides substantial performance improvement over one of the best heuristic approaches considered in the literature, given some standard assumptions about arrival times and holding times of calls. However, we do not view our major contribution as the performance improvements in this particular case. Rather, we consider our major contribution as the general decision-theoretic framework and the discussion regarding how to go about using it in practice. We believe that this framework provides us with a general methodology for evaluating admission-control policies and for characterizing optimal policies.

The rest of this paper is organized as follows. Section II discusses our assumptions about the underlying system and our use of QoS classes. Section III considers how the admission-control problem can be formulated as an MDP and the subtleties involved in doing so. Section IV shows how the optimal admission-control policy can be computed. Section V presents results from an extensive series of simulations that compares the performance of the decision-theoretic admission policy for the case of two QoS classes, one for data and one for video, with a well-known heuristic approach . Related work is described in Section VI, which also offers some concluding remarks.

## II Network Model and QoS Classes

We assume that the network consists of a cellular wireless portion and a wired backbone. The wireless portion consists of a set of cells, each cell contains a single base station (BS). All the BSs are connected to the same Mobile Switching Center (MSC). The MSC is responsible for switching calls between cells and for maintaining connections to the wired backbone. We focus solely on the wireless portion in this paper; an integrated admission-control scheme can be obtained by taking the wired portion into account.

We want to allow the network the possibility of treating different calls in different ways due to, for instance, user preferences and tolerances. We would certainly expect different traffic classes (e.g., voice, video, data) to be treated differently, but, as we observed earlier, we may also want to treat calls within the same traffic class in different ways.

Thus, we propose that each traffic class be partitioned into a number of QoS classes, so that the network provides $`K`$ QoS classes altogether. We may further want to refine each QoS class into a number of layers. The more layers assigned to a traffic stream, the better QoS is provided. Partitions into layers give the system an option for further QoS differentiation beyond just the decision of whether or not to admit a call. This would, for instance, allow us to take advantage of recent advances in video coding  by representing video (or audio) streams as multi-layer scalable flows that can adapt dynamically to changing network and link conditions. Dealing with layers is a straightforward extension of the ideas presented here; for ease of exposition, we do not consider layers further in this paper.

We assume that each QoS class is associated with a set of numbers representing utilities: the utility (cost) per unit of time of handling a call in that service class, the negative utility (cost) of blocking a call, and the cost of dropping a call during a handoff. (The idea of associating a set of utilities with a QoS class was inspired by the QoS contract notion in .)

## III Formulating Admission Control as an MDP

Our goal is to construct an admission-control policy that decides, for each new call and handoff call, whether it should be admitted or rejected and, if it is admitted, at what QoS level. The possibility of queuing incoming calls for later admission is not considered in this paper. We want to find a policy that maximizes expected utility.

It is not sufficient to simply maximize the expected utility of current new call requests and current admitted calls. This does not take into account the future need for handoffs as active users move across cell boundaries. Such an approach would result in future expected utility being much lower than the current expected utility. Instead, we try to maximize the expected total utility (in a sense made precise below). This means we must consider utility streams as opposed to temporally isolated utility values.

We cannot just identify the total utility with the sum of utilities over time, since this is in general an infinite sum. There are two standard approaches in the literature to defining total utility . The first is to discount the utility over time by some factor $`\gamma `$, with $`0<\gamma <1`$. That is, if $`u_k`$ is the utility obtained at time $`k`$, we take the total utility to be $`_{k=1}^{\mathrm{}}\gamma ^ku_k`$. We then try to find the policy that maximizes the expected total utility. This definition is meant to capture the notion of present value in accounting: a dollar now is worth more than a dollar one time unit later. The smaller $`\gamma `$ is, the more we weight the present. This is reasonable if the time units are reasonably large. For example, banks pay interest so that $95 at year $`t`$ can become $100 at year $`t+1`$. This suggests that having $100 at year $`t+1`$ is the same as having $95 at year $`t`$; i.e., we can assign $`\gamma =.95`$ to capture this effect.

A second approach to compute the total utility seems more appropriate in our context, since we are dealing with small time intervals. The focus in this approach is the average utility per unit of time; then the total utility over $`M`$ time units can just be taken to be $`M`$ times the average utility. Thus, in this approach we try to maximize the expected value of $`lim_M\mathrm{}(_{k=1}^Mu_i)/M`$.

Whichever approach in defining the total utility we use, we can formulate the problem of finding the policy which optimizes the expected total utility as a Markov Decision Process (MDP). Formally, an MDP is a tuple $`(S,A,T,R)`$ consisting of a set $`S`$ of states, a set $`A`$ of actions, a transition function $`T:S\times A\mathrm{\Pi }(S)`$, where $`\mathrm{\Pi }(S)`$ is the set of probability distributions over $`S`$, and a reward function $`R:S\times A𝐑`$, where $`𝐑`$ is the set of real numbers. Intuitively, $`T(s,a)`$ describes the probability of ending up in a state $`s^{}S`$ if we perform action $`a`$ in state $`s`$, while $`R(s,a)`$ describes the immediate reward obtained if we perform action $`a`$ in state $`s`$.

There are standard techniques for finding the optimal policy in MDPs, such as value iteration and policy iteration. These algorithms and a number of their variants have been studied in detail, and it is well understood what are the relative advantages of each algorithm (again, see ). We want to model the call-admission problem as an MDP, so as to be able to use all the power of MDPs. We now discuss how this can be done, considering the components of an MDP one by one. We pay particular attention to the problem of keeping the size of the state space manageable. Our discussion here is at a general level; we return to the specific issues raised here when we consider simulation results in Section V.

### III-A The State Space

We represent the state of the cell as the number of calls in progress in the cell. Decisions at a cell are made on the basis of this state. Clearly, the more information about the system we put into the state, the more accurate the model of the system is, and thus, the more accurate our estimation of the actual rewards received. For our algorithms to work, we also need to put enough information into the state to guarantee the Markov property; i.e., we want the probability of making a transition from one state to another to depend only on the current state, not on the previous history. On the other hand, the more details we put into the state, the more states there are, and the longer it will take to compute the optimal policy. If we put in too much details, the state space will be so large that we cannot compute the optimal policy in a reasonable length of time. Thus, there is a tradeoff that must be made when modeling the state; we may have to model only certain features, while ignoring others. A technique such as value iteration computes the optimal policy with respect to the state model. Of course, if our model of the state does not capture enough features of relevance to the problem, the optimal policy computed by the MDP may not be optimal in practice.

We briefly discuss some of these issues that arise in modeling the state here and the choices we made in our simulations.

* Should we include time in the state? Clearly, on one hand, traffic and mobility patterns depend on time of day (and day of the week and week of the year), so we would get a more accurate model by including time. On the other hand, adding time as a separate component in the state space means that the number of states is increased by a factor of $`T`$, where $`T`$ is the total number of time units that we deem relevant. (For example, if we decide that all that is relevant is the hour of the day, then there would be 24 time units; if we want to model the behavior at the level of minutes, then we would have 1440 time units.) It seems to us that, in practice, the overhead of including time is not worth the ensuing computational complexity, and we are better off having a number of separate MDPs, one for each expected pattern, and solving each of them separately. (Thus, for example, we could have a “mid-day” MDP, a middle-of-the-night MDP, and “morning rush hour” MDP, and so on.)
* Should we include information about neighboring cells in the state? The number of calls in neighboring cells (together with the mobility model) in fact determines the handoff probability (the distribution that describes the probability that a call will be handed off in the next $`t`$ time units). The handoff probability is in fact necessary for even defining the MDP, since it affects the transition probability. On the other hand, keeping track of this information can significantly increase the size of the state space. Fortunately, in many cases of interest, it is possible to estimate the handoff probability (and thus the transition probability), although subtleties arise that seem to have been ignored in other papers on the subject. We return to this issue in Section IV.
* Should we keep track of how long each call has been in the system? There are (at least) two reasons why such information may be necessary. For one, it may be necessary in order to estimate how much longer the call will remain in the system. (For example, if the length of a call is characterized by a heavy-tailed distribution, then the probability that a call terminates depends on how long it has lasted.) For another, if the utility of a call is a nonlinear function of the length of the call, it will be necessary to include this information in the state in order to correctly calculate the utilities. In our simulations, neither of these reasons apply. Our assumptions guarantee that the probability of a call termination is independent of how long it has been in progress (i.e. the Markovian property) and our utility does not depend in a nonlinear way on the length of the call.
* Do we have to include in the state information about the most recent call (what QoS class it is in, whether it is a new call or a handoff, etc.)? We have decided to include this information; the alternative would be to have a much more complicated choice of actions. We return to this issue in Section III-B.

Given these considerations, we take the state space $`S`$ to consist of vectors of length $`K+1`$. (Recall that $`K`$ is the number of QoS classes.) We set $`s=(x_1,\mathrm{},x_K,\theta )S`$, where $`x_i`$ is the number of ongoing calls in QoS class $`i`$, for $`i=1,\mathrm{},K`$, and $`\theta `$ is a description of the call event that happens at the current time unit if there is one, and $`n`$ (for no event), otherwise. There are three types of call events: a new-call arrival of QoS class $`i`$, a handoff-call arrival of QoS class $`i`$, and call departure of QoS class $`i`$. We describe these events by pairs of the form $`(r,i)`$, $`(h,i)`$, and $`(d,i)`$, respectively. We assume that at most one call event happens at each time. Thus, there are at most $`3K+1`$ possible values of this last component. (The $`(d,i)`$ event cannot occur if there are no calls of QoS class $`i`$ currently in the cell.) The state space is constrained by the total number of channels in the system. We assume that each call in QoS class $`i`$ requires $`b_i`$ channels and that there are $`N`$ channels altogether. Note that “channels” are not necessarily physical channels; they can be logical channels as well (for instance, the number of concurrent users in CDMA). Thus, $`S=\{s=(x_1,\mathrm{},x_K,\theta ):x_i0,_{i=1}^Kb_ix_iN\}.`$

### III-B The Action Space and Transition Function

Given our representation of states, we need only two possible actions: accept and reject. These actions have the obvious effect if there is a call arrival at the current time unit, and no effect at all if there is a call departure or no call event at the current time unit. This is captured by the transition function. Note that the effect of an action on the first $`k`$ components of a state is completely deterministic; the only uncertainty is what the next call event will be. For example, if $`K=2`$, then in state $`(2,3,(r,2))`$, accept results in a state of the form $`(2,4,\theta )`$ while reject results in a state of the form $`(2,3,\theta )`$. Similarly, in a state of the form $`(2,3,(d,2))`$, both accept and reject result in a state of the form $`(2,2,\theta )`$. The relative probability of each of these outcomes depends on our assumptions about dwell times, mobility (how often calls leave one cell for another), and the probability of call arrival. It may also depend on the policy itself, since the policy affects the number of calls in each cell, which in turn may affect the handoff probability. For example, if the policy rejects all calls, then the handoff probability is guaranteed to be 0. We return to this issue in Sections IV and V.

We can represent the transition function in terms of two matrices, one for the action accept and one for reject. The $`(s,t)`$ entry of the accept matrix describes the probability of going from $`s`$ to $`t`$ if the accept action is performed, and similarly for reject. Since there are only $`3K+1`$ entries in each row that have positive probability, the matrix is relatively sparse. This may make it possible to speed up some of the computations involved.

As we said earlier, we could use a state representation that did not include the last component. We would then need actions of the form $`(a_1,\mathrm{},a_{2K})`$, where each $`a_i`$ is either accept or reject. For $`i=1,\mathrm{},K`$, the $`a_i`$ component tells us what to do if the next call event is an arrival of a new call of QoS class $`i`$; for $`i=K+j`$, $`j=1,\mathrm{},K`$, the $`a_i`$ component tells us what to do if the next call event is a handoff of QoS class $`j`$. Of course, if the next call event is a departure, then we again take the obvious transition. In , it was suggested that this representation would lead to computational efficiencies. However, since we save a factor of only $`3K+1`$ in the size of the state space while increasing the number of possible actions by a factor of $`2^K`$, and since the standard algorithm runs in time $`|S|^2|A|`$, it seems unlikely that this approach would indeed be more computationally efficient.

### III-C The Reward Function

The reward function makes use of the utilities of the QoS classes. However, these utilities do not completely determine the reward. For example, if the utility of QoS class $`i`$ is $`u_i`$, do we obtain the utility (i.e., reward) only once (say when the call is connected)? Do we obtain it for each unit of time that the call is connected? The first possibility corresponds to a charge of a flat rate per call (with perhaps some penalties for dropping a call or blocking it); the second corresponds to a charge per call that is a linear function of its duration. Clearly other schemes are possible as well. Our approach can easily accommodate both flat-rate pricing and linear pricing in a natural way. We represent the reward $`R`$ by a matrix $`(R_{ij})`$, $`i=1,\mathrm{},K`$, $`j=0,1,2`$. Roughly speaking $`R_{i0}`$ is the reward for accepting a call of QoS class $`i`$, if we are thinking of flat-rate pricing, and the reward for carrying a call of QoS class $`i`$ for a unit of time, if we are thinking of linear pricing. $`R_{i1}`$ is the penalty for blocking a call of QoS class $`i`$ and $`R_{i2}`$ is the penalty for dropping a call of QoS class $`i`$.

With the reward matrix in hand, we can now describe the reward function $`R(s,a)`$ in a straightforward way for both flat-rate pricing and linear pricing. (We do not consider other reward policies here.) For flat-rate pricing, we have:

* $`R((\stackrel{}{x},\theta ),\text{accept})=R_{i0}`$ if $`\theta =(r,i)`$
* $`R((\stackrel{}{x},\theta ),\text{accept})=0`$ if $`\theta `$ is $`(d,i)`$, $`(h,i)`$, or $`n`$
* $`R((\stackrel{}{x},\theta ),\text{reject})=R_{i1}`$ if $`\theta `$ is $`(r,i)`$
* $`R((\stackrel{}{x},\theta ),\text{reject})=R_{i2}`$ if $`\theta `$ is $`(h,i)`$
* $`R((\stackrel{}{x},\theta ),\text{reject})=0`$ if $`\theta `$ is $`(d,i)`$ or $`n`$.

For linear pricing, we have:

* $`R((\stackrel{}{x},\theta ),\text{accept})=R_{i0}+_{j=1}^Kx_jR_{j0}`$ if $`\theta `$ is $`(r,i)`$ or $`(h,i)`$
* $`R((\stackrel{}{x},\theta ),\text{accept})=_{j=1}^Kx_jR_{j0}`$ if $`\theta `$ is $`(d,i)`$ or $`n`$
* $`R((\stackrel{}{x},\theta ),\text{reject})=R_{i1}+_{j=1}^Kx_jR_{j0}`$ if $`\theta `$ is $`(r,i)`$
* $`R((\stackrel{}{x},\theta ),\text{reject})=R_{i2}+_{j=1}^Kx_jR_{j0}`$ if $`\theta `$ is $`(h,i)`$
* $`R((\stackrel{}{x},\theta ),\text{reject})=R_{i0}+_{j=1}^Kx_jR_{j0}`$ if $`\theta `$ is $`(d,i)`$
* $`R((\stackrel{}{x},\theta ),\text{reject})=_{j=1}^Kx_jR_{j0}`$ if $`\theta `$ is $`n`$.

## IV Computing the Optimal Policy

Our goal is to find the policy (mapping from states to actions) that maximizes the average sum of rewards. The optimal policy can be obtained using dynamic programming, by a modification of standard techniques like value iteration or policy iteration (see  for more details). To explain why we need to modify the standard techniques, we first briefly review the value iteration algorithm (although the points we make apply equally well to policy iteration, the other standard approach, and all their variants). The value iteration approach is based on the following observation. Let $`p_{xy}^a`$ be the probability of making the transition from state $`x`$ to state $`y`$ if action $`a`$ is taken (this probability is defined by the transition function). Suppose $`\pi `$ is some policy for the MDP. Let $`V_\pi (x)`$ be the value of state $`xS`$ for policy $`\pi `$, that is, the expected reward if we use policy $`\pi `$ starting in state $`x`$. The idea behind value iteration is that we can compute the optimal policy $`\pi ^{}`$ and the optimal value function $`V^{}`$ by successive approximations. We start with an arbitrary value function $`V_0`$. Let $`\pi _0`$ be the optimal choice of action with respect to $`V_0`$; that is

$$\pi _0(x)=\text{argmax}_{aA}\left(R(x,a)+\underset{yS}{}P_{xy}^aV_0(y)\right),$$
(1)
where $`P_{xy}^a`$ is the probability $`T(x,a)(y)`$ of making the transition from $`x`$ to $`y`$ if action $`a`$ is chosen. Suppose we have defined $`\pi _0,\mathrm{},\pi _n`$ and $`V_0,\mathrm{},V_n`$. We then define $`V_{n+1}`$ and $`\pi _{n+1}`$ as follows:

$$V_{n+1}(x)=\underset{aA}{\mathrm{max}}\left(R(x,a)+\underset{yS}{}P_{xy}^aV_n(y)\right);$$
(2)
$$\pi _{n+1}(x)=\text{argmax}_{aA}\left(R(x,a)+\underset{yS}{}P_{xy}^aV_{n+1}(y)\right).$$
(3)
It is a standard result that $`\pi _{n+1}`$ converges to an optimal policy $`\pi ^{}`$ and $`V_n`$ converges to the value $`V^{}`$ of $`\pi ^{}`$. In practice, we choose some $`ϵ`$ and stop the computation when $`|V_n(x)V_{n+1}(x)|<ϵ`$ for all states $`xS`$; $`\pi _n`$ is then an acceptable approximation to $`\pi ^{}`$.

We want to apply value iteration to computing optimal admission decisions. But, as we hinted above, there may be a problem even defining the MDP. Admission decisions in cell $`c`$ must take into account how many calls will be handed off from neighboring cells. If many more handoff calls are likely to arrive, the admission decision must make new call admission decisions more conservatively. How many handoff calls will arrive at a cell $`c`$ depends on the number of calls in $`c`$’s neighbors and on the mobility pattern. However, if $`c`$’s state does not include the number of calls in neighboring cells (as is the case in our model), we must find some way of estimating the number of calls at $`c`$’s neighbors in order to estimate the handoff probability (which in turn affects the transition probability in the MDP). There are two (conflicting) intuitions regarding this estimate. The first is that the number of calls in the current cell (which is part of the cell’s state) is a good estimate of the number of calls at its neighbors. Note that this says that the number of calls in a cell and its neighbors is strongly correlated. The second intuition suggests that, given a policy, a good estimate of the number of calls in each QoS class at a neighboring cell is just the expected number of calls in each QoS class in a state over time as the policy is run. This intuition suggests that, given a policy, the number of calls at $`c`$’s neighbors is uncorrelated with the number of calls at $`c`$.

If the first intuition is correct (as we expect it will be in some cases), then it is relatively straightforward to determine the probability that a call will be handed off to a cell $`c`$ in state $`s`$ (given the mobility model) and thus to define the transition probabilities for the MDP. However, if the second intuition is correct (as experimental evidence shows that it is under the assumptions of our simulation) then the handoff probability (and hence the transition probability) depends on the policy. Thus, it seems we cannot even define the MDP, let alone use value iteration to compute the optimal policy! (We remark that this problem seems not to have been noticed in other papers that use MDPs in this context , which simply assume that the handoff probability is fixed, independent of the policy, and is given as part of the model.)

Fortunately, even if the second intuition is more appropriate, it is still often possible to find the optimal policy by a relatively simple modification of value iteration. We start by guessing a vector $`\stackrel{}{c}_0`$ that describes the expected number of calls in each QoS class. Under the second intuition, provided the guess is correct, it (along with the known call arrival probability and mobility model) is enough to determine the handoff probability and thus the transition probabilities, and hence define an MDP. We then use standard value iteration to obtain the optimal policy $`\pi _0^{}`$ for the resulting MDP. Under minimal assumptions (namely, that for any two states $`s`$ and $`s^{}`$, the probability of reaching $`s^{}`$ starting in $`s`$ is positive when using policy $`\pi _0^{}`$, which is certainly the case for this problem), the policy $`\pi _0^{}`$ determines a stationary probability distribution $`P_0`$ over states . The probability of a state $`s`$ according to $`P_0`$ can be viewed as the probability of finding a cell in state $`s`$ if we sample at random. Let $`\stackrel{}{c}_1`$ be the expected number of calls of each QoS class according to $`P_0`$. We then use $`\stackrel{}{c}_1`$ to calculate the handoff probability, and thus determine the transition probabilities for a new MDP. We can then calculate the optimal policy $`\pi _1^{}`$ for this MDP. We then iterate this procedure. In general, it seems that this approach should converge under some reasonable assumptions, but we have not yet proved this analytically. It does converge for our simulation. However, even if it converges, there is no guarantee that it will converge to an optimal MDP. All that we can guarantee in general is that it converges to a local optimum. Methods such as simulated annealing , genetic algorithms , or Tabu search  should be useful for finding a global optimum.

## V Experimental Results

We have compared our MDP approach to one well-known heuristic in the literature: the NAG policy . We have chosen NAG because it is reported in  to be one of the best admission-control policies in terms of balancing utilization efficiency and connection-level QoS.

### V-A Experimental assumptions

In performing our experiments, we made a number of assumptions. To make the simulations easier to run, we assumed that there are only two QoS classes, one for data and one for video. We used the mobility model proposed in , extended to account for multiple QoS classes and the finite capacity of the cell BS. We also made the following traffic and mobility assumptions:

* The region is covered by $`19`$ hexagonal cells, each cell with a radius $`R=1Km`$. In order to simulate a large area, when a call is handed off beyond the region boundary, it is handed back to another cell on the boundary (with cells having fewer neighbors having a proportionately higher chance of being chosen). This adjusts for the fact that, otherwise, the number of handoffs received on average at the boundary cells will be smaller than at the interior cells.
* Mobiles can travel in any direction with equal probability and with a constant speed $`SP`$.
* Each mobile goes through changes of direction at “arbitrary” places and times.
* Connection requests are generated according to a Poisson process with rate $`\lambda `$ (connections/second/cell) in each cell.
* Each connection can be a data call with probability $`R_{dv}`$ or a video call with probability $`1R_{dv}`$.
* The call-holding time distribution is the same for both video and data, and is exponentially distributed with mean 120 seconds ( $`\frac{1}{\mu }=120`$ seconds).
* The dwell time is exponentially distributed with mean $`\frac{1}{\rho \mu }`$ seconds, where $`\rho =\frac{(3+2\sqrt{3})SP}{9\mu R}`$.
* A video call occupies $`4`$ BU, where a BU is defined to be the bandwidth to carry out one voice call.
* Each cell has a fixed capacity of 100 BU.

Identical assumptions have been made in many similar studies  so, for the sake of comparison, we make them here as well. While these assumptions seem quite reasonable in many contexts, we are well aware that they may be quite inappropriate in others. For example, if we are considering traffic along a highway, assuming that the mobile’s movement is random is clearly incorrect, although it may be more reasonable if we are considering calls in midtown Manhattan. The assumption that call-holding times are exponentially distributed becomes less appropriate as wireless traffic starts to approximate Internet traffic; studies of the Internet suggest that heavy-tailed distributions are more appropriate . Indeed, recent studies of telephone traffic suggest that even for telephone traffic, heavy-tailed distributions may be appropriate , although work by Guerin  supports the use of the exponential distribution. In any case, we stress that we are making these assumptions only for our case study. Nothing in our general framework depends on them.

Under the assumptions made here, the modeling approach we used in Section III is appropriate. Our traffic and mobility model do not depend on time. In addition, our assumptions about Poisson arrival process and exponential call holding time guarantee the Markov property, so we do not need to put time into the state space. We consider flat rate and linear rate pricing; therefore, we do not keep track of how long each call has been in the system. We assume that traffic patterns are homogeneous. The state of the neighboring cell affects the current cell only through the arrival rate of handoff calls, which depends on the number of calls in the cell. Since experimental evidence shows that, under our assumptions, the number of calls at a neighbor is the expected number of calls in a state over time as the policy is run (i.e., the second intuition holds), we can compute the handoff probability and the optimal policy by using the modified value iteration approach discussed in Section IV.

In applying this approach, it is necessary to calculate the transition probabilities for the MDP given an assumption $`\stackrel{}{c}`$ about the expected number of calls of each class. As we observed earlier, all that is needed is to compute the relative probability of the possible types of next call event; the detailed calculations can be found in Appendix A. We now consider the issue of convergence. Under the assumptions used in our simulation, the optimal policy is a threshold . That is, for each type of call-arrival event, there is a threshold such that, if there are fewer calls currently in the system than the threshold, the call is admitted; otherwise it is rejected. If there is only one QoS class, this modification of value iteration converges and computes the optimal policy. The reason for this convergence result is as follows: It is clear that the higher the handoff probability the lower the acceptance threshold (that is, the lower the threshold $`t`$ such that calls are rejected if there are more than $`t`$ calls already in state $`t`$), and vice versa. We can find the optimal policy by doing a binary search; that is, start with an assumption $`c_0`$ about the expected number of calls; compute the optimal policy $`\pi _0^{}`$ according to $`c_0`$, and compute the expected number $`c_0^{}`$ of calls corresponding to $`\pi _0^{}`$. By the argument above, the expected number of calls under the true optimal policy is between $`c_0`$ and $`c_0^{}`$. Let $`c_1=(c_0+c_0^{})/2`$. We compute the optimal policy with respect to $`c_1`$, then iterate. Although this argument does not work in higher dimensions, nevertheless, our simulations do always converge.

### V-B The NAG Policy

The design goal of NAG is to keep the handoff-dropping probability $`P_{hd}`$ below a certain threshold $`\alpha `$, thereby maintaining connection-level QoS. A new call is admitted at cell $`c`$ if admitting it does not raise the handoff-dropping probability of existing calls in the system above $`\alpha `$ and, if admitted, the new call’s handoff-dropping probability is also below $`\alpha `$. The problem is to decide the effect on $`P_{hd}`$ of accepting the new call. NAG does this by estimating the state of cell $`c`$ and its neighboring cells $`T_{est}`$ units of time after the new-call arrival time, for some appropriately chosen $`T_{est}`$. The choice of $`T_{est}`$ is based on the current state of each cell and the aggregate history of handoffs observed in each cell. As observed in , the performance of NAG depends critically on the choice of the interval $`T_{est}`$. It is assumed that $`T_{est}`$ is small enough that the probability that a call experiences a handoff more than once during $`T_{est}`$ time units is negligible. We experimented with different values of $`T_{est}`$ and chose it to be 5 seconds, since this choice seemed to give the best results for NAG in our experiments.

### V-C Numerical Results

There are two main issues we want to study in our simulation. First, we want to understand the behavior of the optimal policy, that is, what it depends on and what it does not depend on. Thus, we study the effect of user utility, the pricing scheme, and traffic and mobility patterns on the optimal policy. Second, we want to compare the performance improvements of the optimal policy over NAG under various conditions. The comparison will yield insight into the behavior of NAG and provide guidelines for the design of more efficient heuristic admission-control policies.

For these studies, we set the reward matrix $`R_{ij}`$ (see Section III) as follows. We took $`R_{i0}`$ to be proportional to the bandwidth requirement of each QoS class; we set $`R_{i1}`$ to be negative and its absolute value to be $`10`$% of $`R_{i0}`$. We varied the ratio $`r_{db_i}`$ ($`R_{i2}`$ divided by $`R_{i1}`$) to study its effects on the optimal policy. We considered two values for $`R_{dv}`$: $`1`$ (which means that all calls are data calls) and $`0.5`$ (which means that half the calls are data and half are video). We also considered two settings for the average speed of the mobile: 100 Km/hr and 50Km/hr. We refer to the former setting as the high user mobility case and the latter as the lower user mobility case.

#### V-C1 The Characteristics of the Optimal Admission Policy

First, we want to study the effect of user utility on the optimal admission policy. To do so, we vary $`r_{db_i}`$ (the ratio between call dropping and call blocking penalty) for the two QoS classes. In Figure 1, we see that for the same offered load, the call-dropping probability in the case of $`r_{db_1}=r_{db_2}=80`$ is smaller than the call-dropping probability in the case of $`r_{db_1}=r_{db_2}=40`$ case. This is what we would expect, since the optimal admission-control policy takes the application utilities into account. The greater the relative penalty for dropping a call, the lower the probability that it will be dropped. Figure 1 also shows that the optimal admission policy does not depend strongly on the traffic pattern parameter $`R_{dv}`$ or on the mobility parameter $`SP`$.

Our simulations do show that the pricing scheme can have a significant impact on the optimal control policy. If $`r_{db_1}=r_{db_2}=80`$, the call dropping probability for the flat pricing scheme is around $`1`$% under high load (see Figure 1(b)), but for the linear pricing scheme, the call dropping probability is around $`10`$% under the same high load (see Figure 2) . This result is also very intuitive. Since the reward ($`R_{i0}\times 1/\mu `$) for accepting a call in the linear pricing scheme is much higher than the reward ($`R_{i0}`$) for accepting a call in the flat pricing scheme, the linear pricing scheme tends to accept more calls than the flat pricing scheme.

#### V-C2 The Expected Utility of Different Admission Control Policies

The goal of the network service provider is to maximize its revenue while providing satisfactory service to the users over time. So the network performance should be measured in terms of the average system revenue over time. Since the system’s utility reflects the utility of users (to some extent), the average system revenue over time also reflects how good is the service that the system provides to the users over time. In our simulation, we compare the expected utilities of NAG and the optimal control policy under different offered loads. To capture the performance degradation of the network as the load increases, the expected utility is normalized with respect to a network with infinite capacity. In this section, we present the results for the flat pricing scheme and lower mobility case. Similar results hold for the linear pricing scheme and for high mobility; we omit details here.

Note that our optimal admission-control policy takes the user’s utility into account automatically. However, NAG does not. The call-dropping probability is selected by NAG in an ad hoc way. With the right choice of parameters, the performances gap between our optimal admission-control policy and NAG decreases. On the other hand, with the wrong choice, the opposite is true.

As our experimental results show, there is no one setting of the call-dropping probability that gives good results over the whole range of interest. For example, Figure 3 describes the results when NAG picks $`P_{hd}=4\%`$ as the design goal. The optimal admission-control policy achieves a performance improvement of approximately $`18`$%, $`55`$% and $`144`$% over NAG at offered loads of $`100`$, $`200`$, and $`300`$, respectively, in the $`R_{dv}=0.5`$ case (see Figure 3(c)). (At load $`300`$, the improvement of $`144`$% corresponds to a factor of more than 3 in the call-dropping probability while maintaining almost the same call blocking probability.) With $`P_{hd}=1\%`$ as NAG’s design goal, as shown in Figure 4, the optimal admission-control policy achieves a performance improvement of approximately $`14`$%, $`21`$%, and $`40`$% over NAG at offered loads of $`100`$, $`200`$, and $`300`$, respectively, in the $`R_{dv}=0.5`$ case. The improvement in the normalized expected utility depends in part on the type of calls that must be dealt with. For example, the improvements in terms of normalized expected utility over NAG at offered load $`100`$, $`200`$, and $`300`$ is $`11\%`$, $`44\%`$, and $`122\%`$, respectively, in the case of $`R_{dv}=1.0`$ when $`P_{hd}=4\%`$ is the design goal (see Figure 3(d)). This is because the optimal policy is biased towards data calls, since data calls can still be accepted in states that video call cannot be accepted due to insufficient bandwidth.

The differences between NAG and our optimal MDP policy become even more dramatic if we change $`r_{db_1}`$ from 80 to 2 (making the penalty for dropping a data call much closer to that of blocking a call; as we observed in the introduction, this might make sense for FTP transfers). In this case, the improvement of the MDP approach over the NAG approach increases from 40% to 70% at offered load $`300`$, with $`P_{hd}=1`$% as NAG’s design goal (see Figure 5).

Of course, once we add utilities into the picture, it would not be difficult to modify NAG so that it attempted at all times to adjust $`P_{hd}`$ to obtain optimal performance. But by doing this, NAG would essentially be approximating our MDP approach. In fact, as our state space grows, we will need to find useful approximation to the MDP approach, since it becomes computationally too expensive. NAG may be one such approach, but there may be better ones as well. The MDP approach at least gives us a framework by which to judge this issue.

## VI Discussion and Related Work

There has been a great deal of related work on admission control, both in the context of wireless and wired networks. Optimal call-admission policies in cellular networks which carry only voice calls were studied in . Near-optimal admission-control policies  and heuristic approaches  have been studied. Bandwidth adaptation using layered encoding has been studied recently in . None of these papers tried to provide a general decision-theoretic framework for the call-admission problem. Rather, they typically focused on the standard scenario (Poisson arrival times; exponentially distributed call holding and dwell times) and tried to solve the problem in that setting. While we believe that our main contribution is the general framework, not its application to the standard scenario, as we saw, our approach does dominate a well-known heuristic approach in this setting.

Previous work has either had the goal of keeping the call-dropping probability below a given threshold  or used a weighted factor between dropping and blocking as the design goal . The problems with choosing an appropriate handoff-dropping probability threshold have already been discussed in detail. The second approach can be viewed as a special case of ours. In  the weighting factor is determined by the relative utilities of call blocking and call dropping. Thus, these approaches are essentially a special case of ours, using flat-rate pricing, with only one QoS class. They assume that the call handoff rates are fixed, and do not deal with the fact that they are influenced by the policy. In addition, these papers do not address subtleties such as the effect of the policy chosen on the handoff rates.

There is another large body of literature on admission control in wired networks. The measurement-based admission-control (MBAC) approaches . Of these,  is perhaps most relevant to our work. For example, in , Renegotiated Constant Bit Rate (RCBR) Service is proposed for variable bit rate video. The main idea to increase the throughput through statistical multiplexing while providing delay and loss guarantees through renegotiation. While the basic idea of renegotiation may prove applicable in the wireless setting, we cannot immediately use this approach due to significant differences between the wired and wireless settings. In particular, since a wireless channel can be used exclusively by only one flow at a time, we cannot multiplex many flows on a wireless channel as easily as we can multiplex flows on bandwidth in the wired case. (For example, if both flows transmit at the same time, the data will be garbled in the wireless case.) Moreover, in MBAC, even if renegotiation fails, the flow keeps its original bandwidth. But for the wireless counterpart, if a handoff fails, the flow loses its original bandwidth.

Our general approach leads to some interesting research issues. All our algorithms are polynomial in the size of the state space. In our model, we used a number of techniques to limit the size of the state space. However, in realistic cases, we can expect to have much larger state spaces. Although the computation of the optimal solution is done off-line, and the admission decisions are made simply through table lookup, there is a limit to the number of states we can feasibly handle. We are currently exploring techniques to provide good approximate solutions in the presence of large state spaces. Motivated by the result in  that the running time in computing the near-optimal policies in arbitrarily large, unstructured MDPs does not depend on the number of states, we believe that MDP can be quite applicable in practice. We expect that, if the state space is large (due to many QoS classes) the behavior of the system will be qualitatively similar to the case when it is small.

## Appendix A Deriving the State-Transition Probabilities

Given our experimental assumptions, the call holding times are exponentially distributed and the call arrival times are determined by a Poisson distribution.  shows experimentally the handoff probability is also exponentially distributed; thus, we make that assumption here, and calculate the parameters experimentally, for each assumption $`\stackrel{}{c}=(c_1,c_2)`$ of the expected number of call of each QoS class.

By taking the minimum of all these distributions, we can compute the PDF describing the time that the next event happens in state $`x=(x_1,x_2,\theta _x)`$. This PDF is defined as

$$f(t)=\omega e^{\omega t},$$
(4)
where $`\omega =(x_1+x_2)\mu +\lambda _1+\lambda _2+(c_1+c_2)\rho \mu `$, $`\lambda _1=R_{dv}\lambda `$, $`\lambda _2=(1R_{dv})\lambda `$;

So the expected time until a new event occurs when in state $`x`$ is

$`\tau (x)`$ $`=`$ $`{\displaystyle _0^{\mathrm{}}}tf(t)𝑑t`$ (5)
$`=`$ $`\left[{\displaystyle \underset{i=1}{\overset{2}{}}}(x_i\mu _i+\lambda _i+c_i\rho \mu )\right]^1`$
The probability of a transition from state $`x`$ to state $`y`$ given action $`a`$ is:

$$P_{xy}^a=\{\begin{array}{cc}\lambda _1\tau (x)\hfill & y=(x_1+\sigma _1,x_2+\sigma _2,(r,1))\hfill \\ \lambda _2\tau (x)\hfill & y=(x_1+\sigma _1,x_2+\sigma _2,(r,2))\hfill \\ c_1\rho \mu \tau (x)\hfill & y=(x_1+\sigma _1,x_2+\sigma _2,(h,1))\hfill \\ c_2\rho \mu \tau (x)\hfill & y=(x_1+\sigma _1,x_2+\sigma _2,(h,2))\hfill \\ x_1\mu \tau (x)\hfill & y=(x_1+\sigma _1,x_2+\sigma _2,(d,1))\hfill \\ x_2\mu \tau (x)\hfill & y=(x_1+\sigma _1,x_2+\sigma _2,(d,2))\hfill \end{array}$$
(6)
where

$$\sigma _i=\{\begin{array}{cc}1\hfill & \text{if }a=accept\text{ and }\theta _x=(r,i)\text{ or }(h,i)\hfill \\ 1\hfill & \text{if }\theta _x=(d,i)\hfill \\ 0\hfill & \text{otherwise.}\hfill \end{array}$$
(7)