2

Consider the renewal process $P(x)$ is generated according to interrenewal distribution $p(x)$, and renewal process $Q(x)$ is generated according to interrenewal distribution $q(x)$. Calculate the Kullback–Leibler divergence between $P(x)$ and $Q(x)$.

Generally, the Kullback-Leibler divergence between two distributions $p(x)$ and $q(x)$ is

$ D_{\mathrm{KL}}(p\|q) = \int_{\chi} p \, \log \frac{p}{q} \, {\rm d}\mu. \!$

where $\chi$ is support of $q(x)$. If you want to calculate $D_{\mathrm{KL}}(P\|Q)$, the problem is that the length of the vector $x$ in $P(x)$ and $Q(x)$ is random. I thought about the following:

$ D_{\mathrm{KL}}(P\|Q) = \sum_n \int_{\chi} P(x|n) \, \log \frac{P(x|n)}{Q(x|n)} \, {\rm d}\mu. \!$

Is this right ? How about characterizing $P$ by joint pdf of number of jumps and the interrenewal distribution $p(x)$?

Chain Markov
  • 15,564
  • 6
  • 36
  • 116
Susan_Math123
  • 2,730
  • I'm not quite sure what you're asking. In general we can't say much about the exact distribution of a renewal counting process. Although your expression for $D_{\mathrm{KL}}(P|Q)$ is using the interrenewal distributions, not those of the renewal process itself. – Math1000 Nov 20 '15 at 14:42
  • @Math1000 Thanks. My question is what can we say about the distribution of a renewal counting process. If instead of interrenewal distributions we want to find the $DKL(P∥Q) $ for the renewals, how we should proceed? Can we can characterize each renewal by the joint pdf of the number of jumps and the interrenewal distribution? – Susan_Math123 Nov 23 '15 at 22:59

1 Answers1

1

I am not familiar with the general renewal process, so I will just use Poisson process between $t=0$ and $t=1$ as an example. We may consider the random variables $(N, T)$, where $N$ is the number of jumps, and $T=(T_1,T_2,...,T_N)$ be the jump times. Similarly, let $(M,S)$ be the random variables from another Poisson process. Now, using the formula

$D((N,T)\|(M,S))=D(N\|M) +D((T|N)\|(S|M))$

Now, the second part of the right hand side is the 'conditional relative entropy', which is defined as

$D((T|N)\|(S|M)) = \sum_{n=1}^\infty D((T|N=n)\|(S|M=n)) = \sum_{n=1}^\infty D(((T_1,T_2,...,T_n)|N=n)\|((S_1,S_2,...,S_n)|M=n)) $

this is well defined, because for each component, the $T$ and $S$ vectors are of the same dimension. And what is interesting about Poisson distribution is that, the conditional distribution (T|N=n), (S|M=n) are the same, regardless of their intensities, both of them are 'uniform' on $[0\ 1]$ ( remember we only consider Poisson process between $t=0$ and $t=1$ here). See the discussion in:

What does it mean for a Poisson point process $\Phi$'s points in $A$, conditioned on $\Phi(A)=k$ to be uniform?

So, the second part is $0$, we end up with

$D((N,T)\|(M,S))=D(N\|M)$

For general renewal process, I don't know whether similar conclusion holds, but the formula is still well defined.

Community
  • 1
Jay.H
  • 1,118
  • Thanks a lot for your answer. I am not sure why the conditional distribution (T|N), (S|M) are the same, regardless of their intensities. $P(T|N) = p(T_1)p(T_2)...p(T_N)$ and $P(S|M) = p(S_1)p(S_2)...p(S_M)$. Why they are identical? – Susan_Math123 Nov 24 '15 at 00:09
  • I added some more details in the answer. – Jay.H Nov 24 '15 at 02:52
  • Will add some details... – Jay.H Nov 24 '15 at 03:00
  • Thanks so much for that. Can I ask give me reason/reference that why considering a Poisson point process as joint pdf of the number of jumps and jump times? And also, reason/reference of support of the expansion of conditional relative entropy? – Susan_Math123 Nov 24 '15 at 03:14
  • For a general renewal process, the jump times are not according to a exponential pdf (which gives you a Poisson) , but they can be according to any pdf but they should be independent and identically distributed. Can you make your solution to cover the general case too? – Susan_Math123 Nov 24 '15 at 03:15
  • You can fully describe a Poisson sample path between $t=0$ and $t=1$ using (a) the number of jumps in $[0 \ 1]$ and (b) the times of all the jumps. Therefore, the full path $N_t, t\in [0\ 1]$ and (# of jumps, times of jumps) have the same "information". – Jay.H Nov 24 '15 at 04:09
  • For the general case, I'm not an expert in this field, you may want to post a new question. It should be an interesting question by itself. I'm sure there should be some known results. – Jay.H Nov 24 '15 at 04:12
  • Thanks again. Your solution is awesome and just applies to Poisson (but my question was general, not Poisson). I think it can be applied to general case too. How about I wait a few days, and if no body answers the general case here, I change the question to Poisson, accept your answer, and post the general question? – Susan_Math123 Nov 24 '15 at 04:38
  • Sorry, I didn't expressed myself clearly, the "general case" I talked about is the general case of the quoted link. Don't worry about starting a new post for this question. I post a new question, http://math.stackexchange.com/questions/1543946, a answer to that one will be helpful for your question here. – Jay.H Nov 24 '15 at 05:11
  • Awesome, thanks for posting the new question. That is really helpful. – Susan_Math123 Nov 24 '15 at 15:10
  • Something is wrong here, since both are renewal, because of the chain rule we can write $\sum_{n=1}^{\infty} D((T|N=n)∥(S|M=n)) = \sum_{n=1}^{\infty} n D((T_1|N=n)∥(S|M_1=n))= \sum_{n=1}^{\infty} n D(T_1∥S_1) = D(T_1∥S_1) \sum_{n=1}^{\infty} n$ – Susan_Math123 Nov 25 '15 at 20:18
  • And the $D(T_1∥S_1) \sum_{n=1}^{\infty} n$ goes to infinity, right? This should not happen. – Susan_Math123 Nov 25 '15 at 20:23
  • Why is $ D((T|N=n)∥(S|M=n)) = nD((T_1|N=n)∥(S_1|M=n))$? – Jay.H Nov 25 '15 at 23:14
  • Because all $T_i$ are i.i.d and the same is true for all $S_i$. You can write the mutual information form of $D_{KL}$ and then use the chain rule. – Susan_Math123 Nov 25 '15 at 23:58
  • Defining the renewal process as (N,T) which is not a probability distribution makes the problem. The problem is that for every probability distribution $P(x)$ we should have the $\sum_{x} P(x)=1$ but this is not true for (N,T) representation since $\sum_{x} P(x)=\sum_{n=1}^{\infty} \int_{\mathbb{R}^n} P(T_1(x_1),T_1(x_2),\cdot,T_1(x_n)) dx $ which is not equal to 1. – Susan_Math123 Nov 26 '15 at 00:03
  • The $T_i$'s are increasing with respect to $i$, they are not independent. Guess you were talking about $T_i-T_{i-1}$? Even these are not independent to each other condition on $N_t=n$ – Jay.H Nov 26 '15 at 13:34
  • We can characterize the renewal process both with $T_i$ or $T_{i-1}$ since they both give you complete information. The definition of renewal process is to have independent and identical distribution for all $T_i$ – Susan_Math123 Nov 26 '15 at 14:00
  • Guess we are talking about different $T_i$'s. I use $T_i$ to represent the time of the $i-th$ jump. So $T_i = \sum_{k=1}^i \tau_k$, where each $\tau_k$ is i.i.d with pdf $\lambda e^{-\lambda t}$. The $T_i$'s are not independent. The $\tau_k$'s are not either condition on $N = n$. – Jay.H Nov 26 '15 at 14:34
  • I am still thinking about it, I might be wrong that $D((T|N=n)∥(S|M=n))=nD((T1|N=n)∥(S1|M=n))$. Can you give me a reference about what you have written as an answer? That would be really really helpful for me. I will read and find the details. – Susan_Math123 Dec 03 '15 at 15:22
  • I am not aware of any reference that address exactly the question. I think what is used in my answer is quite standard. Perhaps you are asking especially about the definition of "condtional relative entropy "? In that case, you may check Thomas and Cover's information theory. – Jay.H Dec 03 '15 at 17:53
  • I mean how we can characterize a renewal process and apply Dkl on it. – Susan_Math123 Dec 03 '15 at 18:35
  • To me that is quite natural. If at certain time, you know how many jumps have occurred and when each of the jump occurred, you know all the information about what happened to the process upto that time, right? – Jay.H Dec 03 '15 at 21:02