text:
# Scaling Dynamics of a Massive Piston in a Cube Filled With Ideal Gas: Exact Results

## 1 The model and main results

This paper is a continuation of \[LPS\], where deterministic scaled equations describing the dynamics of a massive piston in a cubical container filled with ideal gas were given. Here we state exact conditions on the validity of those equations and outline the arguments. Full proofs will be published in a separate paper \[CLS\].

We refer the reader to \[LPS\] and to \[CLS\] as well as \[G, GF, GP, KBM, Li\] for a detailed description of the problem of a massive piston moving in a cylinder. Here we just recall necessary facts.

Consider a cubical domain $`\mathrm{\Lambda }_L`$ of size $`L`$ separated into two parts by a wall (piston), which can move freely without friction inside $`\mathrm{\Lambda }_L`$. Each part of $`\mathrm{\Lambda }_L`$ is filled by a noninteracting gas of particles, each of mass $`m`$. The piston has mass $`M=M_L`$ and moves along the $`x`$-axis under the action of elastic collisions with the particles. The size $`L`$ of the cube is a large parameter of the model, and we are interested in the limit behavior as $`L\mathrm{}`$. The mass $`m`$ of gas particles is fixed. We will assume that $`M`$ grows proportionally to $`L^2`$ and the number of gas particles $`N`$ is proportional to $`L^3`$, while their velocities remain of order one.

The position of the piston at time $`t`$ is specified by a single coordinate $`X=X_L(t)`$, $`0XL`$, its velocity is then given by $`V=V_L(t)=\dot{X}_L(t)`$. Since the components of the particle velocities perpendicular to the $`x`$-axis play no role in the dynamics, we may assume that each particle has only one coordinate, $`x`$, and one component of velocity, $`v`$, directed along the $`x`$-axis.

When a particle with velocity $`v`$ hits the piston with velocity $`V`$, their velocities after the collision, $`v^{}`$ and $`V^{}`$, respectively, are given by

$$V^{}=(1\epsilon )V+\epsilon v$$
(1.1)
$$v^{}=(1\epsilon )v+(2\epsilon )V$$
(1.2)
where $`\epsilon =2m/(M+m)`$. We assume that $`M+m=2mL^2/a`$, where $`a>0`$ is a constant, so that

$$\epsilon =\frac{2m}{M+m}=\frac{a}{L^2}$$
(1.3)
When a particle collides with a wall at $`x=0`$ or $`x=L`$, its velocity just changes sign.

The evolution of the system is completely deterministic, but one needs to specify initial conditions. We shall assume that the piston starts at the midpoint $`X_L(0)=L/2`$ with zero velocity $`V_L(0)=0`$. The initial configuration of gas particles is chosen at random as a realization of a (two-dimensional) Poisson process on the $`(x,v)`$-plane (restricted to $`0xL`$) with density $`L^2p_L(x,v)`$, where $`p_L(x,v)`$ is a function satisfying certain conditions, see below, and the factor of $`L^2`$ is the cross-sectional area of the container. In other words, for any domain $`D[0,L]\times \text{I}\text{R}^1`$ the number of gas particles $`(x,v)D`$ at time $`t=0`$ has a Poisson distribution with parameter $`\lambda _D=L^2_Dp_L(x,v)𝑑x𝑑v`$.

Let $`\mathrm{\Omega }_L`$ denote the space of all possible configurations of gas particles in $`\mathrm{\Lambda }_L`$. For each realization $`\omega \mathrm{\Omega }_L`$ the piston trajectory will be denoted by $`X_L(t,\omega )`$ and its velocity by $`V_L(t,\omega )`$.

As $`L\mathrm{}`$, space and time are rescaled as

$$y=x/L\mathrm{and}\tau =t/L.$$
(1.4)
which is a typical rescaling for the hydrodynamic limit transition (see \[LPS, CLS\] for motivation and physical discussion). We call $`y`$ and $`\tau `$ the macroscopic (“slow”) variable, as opposed to the original microscopic (“fast”) $`x`$ and $`t`$. Now let

$$Y_L(\tau ,\omega )=X_L(\tau L,\omega )/L,W_L(\tau ,\omega )=V_L(\tau L,\omega )$$
(1.5)
be the position and velocity of the piston in the macroscopic variables. The initial density $`p_L(x,v)`$ satisfies

$$p_L(x,v)=\pi _0(x/L,v)$$

where the function $`\pi _0(y,v)`$ is independent of $`L`$. Without loss of generality, assume that $`\pi _0`$ is normalized so that

$$_0^1_{\mathrm{}}^{\mathrm{}}\pi _0(y,v)𝑑v𝑑y=1$$

Then the mean number of particles in the entire container $`\mathrm{\Lambda }_L`$ is equal exactly to

$$E(N)=_0^L_{\mathrm{}}^{\mathrm{}}L^2p_L(x,v)𝑑v𝑑x=L^3$$

In order to describe the dynamics by differential equations, we assume that the function $`\pi _0(y,v)`$ satisfies several technical requirements stated below.

* Smoothness. $`\pi _0(y,v)`$ is a piecewise $`C^1`$ function with uniformly bounded partial derivatives, i.e. $`|\pi _0/y|D_1`$ and $`|\pi _0/v|D_1`$ for some $`D_1>0`$.
* Discontinuity lines. $`\pi _0(y,v)`$ may be discontinuous on the line $`y=Y_L(0)`$ (i.e., “on the piston”). In addition, it may have a finite number ($`K_1`$) of other discontinuity lines in the $`(y,v)`$-plane with strictly positive slopes (each line is given by an equation $`v=f(y)`$ where $`f(y)`$ is $`C^1`$ and $`0<c_1<f^{}(y)<c_2<\mathrm{}`$).
* Density bounds. Let

$$\pi _0(y,v)>\pi _{\mathrm{min}}>0\mathrm{for}v_1<|v|<v_2$$
(1.6)
for some $`0<v_1<v_2<\mathrm{}`$, and

$$\underset{y,v}{sup}\pi _0(y,v)=\pi _{\mathrm{max}}<\mathrm{}$$
(1.7)
The requirements (1.6) and (1.7) basically mean that $`\pi _0(y,v)`$ takes values of order one.
* Velocity “cutoff”. Let

$$\pi _0(y,v)=0,\mathrm{if}|v|v_{\mathrm{min}}\mathrm{or}|v|v_{\mathrm{max}}$$
(1.8)
with some $`0<v_{\mathrm{min}}<v_{\mathrm{max}}<\mathrm{}`$. This means that the speed of gas particles is bounded from above by $`v_{\mathrm{max}}`$ and from below by $`v_{\mathrm{min}}`$.
* Approximate pressure balance. $`\pi _0(y,v)`$ must be nearly symmetric about the piston, i.e.

$$|\pi _0(y,v)\pi _0(1y,v)|<\epsilon _0$$
(1.9)
for all $`0<y<1`$ and some sufficiently small $`\epsilon _0>0`$.

The requirements (P4) and (P5) are made to ensure that the piston velocity $`|V_L(t,\omega )|`$ will be smaller than the minimum speed of the particles, with probability close to one, for times $`t=O(L)`$. Such assumptions were first made in \[LPS\].

We think of $`D_1`$, $`K_1`$, $`c_1`$, $`c_2`$, $`v_1`$, $`v_2`$, $`v_{\mathrm{min}}`$, $`v_{\mathrm{max}}`$, $`\pi _{\mathrm{min}}`$ and $`\pi _{\mathrm{max}}`$ in (P1)–(P4) as fixed (global) constants and $`\epsilon _0`$ in (P5) as an adjustable small parameter. We will assume throughout the paper that $`\epsilon _0`$ is small enough, meaning that

$$\epsilon _0<\overline{\epsilon }_0(D_1,K_1,c_1,c_2,v_1,v_2,v_{\mathrm{min}},v_{\mathrm{max}},\pi _{\mathrm{min}},\pi _{\mathrm{max}})$$

It is important to note that the hydrodynamic limit does not require that $`\epsilon _00`$. The parameter $`\epsilon _0`$ stays positive and fixed as $`L\mathrm{}`$.

Here is our main result:

###### Theorem 1.1

There is an $`L`$-independent function $`Y(\tau )`$ defined for all $`\tau 0`$ and a positive $`\tau _{}2/v_{\mathrm{max}}`$ (actually, $`\tau _{}2/v_{\mathrm{max}}`$ as $`\epsilon _00`$), such that

$$\underset{0\tau \tau _{}}{sup}|Y_L(\tau ,\omega )Y(\tau )|0$$
(1.10)
and

$$\underset{0\tau \tau _{}}{sup}|W_L(\tau ,\omega )W(\tau )|0$$
(1.11)
in probability, as $`L\mathrm{}`$. Here $`W(\tau )=\dot{Y}(\tau )`$.

This theorem establishes the convergence in probability of the random functions $`Y_L(\tau ,\omega ),W(\tau ,\omega )`$ characterizing the mechanical evolution of the piston to the deterministic functions $`Y(\tau ),W(\tau )`$, in the hydrodynamic limit $`L\mathrm{}`$.

The functions $`Y(\tau )`$ and $`W(\tau )`$ satisfy certain (Euler-type) differential equations stated in the next section. Those equations have solutions for all $`\tau 0`$, but we can only guarantee the convergence (1.10) and (1.11) for $`\tau <\tau _{}`$. What happens for $`\tau >\tau _{}`$, especially as $`\tau \mathrm{}`$, remains an open problem. Some experimental results and heuristic observations in this direction are presented in \[CL\] and discussed in Section 4.

Remark 1. The function $`Y(\tau )`$ is at least $`C^1`$ and, furthermore, piecewise $`C^2`$ on the interval $`(0,\tau _{})`$. Its first derivative $`W=\dot{Y}`$ (velocity) and its second derivative $`A=\ddot{Y}`$ (acceleration) remain $`\epsilon _0`$-small: $`sup_\tau |W(\tau )|`$const$`\epsilon _0`$ and $`sup_\tau |A(\tau )|`$const$`\epsilon _0`$, see the next section.

Remark 2. We also estimate the speed of convergence in (1.10) and (1.11): there is a $`\tau _1>0`$ ($`\tau _11/v_{\mathrm{max}}`$) such that $`|Y_L(\tau ,\omega )Y(\tau )|=O(\mathrm{ln}L/L)`$ for $`0<\tau <\tau _1`$ and $`|Y_L(\tau ,\omega )Y(\tau )|=O(\mathrm{ln}L/L^{1/7})`$ for $`\tau _1<\tau <\tau _{}`$. The same bounds are valid for $`|W_L(\tau ,\omega )W(\tau )|`$. These estimates hold with “overwhelming” probability, specifically they hold for all $`\omega \mathrm{\Omega }_L^{}\mathrm{\Omega }_L`$ such that $`P(\mathrm{\Omega }_L^{})=1O(L^{\mathrm{ln}L})`$.

## 2 Hydrodynamical equations

The equations describing the deterministic function $`Y(\tau )`$ involve another deterministic function – the density of the gas $`\pi (y,v,\tau )`$. Initially, $`\pi (y,v,0)=\pi _0(y,v)`$, and for $`\tau >0`$ the density $`\pi (y,v,\tau )`$ evolves according to the following rules.

* Free motion. Inside the container the density satisfies the standard continuity equation for a noninteracting particle system without external forces:

$$\left(\frac{}{\tau }+v\frac{}{y}\right)\pi (y,v,\tau )=0$$
(2.1)
for all $`y`$ except $`y=0`$, $`y=1`$ and $`y=Y(\tau )`$.

Equation (2.1) has a simple solution

$$\pi (y,v,\tau )=\pi (yvs,v,\tau s)$$
(2.2)
for $`0<s<\tau `$ such that $`yvr\{0,Y(\tau r),1\}`$ for all $`r(0,s)`$. Equation (2.2) has one advantage over (2.1): it applies to all points $`(y,v)`$, including those where the function $`\pi `$ is not differentiable.

* Collisions with the walls. At the walls $`y=0`$ and $`y=1`$ we have

$$\pi (0,v,\tau )=\pi (0,v,\tau )$$
(2.3)
$$\pi (1,v,\tau )=\pi (1,v,\tau )$$
(2.4)
* Collisions with the piston. At the piston $`y=Y(\tau )`$ we have

$`\pi (Y(\tau )0,v,\tau )`$ $`=`$ $`\pi (Y(\tau )0,2W(\tau )v,\tau )\mathrm{for}v<W(\tau )`$
$`\pi (Y(\tau )+0,v,\tau )`$ $`=`$ $`\pi (Y(\tau )+0,2W(\tau )v,\tau )\mathrm{for}v>W(\tau )`$ (2.5)
where $`v`$ represents the velocity after the collision and $`2W(\tau )v`$ that before the collision; here

$$W(\tau )=\frac{d}{d\tau }Y(\tau )$$
(2.6)
is the (deterministic) velocity of the piston.

It remains to describe the evolution of $`W(\tau )`$. Suppose the piston’s position at time $`\tau `$ is $`Y`$ and its velocity $`W`$. The piston is affected by the particles $`(y,v)`$ hitting it from the right (such that $`y=Y+0`$ and $`v<W`$) and from the left (such that $`y=Y0`$ and $`v>W`$). Accordingly, we define the density of the particles colliding with the piston (“density on the piston”) by

$$q(v,\tau ;Y,W)=\{\begin{array}{cc}\pi (Y+0,v,\tau )\hfill & \mathrm{if}v<W\hfill \\ \pi (Y0,v,\tau )\hfill & \mathrm{if}v>W\hfill \end{array}$$
(2.7)
* Piston’s velocity. The velocity $`W=W(\tau )`$ of the piston must satisfy the equation

$$_{\mathrm{}}^{\mathrm{}}(vW)^2\mathrm{sgn}(vW)q(v,\tau ;Y,W)𝑑v=0$$
(2.8)

We also remark that for $`\tau >0`$, when (2.5) holds,

$$W(\tau )=\frac{v\pi (Y0,v,\tau )𝑑v}{\pi (Y0,v,\tau )𝑑v}=\frac{v\pi (Y+0,v,\tau )𝑑v}{\pi (Y+0,v,\tau )𝑑v}$$

i.e. the piston’s velocity is the average of the nearby particle velocities on each side.

The system of (hydrodynamical) equations (H1)–(H4) is now closed and, given appropriate initial conditions, should completely determine the functions $`Y(\tau )`$, $`W(\tau )`$ and $`p(y,v,\tau )`$ for $`\tau >0`$. To specify the initial conditions, we set $`p(y,v,0)=\pi (y,v)`$ and $`Y(0)=0.5`$. The initial velocity $`W(0)`$ does not have to be specified, it comes “for free” as the solution of the equation (2.8) at time $`\tau =0`$. It is easy to check that the initial speed $`|W(0)|`$ will be smaller than $`v_{\mathrm{min}}`$, in fact $`W(0)0`$ as $`\epsilon _00`$ in (P5). Note that if the initial conditions at $`\tau =0`$ do not satisfy (2.3)–(2.5), there will be a discontinuity in $`p`$ as $`\tau 0`$ (see also Remark 4 below).

Equation (2.8) has a unique solution $`W`$ as long as the piston interacts with some gas particles on both sides, i.e. as long as

$$inf\{v:\pi (Y+0,v,\tau )>0\}sup\{v:\pi (Y0,v,\tau )>0\}$$

Indeed, the left hand side of (2.8) is a continuous and strictly monotonically decreasing function of $`W`$, and it takes both positive and negative values. The solution $`W(\tau )`$ may not be continuous in $`\tau `$, though. But if $`\pi (y,v,\tau )`$ is piecewise $`C^1`$ and has a finite number of discontinuity lines with positive slopes (as we require of $`\pi _0(y,v)`$ in Section 1), then $`W(\tau )`$ will be continuous and piecewise differentiable.

Remark 3. One can easily check that the total mass $`=\pi (y,v,\tau )𝑑v𝑑y`$ and the total kinetic energy $`2E=v^2\pi (y,v,\tau )𝑑v𝑑y`$ remain constant along any solution of our system of equations (H1)–(H4). Also, the mass in the left and right part of $`\mathrm{\Lambda }_L`$ separately remains constant. Equation (2.8) also preserves the total momentum of the gas $`v\pi (y,v,\tau )𝑑v𝑑y`$, but it changes due to collisions with the walls.

Remark 4. Previously, Lebowitz, Piasecki and Sinai \[LPS\] studied the piston dynamics under essentially the same initial conditions as our (P1)–(P5). They argued heuristically that the piston dynamics could be approximated by certain deterministic equations in the original (microscopic) variables $`x`$ and $`t`$. The deterministic equations found in \[LPS\] correspond to our (2.2)–(2.6) with obvious transformation back to the variables $`x,t`$, but our main equation (2.8) has a different counterpart in the context of \[LPS\], which reads

$$\frac{d}{dt}V(t)=a\left[_V^{\mathrm{}}(vV(t))^2\pi (Y0,v,t)𝑑v_{\mathrm{}}^V(vV(t))^2\pi (Y+0,v,t)𝑑v\right]$$
(2.9)
Here $`X=X(t)`$ and $`V=V(t)=\dot{X}(t)`$ denote the deterministic position and velocity of the piston and $`\pi (x,v,t)`$ the density of the gas (the constant $`a`$ appeared in (1.3)). We refer to \[LPS\] for more details and a heuristic derivation of (2.9). Since (2.9), unlike our (2.8), is a differential equation, the initial velocity $`V(0)`$ has to be specified separately, and it is customary to set $`V(0)=0`$. Alternatively, one can set $`V(0)=W(0)`$, see \[CLS\]. Equation (2.9) can be reduced to (2.8) in the limit $`L\mathrm{}`$ as follows. One can show (we omit details) that (2.9) is a dissipative equation whose solution with any (small enough) initial condition $`V(0)`$ converges to the solution of (2.8) during a $`t`$-time interval of length $`\mathrm{ln}L`$. That interval has length $`L^1\mathrm{ln}L`$ on the $`\tau `$ axis, and so it vanishes as $`L\mathrm{}`$, this is why we replace (2.9) with (2.8) and ignore the initial condition $`V(0)`$ when working with the thermodynamic variables $`\tau `$ and $`y`$. The equation (2.9) is not used in this paper.

We now describe the solution of our equations (H1)-(H4) in more detail. Assume that for some $`\tau >0`$ the gas density $`\pi (y,v,\tau )`$ satisfies the same requirements (P1)-(P4) as those imposed on the initial function $`\pi _0(y,v)`$ in Sect. 1, with constants $`D_1^{}`$, $`K_1^{}`$, $`c_1^{}`$, $`c_2^{}`$, $`v_1^{}`$, $`v_2^{}`$, $`v_{\mathrm{min}}^{}`$, $`v_{\mathrm{max}}^{}`$, $`\pi _{\mathrm{min}}^{}`$ and $`\pi _{\mathrm{max}}^{}`$, whose values are not essential, but are independent of $`\tau `$.

We also assume an analogue of (P5), but this one is not so straightforward, since the piston does not have to stay at the middle point $`y=0.5`$ at any time $`\tau >0`$. We require that

$$|Y(\tau )0.5|<\epsilon _0^{}$$
(2.10)
and for any point $`(y,v)`$ with $`v_{\mathrm{min}}^{}|v|v_{\mathrm{max}}^{}`$ there is another point $`(y_{},v_{})`$ “across the piston” (i.e. such that $`(yY(\tau ))(y_{}Y(\tau ))<0`$) satisfying

$$|y+y_{}1|<\epsilon _0^{},|v+v_{}|<\epsilon _0^{}$$
(2.11)
and

$$|\pi (y,v,\tau )\pi (y_{},v_{},\tau )|<\epsilon _0^{}$$
(2.12)
for some sufficiently small $`\epsilon _0^{}>0`$. Actually, the map $`(y,v)(y_{},v_{})`$, which we denote by $`R_\tau `$, is one-to-one and will be explicitly constructed below. The constant $`\epsilon _0^{}`$ here, just like $`\epsilon _0`$ in (P5), is assumed to be small enough, and moreover

$$\epsilon _0^{}<C_0^{}\epsilon _0$$
(2.13)
with some constant $`C_0^{}>0`$.

We now derive elementary but important consequences of the above assumptions. Since the density $`\pi (y,v,\tau )`$ vanishes for $`|v|<v_{\mathrm{min}}^{}`$, so does the function $`q(v,\tau ;Y,W)`$ defined by (2.7). Moreover, for all $`|W|<v_{\mathrm{min}}^{}`$, the function $`q(v,\tau ;Y,W)`$ will be independent of $`W`$, and so we can write it as $`q(v,\tau ;Y)`$. Also, equation (2.8) can be simplified: the factor sgn$`(vW)`$ can be replaced by sgn$`v`$. Then, expanding the square in (2.8) reduces it to a quadratic equation for $`W`$:

$$Q_0W^22Q_1W+Q_2=0$$
(2.14)
where

$$Q_0=\mathrm{sgn}vq(v,\tau ;Y)𝑑v$$
(2.15)
$$Q_1=v\mathrm{sgn}vq(v,\tau ;Y)𝑑v$$
(2.16)
$$Q_2=v^2\mathrm{sgn}vq(v,\tau ;Y)𝑑v$$
(2.17)
with $`Y=Y(\tau )`$. The integrals $`Q_0,Q_1,Q_2`$ have the following physical meaning:

$$mQ_0=m_Lm_R$$

$$mQ_1=p_Lp_R$$

$$mQ_2=2(e_Le_R)$$

where $`m_L,p_L,e_L`$ represent the total mass, momentum and energy of the incoming gas particles (per unit length) on the left hand side of the piston, and $`m_R,p_R,e_R`$ – those on the right hand side of it. The value $`Q_2`$ also represents the net pressure exerted on the piston by the gas as if the piston did not move. Of course, if $`Q_2(\tau )=0`$, then we must have $`W(\tau )=0`$, which agrees with (2.14).

Next, under the above requirements on $`\pi (y,v,\tau )`$, the function $`q(v,\tau ;Y)`$ is, in a certain sense, nearly symmetric in $`v`$ about $`v=0`$ (see \[CLS\] for details). This fact implies that $`Q_0`$ and $`Q_2`$ are small, more precisely

$$\mathrm{max}\{|Q_0|,|Q_2|\}C^{}\epsilon _0$$
(2.18)
where $`C^{}>0`$ is a constant depending on the parameters $`D_1^{},K_1^{}`$, etc., but not on $`\epsilon _0`$. At the same time, the assumption (P3) guarantees that

$$Q_1Q_{1,\mathrm{min}}>0$$
(2.19)
where $`Q_{1,\mathrm{min}}`$ is a constant depending on $`\pi _{\mathrm{min}}^{},v_1^{},v_2^{}`$, etc., but not on $`\epsilon _0`$.

If $`\epsilon _0`$ is small enough, there is a unique root of the quadratic polynomial (2.14) on the interval $`(v_{\mathrm{min}}^{},v_{\mathrm{min}}^{})`$, which corresponds to the only solution of (2.8). Since this root is smaller, in absolute value, than the other root of (2.14), it can be expressed by

$$W(\tau )=\frac{Q_1\sqrt{Q_1^2Q_0Q_2}}{Q_0}$$
(2.20)
where the sign before the radical is “$``$”, not “$`+`$”. Of course, (2.20) applies whenever $`Q_00`$, while for $`Q_0=0`$ we simply have $`W(\tau )=Q_2/2Q_1`$.

Eqs. (2.18)-(2.20) imply an upper bound on the piston velocity: $`|W(\tau )|B^{}\epsilon _0`$ for some constant $`B^{}>0`$ depending on $`D_1^{},K_1^{}`$, etc., but not on $`\epsilon _0`$. A similar bound holds for the piston acceleration $`A(\tau )=\dot{W}(\tau )`$, since

$$A(\tau )=\frac{(dQ_0/d\tau )W^22(dQ_1/d\tau )W+(dQ_2/d\tau )}{2(Q_1Q_0W)}$$

and $`|dQ_i/d\tau |=|(dQ_i/dY)W|`$const$`\epsilon _0`$, see \[CLS\] for more details.

Next we consider the evolution of a point $`(y,v)`$ in the domain $`G:=\{(y,v):0y1\}`$ under the rules (H1)–(H3), i.e. as it moves freely with constant velocity and collides elastically with the walls and the piston. Denote by $`(y_\tau ,v_\tau )`$ its position and velocity at time $`\tau 0`$. Then (H1) translates into $`\dot{y}_\tau =v_\tau `$ and $`\dot{v}_\tau =0`$ whenever $`y_\tau \{0,1,Y(\tau )\}`$, (H2) becomes $`(y_{\tau +0},v_{\tau +0})=(y_{\tau 0},v_{\tau 0})`$ whenever $`y_{\tau 0}\{0,1\}`$, and (H3) gives

$$(y_{\tau +0},v_{\tau +0})=(y_{\tau 0},2W(\tau )v_{\tau 0})$$
(2.21)
whenever $`y_{\tau 0}=Y(\tau )`$. Note that (2.21) corresponds to a special case of the mechanical collision rules (1.1)–(1.2) with $`\epsilon =0`$ (equivalently, $`m=0`$). Hence the point $`(y,v)`$ moves in $`G`$ as if it was a gas particle with zero mass.

The motion of points in $`(y,v)`$ is described by a one-parameter family of transformations $`F^\tau :GG`$ defined by $`F^\tau (y_0,v_0)=(y_\tau ,v_\tau )`$ for $`\tau >0`$. We will also write $`F^\tau (y_\tau ,v_\tau )=(y_0,v_0)`$. According to (H1)–(H3), the density $`\pi (y,v,\tau )`$ satisfies a simple equation

$$\pi (y_\tau ,v_\tau ,\tau )=\pi (F^\tau (y_\tau ,v_\tau ),0)=\pi _0(y_0,v_0)$$
(2.22)
for all $`\tau 0`$. Also, it is easy to see that for each $`\tau >0`$ the map $`F^\tau `$ is one-to-one and preserves area, i.e. $`\mathrm{det}|DF^\tau (y,v)|=1`$.

Now, because of (P4), the initial density $`\pi _0(y,v)`$ can only be positive in the region

$$G^+:=\{(y,v):0y1,v_{\mathrm{min}}|v|v_{\mathrm{max}}\}$$

hence we will restrict ourselves to points $`(y,v)G^+`$ only. At any time $`\tau >0`$, the images of those points will be confined to the region $`G^+(\tau ):=F^\tau (G^+)`$. In particular, $`\pi (y,v,\tau )=0`$ for $`(y,v)G^+(\tau )`$.

The map $`R_\tau :(y,v)(y_{},v_{})`$ involved in (2.11) and (2.12) can now be defined as $`R_\tau =F^\tau R_0F^\tau `$, where $`R_0(y,v)=(1y,v)`$ is a simple reflection “across the piston” at time $`\tau =0`$.

We now make an important observation. If a fast point $`(y_\tau ,v_\tau )`$ collides with a slow piston, $`|W(\tau )||v_\tau |`$, they cannot recollide too soon: the point must travel to a wall, bounce off it, and then travel back to the piston before it hits it again.

Therefore, as long as (P1)–(P4) hold, the collisions of each moving point $`(y_\tau ,v_\tau )G^+(\tau )`$ with the piston occur at well separated time moments, which allows us to effectively count them. For $`(x,v)G^+`$

$$N(y,v,\tau )=\mathrm{\#}\{s(0,\tau ):y_s=Y(s),v_sW(s)\}$$

is the number of collisions of the point $`(y,v)`$ with the piston during the interval $`(0,\tau )`$. For each $`\tau >0`$, we partition the region $`G^+(\tau )`$ into subregions

$$G_n^+(\tau ):=\{F^\tau (y,v):(y,v)G^+\&N(y,v,\tau )=n\}$$

so $`G_n^+(\tau )`$ is occupied by the points that at time $`\tau `$ have experienced exactly $`n`$ collisions with the piston during the interval $`(0,\tau )`$.

Now, for each $`n1`$ we define $`\tau _n>0`$ to be the first time when a point $`(y_\tau ,v_\tau )G^+(\tau )`$ experiences its $`(n+1)`$-st collision with the piston, i.e.

$$\tau _n=sup\{\tau >0:G_{n+1}^+(\tau )=\mathrm{}\}$$

In particular, $`\tau _1>0`$ is the earliest time when a point $`(y_\tau ,v_\tau )G^+(\tau )`$ experiences its first recollision with the piston. Hence, no recollisions occur on the interval $`[0,\tau _1)`$, and we call it the zero-recollision interval. Similarly, on the interval $`(\tau _1,\tau _2)`$ no more than one recollision with the piston is possible for any point, and we call it the one-recollision interval.

The time moment $`\tau _{}`$ mentioned in Theorem 1.1 is the earliest time when a point $`(y_\tau ,v_\tau )G^+(\tau )`$ either experiences its third collision with the piston or has its second collision with the piston given that the first one occurred after $`\tau _1`$. Hence, $`\tau _{}\tau _2`$, and actually $`\tau _{}`$ is very close to $`\tau _2`$, see below.

The following theorem summarizes the properties of the solutions of the hydrodynamical equations (H1)–(H4).

###### Theorem 2.1 (\[CLS\])

Let $`T>0`$ be given. If the initial density $`\pi _0(y,v)`$ satisfies (P1)–(P5) with a sufficiently small $`\epsilon _0`$, then

* the solution of our hydrodynamical equations (H1)–(H4) exists and is unique on the interval $`(0,T)`$;
* the density $`\pi (y,v,\tau )`$ satisfies conditions similar to (P1)–(P4) for all $`0<\tau <T`$, it also satisfies (2.10)–(2.13);
* The piston velocity and acceleration remain small, $`|W(\tau )|=O(\epsilon _0)`$ and $`|A(\tau )|=O(\epsilon _0)`$;
* we have $`|\tau _kk/v_{\mathrm{max}}|=O(\epsilon _0)`$ for all $`1k<Tv_{\mathrm{max}}`$, and if $`Tv_{\mathrm{max}}>2`$, then also $`|\tau _{}\tau _2|=O(\epsilon _0)`$.

###### Corollary 2.2

If $`\epsilon _0=0`$, so that the initial density $`\pi _0(y,v)`$ is completely symmetric about the piston, the solution is trivial: $`Y(\tau )0.5`$ and $`W(\tau )0`$ for all $`\tau >0`$.

Lastly, we demonstrate the reason for our assumption that all the discontinuity curves of the initial density $`\pi _0(y,v)`$ must have positive slopes. It would be quite tempting to let $`\pi _0(y,v)`$ have more general discontinuity lines, e.g. allow it be smooth for $`v_{\mathrm{min}}<|v|<v_{\mathrm{max}}`$ and abruptly drop to 0 at $`v=v_{\mathrm{min}}`$ and $`v=v_{\mathrm{max}}`$. The following example shows why this is not acceptable.

Example. Suppose the initial density $`\pi _0(y,v)`$ has a horizontal discontinuity line $`v=v_0`$ (say, $`v_0=v_{\mathrm{min}}`$ or $`v_0=v_{\mathrm{max}}`$). After one interaction with the piston the image of this discontinuity line can oscillate up and down, due to the fluctuations of the piston acceleration (Fig. 1). As time goes on, this oscillating curve will “travel” to the wall and come back to the piston, experiencing some distortions on its way, caused by the differences in velocities of its points (Fig. 1). When this curve comes back to the piston again, it may well have “turning points” where its tangent line is vertical, or even contain vertical segments of positive length. This produces unwanted singularities or even discontinuities of the piston velocity and acceleration. The same phenomena can also occur when a discontinuity line of the initial density $`\pi _0(y,v)`$ has a negative slope.

## 3 Sketch of the argument

Our proof of Theorem 1.1 is based on large deviation estimates for the Poisson random variable:

###### Lemma 3.1 (\[CLS\])

Let $`X`$ be a Poisson random variable with parameter $`\lambda >0`$. For any $`b>0`$ there is a $`c>0`$ such that for all $`0<B<b\sqrt{\lambda }`$ we have

$$P(|X\lambda |>B\sqrt{\lambda })2e^{cB^2}$$

This shows that the probabilities of large deviations rapidly decay, as they do for the Gaussian distribution.

The principal step in our proof of Theorem 1.1 is the velocity decomposition scheme described next. Let $`V_L(t,\omega )`$ be the velocity of the piston at time $`t0`$ for a random configuration of particles $`\omega \mathrm{\Omega }_L`$. Let $`\mathrm{\Delta }t>0`$ be a small time increment. Then the law of elastic collision (1.1) implies

$$V_L(t+\mathrm{\Delta }t,\omega )=(1\epsilon )^kV_L(t,\omega )+\epsilon \underset{j=1}{\overset{k}{}}(1\epsilon )^{kj}v_j$$
(3.1)
Here $`k=k(t,\mathrm{\Delta }t,\omega )`$ is the number of particles colliding with the piston during the time interval $`(t,t+\mathrm{\Delta }t)`$, and $`v_j`$ are their velocities numbered in the order in which the particles collide.

We rearrange the formula (3.1) as follows:

$$V_L(t+\mathrm{\Delta }t,\omega )=(1\epsilon k)V_L(t,\omega )+\epsilon \underset{j=1}{\overset{k}{}}v_j+\chi ^{(1)}+\chi ^{(2)}$$
(3.2)
where

$$\chi ^{(1)}=V_L(t,\omega )[(1\epsilon )^k1+\epsilon k]$$

and

$$\chi ^{(2)}=\epsilon \underset{j=1}{\overset{k}{}}v_j[(1\epsilon )^{kj}1]$$

Let us assume that the fluctuations of the velocity $`V_L(s,\omega )`$ on the interval $`(t,t+\mathrm{\Delta }t)`$, are bounded by some quantity $`\delta V`$:

$$\underset{s(t,t+\mathrm{\Delta }t)}{sup}|V_L(s,\omega )V_L(t,\omega )|\delta V$$
(3.3)
Consider two regions on the $`x,v`$ plane:

$$D_1=\{(x,v):\frac{vV_L(t,\omega )(\mathrm{sgn}v)\delta V}{xX_L(t,\omega )}<\frac{1}{\mathrm{\Delta }t},v_{\mathrm{min}}<|v|<v_{\mathrm{max}}\}$$
(3.4)
and

$$D_2=\{(x,v):\frac{vV_L(t,\omega )+(\mathrm{sgn}v)\delta V}{xX_L(t,\omega )}<\frac{1}{\mathrm{\Delta }t},v_{\mathrm{min}}<|v|<v_{\mathrm{max}}\}$$
(3.5)
Each of them is a union of two trapezoids $`D_i=D_i^+D_i^{}`$, $`i=1,2`$, where $`D_i^{}`$ denotes the upper and $`D_i^+`$ the lower trapezoid, see Fig. 2.

Note that $`D_1D_2`$. The bound (3.3) implies that all the particles in the region $`D_1`$ necessarily collide with the piston during the time interval $`(t,t+\mathrm{\Delta }t)`$. Moreover, the trajectory of every point $`(x,v)D_1`$ hits the piston within time $`\mathrm{\Delta }t`$. The bound (3.3) also implies that all the particles actually colliding with the piston during the interval $`(t,t+\mathrm{\Delta }t)`$ are contained in $`D_2`$.

Let us denote by $`k_r^\pm `$ the number of particles in the regions $`D_r^\pm `$ for $`r=1,2`$ at time $`t`$. We also denote by $`k^{}`$ the number of particles actually colliding with the piston “on the left”, and by $`k^+`$ that number “on the right” (of course, $`k^{}+k^+=k`$). Due to the above observations, $`k_1^\pm k^\pm k_2^\pm `$.

Now, suppose that $`t+\mathrm{\Delta }t<\tau _1L`$. Then we show that for typical configurations $`\omega `$ the particles in each domain $`D_r`$, $`r=1,2`$, have never collided with the piston before. Therefore, their number, $`k_r^\pm `$, $`r=1,2`$, satisfies the laws of Poisson distribution, in particular, the large deviation estimate in Lemma 3.1 applies. This gives the bound (for typical $`\omega `$)

$$\lambda _1^\pm \mathrm{\Delta }k_1^\pm k^\pm \lambda _2^\pm +\mathrm{\Delta }k_2^\pm $$
(3.6)
where

$$\lambda _r^\pm =E(k_r^\pm )=L^2_{F_L^t(D_r^\pm )}p_L(x,v)𝑑x𝑑v$$

and $`F_L^t`$ corresponds to the action of $`F^\tau =F^{t/L}`$ in the original time-space coordinates $`x,t`$. The deviations $`\mathrm{\Delta }k_r^\pm `$ in (3.6) can be adjusted by using Lemma 3.1. The difference $`\lambda _2^\pm \lambda _1^\pm `$ is estimated by

$$\lambda _2^\pm \lambda _1^\pm =L^2_{F_L^t(D_2^\pm D_1^\pm )}p_L(x,v)𝑑x𝑑v\mathrm{const}L^2\delta V\mathrm{\Delta }t$$

By putting all these estimates together we get tight bounds on $`k`$ in (3.2). Similarly we get bounds on $`_{j=1}^kv_j`$ in (3.2). The following is the final result of this analysis:

$$V_L(t+\mathrm{\Delta }t,\omega )V_L(t,\omega )=𝒟(t,\omega )\mathrm{\Delta }t+\chi _3$$
(3.7)
Here

$$𝒟(t,\omega )=a[Q_0V_L^2(t,\omega )2Q_1V_L(t,\omega )+Q_2]$$
(3.8)
and $`Q_0,Q_1,Q_2`$ are defined similarly to (2.15)-(2.17), in which $`Y(\tau )`$ must be replaced by the actual piston position $`X_L(t,\omega )/L`$. The error term $`\chi _3`$ in (3.7) is bounded by

$$|\chi _3|\mathrm{const}\frac{\mathrm{ln}L\sqrt{\mathrm{\Delta }t}}{L}$$
(3.9)
which corresponds to Brownian motion-type random fluctuations.

The term $`𝒟(t,\omega )`$ in (3.7) represents the main (“deterministic”) force acting on the piston. The term $`\chi _3`$ describes random fluctuations of that force. When the piston velocity stabilizes, then the main force $`𝒟`$ should vanish, and an “equilibrium” velocity $`\overline{V}_L(t,\omega )`$ will be established. The latter is the root of the equation $`𝒟(t,\omega )=0`$, which is

$$\overline{V}_L(t,\omega )=\frac{Q_1\sqrt{Q_1^2Q_0Q_2}}{Q_0}$$
(3.10)
The reason why $`V_L(t,\omega )`$ converges to $`\overline{V}_L`$ is that $`𝒟`$ is almost proportional to $`\overline{V}_LV_L`$, i.e. $`0<E_1<𝒟/(\overline{V}_LV_L)<E_2<\mathrm{}`$ for some constants $`E_1,E_2`$. In fact, $`\overline{V}_L(t,\omega )`$ is a very slowly changing function of $`t`$, whose derivative is small: $`|d\overline{V}_L(t,\omega )/dt|\mathrm{const}L^1\epsilon _0`$. As a result, $`V_L`$ will always stay close to $`\overline{V}_L`$, more precisely

$$|V_L(t,\omega )\overline{V}_L(t,\omega )|<\mathrm{const}L^1\mathrm{ln}L$$
(3.11)
on the entire zero-recollision interval $`0<t<\tau _1L`$.

Now, the piston coordinate $`Y_L(\tau ,\omega )=X_L(\tau L,\omega )/L`$ is the solution of the differential equation

$$\dot{Y}_L=V_L=\overline{V}_L+\chi _4$$

where $`|\chi _4|<\mathrm{const}L^1\mathrm{ln}L`$ by (3.11). On the other hand, the deterministic piston coordinate $`Y(\tau )`$ is the solution of the equation $`\dot{Y}=W`$, and both $`\overline{V}`$ and $`W`$ are given by the same radical expression, cf. (2.20) and (3.10). Lastly, a simple application of Gronwall’s inequality completes the proof of Theorem 1.1 on the zero-recollision interval $`(0,\tau _1)`$.

The proof on the one-recollision interval $`(\tau _1,\tau _{})`$ goes along the same lines. One major difference is that the number of particles $`k_r^\pm `$, $`r=1,2`$, in the domain $`D_r^\pm `$ constructed in the velocity decomposition scheme is no longer a Poisson variable, so Lemma 3.1 does not apply directly.

To handle this new situation, we pull the domain $`D_r^\pm `$ back in time, as we did before. But now that pullback involves one interaction with the piston (corresponding to the first collision of the particles in $`D_r^\pm `$ with the piston, which occurs during the zero-recollision interval $`0<t<\tau _1L`$).

Since the piston position and velocity at the moment of that first collision are random, the preimage of $`D_r^\pm `$ will be a random domain. Its shape will depend on the piston velocity $`V(t,\omega )`$ during the zero-recollision interval $`0<t<\tau _1L`$. We observe that the boundary of the preimage of $`D_r^\pm `$ is described by a random, yet Hölder continuous function, and its Hölder exponent is $`0.5`$ due to (3.9). Then we pick a small $`d>0`$ and construct a $`d`$-dense set in the space of all Hölder continuous functions in the spirit of a work by Kolmogorov and Tihomirov \[KT\]. The elements of that $`d`$-dense set can be used to construct a finite collection of (nonrandom) domains, so that one of them will approximate the (random) preimage of our $`D_r^\pm `$ (we need to select the small $`d>0`$ carefully to ensure sufficient accuracy of the approximation). Now the number of particles in our random domain (the preimage of $`D_r^\pm `$) can be approximated by the number of particles in the corresponding nonrandom domain. The latter has Poisson distribution, and finally we can apply Lemma 3.1. This trick gives necessary estimates on $`k_r^\pm `$.

A full proof of Theorem 1.1 is given in \[CLS\]. At present, we do not know if this theorem can be extended beyond the critical time $`\tau _{}`$, this is an open question. Some other open problems are discussed in the next section.

## 4 Discussion and open problems

1. The main goal of this work is to prove that under suitable initial conditions random fluctuations in the motion of a massive piston are small and vanish in the thermodynamic limit. We are, however, able to control those fluctuations effectively only as long as the surrounding gas particles can be described by a Poisson process, i.e. during the zero-recollision interval $`0<\tau <\tau _1`$. In that case the random fluctuations are bounded by const$`L^1\mathrm{ln}L`$, see Remark 2 after Theorem 1.1. Up to the logarithmic factor, this bound is optimal, see \[CL\] and earlier estimates by Holley \[H\], Dürr et al. \[DGL\].

During the one-recollision interval $`\tau _1<\tau <\tau _2`$, the situation is different. The probability distribution of gas particles that have experienced one collision with the piston is no longer a Poisson process, it has intricate correlations. We are only able to show that random fluctuations remain bounded by $`L^{1/7}`$, see again Remark 2. Perhaps, our bound is far from optimal, but our numerical experiments reported in \[CL\] show that random fluctuations indeed grow during the one-recollision interval.

We have tested numerically whether random fluctuations remained small after more than one recollision, i.e. at times $`\tau >\tau _2`$. We found that for some initial $`\pi _0`$ they actually increased very rapidly, and we conjectured that the rate of increase was exponential in $`\tau `$. We found, indeed, that at times $`\tau \mathrm{log}L`$ the fluctuations became large even on a macroscopic scale, and then many unexpected phenomena occurred \[CL\].

Interestingly, the exponential growth of random fluctuations seems to be related to the instability of our hydrodynamical equations. We found that small perturbations of the initial density $`\pi _0`$ can grow exponentially in $`\tau `$ under certain conditions, matching the growth of random fluctuations of the piston motion in the mechanical model. We refer the reader to \[CL\] for further discussion and to our work in progress \[CCLP\].

2. It is clear that in our model recollisions of gas particles with the piston have a very “destructive” effect on the dynamics in the system. However, we need to distinguish between two types of recollisions.

We say that a recollision of a gas particle with the piston is long if the particle hits a wall $`x=0`$ or $`x=L`$ between the two consecutive collisions with the piston. Otherwise a recollision is said to be short. Long recollisions require some time, as the particle has to travel all the way to a wall, bounce off it, and then travel back to the piston before it hits it again. Short recollisions can occur in rapid succession.

We have imposed the velocity cut-off (P4) in order to avoid any recollisions for at least some initial period of time (which we call the zero-recollision interval). More precisely, the upper bound $`v_{\mathrm{max}}`$ guarantees the absence of long recollisions. Without it, we would have to deal with arbitrarily fast particles that dash between the piston and the wall very many times in any interval $`(0,\tau )`$. On the other hand, the lower bound $`v_{\mathrm{min}}`$ was assumed to exclude short recollisions.

There are good reasons to believe, though, that short recollisions may not be so destructive for the piston dynamics. Indeed, let a particle experience two or more collisions with the piston in rapid succession (i.e. without hitting a wall in between). This can occur in two cases: (i) the particle’s velocity is very close to that of the piston, or (ii) the piston’s velocity changes very rapidly. The latter should be very unlikely, since the deterministic acceleration of the piston is very small, cf. Theorem 2.1c. In case (i), the recollisions should have very little effect on the velocity of the piston according to the rule (1.1), so that they may be safely ignored, as it was done already in earlier studies \[H, DGL\].

We therefore expect that our results can be extended to velocity distributions without a cut-off from zero, i.e. allowing $`v_{\mathrm{min}}=0`$.

3. In our paper, $`L`$ plays a dual role: it parameterizes the mass of the piston ($`ML^2`$), and it represents the length of the container ($`0xL`$). This duality comes from our assumption that the container is a cube.

However, our model is essentially one-dimensional, and the mass of the piston $`M`$ and the length of the interval $`0xL`$ can be treated as two independent parameters. In particular, we can assume that the container is infinitely long in the $`x`$ direction (so, that $`L`$ is infinite), but the mass of the piston is still finite and given by $`ML^2`$. In this case there are no recollisions with the piston, as long as its velocity remains small. Hence, our zero-recollision interval is effectively infinite. As a result, Theorem 1.1 can be extended to arbitrarily large times. Precisely, for any $`T>0`$ we can prove the convergence in probability:

$$P\left(\underset{0\tau T}{sup}|Y_L(\tau ,\omega )Y(\tau )|C_T\mathrm{ln}L/L\right)1$$

and

$$P\left(\underset{0\tau T}{sup}|W_L(\tau ,\omega )W(\tau )|C_T\mathrm{ln}L/L\right)1$$

as $`L\mathrm{}`$, where $`C_T>0`$ is a constant and $`Y(\tau )`$ and $`W(\tau )=\dot{Y}(\tau )`$ are the solutions of the hydrodynamical equations described in Section 2.

4. Along the same lines as above, we can assume that the container is $`d`$-dimensional with $`d3`$. Then the mass of the piston and the density of the particles are proportional to $`L^{d1}`$ rather than $`L^2`$.

When $`d`$ is large, the gas particles are very dense on the $`x,v`$ plane. This leads to a much better control over fluctuations of the particle distribution and the piston trajectory. As a result, Theorem 1.1 can be extended to the $`k`$-recollision interval $`(\tau _k,\tau _{k+1})`$, where $`k1`$ depends on $`d`$. It can be shown that for any $`k1`$ there is a $`d_k3`$ such that for all $`dd_k`$ the convergence (1.10) and (1.11) holds with $`\tau _{}=\tau _k`$. Therefore, a higher dimensional piston is more stable than a lower dimensional one.

It would be interesting to investigate other modifications of our model that lead to more stable regimes. For example, let the initial density $`\pi _0(y,v)`$ of the gas depend on the factor $`a=\epsilon L^2`$ in such a way that $`\pi _0(y,v)=a^1\rho (y,v)`$, where $`\rho (y,v)`$ is a fixed function. Then the particle density grows as $`a0`$. This is another way to increase the density of the particles, but without changing the dimension. One may expect a better control over random fluctuations in this case, too.

Acknowledgements. N. Chernov was partially supported by NSF grant DMS-9732728. J. Lebowitz was partially supported by NSF grant DMR-9813268 and by Air Force grant F49620-01-0154. Ya. Sinai was partially supported by NSF grant DMS-9706794. This work was completed when N. C. and J. L. stayed at the Institute for Advanced Study with partial support by NSF grant DMS-9729992.


format: text

text:
# 1 Introduction

## 1 Introduction

The Merton framework \[Merton (1974)\] provides an attractive approach to credit risk, relating default probabilities for corporations to their stock prices. The default process is usually modeled by assuming that the corporate assets undergo a simple random walk and the first time the assets fall below a threshold $`T`$ default occurs \[Black and Cox (1976), Longstaff and Schwartz (1995), Leland and Toft (1996), etc.\]. A company may have several types of debt, type $`i`$ contributing $`D_i`$ to a total debt $`D`$ ($`_iD_i=D`$). The debt holders weighted, by debt fraction, average recovery fraction (i.e., total recovery fraction) $`R`$ is equal to $`T/D`$. If default occurred when the assets first passed a threshold equal to $`D`$ then the total recovery fraction would be one. However, the total recovery fraction is typically considerably less than one and its precise value is not known until after the default actually occurs. Hence the default threshold $`T`$ or equivalently the total recovery fraction $`R`$ should be treated as a random variable. Recently first passage models have been generalized to include a fluctuating recovery \[Pan (2001), Finkelstein, et. al. (2002)\]. Expected default probabilities and par spreads $`c_i`$ for credit default swaps have been computed using a first passage model with a fluctuating total recovery fraction $`R`$. The expected default probability, $`P_D(t)`$, for example, is calculated by taking the usual first passage time expression $`P_D(t|R)`$ and taking its expected value over possible values for $`R`$.

Since the recovery fraction for the $`i`$’th type of debt, $`R_i`$ is not equal to $`R`$ it is usually treated as a fixed independent quantity in the calculation of par spread, $`c_i`$ for a default swap on corporate bonds which form the $`i`$’th debt type111For an excellent discussion on the treatment of recovery in various classes of models for credit risk see Altman et. al. (2002).. This assumption neglects the empirical observation that recovery fractions for different classes of bonds typically depend strongly on the total recovery, and there is considerable uncertainty regarding the expected recovery for each class. We argue that the $`R_i`$’s are actually functions of $`R`$ and the main purpose of this paper is to study the implications of this relationship for the pricing of credit default swaps on different subordination classes of bonds. Clearly the $`R_i`$ cannot be completely independent of $`R`$. For example, since

$$\underset{i}{}R_iD_i=RD,$$
(1)
if $`R`$ and the $`R_i`$ go between zero and one then $`R=0`$ implies that all of the $`R_i`$ are zero and $`R=1`$ then all of the $`R_i=1`$.

In a simple scenario where debt of type $`i`$ is subordinate to debt of type $`i1`$ we find the functional dependence of the $`R_i`$ on $`R`$ and use it to compute the par credit default swap spreads, $`c_i`$. Since the default probability $`P_D(t|R)`$ depends on $`R`$ and the recovery fractions $`R_i`$ now also depend on $`R`$ there are correlations between these two quantities which play an important role. We examine the significance of these correlations and find that they cause a substantial decrease in default swap par spreads. The effect is very dramatic for the most senior debt.

Debt cushion for debt of type $`i`$ refers to the proportion of total debt occupied by those junior to it \[Van de Castle and Keisman (1999)\]. The simple scenario we discuss in this paper relates recovery fractions $`R_i`$ to $`R`$ in a way that incorporates the impact of debt cushion on the pricing of credit default swap spreads and we find that expected recovery rates increase substantially as the debt cushion increases.

## 2 Credit Default Swaps in a First Passage Model With Fluctuating Default Threshold

We take the corporate assets $`V_t`$ to undergo the Ito process,

$$\frac{dV_t}{V_t}=\sigma dW_t+\mu dt,$$
(2)
where,

$$E\left[(dW_t)^2\right]=dt$$
(3)
and $`\mu `$ is the coefficient of a drift term. The stochastic process for $`\mathrm{log}(V_t)`$ is obtained using Ito’s lemma

$$d\left(\mathrm{log}V_t\right)=\sigma dW_t+\left(\mu \frac{\sigma ^2}{2}\right)dt,$$
(4)
where $`\mathrm{log}`$ denotes the natural logarithm. Integrating over time

$$V_t=V_0\mathrm{exp}\left(\sigma W_t+\left(\mu \frac{\sigma ^2}{2}\right)t\right).$$
(5)
In this paper, we set $`\mu =0`$ so that the expected value, $`E[V_t]`$ is independent of time \[Pan (2001)\].222For the purpose of pricing credit default swaps, one should use the risk-neutral measure $`dV=rV_tdtCdt+\sigma dW_t`$ if the answer to the delicate question of $`V_t`$ being a traded asset is affirmative. Here, $`r`$ is the risk-free interest rate and $`C`$ arises from dividends and interest payments made on the debt. In this article, we drop the drift terms $`r`$ and $`C`$ in order to concentrate on the effects of debt subordination and debt cushion on the pricing of CDS. Default occurs if the assets $`V_t`$ fall below a threshold $`T`$. If the total corporate debt is $`D`$, the average recovery fraction weighted by debt fraction (i.e., total recovery fraction) is $`R=T/D`$. Because the total recovery fraction is not known at the initial time, the default threshold $`T`$ or equivalently the total recovery fraction $`R`$ is taken to be a random variable with probability distribution $`P(R)`$. The expected survival probability, $`P_S(t)`$, for the fluctuating default threshold case results from weighting the standard (i.e., fixed default threshold) first passage time expression with the probability distribution $`P(R)`$. The survival condition is $`V_t>T`$ which implies that,

$`W_t{\displaystyle \frac{\sigma }{2}}t>{\displaystyle \frac{1}{\sigma }}\mathrm{log}\left({\displaystyle \frac{RD}{V_0}}\right).`$ (6)
The survival probability can be deduced from the above condition since it simply leads to a constant drift Brownian motion with an absorbing barrier. Introducing the convenient notation to signify expectations of a quantity $`f(R)`$ over the recovery probability density function

$$f(R)=_0^1𝑑RP(R)f(R),$$
(7)
the expected survival probability is

$$P_S(t)=P_S(t|R)$$
(8)
where

$$P_S(t|R)=\mathrm{\Phi }\left(\frac{B(R)}{\sqrt{t}}\frac{\sigma \sqrt{t}}{2}\right)\mathrm{exp}\left(\sigma B(R)\right)\mathrm{\Phi }\left(\frac{B(R)}{\sqrt{t}}\frac{\sigma \sqrt{t}}{2}\right).$$
(9)
In equation (9)

$$B(R)=\frac{1}{\sigma }\mathrm{log}\left(\frac{V_0}{DR}\right)$$
(10)
and $`\mathrm{\Phi }`$ is the cumulative normal distribution,

$$\mathrm{\Phi }(a)=\frac{1}{\sqrt{2\pi }}_{\mathrm{}}^a𝑑x\mathrm{exp}\left(\frac{x^2}{2}\right).$$
(11)
Although there have been reports of recovery rates greater than unity, such events are rare and untypical. Hence, we take the upper limit in the range of integration in equation (7) to be $`R=1`$. When $`V_0/D`$ is significantly greater than unity this causes an unrealistically large suppression of default probabilities at small times. It is straightforward to extend the results presented here to allow for $`R>1`$.

The credit default swap par spread $`c_i`$ for a particular type of debt labelled by $`i`$ can be found by equating the expected loss due to the firm defaulting with the credit default swap payments, which are assumed to be made continuously333Equation (12) can be easily generalized to spread payments that are made discretely.. We have

$`c_i={\displaystyle \frac{\left(1R_i(R)\right)\left(1P_S(0|R)_0^t𝑑s\frac{P_S(s|R)}{s}e^{\widehat{r}(s)s}\right)}{_0^t𝑑sP_S(s|R)e^{\widehat{r}(s)s}}},`$ (12)
where $`\widehat{r}(s)`$ is the spot rate of term $`s`$.

In the remainder of this section, we consider a simple scenario for the recovery rates pertinent to different classes of debt at the point of default. Consider $`N`$ different classes of debts

$`D_i,\mathrm{\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}1}iN`$ (13)
in the descending order of seniority such that $`D_1`$ is the most senior. We have the following constraints on the debts:

$`{\displaystyle \underset{i=1}{\overset{N}{}}}D_i=D,`$ (14)
$`{\displaystyle \underset{i=1}{\overset{N}{}}}R_iD_i=RD.`$ (15)
Under the current U.S. bankruptcy legislation, assets of a bankrupt firm are distributed to its creditors according to the Absolute Priority Rule \[Gupton and Stein (2002)\]. Senior debt holders are able to have a claim on the remaining assets before the junior holders can do so. However, in practice the actual recovery rates may depend on a “plan” agreed upon by the claimants. In this article, we apply the Absolute Priority Rule in its strictest sense. We assume that senior holders, when given the chance, are able to claim up to the full recovery rate at which point the next senior holder is able to stake a claim. For example, the most senior holder’s recovery rate initially goes as $`R_1=RD/D_1`$ then caps at $`1`$. The next senior debt holder is unable to recover any amount of the asset until $`R=D_1/D`$, then he recovers $`(RDD_1)/D_2`$ until the recovery rate caps at $`1`$. Repeating this argument, one can show that for the $`i`$’th subordinate, the recovery fraction can be expressed as

$`R_i(R)=\alpha _i(R)\left[\mathrm{\Theta }\left(\alpha _i(R)\right)\mathrm{\Theta }\left(\alpha _i(R)1\right)\right]+\mathrm{\Theta }\left(\alpha _i(R)1\right),`$ (16)
$`\alpha _i(R)={\displaystyle \frac{D}{D_i}}\left(R{\displaystyle \underset{j=1}{\overset{i1}{}}}(D_j/D)\right),`$
where $`1iN`$ and $`R[0,1]`$. $`\mathrm{\Theta }`$ is the step function defined in the following manner:

$`\mathrm{\Theta }(x)=\{\begin{array}{cc}1\hfill & \text{if }x0\hfill \\ 0\hfill & \text{otherwise.}\hfill \end{array}`$ (19)
Obviously, the general expression for the credit default swap par spread $`c_i`$ given in equation (12) can accommodate any form of the recovery rate as a function of the total recovery rate on total debt. The scenario we consider with the recovery rates depending only on the seniority of the debt and the level of debt cushion should prove useful in a general framework for pricing credit default swaps.

## 3 Numerical Results

The total recovery rate for a company is correlated with the level of default activity in the market and is dependent on numerous macroeconomic as well as company specific factors. In this paper, we only concentrate on the effect of seniority on the recovery rates $`R_i`$. We take the total recovery rate to follow the lognormal probability distribution

$`P(R)={\displaystyle \frac{6.48933\times 10^2}{R^{9.20164}}}\mathrm{exp}\left({\displaystyle \frac{50}{9}}(\mathrm{log}(R))^2\right),`$ (20)
which was fit to recovery data from non-financial firms that defaulted from 1987 to 1997 \[Finkelstein, et. al. (2002)\]. Figure 1 plots $`P(R)`$ in equation (20) as a function of $`R`$.

We consider a firm with initial asset to debt ratio of $`V_0/D=2`$, asset volatility $`\sigma =0.4`$ and capital structure composed of three types of debt with, $`D_1/D=0.5`$, $`D_2/D=0.1`$ and $`D_3/D=0.4`$. We have chosen the debt cushion for debt of type $`1`$ to be $`50\%`$ so that its average recovery rate of $`88\%`$ is significantly less than unity. For example, a debt cushion of $`75\%`$ implies an average recovery rate $`R_1(R)`$ of nearly $`100\%`$ and a $`25\%`$ debt cushion yields average recovery rate of $`65\%`$. If we identify debt of type $`1`$ with bank loans, these average recovery rates are in reasonable agreement with the results reported by Van de Castle and Keisman (1999).

Using $`P(R)`$ shown in Figure 1 its cumulative expected default probability, $`P_D(t)=1P_S(t)`$, is plotted in Figure 2 as a function of time $`t`$. Note the suppression at small times. For example, $`P_D(1\mathrm{y}\mathrm{r})`$ is only $`0.5\%`$. As we remarked earlier this occurs because $`V_0/D`$ is significantly greater than unity and fluctuations of $`R`$ greater than $`1`$ are forbidden.

The effect of debt subordination on the pricing of credit default swaps for this firm’s debt is illustrated in Figure 3, where the par spreads, $`c_i`$ are plotted as a function of debt maturity. The lower curve is for debt of type $`1`$, middle curve for debt of type $`2`$ and the upper curve is for the least senior debt of type $`3`$.

The correlations between recovery the rates $`R_i(R)`$ and default probability $`P_D(t|R)=1P_S(t|R)`$ are defined by

$`\xi _i(t)={\displaystyle \frac{R_i(R)P_D(t|R)R_i(R)P_D(t|R)}{\sqrt{R_i(R)^2R_i(R)^2}\sqrt{P_D(t|R)^2P_D(t|R)^2}}},`$ (21)
and they are plotted in Figure 4 as a function of time. The correlations are positive since both the cumulative default probability $`P_D(t|R)`$ and the recovery fractions $`R_i(R)`$ are increasing functions of total recovery fraction $`R`$. These strong correlations lead to a substantial reduction in par spreads for credit default swaps.

In Figure 5, we demonstrate the effect of including the correlation between $`R_i(R)`$ and $`P_D(t|R)`$ on the pricing of credit default swaps. The solid curve plots the $`c_i`$’s with the correlation included and the dotted curve plots the $`c_i`$’s with $`R_i(R)`$ in equation (12) set to the constant expected recovery value $`R_i(R)`$. The correlation substantially decreases credit default par spread values. For example, with the parameters we have chosen the cumulative $`5\mathrm{y}\mathrm{r}`$ default probability for the company is $`23\%`$ and the par spread for a $`5`$ yr credit default swap on the type 2 debt is $`c_2=232\mathrm{b}\mathrm{p}`$. However if $`R_2(R)`$ is replaced by $`R_2(R)=32\%`$ in equation (12), then one finds $`c_2=322\mathrm{b}\mathrm{p}`$.

The effect of this correlation is more significant for the most senior type 1 debt. In that case the recovery is one unless $`R`$ has fluctuated below $`0.5`$. The credit spread then only gets a contribution from this region of $`R`$ integration in equation (12). But for $`R`$ in this region the default probability is small resulting in a small credit default swap par spread. For example, for a $`5\mathrm{y}\mathrm{r}`$ maturity default swap we find that $`c_1`$ is only $`29\mathrm{b}\mathrm{p}`$, however if $`R_1(R)`$ is replaced by $`R_1(R)=88\%`$ in equation (12) then one finds the much larger value $`c_1=57\mathrm{b}\mathrm{p}`$. The very large suppression of credit spreads for the most senior debt caused by the correlation between $`R_i(R)`$ and $`P_D(t|R)`$ may indicate a problem with the general picture where corporate assets undergo a simple random walk in time, default occurs when the asset value first crosses a threshold, the uncertainty of recovery is associated with universal fluctuations in the default threshold and credit default swap spreads are computed by equating expected cash flows.

## 4 Conclusion

Within the context of a first passage default model with a fluctuating default threshold we have explored the implications of the correlation between the recovery fraction for a particular type of debt $`R_i(R)`$ and the default probability $`P_D(t|R)`$ for the pricing of credit default swaps.

A fluctuating default threshold is equivalent to a fluctuating total recovery rate $`R`$. In general a company has several types of debt $`D_i`$ each with a different recovery rate $`R_i`$ and the total recovery rate satisfies $`RD=_iR_iD_i`$, where $`D`$ is the total debt. In a simple scenario where debt of type $`i`$ is subordinate to debt of type $`i1`$, we explicitly derived the functional relationship $`R_i(R)`$. The impact of debt cushion on recovery rate has been known for some time, and this scenario captures its effect on the pricing of credit default swap spreads. Using a form for the probability of total recovery $`P(R)`$ suggested by historical data, we calculated par spreads $`c_i`$ for credit default swaps on corporate bonds with different levels of subordination. We found that the correlation between $`R_i(R)`$ and $`P_D(t|R)`$ dramatically decreases the par spreads for credit default swaps and this effect is greatest for the most senior debt.

As Figure 4 shows there is a positive correlation between recovery rates $`R_i(R)`$ and default probabilities $`P_D(t|R)`$ since both these quantities are increasing functions of the total recovery fraction $`R`$. There is mounting empirical evidence for a negative correlation between default probabilities and recovery rates \[Frye (2000a), Frye (2000b), Altman (2001), Carey and Gordy (2001), Hamilton et. al. (2001), and Altman and Brady (2002)\]. However, it is possible to accommodate this empirically observed behavior within the general class of models we are discussing. For example, the default probability increases as $`\sigma `$ does, and one could introduce a correlation where companies with a larger asset volatility $`\sigma `$ have a lower mean default threshold. Even in such an extension of the model explicitly discussed in this paper the functional dependence of the recovery rates for particular types of debt $`R_i`$ on the total recovery rate (on the total debt) $`R`$ will play an important role in the correct pricing of credit default swaps.

References

Altman (2001), Altman High Yield Bond and Default Study, Solomon Smith Barney, U.S. Fixed Income High Yield Report, July.

Altman, E. and Brady, B. (2002), Explaining Aggregate Recovery Rates on Corporate Bond Defaults, NYU Salomon Center Working Paper Series.

Altman, E., Brady, B., Resti, A. and Sironi, A. (2002) The Link between Default and Recovery Rates: Implications for Credit Risk Models and Procyclicality, working paper.

Black, F. and Cox, J. (1976) Valuing Corporate Securities: Some Effects of Bond Indenture Provisions, Journal of Finance, 31, 351-367.

Carey, M. and Gordy, M. (2001) Systematic Risk in Recoveries on Defaulted Debt, working paper presented at the 2001 Financial Management Association Meetings, Toronto, October 20.

Finkelstein, V., Lardy, J.P., Pan, G., Ta, T. and Tierney, J. (2002), Credit Grades Technical Document, edited by C. Finger.

Frye, J. (2000a) Collateral Damage Detected, Federal Reserve Bank of Chicago, Working Paper, Emerging Issues Series, October 1-14.

Frye, J. (2000b) Depressing Recoveries, Federal Reserve Bank of Chicago, Risk, January.

Gupton, G. and Stein, R. (2002) LossCalc: Moody’s Model for Predicting Loss Given Default (LGD), Moody’s Investors Service, February.

Hamilton, D., Gupton, G., and Berthault, A. (2001) Default and Recovery Rates of Corporate Bond Issuers: 2000, Moody’s Investment Service, February.

Leland, H. and Toft, K. (1996) Optimal Capital Structure, Endogenous Bankruptcy and the Term Structure of Credit Spreads, Journal of Finance, 51, 987-1019.

Merton, R. (1974), On Pricing of Corporate Debt: The Risk Structure of Interest Rates, Journal of Finance 29, 449-470.

Longstaff, F. and Schwartz, E. (1995) A Simple Approach to Valuing Risky Floating Rate Debt, Journal of Finance, 50, 789-819.

Pan, G. (2001) Equity to Credit Pricing, Risk, 99-102, November.

Van de Castle, K. and Keisman, D. (1999) Recovering Your Money: Insights Into Losses From Defaults, Standard & Poor’s CreditWeek, June.


text:
# Local Community Identification through User Access Patterns Rodrigo Almeida and Virgílio Almeida and are partially supported by a number of grants from CNPq-Brazil

## 1 Introduction

Community identification algorithms have been extensively used as a way to improve the quality perceived by users navigating through the Web. Search engines have incorporated this kind of technology as a source of information for their ranking algorithms and new applications, such as automatic directory creation. Furthermore, community identification studies have proven to be of great value to researchers trying to increase their understanding of the information society. .

The use of community identification algorithms to local communities, such as those that interact with portals or use specific services in the Web, has not been much studied. The direct application of existing algorithms to local community identification does not yield relevant results. The main reason is the difference between the processes associated with service creation in the two levels: local and global. The creation of services in the Web as a whole, global context, is governed by distributed and uncoordinated processes. For instance, someone’s decision to reference one page authored by someone else does not have to go through any regulatory agency and does not need its peer’s authorization. Therefore, the majority of links in the Web can be considered to have a semantic of reputation associated with it. . Differently, portals are created in a centralized and coordinated manner. The structures are created for navigational and business purposes leading to a completely different structure . This is why current community identification algorithms do not provide good results in that type of environment.

The availability of user access information in the case of a local context is another important fact that should be noted. The combination of the community identification algorithms with user access information would be very valuable to content providers, that can provide specific services to specific communities .

The inclusion of user access patterns on the community discovery process also allows us to infer communities even from a source that does not have explicit relationship information. Neither the books of an online bookstore nor the games provided by an ISP are explicitly related and, therefore, can take advantage of such technique. As the Web evolves, new kinds of services, not explicitly related, are created and made available to the users accentuating the need for algorithms designed to work based on evidences other than link information. Examples include streaming media and game services.

This work proposes and evaluates a technique for local community identification based on user access patterns. Our approach starts from a well-known community identification algorithm, the Hyperlink-Induced Topic Search (HITS). We then propose a way of transforming user access information into a graph-based structure to be used jointly with the HITS algorithm. A methodology to evaluate communities that takes into account the semantic meaning associated with each community is also supplied. In order to exemplify the benefits of our approach, we show two case studies based on services available on the Internet.

The paper is organized as follows: in Section 2 we present the related work. Section 3 presents the local community identification algorithm and proposes a methodology to evaluate the results. Section 4 presents two case studies, based on actual logs from real online services. Section 5 discusses the concluding remarks and future work.

## 2 Related Work

A considerable amount of research has been developed on community identification over the Web. Most of the approaches focus on analyzing text content, considering vector-space models for the objects usually related to Information Retrieval , hyperlink structure connecting the pages , markup tags associated with the hyperlinks or the combination of the previously cited sources of information . Therefore, they are restricted to objects that contain implicit information provided by the authors.Our work, on the other hand, is based solely on user access behavior.

Besides, we are considering community identification applied to a local context instead of the whole Web. Our approach aims to adapt the graph based community identification algorithm described in . Some modifications to  that takes into account user information have already been proposed in . However, this work was not focused on the community identification capabilities of  and also considered a different representation of user patterns.

Other relevant aspect of our work is the proposal of a community evaluation methodology that can be applied to other techniques already proposed such as  for comparison purposes. Most of the comparison methodologies proposed so far are based on disjunction and coverage of the communities not taking into account semantic meaning.

## 3 Local Community Identification

### 3.1 The HITS Algorithm

The HITS algorithm was initially proposed as a method to improve the quality of searches on the Web . It takes answers to a query from a text-based search engine and changes the ranking of these Web pages considering the underlying hyperlinked structure connecting them. This approach, formerly known as link analysis, was also the base for several other related studies . The links are considered as a way to represent correlations between pages, inducing a certain reputation/quality to a Web page pointed to by another.

The algorithm identifies pages that provide valuable information for a determined query and also, pages that are sources of good links for the query. These two kinds of pages are respectively called authorities and hubs. The query in the search application is used to limit the scope of the Web considered by the algorithm at each execution. Therefore, it limits its coverage to a certain subject expressed by a user in terms of his/her query.

The idea behind HITS is to identify hubs and authorities through a mutually reinforcing relationship existent between the pages. This relationship may be expressed as follows: a good hub is a page that points to good authorities and a good authority is a page that is pointed to by good hubs. This approach is very successful for the search application since it lacks some of the weakness presented by other simple link analysis strategies like indegre and outdegre ranking .

An iterative algorithm may be used to break the circularity of the mutually reinforcing relationship and to compute authority and hub weights for each page. Thus, each page $`p`$, has associated with it an authority weight $`a_p`$, and a hub weight $`h_p`$. These weights form a ranking of the pages ranging from good hubs/authorities, with high $`h_p`$/$`a_p`$ values, to bad ones, with low $`h_p`$/$`a_p`$. The weights are iteratively evaluated by the following procedure:

$`a_p={\displaystyle \underset{qp}{}}h_q`$
$`h_p={\displaystyle \underset{pq}{}}a_q`$
where $`pq`$ indicates the existence of a link link from $`p`$ to $`q`$.

Let A denote the adjacency matrix of the Web page’s subgraph to be considered by the HITS algorithm, i.e., $`A[p,q]`$ is equal to one if there is a link from $`p`$ to $`q`$ and 0 otherwise. The process of computing the weights may be rewritten to:

$`a=A^Th=A^TAa`$
$`h=Aa=AA^Th`$
where $`a`$ and $`h`$ are arrays storing authority and hub information for all the pages considered. Then, it can be shown that, the authority and hub arrays, $`a`$ and $`h`$, converge to the principal eigenvector of $`A^TA`$ and $`AA^T`$ respectively.

Although the initial work of HITS only considered the principal eigenvector of $`A^TA`$ and $`AA^T`$, an extension to it , proposed to use the same approach to identify communities of pages over the whole Web. The approach of the authors is to use the non-principal eigenvectors of the matrices $`A^TA`$ and $`AA^T`$ in order to identify other communities of Web pages. Thus, by computing the non-principal eigenvectors we can identify other $`a`$’s and $`h`$’s arrays identifying other communities. An implicit ranking of the communities can be derived by this method: the principal eigenvectors identifies the most important community over the pages, the second principal eigenvectors explicit the second most important community over the pages, etc.

Our approach applies the methodology to find communities on a graph, introduced by Kleinberg, to another context. Our goal is to identify communities of users that share a common interest, while accessing a service. User access patterns are used in order to infer relationships between them. The generation of the graph representing the relationships and its application to the HITS algorithm is described in the next Section.

### 3.2 Community Identification Process

Usually, the information used by the community identification algorithms is provided by the authors of the services. Thus the communities identified reflect the authors’ perception of the world. For instance, when these methods are applied to the Web , they use information explicited by the links connecting the pages as a way to infer relationship between them. This kind of information such as links or textual information is provided on the creation of the Web page and is influenced by the author’s unique view of the object.

In the case of local community identification, i.e., community identification restricted to a specific service, we consider the users’s viewpoint. The author’s point of view can be taken from the centralized process that creates the service, which is directly reflected in the service organization (e.g., the navigational structure of the service).

Although user access patterns are of great interest to local community identification, it is not straightforward how it should be treated.

At first sight, we would consider the objects as being the source of a unique view about a certain subject. This procedure is successful while considering the whole Web since each page represents a view about a subject provided by its author. Using objects as nodes at the graph and links derived from user access data would not represent such a unique interpretation of the data since different users have different interests when accessing an object. Therefore, we propose to use the accesses to a service in order to create a graph that maps the relationship between its users and not between its objects. This is a departure from the traditional approach taken by community identification algorithms.

Most services in the Web log files that record user requests to their objects. These logs have information about the objects requested by each user and some additional information such as the time it was issued or the status returned. Through the analysis of these logs, we can group requests into user sessions that are limited by a period of inactivity of the users . In this work, the sessions are considered to be the basic unit expressing a user interest, although other basic units such as the user itself or a single request could be used with a few adaptations. Each session presented in the log is considered to be a node of a graph that represent user access patterns. The connection between any two nodes $`p`$ an $`q`$ is directed and the weight, $`S[p,q]`$, between related nodes is computed by:

$`S[p,q]={\displaystyle \frac{O_pO_q}{O_p}}`$
where $`O_n`$ represents the set of objects accessed in the nth session.

After constructing matrix $`S`$, that expresses the relationship between the user sessions, we identify the communities by applying the HITS algorithm exchanging $`A`$ to $`S`$. The authority weight of a session $`s`$ in a community $`c`$, given by $`a_{c,s}`$, is used in order to characterize the communities. The intuition behind this procedure is that the authority weight of a session is related to the authority weight of the objects requested in it. The subject treated by each community is implicitly defined by its members, i.e., sessions with high authority weights.

### 3.3 Community Evaluation and Comparison

After user communities have been identified, a way to express their interrelationship must be provided. This comparison, in terms of their similarities/dissimilarities, is of great value to service providers since it is this sort of information that would help them to design better services. For instance, one might decide to provide a personalized service to its users based on information stored in the communities.

The weights $`a_{c,s}`$, associated with each pair session/community, generate a rank of the sessions within the communities. Based on the rankings, our analysis tries to identify good and bad sessions for each community. These rankings pass through a series of data analysis techniques in order to provide interrelationships and interpretations for the communities.

We use the Spearman rank correlation coefficient  to compare two communities. This correlation coefficient is a non-parametric (distribution-free) rank statistic proposed by Spearman as a measure of the strength of the correlation between two variables through the analysis of the rankings imposed by them. The Spearman method can be used to calculate the correlation between any communities $`a`$ and $`b`$ by:

$`s_{a,b}`$ $`=`$ $`16{\displaystyle \frac{r^2}{N(N^21)}}`$
where $`r`$ is the difference in rank position of corresponding sessions. The $`s_{a,b}`$ value, can be considered to be an approximation to the exact correlation coefficient that could be found if the authority weights for each session were considered.

The Spearman rank correlation varies from -1 to 1. Completely opposite rankings are indicated by -1 while equal rankings are represented by 1. We define distance (i.e., $`d_{a,b}`$) as the separation of two communities and calculate it by the following:

$`d_{a,b}=1s_{a,b}`$
The above definition is useful for visualization purposes and for analyzing the communities, as shown in the examples provided in Section 4.

Another important artifact related to community evaluation is the ability to discover the subjects represented by each of them. A simple, yet robust, method is to take into consideration the objects accessed by the users in each session. We split the sessions into three disjoint sets with respect to each community, the set of members, the set of non-members and the rest of them. The set of members is constituted by the top n sessions of the community ranking. The non-members set is formed by the sessions occupying the lowest n positions of the ranking. The remaining sessions are included in a third set not considered through the rest of the evaluation process. The value of $`n`$ should be chosen based on the level of specificity desired or on the information available about the objects.

After classifying sessions as members, non-member and indifferent, we proceed by evaluating positively the objects accessed by the sessions belonging to the members’ set and negatively the objects accessed by the sessions belonging to the non-members’ set. The weight associated with each pair object/session is calculated by a measure based on a tf-idf  approach, usually employed by information retrieval techniques. The frequency (tf) of an object within a session represents its importance in the scope of the session, while the distinction capability (idf) provided by the object is computed by:

$`idf_o=log\left({\displaystyle \frac{N}{N_o}}\right)`$
where $`N`$ represents the total number of sessions and $`N_o`$ represents the number of session in which the object $`o`$ was accessed.

## 4 Case Studies

This section presents the results obtained by the application of the proposed techniques to two different applications: an online bookstore and an audio streaming media server providing content for an online radio. The focus of interest are the books for the online bookstore and songs for the audio streaming media server. The main reason for choosing these applications was the lack of any explicit relationship between objects provided by the service authors. The data comprises one week of accesses to each service. The dataset from the bookstore was collected from August 1st to August 7th of 1999, while the audio streaming media dataset was collected from January 13th to January 19th of 2002.

The online bookstore considered here is a service specialized on Computer Science literature and operates exclusively on the Internet. Throughout the period, the bookstore received 1.7 million requests, 50,000 of which were requests for information about books, such as: authors, price, category, and reviews. Only those types of requests were considered in this experiment. We used 30 minutes as a threshold for the period of inactivity. As a result, we found 40,000 users sessions.

The online radio service provides a Web interface to an audio streaming media server that provides songs. Users can create personal radios, by specifying the songs they want to listen to, or choose a previous stored radio. In the process of radio creation, users can listen excerpts of the songs before they are inserted in the radio’s playlist. The streaming media server received 2.3 million requests, 662,000 of them were requests for full songs. Only those requests were considered in this experiment because we only wanted to capture the behavior of users who were already listening established radios. Again we used 30 minutes of inactivity period as a threshold. The number of sessions found was 78,000.

### 4.1 Online Bookstore

The local community identification technique was applied to find the top 10 communities in the online bookstore dataset. The communities were named from C1 to C10. The qualitative analysis of subjects covered by each community is presented in Table 1. For this analysis, the first half of the sessions’ ranking were considered to be the community members and the second half the non-members. Information about the categories that each book belongs to were collected from the Amazon 111http://www.amazon.com online store. The weight of each book, computed as explained in Section 3.3, were used to find the most and the least important categories for each community. Analyzing Table 1, we can infer the following interpretation for each community:

* Community C1 is basically formed by users interested in database certification that show less interest in network and programming questions related to Web development.
* Community C2 have users that show some interest in Web development, while their main interests are networked applications involved with it, less importance is given to database and certification program by the users of this community.
* Distributed computing is the main interest treated by community C3, this community is less related to databases and Microsoft platforms/applications.
* Community C4 aggregates users interested in low level programming basically related to operating system’s issues. It is interesting to note that this community is also less related to databases and Microsoft, similar to community C3, because these platforms are, generally, less flexible.
* The main interests of users pertaining to community C5 are hardware specification of database systems. The close relationship between this community and management of such systems, induced by the interest in digital business books, also worths mention.
* Community C6 is formed by users interested in network administration of Microsoft systems. The community is mainly related to certification programs about this subject.
* Low-level programming and scripting for Web development are the main interests of users belonging to community C7. They are are not interested, although, in the network problems related to Web development.
* Community C8 is also related to low-level Web development issues. The main difference between C8 and C7 is the fact that in C8 the database category is underprivileged in favor of the ones bottom-ranked in C7.
* Community C9 is also related to Web development such as C7 and C8, although the users of this community express some interest in certification programs. This information was gathered by the analysis of the whole set of categories for this community.
* Certification in database systems is the main concern of users belonging to community C10.

We use two data analysis techniques, Sammon’s mapping and Hierarchical Clustering, to increase our understanding of the communities. The Sammon’s mapping  is a nonlinear projection method closely related to metric Multi-Dimensional Scaling (MDS). This method tries to optimize a cost function that describes how well pairwise distances in a data set are preserved on the generated projection. The projection derived by the use of Sammon’s mapping can be seen in Figure 1.(a). Figure 1.(b) shows the Hierarchical Clustering obtained by the use of the the pairwise distance matrix between communities and the complete-linkage method . The complete-linkage method works as follows:

1. Assign to each community its own cluster and consider the distance between clusters to be the same one between the respective communities.
2. Find the closest clusters and merge them into a single one.
3. Compute the distances between this new cluster and each of the others. The distance between two clusters is calculated as being the longest distance connecting any sessions belonging to each cluster.
4. Repeat steps 2 and 3 until all session are grouped into a single cluster containing all the sessions.

Figure 1.(c) shows the distances between the clusters merged in each step of the algorithm.

As expected, both methods give similar results. They group together communities that are closely related like C1 and C10, and place apart communities that have no relation like C6 and C5. It is even more interesting to notice that communities like C8 and C9, that at a first look seem similar, are correctly separated by both methods.

The top clusters of the hierarchy shown in Figure 1.(b), separate the dataset in two very distinct groups. The first one, formed by (C2, C3, C4, C5,C7) represents a group where most of the users are interested in low-level questions, like programming and networking, usually related to operating systems. The other one, formed by (C1, C6, C9, C10), represents a group of users mostly interested in certification programs and their interests vary from network administration to Web development. The dispersion of interests found on the latter group was automatically identified. This can be derived from the highest cluster distance considered for this merge, Figure 1.(c), and also by the dispersion of the points on the Sammon’s mapping projection, Figure 1.(a).

The analisys of community clusters can be extended to the whole hierarchy with similar results. The Sammon’s distribution provides a comprehensive visualization of the relations expressed by the hierarchy and the use of both techniques together is a great start point for analysis of community data. The quality of the results obtained in the analysis is an evidence of the applicability of the distance metric based on Spearman correlation.

### 4.2 Audio Streaming Media Server

The same methodology used in the previous section was applied to the audio streaming media dataset. The top 10 communities (C1 to C10) existent on the dataset were identified. The qualitative analysis of styles covered by each community and a short explanation of some Brazilian music styles are presented in Table 2. For this analysis, only the top and bottom 100 session were considered to be the elements of the members’ and non-members’ sets. Unlike the online bookstore, we did not have access to a unique identifier for the songs played. The information available was the title of the songs, CDs and artists, making the process of categorizing data a time-consuming task. Data about the styles of the songs accessed on the considered sessions were collected from Amazon and Submarino222http://www.submarino.com.br, a major online store in Brazil. The Sammon’s mapping for this dataset is presented in Figure 2.(a). Figure 2.(b) and Figure 2.(c) the results obtained by the Hierarchical Clustering method when applied to this dataset.

Like in Section 4.1, we have the following obserrvations for the identified communities. For example, users in communities C9 and C10 represent users interested in international music styles, that do not pay much attention to Brazilian music. Communities C3 and C10, that are located apart in both representations, seems to represent different interests of their users. Although the same kind of analisys based on similarities of communities and their interests can be done for this dataset, we want to point out other dataset features identified by the algorithm without relying upon any explicit information. One of them is related to the structure of the phonographic industry existing in Brazil and the other one is related to the specificity of each dataset.

Even for an untrained observer, Table 2 shows that users of the online radio exhibit strong interest in local music. Much of the categories cited are of Brazilian music, even though all top international albums were also available. This fact is extremely important since it reflects what happens everyday on Brazilian streets. The IFPI Music Piracy Report  shows that over 50% of the piracy in Brazil is domestic and, therefore, many questions concerning the survival of the local phonographic industry production are being raised. The algorithm’s capability of confirming a behavior observed in the the society is very interesting since it can shed light on new questions.

The specificity level of each dataset is different and the algorithm is able to reflect this fact. The online bookstore is specialized in Computer Science while the online radio service provides access to different music styles from different nationalities. The slightly higher distance measures used in the each merge step is an evidence of the latter, Figures 1.(c) and 2.(c). Also we can see in the Sammon’s mapping that the communities found in the audio streaming media dataset, Figure 2.(a), are more spread than the ones of the bookstore dataset, Figure 2.(a).

## 5 Concluding Remarks

The methodology proposed offers several advantages over the graph-based algorithms in their pure form when applied to the context of local community identification. The communities identified represent the user’s perception of the information provided by the services, and this understanding gives service providers a great opportunity to service improvement.

An evaluation methodology based on data analysis available was also proposed. The evaluation technique is based on tf-idf ranking of occurrences and the Spearman rank correlation. The former is used to provide the focus of each community and the latter, derive a pairwise distance metric. The benefits of these methods are exemplified by the case studies, based on actual data of two real services available in the Web.

The results obtained in this paper are encouraging and show that the proposed techniques and metrics are promising for characterizing the interests of users accessing a service in the Web. Yet, this is just an introductory study and we must devote much attention to other possibles metrics, datasets and applicabilities of the proposed technique. The temporal emergence of communities and their evolution is also of great interest. We also intend to compare our results with other methods used for similar purposes.

## 6 Acknowledgments

The authors would like to thank the anonymous service owners and operators for enabling this research to proceed by providing us access to their logs. We also would like to thank the e-SPEED lab team, at the DCC/UFMG, for the continuous help during the development of this research, specially Flávia Ribeiro for helping with the revision of some of the text presented in this paper.