I am currently working on the following Problem:

Imagine you are given a $d$-ary tree $T_d$, which means an infinite tree with one vertex $x_0$ on top and in which each vertex has $d$ children.

Next, I'm assigning iid random variables $\omega_e$ to all edges $e$ in the graph. Here $\omega_e$ should follow an exponential distribution with mean $d$.

Now define $$X_n:=\min\{\frac{1}{|t|}\sum_{e\in t}\omega_e: t\text{ is a subgraph of }T_d, |t|=n, x_0\in t\}.$$

where, in a slight abuse of notation, I wrote $|t|=n$ to say "$t$ has exactly $n$ edges" and $e\in t$ just means "the edge $e$ is contained in the edge set of the subgraph $t$"

So I'm basically looking for the "lightest" or "shortest" subgraphs of a given length $n$ and then compute the mean weight.

So much for the model, and here comes the actual question:

Does the sequence $X_n$ satisfy a large deviations principle for $n\to\infty$? If yes, what are speed and rate function?

I already tried applying the Gärtner-Ellis Theorem but couldn't show that $$\Lambda(\lambda)=\lim_{n\to\infty}\frac{1}{n}\log\mathbb{E}[e^{n\lambda X_n}]$$ is indeed finite for every $\lambda\in \mathbb{R}$ (which is one of the two prerequisites of the Theorem, the other being that the map $\lambda\mapsto\Lambda(\lambda)$ is differentiable.)

In case it helps: you can use that $X_n$ converges in probability to a constant $c$ for $n\to\infty$ (I already proved that).

I also proved that the series $X_n$ converges in $\mathcal{L}^1$, however almost sure convergence is still missing (and that's actually the reason why I'm interested in an LDP)...

Since this is my first question on MO, I'm not quite sure if it fits on this site. It is however an actual research problem for me and it also seemed to be too "hard" for MSE.

  • $\begingroup$ Why do you need $\Lambda(\lambda)<\infty$ for all $\lambda$? This is definitely not necessary for the Gartner-Ellis theorem! See the statement of Theorem 2.3.6 inDembo-Zeitouni $\endgroup$ – ofer zeitouni Dec 5 '15 at 6:59
  • $\begingroup$ I cited the Gärtner-Ellis Theorem as I knew it, so thank you very much for the hint! In Dembo-Zeitouni, $\Lambda(\lambda)$ is only required to be an "extended real number" which also includes $\infty$ right? $\endgroup$ – ssbm Dec 7 '15 at 16:37
  • $\begingroup$ right. I do not know that it helps you though, as computing the log mgf does not seem easy (I fail to see an obvious subadditivity). $\endgroup$ – ofer zeitouni Dec 7 '15 at 16:51

Your Answer

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

Browse other questions tagged or ask your own question.