Consider the following extension of the notion of convexity of continuous functions to functions defined over $\mathcal{I} = \{0,\ldots,n \}$ — that is, to vectors: $f$ is convex if for any $\alpha \in [0,1]$ and for all $k\in \{ \ell \in \mathcal{I}: \ell \leq \alpha i+ (1-\alpha)j\}$ it holds that:

$$\alpha f_i + (1-\alpha)f_j \geq f_{k}.$$

Consider a Markov chain with right stochastic $n\times n$ transition matrix $P$ over the state space indexed by $\mathcal{I}$.

Consider the convex vector $g_i = i^2$ , I would like to know whether there is any condition — or whether it is even plausible that there might be some; I suspect not — to be placed on the stochastic matrix $P$ to ensure that

$$f := (I_n - \delta P)^{-1} g$$

is convex or not. Here $0 < \delta < 1$ and $I_n$ is the $n \times n$ identity matrix.

The motivation: $g$ is a cost incurred for each sojourn of the chain in state $i$, $f$ is the discounted expected cost of the chain when the future is discounted by $\delta$

A related problem is when instead one considers a similar chain but the $0-th$ state is taken to be absorbing and want to compute an approximation of the vector of expected absorption times given by

$$h := (I_{n-1} - \delta [P]_{0})^{-1} \boldsymbol{1}_{n-1}.$$

where $[P]_{0}$ is the sub-stochastic matrix obtained by deleting the $0-th$ column and row of $P$.

If this helps in any way, $P$ has a tridiagonal structure meaning that the Markov chain it represents is a nearest neighbor random walk on the line.

  • $\begingroup$ You need a definition of convexity which I believe I've given at the bottom $\endgroup$
    – Three Diag
    Apr 11 '18 at 12:26
  • $\begingroup$ I guess that what I should add is that I would fix one ordering of the states of the chain for which I'd ask this to be true. This would be the natural order of the states on the lattice where the walk is performed $\endgroup$
    – Three Diag
    Apr 11 '18 at 12:29
  • $\begingroup$ Thanks for the editing, I also fixed the definition of convexity. $\endgroup$
    – Three Diag
    Apr 11 '18 at 12:38
  • $\begingroup$ Can you describe $P$? I understand you do not assume it is right stochastic ($P{\bf 1}_n={\bf 1}_n$) otherwise $f={1\over 1-\delta}{\bf 1}_n$. $\endgroup$ Apr 11 '18 at 18:29
  • $\begingroup$ @PietroMajer you are right. Alas, I was too quick in generalizing my problem. I've edited the question with a more meaningful question and some indication of where I'm coming from too, as well as correcting the notion of convexity. $\endgroup$
    – Three Diag
    Apr 11 '18 at 19:29

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.