4
votes
1answer
184 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 ...
1
vote
0answers
18 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
138 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 = ...