Tagged Questions
4
votes
1answer
181 views
Lower bound for multivariate recurrence
I have a recurrence that looks like
$$p(i,j,k) = \frac{j}{n}p(i-1,j-1,k-1) + \frac{i-j}{n}p(i-1,j,k-1)$$
$$p(i,0,k) = 1$$
$$p(i,j,0) = 0$$
$$p(0,j,k) = 0$$
The base cases are to be considered in ...
0
votes
0answers
12 views
Some questions about a “relaxed” invariant probability problem $|\mu(P-I)|\leq \epsilon$
Let's consider the set $\mathcal{M}=\{\mu:|\mu(P-I)|_1\leq \epsilon\}$ where $\mu$ is a probability vector, $P$ is the transition matrix of a discrete homogeneous Markov chain, $I$ is the identity ...
1
vote
1answer
83 views
Chernoff bound for Geometric RVs compared to exact tail bound
I keep getting a result I can't interpret.
X is a Geometric RV with distribution ($0<\rho<1$)
$$
\pi_k = \rho^k(1- \rho)
$$
so directly applying Geometric series the tail bound is
$$
B_1 = ...
0
votes
0answers
41 views
Exponential decay of optimal stopping rule
I'm trying to prove the following:
For any $\lambda,\tau$, probability distribution, if $T$ is an optimal stopping rule from $\lambda$ to $\tau$ then for all $k\geq 1$,
$$
...
