Take the 2-minute tour ×

Suppose I have a variable $s$ that has a geometric distribution with success parameter x. So the probability of success on trial $s$ is

$p_s = (1 - x)^{s - 1} x$,

Consider the following function of $s$

$V(s) = \delta^s$,

where $\delta < 1 $. Then the expected value of this function is given by

$\sum_ 1^{\infty} V(s) p_s = \frac{\delta x} {1 - \delta (1 - x)}$.

Consider now the deviation of V(s) from its mean :

$(V(s) - \frac{\delta x} {1 - \delta (1 - x)}) $

What distribution does this have?

What I am really interested in is the behavior of the follow ordinary stochastic differential equation:

$\dot{V} = \delta^s - V$,

stochastic because the law of motion depends on the random variable $s$. The stochastic approximation technique allows me to focus on the mean dynamics, which are given by

$\dot{V} = \frac{\delta x} {1 - \delta (1 - x)} - V$,

whose equilibrium is simply $\hat{V} = \frac{\delta x} {1 - \delta (1 - x)}$.

I would like to characterize the large deviation properties of the original ODE, IE calculate the exponential likelihood $V$ crosses a particular boundary $c$.

For example, if $\delta = .95$ and $x= .01$, $\hat{V} = 0.159664$. If we set $V_0 = 0.159664$, and let $V_t = V_{t-1} + .2 (\delta^s - V_{t-1})$, and $s$ has the above distribution, how do I calculate the expected time to $V_t$ crossing, say, $c=.4$? What is the associated rate function?

Editing to give the background to the problem:

I am interested in the following stochastic dynamic system:

$V_t = V_{t-1} + \gamma (\delta^{S_{t-1}} - V_{t-1})$,

where $\delta <1$, $\gamma<1$, both positive, and each $S_t$ is an i.i.d. geometric random variable with success parameter $x$. What this models is agents who have to wait a geometric length of time to get a reward of value 1, and they have time discount factor $\delta$, and they are learning the expected value of their reward using a constant gain adaptive learning procedure, with gain $\gamma$.

So considering $S$ as following a Poisson, rather than Geometric, makes little difference to the sense of the problem. The goal is

  1. Find the equilibria of the learning dynamics

  2. Characterize the mean time to escape from this equilibrium, the large deviation properties.

So, for large deviation properties, I should be able to use something like Cramer's theorem, I think. As Mike says below, iterating the dynamics gives

$V_t = (1−γ)^tV_0+γ\sum_{k=0}^{t−1}(1−γ)^{t−1−k}δ^{S_k}$

So it all depends on $\sum_{k=0}^{t−1}(1−γ)^{t−1−k}δ^{S_k}$, the discounted sum of some random variables.

The Probability that $V_t >c$ is then given by

$Pr(V_t > c ) = Pr(\sum_{k=0}^{t−1}(1−γ)^{t−1−k}δ^{S_k} > \frac{c-(1−γ)^tV_0}{\gamma})$

Let $Z:=\frac{c-(1−γ)^tV_0}{\gamma}$. so we need the distribution of $\sum_{k=0}^{t−1}(1−γ)^{t−1−k}δ^{S_k}$, which as Mike says is a discounted sum of independent random variables, and so we have that this is approximately normal, for large $t$.

Turning now to the question of large deviations, if things were not discounted by powers of $(1-\gamma)$, we could appeal directly to Cramer's Theorem;

$ Pr(\sum \delta^{S_k} > n a) \leq Exp[-n(r^* a - Log(E[Exp(r^* \delta^S)])] $

where $r^* $ is chosen to maximize $r a - Log(E[Exp(r \delta^S)]$. The problem would be to simply calculate the moment generating function of $\delta^S$. But, I don't exactly want $Pr(\sum \delta^{S_k} > n a)$, I need $ Pr(\sum (1-\gamma)^{t-1-k} \delta^{S_k} > a)$; so not an average of $\delta^{S_k}$s, but a discounted sum. so it is not quite a direct application.

share|improve this question
If a random variable $X$ has distribution $P_X$, then $Y = X-E(X)$ is merely a translated version of $X$. It has the distribution $P_Y(Y = y) = P_X(X = E(X)+y)$. This answers the first part of your question. –  Dinesh Oct 12 '10 at 22:10
Since $\sum (1-\gamma)^{t-1-k} \delta^{S_k}$ is approximately normal, you can get a good approximation to $P(\sum (1-\gamma)^{t-1-k} \delta^{S_k} > a)$ from software or from a table of normal distribution values. –  Mike Spivey Oct 19 '10 at 20:02

1 Answer 1

If $\delta > 0$, then the transformations you are applying to the random variable $S$ to get the quantity $T = \delta^S - \frac{\delta x}{1 - \delta(1-x)}$ are all one-to-one. Since $S$ is discrete, this means you can construct the probability distribution of $T$ by inverting those transformations. This would yield

$$P(T = t) = P\left(\delta^S - \frac{\delta x}{1 - \delta(1-x)} = t\right) = P\left(S = \frac{\ln\left(\frac{\delta x}{1 - \delta(1-x)} + t\right)}{\ln \delta}\right) = (1 - x)^{y-1} x,$$

where $$y = \frac{\ln\left(\frac{\delta x}{1 - \delta(1-x)} + t\right)}{\ln \delta},$$

for any value of $t$ such that $y$ is in the set $\{1, 2, \ldots\}$.

Maybe someone else can help you with the other questions.

I've thought some more about your problem. The recursion in your dynamical system yields the expression

$$V_t = (1- \gamma)^t V_0 + \gamma \sum_{k=0}^{t-1} (1 - \gamma)^{t-1-k} \delta^{S_k}.$$

So you have a sum of discounted random variables. If they were not discounted the distribution would be approximately normal for large $t$. It turns out, though, that there is an analogous result for the distribution of a sum of discounted random variables -- a discounted central limit theorem, as it were. You might have some success using this discounted central limit theorem as an approximation.

Here are the specifics. Let $Y_v = \sum_{k=0}^{\infty} v^k X_k$, where the $X_k$'s are independent and have a common distribution function. Let

$$Z_v = \frac{\sqrt{1-v}}{\sigma} \left(Y_v - \frac{\mu}{1-v}\right).$$

Then $Z_v$ is asymptotically normal with mean $0$ and variance $\frac{1}{1+v}$, for $v \to 1$, where $\mu$ and $\sigma$ are the common mean and standard deviation of the $X_k$'s. (The expected value of $|X_k - \mu|^3$ must exist, too.)

Moreover, there is a bound on the error in this approximation. Let $F_v(x)$ and $N_v(x)$ be the cdf's of the $Z_v$ random variable and of a normal with mean $0$ and variance $\frac{1}{1+v}$, respectively. Then

$$|F_v(x) - N_v(x)| \leq \frac{C \rho \sqrt{1-v}}{\sigma^3},$$ where $\rho = E[|X_k - \mu|^3]$ and $C = 5.4$.

The reference is Hans Gerber, "The Discounted Central Limit Theorem and Its Berry-Esseen Analogue," Annals of Mathematical Statistics 42(1), pp. 389-392, 1971.

share|improve this answer
I feel like it should be reducible to a statement about a negative binomial distribution - allowing $V_t$ to wander far from $\hat{V}$ really requires getting enough realizations of $S$ that are from from \emph{its} mean. So it ought to be reducible to a statement about sums of realizations of $S$, and the sum of geometric variables has a negative binomial distribution, whose large deviation bounds are quite sharp, since it is exponential in the tail. For some reason I am having trouble putting it into that form, however. –  Dennis Oct 13 '10 at 14:04
After working a bit, it definitely seems that what I need is to say something about $\sum_{t=1}^n \delta^{S_t}$, that is, my deviation properties depend on the distribution of sums $\delta^{S_t}$. Your work above gives the distribution of each term of this sum, and it is something like a rescaled geometric. Does it follow that the sum is some kind of negative binomial? –  Dennis Oct 13 '10 at 19:46
I don't think so. The reason has to do with the support of a geometric distribution (which is closed under addition) vs. that of the transformed distribution you want (which is not necessarily). For example, take $n = 2$. If $S_1$ and $S_2$ are geometric, then you can achieve $S_1 + S_2 = 2$ via any of $(0,2), (1,1), (0,1)$, which is where the negative binomial aspect comes from. However, with your transformed geometrics and $\delta = 0.5$, then you can achieve $\delta^{S_1} + \delta^{S_2} = 1.25$ only with $(0,2)$ and $(2,0)$. The value $(1,1)$ yields $\delta^{S_1} + \delta^{S_2} = 1$. –  Mike Spivey Oct 13 '10 at 20:30
Can you approximate the geometric distribution with an exponential one? You wouldn't run into the same kinds of problems with the support if you were working with a continuous random variable. –  Mike Spivey Oct 13 '10 at 20:31
I think that could be easily justified, in this context. I will write up something to add to the question, to give a little more background in the problem. –  Dennis Oct 13 '10 at 20:37

Your Answer


