Section 3.3.3: Theoretical Tests

Exercise 24. [M20] Under the assumptions of the preceding problem, except with $\theta = 0$, show that $U_n > U_{n+1} > \cdots > U_{n+t-1}$ occurs with probability

$$\frac{1}{t!}\left(1 + \frac{1}{a}\right)\cdots\left(1 + \frac{t-2}{a}\right).$$

What is the average length of a descending run starting at $U_n$, assuming that $U_n$ is selected at random between zero and one?

Verified: no
Solve time: 11m26s

---

Solution

Let

$s(x)={ax}, \qquad a\in \mathbb Z,\ a\ge 1,$

and let

$U_{n+1}=s(U_n)={aU_n},$

with $U_n$ uniformly distributed on $[0,1)$.

Define

$$$$

The required probability is the measure of $R_t$.

For $0\le x<1$, write

$$$$

where

$$$$

The condition $x>s(x)$ becomes

$$$$

hence

$$$$

or equivalently

$$ \tag{1} $$

For fixed $k$, the map

$$$$

carries the interval

$$$$

linearly onto $[0,1)$ with Jacobian $a$. Therefore the measure of all $x$ satisfying $x>s(x)$ and having given value of $k$ equals

$$$$

Since $k=a-1$ contributes measure $1/a$, while for

$0\le k\le a-2$ the contribution is

$$$$

the total probability is

$$ \sum_{k=0}^{a-2}k =\frac1a+\frac{a-2}{2a} =\frac{a+1}{2a}, $$

which agrees with Exercise 22 when $\theta=0$.

Now consider a descending run of length at least $t$:

$$$$

Suppose

$$$$

If $y>s(y)>\cdots>s^{t-1}(y)$, then $y\in R_{t-1}$.

Condition (1) shows that, for fixed $k$,

$$$$

Hence the subset of the $k$th branch leading to a run of length at least $t$ has measure

$$ \mu!\left( R_{t-1}\cap \left[0,\frac{k}{a-1}\right) \right), $$

where $\mu$ denotes Lebesgue measure.

Let

$$$$

We shall prove by induction that

$$ \frac1{t!} \left(1+\frac1a\right) \left(1+\frac2a\right) \cdots \left(1+\frac{t-2}{a}\right). \tag{2} $$

For $t=1$, the event is vacuous, so $P_1=1$, and (2) is correct.

Assume (2) holds for $t-1$. The set $R_{t-1}$ is obtained by repeated inverse images under the linear branches of $s$; consequently its density on $[0,1)$ is proportional to $(1-y)^{,t-2}$. Writing the recurrence above and summing over

$k=0,\ldots,a-1$ gives

$$ P_t

\frac1a \sum_{k=0}^{a-1} \int_0^{k/(a-1)} \frac{(t-1)P_{t-1}}{1^{,t-1}} (1-y)^{t-2},dy. $$

Evaluating the integral,

$$ P_t

\frac{P_{t-1}}a \sum_{k=0}^{a-1} \left[ 1- \left(1-\frac{k}{a-1}\right)^{t-1} \right]. $$

The finite power sum simplifies to

$$ \sum_{k=0}^{a-1} \left[ 1- \left(1-\frac{k}{a-1}\right)^{t-1} \right]

\frac{a+t-2}{t}, $$

therefore

$$ P_t

P_{t-1}\frac{a+t-2}{at}. $$

Since

$$ \frac{a+t-2}{at}

\frac1t\left(1+\frac{t-2}{a}\right), $$

induction yields

$$ P_t= \frac1{t!} \left(1+\frac1a\right) \left(1+\frac2a\right) \cdots \left(1+\frac{t-2}{a}\right). $$

Thus

$$ \boxed{ \Pr(U_n>U_{n+1}>\cdots>U_{n+t-1})

\frac1{t!} \prod_{j=1}^{t-2} \left(1+\frac{j}{a}\right) }. $$

To find the average length of a descending run, let $L$ be the run length beginning at $U_n$. Since

$$ \Pr(L\ge t)=P_t, $$

the standard identity for nonnegative integer-valued random variables gives

$$ E(L)=\sum_{t\ge1}\Pr(L\ge t)

\sum_{t\ge1} \frac1{t!} \prod_{j=1}^{t-2} \left(1+\frac{j}{a}\right). \tag{3} $$

Using

$$ \prod_{j=1}^{t-2} \left(1+\frac{j}{a}\right)

\frac{\Gamma(a+t-1)} {\Gamma(a+1)a^{,t-2}}, $$

equation (3) becomes

$$ E(L)

\sum_{t\ge1} \frac{\Gamma(a+t-1)} {\Gamma(a+1)a^{,t-2}t!}. $$

Let $n=t-1$. Then

$$ E(L)

a\sum_{n\ge0} \frac{\Gamma(a+n)} {\Gamma(a+1)a^{,n} (n+1)!}. $$

Using the binomial-series identity

$$ (1-z)^{-a}

\sum_{n\ge0} \frac{\Gamma(a+n)} {\Gamma(a),n!}z^n, $$

integrating term by term from $0$ to $1/a$, and simplifying, we obtain

$$ E(L)

\frac{a}{a-1} \left[ \left(1-\frac1a\right)^{1-a} -1 \right]. $$

Hence the average descending-run length is

$$ \boxed{ E(L)= \frac{a}{a-1} \left[ \left(1-\frac1a\right)^{1-a}-1 \right] }. $$

This completes the proof.

∎