# Tagged Questions

**7**

votes

**3**answers

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

**3**answers

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

**0**answers

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

**0**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**2**answers

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

**1**answer

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

**2**answers

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

**1**answer

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

**1**answer

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

**3**answers

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

**1**answer

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

**0**answers

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

**2**answers

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

**2**answers

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

**1**answer

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

**1**answer

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

**0**answers

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

**2**answers

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 ...