5
$\begingroup$

Let $X$ be a IID random variable with support in $[0,1]$ and CDF given by a Beta distribution, i.e. $X \sim \mathrm{Beta}(\alpha,1)$.

Let $Z_i = \min(X_i,Y_{i-1})$, $\forall i >1$. I would like to compute $\mathbb{E}[Z_i]$, knowing that:

\begin{align} Y_1 &= Z_1 = X_1, \; \mbox{when} \; i=1,\\ Y_i &= \frac{1}{i} \sum \limits_{t=1}^{i} Z_t, \forall i >1. \end{align}

How can I compute $\mathbb{E}[Z_i]$ ? As $\alpha \to \infty$, $\mathbb{E}[X] = \frac{\alpha}{\alpha+1} \to 1$, implying that $\mathbb{E}[Y] \to 1$ as well. Then intuitively $\mathbb{E}[Z_i] \to 0$. Am I right ? How could I formulate $\mathbb{E}[Z_i]$ more generally ?

$\endgroup$
  • $\begingroup$ Is there perhaps a typographical error near the end? Since $Y_i$ is the mean of the $Z_t$, how could it be possible or even "intuitive" for the expectation of the $Z_t$ to approach zero while the expectation of their averages approaches $1$? $\endgroup$ – whuber Sep 12 '14 at 15:55
  • $\begingroup$ What is $Y_1$? It's not defined in your question. $\endgroup$ – heropup Sep 12 '14 at 16:17
  • $\begingroup$ @heropup $Y_1 = X_1$. $\endgroup$ – flo Sep 12 '14 at 16:51
  • $\begingroup$ @whuber Not sure but my intuition was that the expected probability for $Z$ to be smaller than $1$ is $0$ when both $\mathbb{E}[X]$ and $\mathbb{E}[Y]$ tend towards $1$. $\endgroup$ – flo Sep 12 '14 at 16:52
10
$\begingroup$

Explicit computation of these expectations appears to be out of the question once the index exceeds two or three, so I will focus on issues that had been emphasized in earlier versions of the question:

  1. What happens (asymptotically) as $i$ increases?

  2. What happens as $\alpha$ increases?

The answers turn out to be interesting, unusual, and perhaps counterintuitive. I was surprised by the results and therefore felt it worthwhile to post such a lengthy answer for those who appreciate the subtle interplay of intuition, simulation, and analysis and to expose any flaws in my analysis to critical examination.


Exploration and Intuition

Let's get a handle on this process by describing it in words. A sequence of random values $(X_i)$ generates sequences $(Y_i)$ and $(Z_i)$. $Z_i$ is the smaller of (a) the current value of $X$ (namely, $X_i$) and (b) the average of all its previous values (which is called $Y_{i-1}$). This has two effects:

  1. Because $Z_i$ cannot be any larger than $Y_{i-1}$, it follows (by inducting on $i$) that averaging $Z_i$ with all the previous $Y_j$ cannot increase $Y$. Thus, $(Y_i)$ is a non-increasing sequence. It decreases only when a value of $X$ falls below the running average of the $Z_i$.

  2. The further along we go (that is, the larger the index $i$ is), the smaller is the possible change from $Y_{i-1}$ to $Y_i$, because the weight of $Z_i$ in the average is just $1/i$.

These effects show that any single realization of the process $(Y_i)$ must decrease more and more slowly, leveling off to a horizontal asymptote (because the $X_i$ are bounded below by $0$). Furthermore, one's intuition might suggest that when smaller values of $X_i$ are rare, then this asymptote ought to be positive. That is precisely what simulations suggest, as in the left hand plot in the figure which shows one realization of $(X_i)$ (as gray dots) and the corresponding $(Y_i)$ (as a dark graph) and $(Z_i)$ (as a faint red graph bouncing between the graph of $(Y_i)$ and the lowest values of the $(X_i)$):

Figure

The right hand plot displays, in red, $50$ independent realizations of $(Y_i)$, again for $\alpha=2$. (The black curve will be explained later.) Indeed, all these realizations seem to level off quickly to asymptotic values. The striking thing, though, is that these values differ quite a bit. The differences are induced by the large changes occurring very early on in the processes: when the very first one or two of the $X_i$ are small, all subsequent values of $(Y_i)$ must be even smaller. Here we have an example of a stochastic process with an extremely high degree of autocorrelation.

If this intuition is correct, then the expectations $\mathbb{E}(Y_i)$ ought to be a decreasing function of $i$ and level off to some nonzero value depending on $\alpha$.

Most of this intuition is good--except that the probability that $(Y_i)$ levels off to a nonzero value is nil. That is, despite all appearances, essentially all realizations of $(Y_i)$ eventually go to zero! One of the more amazing results concerns how long this will take. First, though, let's see why a nonzero asymptotic value is so unlikely.

Analysis of $(Y_i)$

Consider one realization of $(X_i)$, which can be denoted $(x_i) = x_1, x_2, \ldots, x_i, \ldots$. Associated with it are realizations of $(Y_i)$ and $(Z_i)$, similarly denoted with lower case letters. Suppose that $(y_i)$ reaches some value $y \gt 0$ asymptotically. Since $(y_i)$ is nondecreasing, this means that for any $\epsilon\gt 0$ there exists an integer $n$ such that

$$y + \epsilon > y_i >= y$$

for all $i \ge n$.

Consider what happens when $x_i$ has a value smaller than $y_{i-1}$. The change in the running average $(y_i)$ is

$$y_{i} - y_{i-1} = \frac{(i-1)y_{i-1} + x_i}{i} - y_{i-1} = \frac{iy_{i-1} + x_i-y_i}{i}- y_{i-1} = \frac{x_i-y_i}{i}.$$

I am going to underestimate the size of that change by replacing it by $0$ if $z_i \ge y$ and, otherwise, by $(z_i - y)/i$. In other words, let's only count the amount by which $x_i$ is less than the asymptotic value $y$.

I will further underestimate the rate at which such decreases occur. They happen exactly when $x_i \le y_{i-1}$, which is more often than when $x_i \le y$. Writing $F$ for the CDF of $X$, this rate is $F(y)$, allowing us to express the expected value of the change at step $i$ as being an amount more negative than

$$\frac{F(y) (\mathbb{E}(X\, |\, X \lt Y) - y)}{i}.$$

Consider, now, what happens to $(y_i)$ starting at $y_n$ and continuing for a huge number of steps $m \gg n$ to $y_{m+n}$. Accumulating these conservative estimates of the decreases causes $y_n$ to drop to a value expected to be less than the sum of the preceding fractions. I will underestimate the size of that sum by replacing the denominators $n+1, n+2, \ldots, n+m$ by the largest denominator $m+n$. Because there are now $m$ identical terms in the sum, this underestimate equals

$$\frac{m F(y) (\mathbb{E}(X\, |\, X \lt Y) - y)}{m+n}.$$

Finally, we need to compare this expectation to what really is happening with the realization $(y_i)$. The Weak Law of Large Numbers says that for sufficiently large $m$, this realization is almost certain to exhibit a net decrease that is extremely close to the expected decrease. Let's accommodate this sense of "extremely close" by (a) taking $m$ much larger than $n$ but (b) underestimating $m/(m+n)$ as $1/2$. Thus,

It is almost certain that the change from $y_n$ to $y_{m+n}$ is greater in magnitude than

$$\beta(y) = \frac{F(y) (\mathbb{E}(X\, |\, X \lt Y) - y)}{2} \le 0.$$

It is of logical importance that $m$ did not really depend on $n$: the only relationship among them is that $m$ should be much larger than $n$. Return, then, to the original setting where we supposed that $y$ was a nonzero horizontal asymptote of $(y_i)$. Choose $\epsilon = -\beta(y)$. Provided this was nonzero, it determined the value of $n$ (at which the sequence $(y_i)$ finally approaches within $\epsilon$ of its asymptote). By taking a sufficiently large $m$, we have concluded that $(y_i)$ eventually must decrease by more than $\epsilon$. That is,

$$y = y + \epsilon + \beta(y) > y_{m+n}.$$

Therefore we must have been wrong: either $y$ is not an asymptote of $(y_i)$ or else $\beta(y) = 0$. However, $\beta(y) = 0$ only when $y$ is smaller than all numbers in the support of $X$. In the case of a Beta distribution (any Beta distribution), the support is always the full unit interval $[0,1]$. Consequently, the only possible value at which almost all realizations $y_i$ can level off to is $0$. It follows immediately that

$$\lim_{i\to \infty} \mathbb{E}(Y_i) = 0.$$


Conclusions

For $X \sim $ Beta$(\alpha, 1)$, $F(x) = x^\alpha$ concentrates more and more of the probability near $1$ as $\alpha$ increases. Consequently it is obvious (and easily proven) that

$$\lim_{\alpha \to \infty} \mathbb{E}(Y_i) = 1.$$

Since $Z_i \le Y_i$ by definition, its expectation is squeezed between the expectation of $Y_i$ and zero, whence

$$\lim_{i\to \infty} \mathbb{E}(Z_i) = 0.$$


Comments

Notice that the results for the limiting values with respect to $i$ did not require that the $X_i$ have Beta distributions. Upon reviewing the argument is becomes clear that indeed the $X_i$ do not need to have identical distributions, nor do they need to be independent: the key idea behind the definition of $\beta(y)$ is that there needs to be a nonzero chance of seeing values of the $X_i$ that are appreciably less than $y$. This prevents most realizations $(y_i)$ from leveling off to any value $y$ for which $\beta(y)\gt 0$.

The rates at which realizations reach zero, however, can be astonishingly slow. Consider the problem setting again, in which the $X_i$ are iid with common CDF $F(x) = x^\alpha$. According to the previous estimates the expected rate of change is approximately

$$\frac{F(y) (\mathbb{E}(X\, |\, X \lt Y) - y)}{i} = \frac{y^\alpha (\alpha/(\alpha+1)y - y)}{i}.$$

The solution can be closely approximated by taking these differences to be derivatives of the expectation $f(i) = \mathbb{E}(Y_i)$ and integrating the resulting differential equation, yielding (for $\alpha \gt 1$)

$$f(i) \approx \left(\frac{\alpha}{\alpha+1}\left(\log(i)+C\right)\right)^{-1/\alpha}$$

for some constant of integration $C$ (which we may ignore when studying the asymptotics for $i\to\infty$). Remember, this was obtained by consistently underestimating the rate of decrease of $f$. Therefore, $f$ approximates an upper bound of the realizations of $(Y_i)$ with probability $1$. Its graph (for $C=0$) is the thick black curve shown in the right-hand plot of the figure. It has the right shape and actually seems to be a pretty good approximation to the upper envelope of these realizations.

This is a very slowly decreasing function. For instance, we might inquire how long it would take for the realizations to draw close to $0$: say, down to $y$. The general solution (ignoring $C$, which makes relatively little difference) is

$$i \approx \exp\left(\frac{\alpha+1}{\alpha}y^{-\alpha}\right).$$

Even with $\alpha=2$ (where each $X$ has an appreciable chance of being close to $0$), and $y=0.1$ (which isn't even terribly close to $0$), the solution is $i\approx 1.4\times 10^{65}$. For $\alpha=100$ and $y=1/2$, $i$ is near $10^{10^{30}}$. I am not going to wait around for that simulation to finish! The moral here is that simulations can sometimes deceive. Their correct interpretation must be informed by an analysis of the underlying phenomenon being simulated.

These asymptotic approximations appear to be pretty good, bringing us at least partway back from the purely limiting results obtained and the request in the question for information about the individual expectations $\mathbb{E}{Z_i}$, which will be less than but close to $\mathbb{E}{Y_i}$.

$\endgroup$
  • 1
    $\begingroup$ Thanks a lot for this complete and very interesting analysis, @whuber. $\endgroup$ – flo Sep 16 '14 at 21:25
2
$\begingroup$

A conditional approach appears possibly helpful here.

The variable $Z_{i+1}$ can be written using indicator functions,

$$Z_{i+1} = X_{i+1}\cdot I_{\{X_{i+1} \leq Y_i\}}+Y_i\cdot [1-I_{\{X_{i+1} \leq Y_i\}}] $$

Denote $\mathcal F_i$ the sigma-algebra at time $i$, that includes $Z_i$ and hence $Y_i$ and consider the conditional expected value

$$E[Z_{i+1}\mid \mathcal F_i] = E[X_{i+1}\cdot I_{\{X_{i+1} \leq Y_i\}}\mid \mathcal F_i]+Y_i\cdot \Big(1-E[I_{\{X_{i+1} \leq Y_i\}}\mid\mathcal F_i]\Big) $$

$$=\int_0^{Y_i}xf_X(x)dx + Y_i\cdot \Big(1-P[X_{i+1} \leq Y_i]\Big)$$

where we have used the fact that the $X$'s are i.i.d. Using the $\text{Beta}(\alpha,1)$ distributional assumption on $X$ we have

$$E[Z_{i+1}\mid \mathcal F_i] = \frac{\alpha}{1+\alpha}x^{1+\alpha}\Big|^{Y_i}_0+Y_i\cdot \Big(1-Y_i^\alpha\Big) =Y_i -\frac 1{1+\alpha}Y_i^{1+\alpha}$$

Therefore

$$E(Z_{i+1}) = E\Big(E[Z_{i+1}\mid \mathcal F_i]\Big) = E(Y_i) -\frac 1{1+\alpha}E(Y_i^{1+\alpha}) \tag{1}$$

We can write

$$(1+i)Y_{i+1} = \sum \limits_{t=1}^{i+1} Z_t = \sum \limits_{t=1}^{i} Z_t +Z_{i+1}$$

$$\Rightarrow \frac {1+i}{i}E[Y_{i+1}] = E(Y_i) +\frac 1i E(Z_{i+1}) \Rightarrow E(Y_i) = \frac {1+i}{i}E[Y_{i+1}] - \frac 1i E(Z_{i+1})$$

Inserting into $(1)$ and re-arranging we get

$$E(Z_{i+1}) = \frac {1+i}{i}E[Y_{i+1}] - \frac 1i E(Z_{i+1}) -\frac 1{1+\alpha}E[Y_i^{1+\alpha}]$$

$$\Rightarrow E(Z_{i+1}) = E[Y_{i+1}]-\frac i{1+i}\frac 1{1+\alpha}E[Y_i^{1+\alpha}] \tag{2}$$

which links (partly) the concurrent expected values of $Z$ and $Y$.

Moreover, equating the right-hand-sides of $(1)$ and $(2)$ and re-arranging we get

$$E(Y_{i+1}-Y_i) = -\frac{1}{1+i}\frac 1{1+\alpha}E[Y_i^{1+\alpha}] \tag{3}$$

which perhaps can make us "suspect" that the approach to zero may be slow.

$\endgroup$
  • $\begingroup$ The idea of obtaining a recursion is excellent, but how do you propose to relate the expectation of $Y_i^{1+\alpha}$ to the expectation of $Y_i$ itself? $\endgroup$ – whuber Sep 17 '14 at 15:36
  • $\begingroup$ @whuber I am still thinking about it, and trying various approaches. Not very optimistic, for the moment. $\endgroup$ – Alecos Papadopoulos Sep 17 '14 at 15:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.