format: text

text:
# Exact PT-Symmetry Is Equivalent to Hermiticity.

## Acknowledgment

This work has been supported by the Turkish Academy of Sciences in the framework of the Young Researcher Award Program (EA-T$`\ddot{\mathrm{U}}`$BA-GEB$`\dot{\mathrm{I}}`$P/2001-1-1).


text:
# On Neumann “superlinear” elliptic problems

## 1 Introduction

In this paper we are going to show the existence of a nontrivial solution to the following model problem,

$$\{\begin{array}{ccc}\mathrm{\Delta }(u)=2uln(1+u^2)+\frac{|u|^2}{1+u^2}2u+u(sin(u)cos(u))\text{ a.e. on }\mathrm{\Omega }\hfill & & \\ \frac{u}{\eta }=0\text{ a.e. on }\mathrm{\Omega }.\hfill & & \end{array}$$
(1)
As one can see the right hand side is superlinear. But we can not use an Ambrosetti-Rabinowitz condition in order to obtain that the corresponding energy functional satisfies (PS) condition. Let us recall the well-known Ambrosetti-Rabinowitz condition:

There exists some $`\theta >2`$ such that

$`0<\theta F(u)f(u)u,`$
for all $`|u|>M`$ for big enough $`M`$. Here, by $`F`$ we denote the function $`F(u)=_0^rf(r)𝑑r`$.

We can see that for our model problem there is not such a $`\theta >2`$.

For such kind of problems there are some papers that extends the well-known Ambrosetti-Rabinowitz condition. For example one can also see the very interesting result of D.G. de Figueiredo-J. Yang  who considers semilinear problems such that the corresponding energy functional does not satisfy a (PS) condition. Also, Gongbao Li-HuanSong Zhou  made some progress in this direction. But they assume that $`f(u)0`$ for all $`u`$. Take problem (1) and see that that $`f(u)\mathrm{}`$ as $`u\mathrm{}`$, thus we can not say that $`f(u)0`$ for all $`u`$. So, we can not use their method in order to obtain a nontrivial solution. Finally, let us mention the work of Costa-Magalhaes . In this paper we extend the results of  using deferent arguments in our proof. The authors there have proposed the following hypotheses, among others,

$`f(s)spF(s)a|s|^\mu ,\text{ for all }s,`$
with $`\mu \frac{N/p}{qp}`$ for some $`q<p^{}=\frac{Np}{Np}`$. Thus $`f(s)spF(s)`$ must grows faster than $`s^{\frac{N/p}{qp}}`$.

Our existence theorem, considers more general Neumann problems than our model problem and at the end of the paper we give a second example. We must also note that non of the above papers considers Neumann problems.

Let us introduce the $`(PS)`$ that we are going to use.
Cerami $`(PS)`$ condition Let $`X`$ be a Banach space and $`I:X`$. For every $`\{u_n\}X`$ with $`|I(u_n)|M`$ and $`(1+||u_n||)<I^{^{}}(u_n),\varphi >0`$ for every $`\varphi X`$ there exists a strongly convergent subsequent. This condition has introduced by Cerami (see , ).

## 2 Basic Results

We are going to show an existence result for the following Neumann problem,

$$\{\begin{array}{ccc}\mathrm{\Delta }_p(u)=f(x,u)\text{ a.e. on }\mathrm{\Omega }\hfill & & \\ \frac{u}{\eta _p}=0\text{ a.e. on }\mathrm{\Omega },p2.\hfill & & \end{array}$$
(2)
We suppose that $`\mathrm{\Omega }`$ is a bounded domain with sufficient smooth boundary $`\mathrm{\Omega }`$. By $`\mathrm{\Delta }_p`$ we denote the well-known $`p`$-Laplacian operator, i.e. $`\mathrm{\Delta }_p(u)=div(Du^{p2}Du)`$.

From now on we will denote by $`F(x,u)=_o^rf(x,r)𝑑r`$ and $`h(x,u)=\frac{F(x,u)}{|u|^p}`$. We suppose the following assumptions on $`f`$,

H(f)$`f:\mathrm{\Omega }\times `$ is a Carathéodory function such that

1. for almost all $`x\mathrm{\Omega }`$ and for all $`u`$ we have that $`|f(x,u)|C(1+|u|^{\tau 1})`$, with $`\tau <p^{}=\frac{np}{np}`$ and $`C>0`$;
2. there exists some $`r<p`$ such that for every $`k^+`$ we can find big enough $`M>0`$ such that

$`0<({\displaystyle \frac{k}{|u|^r}}+p)F(x,u)f(x,u)u`$
for almost all $`x\mathrm{\Omega }`$ for all $`u`$ with $`|u|>M`$;
3. uniformly for almost all $`x\mathrm{\Omega }`$ we have $`lim\; sup_{u0}h(x,u)\theta (x)`$, with $`\theta (x)0`$ and $`_\mathrm{\Omega }\theta (x))dx<0`$.

###### Remark 1

Note that condition $`H(f)(ii)`$ is weaker than the classical condition of Ambrosetti-Rabinowitz. It is easy to see from $`H(f)(ii)`$ that

$$F(x,u)c|u|^p\frac{1}{e^{\frac{1}{r|u|^r}}},$$

with $`c>0`$. From this we conclude that $`lim\; inf_{|r|\mathrm{}}h(x,r)>0`$.

Let us define first the energy functional $`I:W^{1,p}(\mathrm{\Omega })`$ by $`I(u)=\frac{1}{p}Du_p^p_\mathrm{\Omega }F(x,u(x))𝑑x`$. Under conditions $`H(f)`$ it is well known that $`I`$ is well defined and is a $`C^1`$ functional. We are going to use the Mountain-Pass Theorem, so our first lemma is that $`I`$ satisfies the Cerami $`(PS)`$ condition.

###### Lemma 1

$`I`$ satisfies the Cerami $`(PS)`$ condition.

Proof

Let $`\{u_n\}W^{1,p}(\mathrm{\Omega })L^{\mathrm{}}(\mathrm{\Omega })`$ such that $`|I(u_n)|M`$ and $`(1+||u_n||_{1,p})<I^{^{}}(u_n),\varphi >0`$ for every $`\varphi W^{1,p}(\mathrm{\Omega })L^{\mathrm{}}(\mathrm{\Omega })`$. We must show that $`u_n`$ is bounded. Suppose that $`u_n_{1,p}\mathrm{}`$. We will show that $`Du_n_p\mathrm{}`$. Indeed, from the choice of the sequence we have

$`MDu_n_p^p{\displaystyle _\mathrm{\Omega }}pF(x,u_n)𝑑xM,`$
$`{\displaystyle _\mathrm{\Omega }}F(x,u_n)𝑑xM+Du_n_p^p`$
$`cu_n_p^pM+Du_n_p^p,`$
here have used $`H(f)(ii)`$ (see also Remark 1).

Thus, we can not suppose that $`Du_n_p`$ is bounded because then $`u_n_p\mathrm{}`$ and then from the above relation we obtain a contradiction. So, it follows that $`Du_n_p\mathrm{}`$ and moreover

$`u_n_p^p(\epsilon _n+c)Du_n_p^p,`$
with $`\epsilon _n0`$.

It follows then that there exists some $`c_1,c_2`$ such that

$`c_1u_n_{1,p}Du_n_pc_2u_n_{1,p}.`$ (3)
Then, from the choice of the sequence it follows

$`MDu_n_p^p+{\displaystyle _\mathrm{\Omega }}pF(x,u_n)𝑑xM,`$ (4)
and choosing $`\varphi =u_n`$

$`\epsilon _n{\displaystyle \frac{u_n_{1,p}}{1+u_n_{1,p}}}Du_n_p^p{\displaystyle _\mathrm{\Omega }}f(x,u_n)u_n𝑑x\epsilon _n{\displaystyle \frac{u_n_{1,p}}{1+u_n_{1,p}}}.`$ (5)
Consider now the sequence $`a_n=\frac{1}{u_n_{1,p}^r}`$. Then multiply inequality (4) with $`a_n+1`$, substituting with (5) and using (3) we arrive at

$`cu_n_{1,p}^{pr}a_nDu_n_p^p`$
$`{\displaystyle _\mathrm{\Omega }}(a_n+1)pF(x,u_n)f(x,u_n)u_ndx+(a_n+1)M+\epsilon _n{\displaystyle \frac{u_n_{1,p}}{1+u_n_{1,p}}}.`$ (6)
Let $`y_n(x)=\frac{u_n(x)}{u_n_{1,p}}`$. Then, it is clear that there exists some $`k`$ such that $`|y_n(x)|k`$ a.e. on $`\mathrm{\Omega }`$.

Let $`\mathrm{\Omega }_1=\{x\mathrm{\Omega }:|u(x)|M\}`$. In view of $`H(f)(i)`$ we have that for every $`M>0`$ there exists some $`C>0`$ such that

$`{\displaystyle _{\mathrm{\Omega }_1}}(a_n+1)pF(x,u_n(x))f(x,u_n(x))u_n(x)dxC.`$
Also we have

$`{\displaystyle _{\mathrm{\Omega }\mathrm{\Omega }_1}}a_nF(x,u_n(x))𝑑x+{\displaystyle _{\mathrm{\Omega }\mathrm{\Omega }_1}}pF(x,u_n(x))f(x,u_n(x))u_n(x)dx`$
$`{\displaystyle _{\mathrm{\Omega }\mathrm{\Omega }_1}}({\displaystyle \frac{k^r}{|u_n(x)|^r}}+p)F(x,u_n(x))f(x,u_n(x))u_n(x)dx.`$
Choose now big enough $`M>0`$ such that $`H(f)(ii)`$ holds for $`k^r`$. Going back to (6), we obtain a contradiction to the hypothesis that $`u_n`$ is not bounded.

In order to show that $`I`$ satisfies the $`(PS)`$ condition in $`W^{1,p}(\mathrm{\Omega })`$ we have to show that for every $`\{u_n\}W^{1,p}(\mathrm{\Omega })`$ with $`|I(u_n)|M`$ and $`(1+||u_n||_{1,p})<I^{^{}}(u_n),\varphi >0`$ for every $`\varphi W^{1,p}(\mathrm{\Omega })`$ then $`\{u_n\}`$ must be bounded in $`W^{1,p}(\mathrm{\Omega })`$. But it is well-known that $`W^{1,p}(\mathrm{\Omega })L^{\mathrm{}}(\mathrm{\Omega })`$ is dense to $`W^{1,p}(\mathrm{\Omega })`$. So, for every $`u_n`$ there exists some sequence $`\widehat{u}_n^kW^{1,p}(\mathrm{\Omega })L^{\mathrm{}}(\mathrm{\Omega })`$ such that $`lim_k\mathrm{}\widehat{u}_n^ku_n`$ strongly in $`W^{1,p}(\mathrm{\Omega })`$.

From the continuity of $`I,I^{^{}}`$ we have that $`\widehat{u}_n^k`$ must also satisfy $`|I(\widehat{u}_n^k)|M`$ and $`(1+||\widehat{u}_n^k||_{1,p})<I^{^{}}(\widehat{u}_n^k),\varphi >0`$ for every $`\varphi W^{1,p}(\mathrm{\Omega })L^{\mathrm{}}(\mathrm{\Omega })`$ and for big enough $`k`$.

So, if we suppose that $`u_n_{1,p}\mathrm{}`$ then it follows that $`\widehat{u}_n^k_{1,p}\mathrm{}`$ and that is a contradiction following the previous arguments.

Finally, using well-known arguments we can prove that in fact $`\{u_n\}`$ have a convergent subsequence.

$`\underset{¯}{\underset{¯}{QED}}`$

###### Lemma 2

There exists some $`\xi `$ such that $`I(\xi )0`$.

Proof

We claim that there exists big enough $`\xi `$ such that $`I(\xi )0`$. Suppose not. Then there exists a sequence $`\xi _n\mathrm{}`$ such that $`I(\xi _n)c>0`$. That means

$`{\displaystyle _\mathrm{\Omega }}F(x,\xi _n)𝑑xc>0.`$
Using now $`H(f)(ii)`$ (see also Remark 1) we can say that for almost all $`x\mathrm{\Omega }`$ and all $`u`$ we have that $`F(x,u)\mu |u|^pc`$. So, it follows that

$`\mu |\xi _n|^pc\text{ for every }n.`$
But this is a contradiction.

$`\underset{¯}{\underset{¯}{QED}}`$

###### Lemma 3

There exists some $`\rho >0`$ small enough and $`a>0`$ such that $`I(u)a`$ for all $`u_{1,p}=\rho `$ with $`uW^{1,p}(\mathrm{\Omega })`$.

Proof Suppose that this is not true. Then there exists a sequence $`\{u_n\}W^{1,p}(\mathrm{\Omega })`$ such as $`u_n_{1,p}=\rho _n`$ with $`\rho _n0`$, with the property that $`I(u_n)0`$. So we arrive at

$`Du_n_p^pp{\displaystyle _\mathrm{\Omega }}F(x,u_n(x))𝑑x`$ (7)
Let $`y_n(x)=\frac{u_n(x)}{u_n_{1,p}}`$. Using $`H(f)(i),(iii)`$ we can prove that there exists $`\gamma >0`$ such that

$`pF(x,u)(\theta (x)+\epsilon )|u|^p+\gamma |u|^p^{}`$
Take in account the last estimation and dividing (7) with $`u_n_{1,p}^p`$ we arrive at

$`Dy_n_p^p{\displaystyle _\mathrm{\Omega }}(\theta (x)+\epsilon )|y_n(x)|^p𝑑x+\gamma _1u_n_p^{p^{}p}.`$ (8)
Therefore, we obtain that $`Dy_n_p0`$. Recall that $`y_ny`$ strongly in $`L^p(\mathrm{\Omega })`$. Using the lower semicontinuity of the norm we arrive at $`Dy_plim\; infDy_n_plim\; supDy_n_p0`$. Thus, $`Dy_p=0`$ and from this we deduce that $`y=\xi `$. But we have that $`y_ny`$ weakly in $`W^{1,p}(\mathrm{\Omega })`$ and that $`Dy_n_pDy_p`$, so from the uniform convexity of $`W^{1,p}(\mathrm{\Omega })`$ we obtain that $`y_ny`$ strongly in $`W^{1,p}(\mathrm{\Omega })`$ and using the fact that $`y_n_{1,p}=1`$ we conclude that $`\xi 0`$.

Going back to (8) and taking the limit we arrive at

$`{\displaystyle _\mathrm{\Omega }}\theta (x)|\xi |^p𝑑x0.`$
But this is a contradiction.

$`\underset{¯}{\underset{¯}{QED}}`$

Using now the well-known Mountain Pass theorem we obtain the desired result.

## 3 Applications to Differential Equations

Consider the following elliptic equation,

$$\{\begin{array}{ccc}\mathrm{\Delta }(u)=2uln(1+u^2)+\frac{|u|^2}{1+u^2}2u+u(sin(u)cos(u))\text{ a.e. on }\mathrm{\Omega }\hfill & & \\ \frac{u}{\eta }=0\text{ a.e. on }\mathrm{\Omega }.\hfill & & \end{array}$$
(9)
Here, as before, $`\mathrm{\Omega }^n`$ is a bounded domain with smooth enough boundary $`\mathrm{\Omega }`$.

We can check that the corresponding energy functional does not satisfy an Ambrosetti-Rabinowitz type condition. Moreover, we can not say that $`f(u)0`$ nor that $`f(u)+f(u)=0`$, thus we can not use the arguments of , , even if our problem had Dirichlet boundary conditions. Finally, $`f()`$ does not satisfy the condition of  because does not exist $`p>1`$ such that $`f(u)\mu u^p`$ for all $`uT`$ for big enough $`T`$. Also, we can choose big enough $`n`$ (i.e. the dimension of our problem) and see that the above problem does not satisfy the conditions of .

However, we can check that $`f()`$ satisfies the conditions that we have proposed.

We can see also that $`h`$ did not have to go to infinity. Take for example as $`F(u)=|u|^p(a+(ba)\frac{|u|^r}{1+|u|^r})`$. Choose $`a<\frac{\lambda _1}{p},b>0`$ and for a suitable choice of $`r`$ (for example $`r<p`$) we can see that $`f`$ satisfies all the hypotheses that we have proposed.


text:
# Rapid Mixing in Markov Chains

## 1. Examples

We consider “counting problems”, where there is an implicitly defined finite set $`X`$ and one wishes to compute exactly or approximately $`|X|`$. In many situations, the approximate counting problem can be reduced to the problem of generating uniformly at random an element of $`X`$ (the random generation problem). This is often the relatively easier part. Then, the generation problem is solved by devising a Markov Chain with set of states $`X`$ with uniform steady state probabilities and then showing that this chain “mixes rapidly” - i.e., is close to the steady state distribution after a number of steps which is bounded above by a polynomial in the length of the input. \[The proof of rapid mixing is often the challenging part.\] We will illustrate the problem settings and scope of the area by means of three examples in this section. Then we will outline some tools for proving rapid mixing and describe very briefly how the tools are applied in some examples. This paper presents a cross-section of methods and results from the area. A more comprehensive survey can be found in .

Our first example is the permanent of a $`n\times n`$ matrix $`A`$. Valiant  showed that the exact computation of the permanent is # P - hard, i.e., every problem in a class of problems called # P is reducible to the exact computation of the permanent of a matrix; thus it is conjectured that it is not solvable in polynomial time. The hardness result holds even for the case with each entry a 0 or a 1 whence the problem is to find $`|X|`$ where $`X=\{\sigma S_n:A_{i,\sigma (i)}=1i\}.`$ Note that $`X`$ here is implicitly defined by $`A`$. In the general case, we may think of $`A`$ as specifying a weight $`_iA_{i,\sigma (i)}`$ on each $`\sigma `$ in $`X`$.

As usual, we measure running time as a function of $`n`$, a natural parameter of the problem (like the $`n`$ above) and $`1/ϵ`$, where $`ϵ>0`$ is the relative error allowed. Our primary aim is a polynomial  (in $`n,1/ϵ`$) time bounded algorithm; but, we will also discuss methods which help improve the polynomial. A recent breakthrough due to Jerrum, Sinclair, Vigoda  gives an approximation algorithm with such a time bound for the permanent (of a matrix with non-negative entries) settling this important open problem.

Our second example starts with the classical problem of computing the volume of a compact convex set in Euclidean $`n`$ space $`𝐑^n`$. Dyer, Frieze and the author  gave polynomial time algorithm for estimating the volume to any specified relative error $`ϵ`$. They first reduce the problem to that of drawing a random point from the convex set (with uniform probability density). They then impose a grid on space and do a “coordinate random walk” - from current grid point $`x`$ in $`K`$, pick one of the $`2n`$ coordinate neighbours $`y`$ of $`x`$ at random and go to $`y`$ if $`yK`$; otherwise, stay at $`x`$. Under mild conditions, it is easy to show that the steady state distribution is uniform (over the grid points in the set); they show that in a polynomial (in $`n`$) number of steps, we are “close” to the steady state. \[The number of states of the chain can be exponentially large.\]

Lovász and Simonovits  have devised a continuous state space random walk called the “ball walk” which performs better. In this, we choose at the outset a “step size” $`\delta >0`$. From the current point $`x`$, we pick at random (with uniform density) a point $`y`$ in a ball of radius $`\delta `$ with $`x`$ as center. We go to $`y`$ if it is in $`K`$, otherwise, we stay at $`x`$.

More generally, we may consider the integration (a “continuous” analog of counting) of a function over a convex set $`K`$. Of particular interest are logarithmically-concave (a positive real valued function $`F`$ is log-concave over a domain if $`\mathrm{log}F`$ is concave over the domain) functions, since many families of familiar probability density functions like the multi-variate normal are log- concave. One may use the Metropolis version of the random walks for convex set (cf section 1.). Rapid mixing has been proved for this general case too .

Our third set of examples concerns the Ising model and other Statistical Mechanics problems. (see  and references there). The computational problem arising from the Ising model is the following : we are given a real symmetric $`n\times n`$ matrix $`V`$ (the entries of $`V`$ arise as pairwise interaction energies), a real number $`B`$ (the external field) and a positive real number $`\beta `$ (the temperature). The Ising partition function is defined as

$$Z=Z(V_{ij},B,\beta )=\underset{\sigma \{1,+1\}^n}{}e^{\beta H(\sigma )},\text{where }H(\sigma )=\underset{i,j}{}V_{ij}\sigma _i\sigma _jB\underset{k}{}\sigma _k.$$

Jerrum and Sinclair  presented a polynomial time approximation algorithm to compute $`Z`$ in the case when all $`V_{ij}`$ are non-negative (called the ferromagnetic case).

Their algorithm for the ferromagnetic case first reduces the problem to the corresponding sampling problem and then more interestingly reduces this sampling problem to another one where we are given a graph (explicitly) $`G(V,E)`$ with positive edge weights $`w(e)`$. The problem is to pick a subset of edges of $`G`$ at random such that the probability of picking a particular subset $`T`$ is proportional to

$$w(T)=\mu ^{|\text{odd}(T)|}\underset{eT}{}w(e),$$

where $`\mu `$ is a given positive number and odd$`(T)`$ denotes the set of odd degree vertices in $`T`$. \[Note that in this case $`X`$ is the set of all subsets of edges and we have probabilities $`𝒫`$ on $`X`$ as given above, where $`X,𝒫`$ are implicitly defined by giving $`G,w`$.\]

## 2. Preliminaries, eigenvalue connection

Most of what we say extends naturally to continuous state space chains (where the set of states is (possibly uncountably) infinite) under mild conditions of measurability, but for ease of notation, here we state it for chains with a finite number of states. If $`P`$ is the transition probability matrix with $`P_{xy}`$ denoting the probability of transition from state $`x`$ to state $`y`$, for any natural number $`t`$, the matrix power $`P^t`$ denotes the $`t`$step transition probabilities. All our chains will be connected and aperiodic and thus have steady state probabilities - $`\pi (y)=lim_t\mathrm{}P_{x,y}^t`$. ($`\pi (y)`$ exists and is independent of the start state $`x`$). \[The notation $`\pi ()`$ will be used throughout for steady state probabilities.\] We let the vector $`p^{(t)}=p^{(0)}P^t`$ denote the probabilities at time $`t`$ where we start with the initial distribution $`p^{(0)}`$. All our chains will be “time-reversible”, i.e., $`\pi (x)P_{xy}=\pi (y)P_{yx}`$ will be valid for all pairs $`x,y`$.

From Linear algebra, we get that the eigenvalues of $`P`$ are $`1=\lambda _1>\lambda _2\lambda _3\mathrm{}\lambda _N1`$ (where $`N`$ is the number of states). Standard techniques yield :

###### Theorem 1.

For a finite time-reversible Markov Chain, with $`\pi _0=\mathrm{min}_x\pi (x)`$, for any $`t`$,

$$\underset{x}{}\left|p^{(t)}(x)\pi (x)\right|\frac{1}{\pi _0}\left[\mathrm{max}(|\lambda _2|,|\lambda _N|)\right]^t.$$

Modifying a Markov Chain by making it stay at the current state with probability 1/2 and move according to its transition function with probability 1/2 ensures that $`\lambda _N>0`$ while only increasing the (expected) running time by a factor of 2; so in the maximum above, we need only consider $`\lambda _2`$. We call a chain “lazy” if $`P_{xx}\frac{1}{2}x.`$ We will use the phrase mixing time to denote the least positive real $`\tau `$ such that for any $`p^{(0)}`$, $`_x|p^{(\tau )}(x)\pi (x)|1/4`$. It is known  that then for $`t\tau \mathrm{log}(1/ϵ)`$, we have $`_x|p^{(t)}(x)\pi (x)|ϵ`$.

If we have a time-reversible Markov Chain on a finite set of states with transition probability matrix $`P`$ with steady state probabilities $`\pi (x)`$ and $`F`$ is a positive real valued function on the states, there is a simple modification of the chain with steady state probabilities - $`\pi (x)F(x)/_yF(y)`$, called the the Metropolis modification. It has transition probabilities - $`P_{xy}^{}=P_{xy}\text{Min}(1,\frac{F(y)}{F(x)})\text{ for }xy`$. This construction is used in many instances including as mentioned in the introduction for sampling according to log-concave functions.

## 3. Techniques for proving rapid mixing

### 3.1. Conductance

Alon and Milman  and Sinclair and Jerrum  related $`\lambda _2`$ to a combinatorial quantity called “conductance” (in what may be looked on as a discrete analog of Cheeger’s inequality for manifolds). This has turned out to be of great use in practice; often, first proofs of polynomial time convergence use conductance.

For any two subsets $`S,T`$ of states, the ergodic flow from $`S`$ to $`T`$ (denoted $`Q(S,T)`$) is defined as $`Q(S,T)=_{xS,yT}\pi (x)P_{xy}`$. The conductance $`\mathrm{\Phi }`$ is defined by :

$$\mathrm{\Phi }(S)=\frac{Q(S,\overline{S})}{\pi (S)}\mathrm{\Phi }=\underset{S:0<\pi (S)<3/4}{\mathrm{min}}\mathrm{\Phi }(S).$$

$`\mathrm{\Phi }(S)`$ is the probability of escaping from $`S`$ to $`\overline{S}`$ conditioned on starting in $`S`$ in the steady state; since $`p^{(0)}`$ may be this distribution, it is intuitively clear that if the conductance of any set is low, then the mixing time is high. More interestingly,  and  show also a converse.

###### Theorem 2.

For a time-reversible, lazy, ergodic Markov chain with conductance $`\mathrm{\Phi }`$, we have

$$12\mathrm{\Phi }\lambda _21\frac{1}{2}\mathrm{\Phi }^2.$$

While conductance has helped bound the mixing time for some complicated chains (including the three examples mentioned in the introduction), it is not a fine enough tool to give the correct bounds for some simple chains. For example, consider the lazy version of the random walk on the $`2^n`$ vertices on the $`n`$ cube, where in each step, one picks at random one of the $`n`$ neighbours of the current vertex to go to. The mixing time is known to be $`O(n\mathrm{log}n)`$. Conductance is $`\mathrm{\Theta }(1/n)`$ for this example, yielding only a mixing time of $`O(n^3)`$ by Theorems (2) and (1).

A striking contrast is the random walk on the vertices of the cube truncated by a half-space (i.e., the set of 0-1 vectors satisfying a given linear inequality.) Morris and Sinclair  showed that the conductance of this walk is at least $`1/p(n)`$ for a polynomial $`p()`$.

We now discuss a recent improvement of conductance for chains with a finite number of states from , ; similar results hold for chains with infinite number of states. In addition to measuring the ergodic flow from $`S`$ to $`\overline{S}`$, we now also see if the flow is “well-spread out” in the sense that we “block” a set $`B\overline{S}`$, and then see if $`Q(S,\overline{S}B)`$ is still high. We now define for $`S`$ with $`0<\pi (S)3/4`$,

$$\mathrm{\Psi }(S)=\text{sup}_{\alpha (0,\pi (S))}\underset{B\overline{S};\pi (B)\alpha }{\mathrm{min}}\frac{\alpha Q(S,\overline{S}B)}{\pi (S)^2}.$$

It is easy to show that a set $`B`$ with $`\pi (B)\frac{1}{2}Q(S,\overline{S})`$, blocks at most 1/2 of the flow from $`S`$ to $`\overline{S}`$, so we have $`\mathrm{\Psi }(S)\frac{1}{4}\mathrm{\Phi }(S)^2`$. Thus, an assertion that mixing time is $`O(\mathrm{log}(1/\pi _0)\mathrm{min}_S\mathrm{\Psi }(S))`$ would be at least as strong a result as we get from Theorems (2) and (1). We prove a theorem which implies this assertion; indeed, instead of taking $`\mathrm{min}_S\mathrm{\Psi }(S)`$, the theorem takes an “average” of this quantity over different set sizes. We say that $`\psi :[0,3/4][0,1]`$ is a “blocking conductance function” (b.c.f.) if (the second condition is technical)

$`S,0<\pi (S)3/4,\mathrm{\Psi }(S)\psi (\pi (S))\text{and}\psi (t)2\psi (t^{})0tt^{}{\displaystyle \frac{4}{3}}t.`$
###### Theorem 3.

If $`\psi `$ is a blocking conductance function of a lazy, ergodic, time-reversible, finite Markov chain, with $`\pi _0=\mathrm{min}_x\pi (x)`$, then, the mixing time is at most

$$500_{t=\pi _0}^{3/4}\frac{1}{t\psi (t)}𝑑t.$$

This has been used to improve the analysis of the ball walk for convex sets in  and also some other examples in . Also,  uses Theorem (3) to argue that the mixing time of the grid lattice, (in a fixed number of dimensions) where some edges have failed according to a standard percolation model is still within a constant of the mixing time of the whole.

### 3.2. Coupling

Another important technique for proving rapid mixing is “Coupling”. A coupling is a stochastic process $`(X_t,Y_t),t=0,1,2,\mathrm{}`$, where each of $`\{X_t,t=0,1,\mathrm{}\}`$ and $`\{Y_t,t=0,1,2,\mathrm{}\}`$ is marginally a copy of the chain. \[They may be mutually dependent.\] So, we run “two copies” of the chain $`(X_t,Y_t)`$ in tandem. If $`Y_0`$ is distributed according to $`\pi `$, the steady state distribution, then, the distribution $`p^{(t)}`$ of $`X_t`$, satisfies

$$\underset{x}{}|p^{(t)}(x)\pi (x)|\text{ }\text{Pr}(X_tY_t).$$

To apply this, one must construct a coupling $`(X_t,Y_t)`$ for which $`X_t`$ and $`Y_t`$ “meet” as fast as possible. This can prove difficult. Path coupling introduced by Bubley and Dyer  which we describe now simplifies the task quite a bit. In path coupling, we have an underlying connected directed graph $`G`$ on the set of states. ($`G`$ could just be the graph of the Markov Chain.) $`G`$ defines distances between pairs of states - namely the length of the shortest path in $`G`$. We only need to define a coupling of adjacent pairs of vertices, with the property that for every pair of adjacent (in $`G`$) vertices $`(u,v)`$, the expected distance between the next states of $`u,v`$ is at most $`\beta <1`$. They then show that

###### Theorem 4.

If $`D`$ is the diameter (of $`G`$), then for any $`t>0`$, $`\text{ }\text{Pr}(X_tY_t)D\beta ^t`$.

Propp and Wilson  have designed a method they call Coupling from the Past. This applies to chains with a partial order on the set of states with a least state $`\underset{¯}{0}`$ and a greatest state $`\underset{¯}{1}`$. They show that running two copies of the Chain backwards - one from $`\underset{¯}{0}`$ and one from $`\underset{¯}{1}`$ \- with a coupling satisfying a certain monotonicity condition until they “meet” gives us a good upper bound on the number of steps needed to mix. We refer the reader to  for details.

### 3.3. Other methods

One way to prove a lower bound on conductance for a chain with a finite set of states $`X`$ is to construct a family of $`|X|^2`$ paths - one from each state to each other using as edges the transitions of the Markov Chain, so that no transition is “overloaded” by too many paths. We do not supply here any more details of this technique referred to as the method of “canonical paths” and used by Jerrum and Sinclair .

We may look upon the construction of these paths as routing a multi-commodity flow through the network and apply techniques from Network Flows.  pursues this.  uses different measures of congestion to achieve improved results in some cases and their methods are applied in .

Another important method is the use of logarithmic Sobolev inequalities, where, we use (relative) entropy - $`\text{Ent}(p^{(t)})=_xp^{(t)}(x)\mathrm{log}\frac{p^{(t)}(x)}{\pi (x)}`$ as the measure of distance. It is known that for ergodic Markov Chains, this distance declines exponentially ; i.e., there is a constant $`\alpha (0,1)`$ such that

$$\text{Ent}(p^{(t)})\alpha ^t\text{Ent}(p^{(0)}).$$

Note that $`\text{Ent}(p^{(0)})\mathrm{log}(1/\pi _0)`$. So, it suffices to choose $`t=(\mathrm{log}\mathrm{log}\frac{1}{\pi _0}+\mathrm{log}(1/ϵ))`$ $`/(1\alpha )`$ to reduce the entropy to $`ϵ`$; the dependence on $`1/\pi _0`$ is thus better. But we need to determine $`\alpha `$ which is only known for simple chains. It is known that $`\alpha >\lambda _2`$, so the most that this method could save over using something like Theorem (1) is the $`\mathrm{log}(1/\pi _0)`$ factor.  and  contain several comparisons between the log-Sobolev inequalities, eigenvalue bounds and conductance.  uses the log-Sobolev inequality to prove better bounds on the Metropolis version of the coordinate random walk for log-concave functions.

For the random walk on the cube a simple coupling argument, which, moves both $`X_t`$ and $`Y_t`$ in the same coordinate, trying to make them equal - shows that mixing time is $`O(n\mathrm{log}n)`$. Some sophisticated Fourier Transform methods have been used to get much more exact results here and the results are applicable in other contexts too.

A traditional approach to sampling from a probability distribution involves the so-called “Stopping Rules” , where one specifies a rule for when to stop the Markov Chain and shows that if we follow the rule, we sample (exactly) from the desired distribution.  contain results about the expected time needed for certain stopping rules, which then serves as an upper bound on the number of steps needed to converge.

We also mention two general techniques for deriving convergence rates of a Markov Chain from the knowledge of convergence rates for a simpler-to-analyze chain. The first one is called Comparison and is developed in . The second technique is called Decomposition ; here one decomposes the chain into chains on subsets of states and derives a bound on the convergence rate of the whole chain based on the rates for the “sub-chains” and the interconnections between them.

## 4. Solution of sampling and counting problems

PERMANENT

We consider the permanent of a $`n\times n`$ 0-1 matrix $`A`$. We may define a bipartite graph corresponding to the matrix. Each $`\sigma S_n`$ with $`A_{i,\sigma (i)}=1`$ for all $`i`$ corresponds to a perfect matching in the graph. Let $``$ be the set of perfect matchings in the graph. Unfortunately, no rapidly mixing Markov Chain with only $``$ as the set of states is known. Broder  first defined the following Markov Chain. We also include the set of “near- perfect” matchings - $`^{}`$ (a near-perfect matching has $`\frac{n}{2}1`$ edges, no two incident to the same vertex). Transitions of the Markov Chain are as follows: In any current state, $`M`$, we pick an edge $`e=(u,v)`$ of the graph uniformly at random (all edges are equally likely) and

* if $`M_n`$ and $`eM`$, move to $`M^{}=Me`$.
* If $`M_{n1}`$ and $`u`$ and $`v`$ are both unmatched in $`M`$, then move to $`M^{}=M+e`$.
* $`M_{n1}`$, $`u`$ is matched to $`w`$ in $`M`$ and $`v`$ unmatched, then move to $`M^{}=(M+e)(u,w)`$; make a symmetric move if $`v`$ is matched and $`u`$ unmatched.
* In all other cases, stay at $`M`$.

 showed that if $`A`$ is dense (each row has at least $`n/2`$ 1’s), then the chain above mixes rapidly and in addition that $`|^{}|p(n)||`$ for a polynomial $`P()`$. Thus, rejection sampling - accept result of a run of the chain if the result is in $``$ yields a polynomial time sampling procedure.

Jerrum, Sinclair and Vigoda  develop an algorithm for the general 0-1 permanent (including the non-dense case). Here is very brief sketch of their algorithm : An edge-weighting $`w`$ assigns a (positive) real weight $`w(e)`$ to each edge. For a matching $`M`$ $`w(M)=_{eM}w(e)`$ is its weight. For a set $`S`$ of matchings, $`w(S)=_{MS}w(M)`$. Finally, for each pair of vertices $`(u,v)`$, define $`w^{}(u,v)`$ to be the ratio of the weight of all perfect matchings to the weight of all near-perfect matchings which leave $`u,v`$ unmatched. Then define the “modified weight” $`w^{}(M)`$ of a matching $`M`$ to be $`w(M)`$ if $`M`$ is perfect and $`w(M)w^{}(u,v)`$ if $`M`$ leaves $`u,v`$ unmatched. They first show that a Metropolis version of the above random walk to sample according to $`w^{}(M)`$ mixes rapidly. But the $`w^{}`$ are not known; they argue that if we start with the complete graph and go through a sequence of graphs, where in each step, we lower the edge weight of a non-edge of $`G`$ by a factor, then we can successively estimate $`w^{}`$ for each edge-weighting (of the complete graph) in the sequence. The final element of the sequence has low enough weights for the non-edges that it gives a good approximation to the permanent.

THE ISING MODEL

Recall the subgraph sampling problem in section 1. Here is the random walk they use. The states of the Markov Chain are the subsets of $`E`$. Their chain is the Metropolis version of the following simple Markov Chain whose steady state probabilities are uniform over all subsets of the edges, namely : at any current subset $`T`$ of $`E`$, pick uniformly at random an edge $`eE`$; if $`eT`$, then go to $`T^{}=Te`$, otherwise go to $`T^{}=T+e`$. They also make the chain lazy. The proof of a lower bound on conductance relies on a canonical paths argument.

The algorithm that is preferred by physicists is the one due to Swendsen and Wang . This algorithm switches the signs on large blocks of vertices of the graph at once. But while this seems to work well in practice, no proof of rapid mixing is known.

CONVEX SETS, LOG-CONCAVE FUNCTIONS

Consider the ball walk in a convex set $`K`$ in $`𝐑^n`$ with balls of radius $`\delta `$. We use the notation $`P_{xy}`$ for the transition probability density from $`x`$ to $`y`$ here. The conductance of a (measurable) subset $`S`$ of $`K`$ is now defined as

$$\frac{_{xS}_{yKS}\pi (x)P_{xy}}{\mathrm{min}(\pi (S),1\pi (S))}.$$

Let $`S`$ be the boundary of $`S`$ interior to $`K`$. Since points $`xS`$ on or near $`S`$, intuitively have a high $`_yP_{xy}`$, a lower bound on $`\mathrm{Vol}_{n1}(S)`$ would seem to imply a lower bound on conductance. This is indeed the case. Lower bounds on $`\mathrm{Vol}_{n1}(S)`$ have been the subject of much effort. The most general result known is the following.

###### Theorem 5.

Isoperimetry Suppose $`K`$ is a compact convex set in $`𝐑^n`$ of diameter $`d`$ and $`F`$ is a positive real-valued log-concave function on $`K`$. Then for any measurable $`SK`$ with $`_SF(1/2)_KF`$, and measurable boundary $`S`$ interior to $`K`$, we have

$$_SF\frac{2}{d}_SF.$$

The theorem was first proved for the case $`F1`$ by Lovász and Simonovits  and independently also by Khachiyan and Karzanov . The result was generalized to the case of general log-concave measures $`F`$ by Applegate and Kannan  using the same techniques. We may add an extra factor of $`\mathrm{ln}(_KF/_SF)`$ to the right hand side; this was proved independently in  and also by Bobkov . The most recent algorithm for computing the volume of convex sets is in , where references to earlier papers may be found.

OTHER EXAMPLES

There are many other counting problems on which progress has been made using this method. Again, we are not able to present a comprehensive review here.

A notable result is the one for the truncated cube already mentioned in section 3.. Another example of interest is Contingency Tables - where we are given $`m,n`$ (positive integers) and the row and column sums of an $`m\times n`$ matrix $`A`$. The problem is to sample uniformly at random from the set of $`m\times n`$ matrices with non-negative integer entries with these row and column sums. The problem remains open, but there are several partial results ,.

There are many tiling problems, where the problem is to pick a random tiling of say a large square in the plane by dominoes of a given shape. These problems arise in Statistical Mechanics. For regular shapes, it is often possible to devise a polynomial time algorithm to count the number exactly. But it is important to devise algorithms with low polynomial time bounds. There has been much progress here - see  and references there. Random generation of colorings and independent sets of a graph has received much attention lately due to connections to Statistical Mechanics .

Acknowledgment. I thank Ravi Montenegro for suggesting some changes in the manuscript.


text:
# Probabilistic aspects of Al-Salam–Chihara polynomials

## 1. Introduction and main identity

The aim of the paper is to point out the connection of Al-Salam–Chihara polynomials with a regression problem in probability, and to use it to give a new simple derivation of their density. Our approach exploits identity (1.9) below, which connects the Al-Salam–Chihara polynomials to the continuous $`q`$-Hermite polynomials. This connection is more direct and elementary but less general than the technique of attachment exploited in \[BI96, Section 2\]. We also compute determinants of Hankel matrices with entries which are linear combinations of the $`q`$-Hermite polynomials.

The Al-Salam–Chihara polynomials were introduced in \[ASC76\] and their weight function was found in \[AI84\]. We are interested in the renormalized Al-Salam–Chihara polynomials $`\{p_n(x|q,a,b)\}`$, which are defined by the following three term recurrence relation

$$p_{n+1}\left(x\right)=\left(xaq^n\right)p_n\left(x\right)\left(1bq^{n1}\right)[n]_qp_{n1}\left(x\right)(n0),$$
(1.1)
with the usual initial conditions $`p_1(x)=0`$, $`p_0(x)(x)=1`$. Here, we use the standard notation

$`[n]_q`$ $`=`$ $`1+q+\mathrm{}+q^{n1},`$
$`[n]_q!`$ $`=`$ $`[1]_q[2]_q\mathrm{}[n]_q,`$
$`\left[\begin{array}{c}n\\ k\end{array}\right]_q`$ $`=`$ $`{\displaystyle \frac{[n]_q!}{[nk]_q![k]_q!}},`$
with the usual conventions $`[0]_q=0,[0]_q!=1`$.

For $`|q|<1`$, their generating function

$$f(t,x|q,a,b)=\underset{n=0}{\overset{\mathrm{}}{}}\frac{t^n}{[n]_q!}p_n(x|q,a,b)$$

is given by

$$f(t,x|q,a,b)=\underset{k=0}{\overset{\mathrm{}}{}}\frac{1(1q)atq^k+(1q)bt^2q^{2k}}{1(1q)xtq^k+(1q)t^2q^{2k}};$$
(1.3)
compare \[AI84, (3.6) and (3.10)\].

The corresponding (renormalized) continuous $`q`$-Hermite polynomials $`H_n(x|q)=p_n(x|q,0,0)`$ satisfy the three term recurrence relation

$$H_{n+1}(x)=xH_n(x)[n]_qH_{n1}(x).$$
(1.4)
For $`|q|<1`$ their generating function $`\varphi (t,x|q)=_{n=0}^{\mathrm{}}\frac{t^n}{[n]_q!}H_n(x|q)`$ is

$$\varphi (t,x|q)=\underset{k=0}{\overset{\mathrm{}}{}}\left(1(1q)xtq^k+(1q)t^2q^{2k}\right)^1.$$
(1.5)
Of course, these are well known special cases of (1.1) and (1.3), see \[ISV87, (2.11) and (2.12)\] which we state here for further reference.

We will also use polynomials $`\{B_n(x|q)\}`$ defined by the three term recurrence relation

$$B_{n+1}\left(x\right)=q^nxB_n\left(x\right)+q^{n1}[n]_qB_{n1}\left(x\right)(n0)$$
(1.6)
with the usual initial conditions $`B_1=0,B_0=1`$. These polynomials are related to the $`q`$-Hermite polynomials by

$$B_n(x|q)=\{\begin{array}{cc}i^nq^{n(n2)/2}H_n(i\sqrt{q}x|\frac{1}{q})\hfill & \text{ if }q>0\hfill \\ (1)^{n(n1)/2}|q|^{n(n2)/2}H_n(\sqrt{|q|}x|\frac{1}{q})\hfill & \text{ if }q<0\hfill \end{array},$$
(1.7)
and have been studied in \[Ask89\], \[IM94\]. Their generating function $`\psi (t,x|q)=_{n=0}^{\mathrm{}}\frac{t^n}{[n]_q!}B_n(x|q)`$ is given by

$$\psi (t,x|q)=\underset{k=0}{\overset{\mathrm{}}{}}\left(1(1q)xtq^k+(1q)t^2q^{2k}\right).$$
(1.8)
We now point out the mutual relationship between the Al-Salam–Chihara polynomials $`\{p_n(x|q,a,b)\}`$ and the polynomials $`\left\{H_n\left(x|q\right)\right\}_{n0}`$ and $`\left\{B_n\left(x|q\right)\right\}_{n0}`$.

###### Theorem 1

For all $`a,c,q`$, $`c0`$, and $`n1`$ we have

$$p_n(x|q,a,b)=\underset{k=1}{\overset{n}{}}\left[\begin{array}{c}n\\ k\end{array}\right]_qc^{nk}B_{nk}(\frac{a}{c}|q)\left(H_k(x|q)c^kH_k(\frac{a}{c}|q)\right),$$
(1.9)
where $`b=c^2`$.

###### Proof.

From the recurrence relations (1.1), (1.4), and (1.6), it is clear that $`p_n(x|q,a,b)`$, $`H_n(x|q)`$, and $`B_n(x|q)`$ are given by polynomial expressions in variable $`q`$. The $`q`$-binomial coefficient $`\left[\begin{array}{c}n\\ k\end{array}\right]_q`$ is also a polynomial in $`q`$. Therefore, we see that identity (1.9) is equivalent to a polynomial identity in variable $`q`$. Hence it is enough to prove that (1.9) holds true for all $`|q|<1`$. When $`|q|<1`$, inspecting (1.3), (1.5), and (1.8) we notice that for $`b=c^2`$ we have

$$f(t,x|q,a,b)=\psi (tc,a/c|q)\varphi (t,x|q),$$
(1.10)
and

$$\psi (t,x|q)\varphi (t,x|q)=1.$$
(1.11)
Therefore,

$$f(t,x|q,a,b)=1+\psi (ct,a/c|q)\left(\varphi (t,x|q)\varphi (ct,a/c|q)\right),$$

which is valid for all small enough $`|t|`$. Comparing the coefficients at $`t^n`$ for $`n1`$ and taking into account that $`H_k(x|q)c^kH_k(\frac{a}{c}|q)=0`$ for $`k=0`$, we get (1.9). ∎

###### Remark 1.

One could split (1.9) into the following two separate identities, which are implied by (1.10) and (1.11) respectively:

$$n0:p_n(x|q,a,c^2)=\underset{k=0}{\overset{n}{}}\left[\begin{array}{c}n\\ k\end{array}\right]_qc^{nk}B_{nk}(\frac{a}{c}|q)H_k(x|q),$$
(1.12)
$$n1:\underset{k=0}{\overset{n}{}}\left[\begin{array}{c}n\\ k\end{array}\right]_qB_{nk}(x|q)H_k\left(x|q\right)=0.$$
(1.13)
Formula (1.12) is a renormalized inverse of formula \[IRS99, (4.7)\], who express the $`q`$-Hermite polynomials as linear combinations of Al-Salam–Chihara polynomials. Formula (1.13) resembles \[Car56, (2.28)\], who considers $`q`$-Hermite polynomials of the form $`h_n(x|q)={\displaystyle \underset{k=0}{\overset{n}{}}}\left[\begin{array}{c}n\\ k\end{array}\right]_qx^k`$, paired with $`b_n(x|q)=h_n(x|1/q)`$.

## 2. Probabilistic aspects

Quadratic regression questions in the paper \[Bry01\] lead to the problem of determining all probability distributions $`\mu `$ which are defined indirectly by the relationships

$$H_n(x|q)\mu (dx)=\rho ^nH_n(y|q)n=1,2,\mathrm{},$$
(2.1)
where $`y,\rho ,q`$ are fixed parameters, and $`\left\{H_n\right\}_{n0}`$ is the family of the $`q`$-Hermite polynomials.

Our next result shows that this problem can be solved using the Al-Salam–Chihara polynomials.

###### Theorem 2

If $`\mu =\mu (dx|\rho ,y)`$ satisfies (2.1), then its orthogonal polynomials are Al-Salam–Chihara polynomials $`\{p_n(x|q,a,b)\}`$ with $`a=\rho y`$, $`b=\rho ^2`$.

###### Proof.

Recall that $`H_n(x|q)=p_n(x|q,0,0)`$. Thus if $`\rho =0`$ then (2.1) implies that $`p_n(x|q,a,b)\mu (dx)=0`$ for all $`n=1,2,\mathrm{}`$. Suppose now that $`\rho 0`$. Combining (1.9) with (2.1) we get

$$p_n(x|q,a,b)\mu (dx)=\underset{k=0}{\overset{n}{}}\left[\begin{array}{c}n\\ k\end{array}\right]_q\rho ^{nk}B_{nk}(y|q)\left(H_k(x|q)\rho ^kH_k(y|q)\right)\mu (dx)=0$$

for all $`n=1,2,\mathrm{}`$. Since $`\{p_n\}`$ satisfy a three step recurrence, this implies $`p_k(x)p_n(x)\mu (dx)=0`$ for all $`0k<n`$. ∎

Next we answer an unresolved case from \[Bry01\].

###### Corollary 1.

Fix $`q>1,y`$. Let $`_q=\{1,1/q,1/q^2,\mathrm{},1/q^n,\mathrm{},0\}`$.

* If $`\rho ^2_q`$ then (2.1) has no probabilistic solution $`\mu `$.
* If $`\rho ^2_q`$ is non-zero, then the probabilistic solution of (2.1) exists, and is a discrete measure supported on $`1+\mathrm{log}_q1/\rho ^2`$ points.

###### Proof.

Suppose that $`\mu `$ is positive and solves (2.1). Therefore its monic orthogonal polynomials satisfy the three term recurrence relation

$$p_{n+1}(x)=(x\rho yq^n)p_n(x)(1\rho ^2q^{n1})p_{n1}(x).$$
(2.2)
For a positive non-degenerate measure $`\mu _y(dx)`$, and $`n1`$ we have

$$p_n^2(x)\mu _y(dx)=(1\rho ^2q^{n1})p_{n1}^2(x)\mu _y(dx).$$
(2.3)
if $`\rho ^2_q`$ then $`(1\rho ^2q^{n1})0`$ for all $`n`$. Since $`p_0^2(x)\mu _y(dx)>0`$, this shows that $`p_n^2(x)\mu _y(dx)>0`$ for all $`n0`$. But then the coefficients $`1\rho ^2q^{n1}`$ must be non-negative for all $`n`$, which is false. This proves (i).

To conclude the proof it remains to notice that if $`\rho ^2=1/q^m`$ then from (2.2) and (the proof of) Favard’s theorem, see \[Fre71, Theorem II.1.5\], it follows that the solution of (2.1) is given by a measure supported on the roots of the polynomial $`p_{m+1}`$. Indeed, (2.2) implies that the polynomial $`p_{m+2}`$ is divisible by $`p_{m+1}`$. Therefore, $`p_{m+1}`$ is the common factor of all polynomials $`\{p_k:km+1\}`$. It is also known, see \[Fre71, Theorem I.2.2\], that $`p_{m+1}`$ has exactly $`m+1`$ distinct real roots $`x_1,\mathrm{},x_{m+1}`$. Thus, any measure $`\mu (dx)=\lambda _j\delta _{x_j}`$ supported on the roots of polynomial $`p_{m+1}`$ satisfies $`p_{m+1+k}\mu (dx)=0`$. Solving the remaining $`m+1`$ equations $`p_0\mu (dx)=1`$, and $`p_k(x)\mu (dx)=0,k=1,2,\mathrm{},m`$ for $`\lambda _j`$, we get a measure that solves (2.1). This measure is non-negative as the coefficients at the third term in the recurrence (2.2) are non-negative for $`n=1,\mathrm{},m`$, see \[Fre71, page 58\]. ∎

From Theorem 2 it follows that if the solution of (2.1) exists, then it is given by the distribution of the Al-Salam-Chihara polynomials. The distribution of the Al-Salam-Chihara polynomials is derived in \[AI84, Chapter 3\]. However, in \[Bry01, Proposition 8.1\] we found the solution of (2.1) which relies solely on the facts about the $`q`$-Hermite polynomials. We repeat the latter argument here, and then use it to re-derive the distribution of the corresponding Al-Salam–Chihara polynomials.

###### Corollary 2.

If $`\rho ,q,y`$ are such that $`|\rho |<1`$,$`|q|<1`$, and $`y^2(1q)<4`$, then the probabilistic solution of (2.1) is given by the absolutely continuous measure $`\mu `$ with the density on $`x^2<4/(1q)`$ given by

$$\frac{\sqrt{1q}}{2\pi \sqrt{4(1q)x^2}}\underset{k=0}{\overset{\mathrm{}}{}}\frac{(1\rho ^2q^k)\left(1q^{k+1}\right)\left((1+q^k)^2(1q)x^2q^k\right)}{(1\rho ^2q^{2k})^2(1q)\rho q^k(1+\rho ^2q^{2k})xy+(1q)\rho ^2(x^2+y^2)q^{2k}}$$

###### Proof.

The distribution of the $`q`$-Hermite polynomials $`H_n(x|q)`$ is supported on $`x^2<4/(1q)`$ with the density

$$f_H(x)=\frac{\sqrt{1q}}{2\pi \sqrt{4(1q)x^2}}\underset{k=0}{\overset{\mathrm{}}{}}\left((1+q^k)^2(1q)x^2q^k\right)\underset{k=0}{\overset{\mathrm{}}{}}(1q^{k+1}),$$

see \[ISV87, (2.15)\]. Moreover, since $`|H_n(x)|C_q(n+1)(1q)^{n/2}`$ when $`x^2,y^24/(1q)`$, the series

$$g_H(x,y,\rho )=\underset{n=0}{\overset{\mathrm{}}{}}\frac{\rho ^n}{[n]_q!}H_n(x)H_n(y)$$
(2.4)
converges uniformly and defines the Poisson-Mehler kernel which is given by

$$g_H(x,y,\rho )=\underset{k=0}{\overset{\mathrm{}}{}}\frac{(1\rho ^2q^k)}{(1\rho ^2q^{2k})^2(1q)\rho q^k(1+\rho ^2q^{2k})xy+(1q)\rho ^2(x^2+y^2)q^{2k}};$$
(2.5)
this is the renormalized version of the well known result, see eg. \[IS88, (2.2)\] who consider the $`q`$-Hermite polynomials given by $`\{(1q)^{n/2}H_n(2x/\sqrt{1q}|q)\}`$ instead of our $`\{H_n(x|q)\}`$.

Since (1.4) implies that $`H_n^2(x|q)f_H(x)𝑑x=[n]_q!`$, it follows from (2.4) that

$$_{2/\sqrt{1q}}^{2/\sqrt{1q}}H_n(x|q)g_H(x,y,\rho )f_H(x)𝑑x=\rho ^nH_n(y).$$

###### Corollary 3.

If $`q,a,b`$ are such that $`|q|<1`$, $`0<b<1`$, and $`a^2(1q)<4b`$, then the distribution of the Al-Salam-Chihara polynomials $`\{p_n(x|q,a,b)\}`$ is absolutely continuous with the density on $`x^2<4/(1q)`$ given by

$$\frac{\sqrt{1q}}{2\pi \sqrt{4(1q)x^2}}\underset{k=0}{\overset{\mathrm{}}{}}\frac{(1bq^k)\left(1q^{k+1}\right)\left((1+q^k)^2(1q)x^2q^k\right)}{(1bq^{2k})^2(1q)aq^k(1+bq^{2k})x+(1q)(bx^2+a^2)q^{2k}}.$$

###### Proof.

By Theorem 2, the distribution of polynomials $`p_n`$ solves (2.1) with $`\rho =\sqrt{b},y=a/\rho `$. Thus the formula follows from Corollary 2. ∎

###### Remark 2.

Iterating (2.1) we see that the measure corresponding to the parameter $`\rho _1\rho _2`$ instead of $`\rho `$ is given by

$`\mu (|\rho _1\rho _2,x)={\displaystyle }\mu (|\rho _1,y)\mu (dy|\rho _2,x).`$ (2.6)
For $`\left|q\right|<1,|\rho |<1`$ the density of $`\mu `$ is given in Corollary 2, hence after simplifying common factors and substitution $`x=2\xi /\sqrt{1q},`$ $`y=2\eta /\sqrt{1q},`$ $`z=2\zeta /\sqrt{1q}`$, the relationship (2.6) takes the following form

$`{\displaystyle _1^1}{\displaystyle \underset{k=0}{\overset{\mathrm{}}{}}}{\displaystyle \frac{(1\rho _1^2q^k)\left(1q^{k+1}\right)\left((1+q^k)^24\eta ^2q^k\right)}{(1\rho _1^2q^{2k})^24\rho _1q^k(1+\rho _1^2q^{2k})\eta \zeta +4\rho _1^2(\eta ^2+\zeta ^2)q^{2k}}}`$
$`\times {\displaystyle \underset{k=0}{\overset{\mathrm{}}{}}}{\displaystyle \frac{(1\rho _2^2q^k)}{(1\rho _2^2q^{2k})^24\rho _2q^k(1+\rho _2^2q^{2k})\xi \eta +4\rho _2^2(\eta ^2+\xi ^2)q^{2k}}}{\displaystyle \frac{d\eta }{2\pi \sqrt{1\eta ^2}}}`$
$`=`$ $`{\displaystyle \underset{k=0}{\overset{\mathrm{}}{}}}{\displaystyle \frac{(1\rho _1^2\rho _2^2q^k)}{(1\rho _1^2\rho _2^2q^{2k})^24\rho _1\rho _2q^k(1+\rho _1^2\rho _2^2q^{2k})\xi \zeta +4\rho _1^2\rho _2^2(\zeta ^2+\xi ^2)q^{2k}}}.`$
## 3. Determinants of Hankel matrices

In this section we are interested in calculating the determinants of the Hankel matrices

$$M_n=[m_{i+j}]_{i,j=0,\mathrm{}n1},$$

where $`m_i=x^i\mu (dx)`$ are the moments of certain (perhaps signed) measure $`\mu `$. It is well known that for positive measures we must have $`detM_n0`$, and that these determinants can be read out from the three term recurrence for the corresponding monic orthogonal polynomials.

Consider first the moments $`m_k(y)=x^k\mu (dx)`$ of the (perhaps signed) measure $`\mu =\mu _{y,\rho }`$, which solves (2.1). Then $`m_k(y)`$ are polynomials of degree $`k`$ in variable $`y`$, and can be written as follows. Let $`a_{n,2i}`$, $`in/2`$ be the coefficients in the expansion of monomial $`x^n`$ into the $`q`$-Hermite polynomials,

$$x^n=\underset{i=0}{\overset{n/2}{}}a_{n,2i}H_{n2i}\left(x|q\right),n0.$$

Then

$$m_n(y)=x^n𝑑\mu \left(x\right)=\underset{k=0}{\overset{n/2}{}}\rho ^{n2k}a_{n,2k}H_{n2k}\left(y|q\right).$$

Let $`S_n`$ be the Hankel matrix of moments $`m_k(y)`$,

$$S_n(y|q,\rho )=\left[\begin{array}{cccccccccccccccccccc}m_0(y)& m_1(y)& \mathrm{}& m_{n1}(y)& & & & & & & & & & & & & & & & \\ m_1(y)& m_2(y)& & & & & & & & & & & & & & & & & & \\ \mathrm{}& & \mathrm{}& \mathrm{}& & & & & & & & & & & & & & & & \\ m_{n1}(y)& & \mathrm{}& m_{2n2}(y)& & & & & & & & & & & & & & & & \end{array}\right].$$

It is well known that $`detS_n`$ is the product of the coefficients at the third term of (2.2), which implies the following.

###### Corollary 4.

$`detS_{n+1}/detS_n=[n]_q!_{i=1}^n\left(1\rho ^2q^{i1}\right).`$

Our second Hankel matrix has an even simpler form. As indicated in \[IS97\], \[IS02\] the $`q`$-Hermite polynomials can be viewed as moments of a signed measure, $`H_n(x|q)=u^n\mu (du|x,q)`$. It turns out that measure $`\mu (du|x,q)`$ cannot be positive even for a single value of $`x`$. To see this, consider the following $`n\times n`$ matrices

$$M_n(x|q)=\left[\begin{array}{cccccccccccccccccccc}H_0(x|q)& H_1(x|q)& H_2(x|q)& \mathrm{}& H_{n1}(x|q)& & & & & & & & & & & & & & & \\ H_1(x|q)& H_2(x|q)& & & H_n(x|q)& & & & & & & & & & & & & & & \\ H_2(x|q)& & \mathrm{}& & H_{n+1}(x|q)& & & & & & & & & & & & & & & \\ \mathrm{}& & & \mathrm{}& \mathrm{}& & & & & & & & & & & & & & & \\ H_{n1}(x|q)& H_n(x|q)& & \mathrm{}& H_{2n2}(x|q)& & & & & & & & & & & & & & & \end{array}\right].$$

The following $`q`$-generalization of \[Kra99, (3.55)\] shows that the determinants $`detM_n(x|q)`$ are free of the variable $`x`$, and take negative values.

###### Theorem 3

$$\frac{detM_{n+1}}{detM_n}=(1)^nq^{n(n1)/2}[n]_q!.$$

###### Proof.

Using (1.4), we row-reduce the first column of the matrix. Namely, from the second row of $`M_{n+1}`$, we subtract the first one multiplied by $`x`$. Similarly, for $`i3`$, we subtract $`x`$ times row $`i1`$ and add the $`i2`$-th row multiplied by $`[i1]_q`$. Taking (1.4) into account, $`detM_{n+1}(x|q)`$ becomes

$$det\left[\begin{array}{cccccccccccccccccccc}H_0& H_1& H_2& \mathrm{}& H_n& & & & & & & & & & & & & & & \\ 0& ([0][1])H_0& ([0][2])H_1& & ([0][n])H_{n1}& & & & & & & & & & & & & & & \\ 0& ([1][2])H_1& ([1][3])H_2& & ([1][n+1])H_n& & & & & & & & & & & & & & & \\ \mathrm{}& & & \mathrm{}& \mathrm{}& & & & & & & & & & & & & & & \\ 0& ([n1][n])H_{n1}& ([n1][n+1])H_n& \mathrm{}& ([n1][2n1])H_{2n}& & & & & & & & & & & & & & & \end{array}\right].$$

Now, we use the fact that for $`mn`$ we have $`[n]_q\left[m\right]_q=q^m\left[nm\right]_q.`$ Thus $`detM_{n+1}(x|q)`$ becomes

$$det\left[\begin{array}{cccccccccccccccccccc}H_0& H_1& H_2& \mathrm{}& H_{n1}& & & & & & & & & & & & & & & \\ 0& [1]H_0& [2]H_1& & [n]H_{n1}& & & & & & & & & & & & & & & \\ 0& q[1]H_1& q[2]H_2& & q[n]H_n& & & & & & & & & & & & & & & \\ \mathrm{}& & & \mathrm{}& \mathrm{}& & & & & & & & & & & & & & & \\ 0& q^{n1}[1]H_{n1}& q^{n1}[2]H_n& \mathrm{}& q^{n1}[n]H_{2n}& & & & & & & & & & & & & & & \end{array}\right].$$

Expanding $`detM_{n+1}`$ with respect to the first column, and factoring out the common factors $`q^{i1}`$ from the $`i`$-th row and $`[j]_q`$ from the $`j`$-th column of the resulting matrix, we get

$$detM_{n+1}=\left(1\right)^nq^{_{i=1}^{n1}i}\underset{j=1}{\overset{n}{}}[j]detM_n=\left(1\right)^nq^{n\left(n1\right)/2}[n]_q!detM_n.$$

Formula stated in Corollary 4 was originally discovered through symbolic computations and motivated this paper. We were unable to find a direct algebraic proof along the lines of the proof of Theorem 3, and our search for the explanation of why $`detS_n(y)`$ does not depend on $`y`$ lead us to Al-Salam–Chihara polynomials and identity (1.9).

The the fact that Hankel determinants formed of certain linear combinations of the $`q`$-Hermite polynomials do not depend on the argument of these polynomials as exposed in Theorem 3 and Corollary 4 is striking and unexpected to us. A natural question arises whether other linear combinations have this property.

Acknowledgement Part of the research of WB was conducted while visiting Warsaw University of Technology. The authors thank Jacek Wesołowski for several helpful discussions.