7
votes
3answers
313 views

The distribution of the shortest path through $n$ points

In the big picture, I'd like to know: if I sample $n$ points uniformly at random in the unit square, what is the probability that the shortest path that visits each one of them is very small? More ...
14
votes
3answers
644 views

“Entropy” proof of Brunn-Minkowski Inequality?

I read in an information theory textbook the Brunn-Minkowski inequality follows from the Entropy Power inequality. The first one says that if $A,B$ are convex polygons in $\mathbb{R}^d$, then $$ ...
8
votes
0answers
204 views

Hasse-Weil Bound and Chebyshev Inequality

I was reading about the Hasse-Weil bound for the number of points in on a curve over the finite field $\mathbb{F}_q$. $$ \big| |C(\mathbb{F}_q)| - (q+1) \big| \leq 2g \sqrt{q} $$ However, this ...
2
votes
0answers
131 views

An optimization in Markov Chain

We are given two correlated random variables $V$ and $X$ supported over a finite alphabets $\mathcal{V}$ and $\mathcal{X}$. Suppose the marginal $P_V$ and conditional distribution $P_{X|V}$ are ...
0
votes
1answer
158 views

Supremum in a Markov chain model

A Markov chain $X$ with finite state space $\{1,2,\cdots,N\}$ is defined on a probability space $(\Omega, P, \mathcal{F})$ equiped with filtration $\{\mathcal{F}_t\}$. And we assume that we can reach ...
1
vote
1answer
99 views

Kalman filter with long term bias

I was reading about the Kalman filter and I do not understand how it should be used when our measurements have a long term offset like GPS location updates do. As I understand, the Kalman filter ...
0
votes
1answer
258 views

Anyone has Kushner's book “Introduction to stochastic control” 1971? I need a theorem from it

In a paper I'm reading, it refers to Theorem 8, Page 217 of the book "Introduction to Stochastic Control" H. J. Kushner, New York: Holt, Reinhart, and Winston 1971. Unfortunately I don't have it and ...
2
votes
1answer
137 views

Upper bound concerning Snell envelope

Consider, on a filtred probability space $ \left (\Omega, \mathcal F, \mathbb F , \mathbb P \right )$ where $ \mathbb F = \left(\mathcal F_ t \right )_ {t\geq 0}$ is filtration satisfying the usuual ...
7
votes
1answer
302 views

Probability density that minimizes the sample range

Let $\mathcal{F}$ denote the set of all "concave probability distributions" on the unit interval, that is, all functions $f:[0,1]\to \mathbb{R}$ such that $f$ is concave, $f(x)\geq 0$ for all $x\in ...
2
votes
1answer
198 views

An optimization problem, non complete bipartite graph and hungarian algorithm

I have two tables at my disposal, one work dataset and one reference dataset. Each dataset has got two columns, lets say these are fields A and B. I would like the rows in reference dataset with the ...
1
vote
2answers
748 views

When do maximum and expectation commute?

Hi, I'm looking for conditions on $G(t,x)$ such that $$ \sup\limits_{t\in [0,1]}E[G(t,X)]=E[\sup\limits_{t\in [0,1]}G(t,X)] $$ where $X$ is a random variable (it's easy to see that $\sup\limits_{t\in ...
0
votes
1answer
242 views

Is it known that every PDF continuous in all $R^n$ has a maximum? [closed]

I'm working with maximum a posteriori estimation and managed to show that every probability density function that is continuous in all $R^n$ always has at least one global maximum. I've search around ...
1
vote
2answers
165 views

Bound on expression from probability distributions

I came across this issue while trying to combine multiple probability distributions into a single distribution which approximates them all simultaneously. This boils down to maximizing this expression ...
4
votes
1answer
447 views

An optimization problem involving sum of binomial coefficients upto some value

I would like to minimize $f(s, n, \epsilon)$ with respect to $s$ where $$f(s,n,\epsilon) = \left( 1 + \frac{n}{2^s} \right)\frac{1}{s} \sum_{k=0}^{\lfloor s\epsilon \rfloor} {s \choose k}~.$$ Note ...
1
vote
1answer
154 views

Max Absolute Difference of Expectations under Change of Measure

Given a sample space $\Omega=\{ 1,\cdots,N \}$, a random variable $x$ defined on $\Omega$ that takes value $x_1,\cdots,x_N$, and a set of strictly positive real numbers $w_1,\cdots,w_N$. Define for ...
1
vote
3answers
433 views

convergence in distribution of stochastic gradient descent.

The stochastic gradient descent algorithm where only a noisy gradient (zero mean noise) is used to update current estimate is known to converge almost surely to the minimizer. However, if one is ...
2
votes
1answer
248 views

Concentration of measure and bounds on variance

I am trying to characterize the sensitivity of a function $f: R^N\to{}R$ to the perturbations in the input vector $\mathbb{x}=\left[x_1,\dots{}x_N\right]$. For that purpose, I evaluate Cramer-Rao ...
3
votes
0answers
320 views

maximum variance unfolding

Consider positive weights $\pi_1, \ldots, \pi_n$ (one can suppose that they add up to $1$) and $n-1$ lengths $d_1, \ldots, d_{n-1}$. Is there an analytical solution to the following problem: find the ...
4
votes
2answers
1k views

Commuting supremum and expectation

Given a one-parametric random function on a probability space $(\Omega,\mathcal F,\mathbb P)$: $X:U\times\Omega\to \mathbb R \text{ and } (a,w)\mapsto X(a,w), \text{ with } \sigma(X(a))\subseteq ...
8
votes
2answers
648 views

Covering a random graph with spanning trees.

Let $G=(V,E)$ be a connected graph, say $V=\{1,\ldots,n\}$. Let $F=(V,E')$ be a uniformly random forest in $G$. (In other words, $E'$ is a subset of edges $E$ not containing a cycle, and it is ...
6
votes
1answer
687 views

Random, Linear, Homogeneous Difference Equations and Time Integration Methods for ODEs

Most methods (that I know of) of numerically approximating the solution of ODEs are "general linear methods". For this type of method, the so-called 'linear stability' is examined by applying the ...
-2
votes
1answer
702 views

Determine noise distribution [closed]

I'm trying to solve the following least squares problem: $\underset{x}{\text{min}} ||Ax - \tilde{b}||_2$ where $Ax = b$ and $\tilde{b} = b + w$ Question: How do I determine which probability ...
4
votes
0answers
463 views

Dynamic programming principle (DPP)

In stochastic control problem, one shall use the measurable selection theorem to prove DPP. It was discussed in discrete time case in [Bertsekas and Shreve 1978]. Is there unified framework in ...
0
votes
2answers
532 views

univariate prior corresponding to weighted sum of L1 and L2 penalties?

Is there a univariate probability distribution $p_{\lambda,\alpha}(\beta)$ over the reals, parameterized by $\lambda > 0$ and $1 >= \alpha >= 0$, such that $p_{\lambda,\alpha} \propto ...