Memory-less Property of Distribution

By definition, memorylessness means the distribution of waiting time (in continuous case) or number of trials (in discrete case) does not depend on how much time has passed or how many trials you have tried. There are only two distributions are memoryless: exponential distribution in continuous case, and geometric distribution in discrete case. Actually geometric is analogous to exponential. Mathematically, memorylessness can be expressed as below where m and n are non-negative integers in discrete case, or non-negative real numbers in continuous case:
$$P(X \ge m+n | X \geq m) = P(X \ge n)$$
Using conditional probability, we can write left hand side to
$$ P(X \ge m+n | X \geq m) =  \frac {P( X \ge m+n, X \geq m)}{P(X \geq m)}$$
Since m and n are both non-negative, we can simplify the numerator as $P( X \ge m+n, X \geq m) = P(X \ge m+n)$, so above equation becomes
$$P(X \ge m+n | X \geq m) =  \frac {P( X \ge m+n)}{P(X \geq m)} $$

It is not hard to prove why exponential and geometric distributions are memoryless. We can just plug in the cdf and work it out. I will prove for the exponential distribution, and geometric distribution should be analogous to exponential distribution. As we know the cdf of exponential distribution is $F(x) = 1 - \lambda e^{- \lambda x}$, for $ x \geq 0$. We can then plug it in the above equation:
$$ P(X \ge m+n | X \geq m) =  \frac {P( X \ge m+n)}{P(X \geq m)} = \frac {e^{- \lambda (m+n)}} { e^{ - \lambda m} } = 1- (1 - e^{ - \lambda n})= 1-F(n) = P (X \geq n)$$

Exponential and geometric distributions are only memoryless distributions. We can prove it as below. First, we define a function $G(m) = P(X \ge m)$. From $\frac {P( X \ge m+n)}{P(X \geq m)} = P (X \geq n)$, we can easily see $G(m + n) = G(m)G(n)$. Let n = m, we can easily see $G(2m) = G(m)^2$, and $G(3m) = G(m + 2m)= G(m)G(2m) = G(m)^3$. To generalize, we can get $G(a*m)=G(m)^a$ a is an integer. From $G(2m) = G(m)^2$, if we substitute m with m/2, we can immediately get $G(m/2) = G(m)^{1/2}$. Similarly, from $G(a*m)=G(m)^a$, we can get $G(m/a) = G(m)^{1/a}$ a is an integer. Now we can further generalize this to apply to any rational number $a/b$ that $G((a/b)m) = G(m)^{a/b}$. In order to generalize this to all positive real numbers, we can take limit of a series rational numbers, and it will still hold. We can simplify and make m = 1, then rewrite it to base of e, so the equation becomes $G(a) = e^{a*ln(G(1))}$. Since $G()$ is a probability, so $G(1)$ is between 0 and 1, and $ln(G(1))$ is a negative real number. We can define $ln(G(1))$ as $-\lambda$. Now it is obvious $G(a)$ as a can take any real positive number is just the $1 - (1 - e^{- \lambda a})$, which is $1 - F(a)$ where $F$ is the cdf of exponential distribution. For geometric proof, when a only takes positive integers, $G(a) = G(1)^a = 1 - (1 - G(1)^a) = 1 - F(a)$, where $F$ is cdf of geometric distribution.

Comments

Post a Comment

Popular posts from this blog

Perform efficient Latent Semantic Index using Python

Image
First of all, Latent Semantic Index(LSI) and Latent Semantic Analysis(LSA) are interchangeable terms. In E-discovery world, we often use LSI but in other fields, researchers often use LSA.  Latent semantic analysis   is widely used in information retrieval to search for similar documents. In E-discovery doc review, finding similar documents can drastically decrease the number of documents case team have to review so it is a powerful and essential tool in today's E-discovery industry. LSI is the thing behind Relativity conceptual analytics .  What is LSI and the intuition The main idea of LSI can be generalized in one simple sentence: Words with similar meaning will occur in similar documents .  Each document can have several topics and several words together can be used to express a topic. In another word, each document consists of a mixture of topics, and each topic consists of a collection of words. A word can appear several topics but the mixtures are dif...
Read more

SVM

Image
SVM has been a quite hot topic in recent E-discovery scene. The reason is Relativity has introduced Active Learning which is based on SVM. Now everybody knows it works especially well on classification. However what on earth is SVM? This blog is meant to take you through it briefly so you can know something more than just how to set up an active learning project in Relativity (: Introduction First of all, SVM is a supervised learning algorithm in general, meaning it is often used to classify data which is fundamentally different from LSI. You will need labelled data to train SVM model to predict on unseen data. In a nutshell, SVM is trying to find the hyperplane that can maximize the separation margins. So in another word, there might be many hyperplanes that can separate your data, but SVM is trying to find the best one for you! Nearly all the SVM tutorials will explain what is hyperplane and what is the margins, so i wont discuss it much about them here. The basic SVM is linear ...
Read more

Open Source to E-discovery

Image
As a data scientist who is working in E-discovery industry, I am glad to be able to use many good tools to work with E-discovery data, i.e. Nuix for processing, Relativity for review and some analytics, and so on. However, the limitation for any hard-coded software is they do not always work well when data is messy and unorganized. Coupled with the high license fees and server fees, those tools are not always a good option. So, is there anything free that you can rely on to perform all the core functionalities that those big tools provide? Well, the answer is yes and no. Yes, there are numerous open source tools that can do what you are looking for, and No, you still need to pay money for hiring a data scientist but not pay money for software. To demonstrate an open source approach to E-discovery, I decide to start writing blogs about this topic. When it comes to data, Python is hands down a very good option. (The other equivalent is R). Python has a very complete and robust standar...
Read more