Recent posts in Engineering Mathematics

https://www.probabilitycourse.com/

The webpage of Hossein Pishro-textbook Nik's Introduction to Probability, Statistics, and Random Processes. It is an open access peer-reviewed textbook designed for undergraduate and first-year graduate level courses on the subject. This probability textbook may be utilised by both students and practitioners in engineering, mathematics, finance, and other relevant subjects.

​​​​​​1. Overview

In this article, we’ll discuss the geometric probability distribution and its properties. We will prove each property mathematically and understand its significance. This article assumes basic knowledge of discrete mathematics and algebra for proofs.

2. Basic Definitions

We begin with a few basic definitions that will set the stage for things to come.

Sample space: A collection or set of discrete points $\Omega$ that is countable. A set of values $S$ is said to be countable when there exists a bijection $f: S → A$ where $A$ is a known countable set, such as the set of integers. Each point in the sample space represents an outcome.

A sample space may also be made of a continuous interval of points, but that is outside the scope of this article.

Conditional probability: Given events $A$ and $B$ as subsets of $\Omega$, the value $P(A | B)$ is the probability that $A$ occurs given that $B$ has already occurred. It is the probability of $A$ scaled down to the conditional universe of $B$.

Discrete random variable: A random variable $X$ is a function $g: \Omega → A$ where $A$ is a subset of $\mathbb{R}$ and $\Omega$ is the sample space. Think of $X$ as taking on input values in $\Omega$ with a certain probability and providing a corresponding meaningful output. For example: we have a set of students and we want to measure their weights. The set of students is our sample space $\Omega$. $W$ could be a random variable that takes any student in this set as input, and outputs a weight value associated with the student. The more frequently a weight value is seen, the more probability it has of occurring.

Probability mass function (PMF): A function $f: A → [0, 1]$ where $A$ is the subset of values that $X$ takes on, as given above. We usually use the notation $P(X = x)$ where $x\ \epsilon\ A$.

Cumulative distribution function (CDF): In terms of our notation, it is the function $P(X \le x)$. 

A random variable $X$ is geometric if it adheres to the properties of the geometric distribution.

3. The Geometric Probability Mass Function

A geometric random variable $X$ represents the number of trials it takes for an event of interest to occur. Each trial is independent and has no bearing on the others. $X$ takes on the values $1$, $2$, $3$ and so on.

For example, we might want to measure the number of times a coin is tossed until a head appears. Say the heads outcome occurs with probability $p$. This implies that the only other outcome, the tails, happens with probability $1\ – p$. The geometric PMF then takes the form -:

$P(X = x) = (1\ – p)^{x\ – 1}p$

This means that $x\ – 1$ trials failed before the success occurred. Visually, this looks like a downward sloping set of discrete points on the XY plane. The sample space is plotted on the X-axis and the probability of each point is plotted on the Y-axis. The height of a point in this plot tells us how probable it is, and these heights decrease in the form of a geometric progression.

A more contrived example could involve a game with a number of outcomes. One of the outcomes signifies the end of the game. The others force the game to repeat. We are to measure the number of rounds the game takes before it completes.

4. The Geometric Cumulative Distribution Function

The CDF gives us a convenient measure of the probability of input points up to a given baseline $x$. For geometric distributions, it takes on the form -:

$P(X \le x) = 1\ – (1\ – p)^x$

A proof of the above fact follows from taking the summation -:

$ P(X \le x) = \sum_{k = 1}^{x}(1\ – p)^{k\ – 1}p$

                   $ = p\sum_{k = 1}^{x}(1\ – p)^{k\ – 1}$

                   $ = p\frac{1\ –\ (1\ –\ p)^{x\ – 1 + 1}}{1\ –\ (1\ –\ p)}$     [geometric progression]

                   $ = 1\ – (1\ – p)^x$         [cancel out $p$]

5. Expected Value of a Geometric Random Variable

The expectation of a random variable $E[X]$ is fundamentally a weighted average. Each real value in the output set is weighted by the probability that it occurs. If more points in the sample space correspond to a particular output, that output has a greater weightage. It is also called the mean of the distribution. It can be described by the general formula -:

$E[X] = \sum_{k = a}^{b}k\ P(X = k)$

The expectation of a geometric random variable in particular looks like -:

$E[X] = \sum_{k = 1}^{\infty}k\ (1\ – p)^{k\ – 1}p$

This summation has a closed form which we can extract through the use of calculus. We describe this manipulation below. First, note that the sum of an infinite geometric progression can be described as -:

$\sum_{n = 0}^{\infty}x^n = \frac{1}{1\ –\ x}$

Differentiate on both sides with respect to $x$ to get -:

$\sum_{n = 1}^{\infty}nx^{n\ – 1} = \frac{1}{(1\ –\ x)^2}$

Using the above result, we proceed as follows -:

$E[X] = p\sum_{k = 1}^{\infty}k\ (1\ – p)^{k\ – 1}$

           $ = p\frac{1}{(1\ –\ (1\ –\ p))^2}$

           $ = p\frac{1}{p^2}$

           $ = \frac{1}{p}$

6. Variance of a Geometric Random Variable**

The variance of a random variable $Var(X)$ measures the spread of the distribution. It represents the expected average square distance of $X$ from the mean. In general,

$Var(X) = E[(X\ – \mu)^2] = E[(X\ – E[X])^2]$

The variance can also be calculated using the formula -:

$Var(X) = E[X^2]\ – (E[X])^2$

In the case of the geometric distribution, $E[X] = \frac{1}{p}$ and $(E[X])^2 = \frac{1}{p^2}$. It remains to calculate $E[X^2]$. We do this by algebraic manipulation and application of linearity of expectation as follows -:

$E[X^2] = E[X^2\ – X + X] = E[X(X\ – 1) + X] = E[X(X\ – 1)] + E[X]$.

Further, let $1\ – p = q$. Note that $X(X\ – 1)$ is itself a random variable, as it is the function of a random variable. Therefore, it makes sense to be able to calculate its expectation.

$E[X(X\ – 1)] = p\sum_{x = 1}^{\infty}x\ (x\ – 1)\ q^{x\ – 1}$

This is equivalent to writing -:

 $E[X(X\ – 1)] = p\frac{d}{dq}\left (\sum_{x = 1}^{\infty}(x\ – 1)\ q^x \right )$

                         $ = p\frac{d}{dq}\left (q^2\ \sum_{x = 2}^{\infty}(x\ – 1)\ q^{x\ – 2}\right )$

                         $ = p\frac{d}{dq}\left (q^2\ \frac{d}{dq}\left (\sum_{x = 2}^{\infty}q^{x\ – 1}\right )\right )$

                         $ = p\frac{d}{dq}\left (q^2\ \frac{d}{dq}\left (\sum_{x = 1}^{\infty}q^{x}\right )\right )$

                         $ = p\frac{d}{dq}\left (q^2\ \frac{d}{dq}\left (\frac{1}{1\ –\ q}\ – 1\right )\right )$

                         $ = p\frac{d}{dq}\left (q^2\ \left (\frac{1}{(1\ –\ q)^2}\right )\right )$

                         $ = p\ \frac{2q}{(1\ –\ q)^3}$

                         $ = p\ \frac{2(1\ –\ p)}{(1\ –\ (1\ –\ p))^3}$

                         $ = \frac{2\ –\ 2p}{p^2}$

Plugging in this result, we get -:

$Var(X) = E[X(X\ – 1)] + E[X]\ – (E[X])^2$

               $ = \frac{2\ –\ 2p + p\ –\ 1}{p^2}$

               $ = \frac{1\ –\ p}{p^2}$

7. Memorylessness of the Geometric Distribution

An interesting property inherent in the geometric distribution is its memorylessness. If we were to begin observing the experiment after a given number of trials, the remaining trials would follow the same distribution as the trials that have elapsed. It is as if we had started over!

Suppose we start observing after $a$ trials have elapsed, and a further $b$ trials occur. We claim that -:

$P(X \gt a + b | X \gt a) = P(X \gt b)$

To prove this, first note that -:

$P(A | B) = \frac{P(A\ \cap\ B)}{P(B)}$

So we have that -:

$P(X \gt a + b | X \gt a) = \frac{P(X\ \gt\ a + b\ \cap\ X\ \gt\ a)}{P(X\ \gt\ a)}$

But $X \gt a + b \cap\ X \gt a = X \gt a + b$

Therefore we have -:

$P(X \gt a + b | X \gt a) = \frac{P(X\ \gt\ a + b)}{P(X\ \gt\ a)}$

Here we may use the CDF to quickly calculate $P(X \gt x)$ style probabilities.

$P(X \gt x) = 1\ – P(X \le x) = (1\ – p)^x$

Thus we get -:

$P(X \gt a + b | X \gt a) = \frac{(1\ –\ p)^{a + b}}{(1\ –\ p)^a} = (1\ – p)^b = P(X \gt b)$

8. Conclusion

In this article, we discussed the various properties of the geometric distribution. We understood which situations can be modelled by this distribution. Further, we algebraically proved each property and underlined what they really mean.

Given an infinite sequence of numbers $<a_0, a_1, a_2, a_3, . . .>$, the (ordinary) generating function for the sequence is defined to be the power series:

Consider the binomial expansion of $(1-x)^n$, where $n\in \mathbb{Z}^+$

$(1-x)^n = \sum_{i=0}^{n}\binom{n}{i}(-x)^i$

$\quad = 1 - nx + \frac{n(n-1)}{2!}x^2 – \frac{n(n-1)(n-2)}{3!}x^3 \ldots +(-1)^k\frac{n(n-1)(n-2)\ldots (n-k+1)}{k!}x^k .\ldots + (-1)^nx^n $

Note that if we substitute $n$ with its negative value, the expansion fails to converge, i.e.

$(1-x)^{-n}  = 1 - (-n)x + \frac{(-n)(-n-1)}{2!}x^2 - \frac{(-n)(-n-1)(-n-2)}{3!}x^3  +\ldots $

$\qquad =1 + nx + \frac{n(n+1)}{2!}x^2 + \frac{n(n+1)(n+2)}{3!}x^3  +\ldots $

$\qquad = \sum_{i=0}^{\infty}\binom{n+i-1}{i}x^i$

(Expansion of $(1+x)^{-n}$ is the same, but with alternating signs. Try to derive it yourself)

In 99% of the cases, we’ll be dealing with $(1-x)^{-n}$ as far as GATE is concerned.

Applying the above formula for $n=-1$, we get

 (Notice that it’s a generating function for the sequence $<1,1,1,...>$)

Similarly for $n=-2$, we get

(Notice that it’s a generating function for the sequence $<1,2,3,4,5,...>$) 

**Operations on Generating Functions**

Let’s assume two generating functions:

$A(x) =  \sum_{i=0}^{\infty}a_ix^i $

$B(x) =  \sum_{i=0}^{\infty}b_ix^i $

1. $\forall \alpha, \beta \in \mathbb{R}$,  $ \alpha A(x) + \beta B(x)$ is another generating function $C(x)$ where

2.  $A(x)\times B(x)$ is another generating function $D(x)$ where

3. $A^2(x) = A(x) \times A(x)$ is another generating function $E(x)$ where

4. $A(kx)$ is another generating function $F(x)$ where

5. $x^mA(x)$, $m\in\mathbb{N}$ is another generating function $G(x)$ where

6. $(1-x)A(x) = A(x) – xA(x)$ is another generating function $H(x)$ where

7. $\frac{A(x)}{(1-x)} = A(x)[1+x+x^2+x^3+...] = A(x) + xA(x) + x^2A(x) + . . . $ is another generating function $J(x)$ where

8. $A’(x) = \frac{d}{dx}A(x)$ is another generating function $K(x)$ where  

(**Note: Try deriving all the 8 operations above, pretty easy and mechanical)

Kind of questions that may be asked in GATE:

1. Given something like $(a_0x^k + a_1x^{k+1} + a_2x^{k+2} + ...)^m$, find the coefficient of $x^p$, where $k,m,p, a_i \in \mathbb{N}, \forall i \in \{0,1,2,...\}$ 

Approach: If all the coefficients are $1$, take $x^k$ as common and bring it out, i.e.

Now $(1-x)^{-m}$ is simply $\sum_{i=0}^{\infty}\binom{m+i-1}{i}x^i$. Putting everything together, we just need to find coefficient of $x^p$ in the expression:

If we let $p = km + z$ where $z \in \mathbb{N}$, then the coefficient of $x^p$ is just the coefficient of $x^z$ in $\sum_{i=0}^{\infty}\binom{m+i-1}{i}x^i$ which is simply $\binom{m+z-1}{z} = \binom{m+p-km-1}{p-km}$

If not all the coefficients $a_i$ in $(a_0x^k + a_1x^{k+1} + a_2x^{k+2} + ...)^m$ are $1$, then like before, bring out $x^k$ and simply try to bring $(a_0 + a_1x + a_2x^2 + ...)$ into closed form (maybe use the “manipulation” technique as mentioned below), then raise it to power $m$ and rest of the calculation is pretty similar to the one I wrote above. Pretty time consuming and tedious stuff depending on what the coefficients are, but considering GATE, the expression should be a direct expansion of $x^k(1\pm x)^{-n}$ where $k,n \in \mathbb{Z}^+$

2. Given an expression for calculating each coefficient of some generating function (i.e. each term of the infinite sequence), find the closed form of that generating function.

Approach: Check if the expression involves $’+’$ symbol. If it does, then the resulting generating function will be a sum of generating functions generated by each of those terms. For example, if $a_i = 7i + 6i^2$, then generating function of $A(x)$ is simply the sum of generating functions of the sequences $<(7\times 0), (7\times 1), (7\times 2), . . .>$ and $<(6\times 0^2), (6\times 1^2), (6\times 2^2), ...>$ respectively.

If there’s no $’+’$ symbol, then it’s simply the generating function generated by that single term. Here’s an example to make things concrete:

If each term of an infinite sequence $\{a_n\}$ is calculated as $a_i = 7i + 6i^2, \forall i \in \{0,1,2,3,...\}$, find the generating function generated by the sequence $\{a_n\}$ 

Ans: As stated above, if we assume $A(x)$ to be the generating function generated by the sequence $\{a_n\}$, then $A(x) = B(x) + C(x)$, where $B(x)$ and $C(x)$ are generating functions of the sequences $<(7\times 0), (7\times 1), (7\times 2), . . .>$ and $<(6\times 0^2), (6\times 1^2), (6\times 2^2), ...>$ respectively.

$B(x) = 0 + 7x + 14x^2 + 21x^3 + … = 7(1x + 2x^2 + 3x^3 + ….) = 7x(1+2x+3x^2+4x^3+...) = 7x(1-x)^{-2}$

Calculating $C(x)$ is a bit tricky.

$C(x) = 0 + (6\times 1^2)x + (6\times 2^2)x^2 + (6\times 3^2)x^3 + … = 6(0 + 1^2x + 2^2x^2 + 3^2x^3 + ...)$

Using the “manipuation” technique (more on it below),

$(1-x)^{-2} = 1 + 2x + 3x^2 + 4x^3 + ….$

$=> x(1-x)^{-2} = x + 2x^2 + 3x^3 + 4x^4 + ….$

$=> \frac{d}{dx}[x(1-x)^{-2}] = 1^2 + 2^2x + 3^2x^2 + 4^2x^3 + ….$

$=> x[\frac{d}{dx}[x(1-x)^{-2}]] = 1^2x + 2^2x^2 + 3^2x^3 + 4^2x^4 + ….$

Therefore, $C(x) = 6[x[\frac{d}{dx}[x(1-x)^{-2}]]]$. Solving it, we get $C(x) = 6x(1+x)(1-x)^{-3}$.

Putting everything together,

$A(x) = B(x) + C(x) = \frac{7x}{(1-x)^2} + \frac{6x(1+x)}{(1-x)^3}$

”Manipulation” technique (or what I like to call it)

Given a generating function $A(x) = \sum_{i=0}^{\infty}a_ix^i$, whose closed form is not immediately apparent, start off with a generating function $G(x)$ of the form $\frac{1}{(1\pm x)^n}$ (or even something more complicated) which looks kinda similar to that of $A(x)$. The idea is to manipulate $G(x)$ by a series of multiplication/differentiation/integration ..or whatever operations, to make the RHS of it similar to that of $A(x)$.

Here’s a quick example of what I meant. Consider $A(x) = 1^2 + 2^2x + 3^2x^2+ 4^2x^3 + ...$

It’s looks kinda similar to $(1-x)^{-2} = 1 + 2x + 3x^2 + 4x^3 + . . . $.

So we can manipulate it like this:

$=> (1-x)^{-2} = 1 + 2x + 3x^2 + 4x^3 + . . . $

$=> x(1-x)^{-2} = x + 2x^2 + 3x^3 + 4x^4 + . . . $

$=> \frac{d}{dx}[x(1-x)^{-2}] = 1 + 2^2x + 3^2x^2 + 4^2x^3 + . . . = A(x) $

Therefore $A(x) = \frac{d}{dx}[x(1-x)^{-2}]  = \frac{1+x}{(1-x)^3}$

(These were pretty much my notes on Generating Functions for GATE 2020. Although this should pretty much cover everything needed for GATE, do refer to explanations from books as well (I recommend ”Principles and Techniques in Combinatorics” by Chen Chuan Chong) and of course, practice the questions (a lot of them !!))

GRAPH Theory slides from GO classroom

http://discrete.openmathbooks.org/dmoi2/section-27.html

This covers of basics of generating function

And for Recurrence relation

https://www.tutorialspoint.com/discrete_mathematics/discrete_mathematics_recurrence_relation.htm

Hey there,

I’ve found an interactive website to revise some mathematics concepts.(For Graph Theory and Probability)

Here ‘s the link: https://mathigon.org/course/graphs-and-networks/introduction

HOPE IT HELPS :)

Information Collected from multiple sources(primarily from Wikipedia, Wolfram Alpha and Narsingh Deo Textbook)

For more information visit GO Classroom: https://classroom.gateoverflow.in/course/view.php?id=12

MATHEMATICAL LOGIC

COMBINATORICS

GRAPH THEORY

For more information visit GO Classroom : https://classroom.gateoverflow.in/course/view.php?id=9

I found this channel on YouTube which has short videos for Maths and Discrete Maths topics.

Watch the videos for topics you want to revise.

https://m.youtube.com/user/thetrevtutor

Important Questions:

http://gateoverflow.in/questions/mathematics/discrete-mathematics/graph-theory?sort=featured

More Questions:

Some Good Questions useful for GATE

Important Ones

http://gateoverflow.in/questions/mathematics/probability?sort=featured

https://www.facebook.com/events/1461890050775907/permalink/1472730633025182/

Important Ones

http://gateoverflow.in/questions/mathematics/discrete-mathematics/combinatory?sort=featured

Course Exercises

Important Questions

https://gateoverflow.in/questions/mathematics/discrete-mathematics/set-theory%26algebra?sort=featured

Important Ones

http://gateoverflow.in/questions/mathematics/discrete-mathematics/mathematical-logic?sort=featured

More Questions:

First Order Logic