Categories
Combinatorics IIT JAM Statistics ISI M.Stat PSB

Vandermone’s SRSWR | MStat 2017 PSB Problem 3

This is a beautiful problem form ISI MStat 2017 PSB Problem 3, where we use the basics of Bijection principle and Vandermone’s identity to solve this problem.

Problem

Consider an urn containing 5 red, 5 black, and 10 white balls. If balls are drawn without replacement from the urn, calculate the probability that in the first 7 draws, at least one ball of each color is drawn.

Prerequisites

  • Algebrify the problem
  • Vandermone’s Identity $${{n_{1}+\cdots+n_{p}} \choose m} = \sum_{k_{1}+\cdots+k_{p}=m} {n_{1} \choose k_{1}} \times {n_{2} \choose k_{2}} \times \cdots \times {n_{p} \choose k_{p}}$$

Solution

It may give you the intuition, there is atleast in the problem, so let’s do complementing counting. Okay! I suggest you to travel that path to help you realize the complexity of that approach.

Nevertheless, let’s algebrify the problem.

You want to select \(x_1\) red balls, \(x_2\) blue balls, and \(x_3\) white balls so that \(x_1 + x_2 + x_3 = 7\).

Now, \( 1 \leq x_1 \leq 5\), \(1 \leq x_2 \leq 5\) and \(1 \leq x_3 \leq 10\) represents our desired scenario.

\( 0 \leq x_1 \leq 5\), \(0 \leq x_2 \leq 5\) and \( 0 \leq x_3 \leq 10\) denotes total number of cases.

Now, for each such triplet (\(x_1, x_2, x_3\)) of the number of balls of each colour we have selected, we can select them in \( { 5 \choose x_1} \times {5 \choose x_2 } \times {10 \choose x_3} \).

Let \( P = \{ (x_1, x_2, x_3) | x_1 + x_2 + x_3 = 7, 0 \leq x_1 \leq 5, 0 \leq x_2 \leq 5, 0 \leq x_3 \leq 10 \} \).

Total Number of Ways we can select the 7 balls =

$$ \sum_{(x_1, x_2, x_3) \in P} { 5 \choose x_1} \times {5 \choose x_2 } \times {10 \choose x_3} = { {5 + 5 + 10} \choose { x_1 + x_2+ x_3} } = { {5 + 5 + 10} \choose {7} }$$

\( Q = \{ (x_1, x_2, x_3) | x_1 + x_2 + x_3 = 7, 1 \leq x_1 \leq 5, 1 \leq x_2 \leq 5, 1 \leq x_3 \leq 10 \} \).

Total Number of Ways we can select the 7 balls such that at least one ball of each color is drawn =

$$ \sum_{(x_1, x_2, x_3) \in Q} { 5 \choose x_1} \times {5 \choose x_2 } \times {10 \choose x_3}$$

Let, \( R = \{ (z_1, z_2, z_3) | z_1 + z_2 + z_3 = 4, 0 \leq z_1 \leq 4, 0 \leq z_2 \leq 4, 0 \leq z_3 \leq 9 \} \).

Observe that \(Q\) has a bijection with \(R\). \( x_i = z_i +1\).

Total Number of Ways we can select the 7 balls such that at least one ball of each color is drawn =

$$ \sum_{(x_1, x_2, x_3) \in R} { 4 \choose z_1} \times {4 \choose z_2 } \times {9 \choose z_3} = { {4 + 4 + 9} \choose { z_1 + z_2+ z_3} } = { {4 + 4 + 9} \choose {4} }$$

Exercises

  • Prove the Vandermone’s Identity.
  • Find the Probability.
  • Generalize the problem to general numbers and prove it.
  • Generalize the problem where the lower bounds of \(x_i\) are \(m_i\).
  • What if there are upper bounds on \((x_1, x_2, x_3)\)? [ Hint: Generating Functions ].

Stay Tuned! Stay Blessed!

Categories
Combinatorics IIT JAM Statistics ISI M.Stat PSB

Let’s Permute | ISI MStat 2018 PSB Problem 3

This problem is an easy application of the basic algorithmic ideas to approach a combinatorics problem using permutation and combination and basic counting principles. Enjoy this problem 3 from ISI MStat 2018 PSB.

Problem

Consider all permutations of the integers \(1,2, \ldots, 100\) . In how many
of these permutations will the \(25^{th}\) number be the minimum of the
first 25 numbers and the \(50^{th}\) number be the minimum of the first 50
numbers?

Prerequisites

Solution

Whenever you are counting, think in terms of algorithms or steps in which you will do the task given in the problem and count each of the steps. Now the conjunction in between the steps ( and \(\cap\) , or \(\cup\) ) will show you the way.

Steps

Select the first 50 numbers. Fix the minimum element. Out of the 49 other elements, select the first 25 numbers. Fix the minimum element of these 25 numbers. Then permute the rest.

AND for each of these selections of two sets (Multiplication Principle),

Step 2

Once you select the three sets, the minimum of each of these sets is already fixed. So, for each of these sets, you have to permute the other first 24 numbers (1 – 24) and the next 24 numbers (from 26 – 49) and the other 50 numbers (50 – 100).

You can do that in \(24! \times 24! \times 50! \) ways.

Therefore, you can do the whole task in \( {100 \choose 50} \times { 49 \choose 25 } \times 24! \times 24! \times 50!\) ways.

Food for Thought

  • Do the problem for \(2n\) numbers.
  • Do the problem if you want to fix the minimum \(k\) numbers in each set out of \(2n\) numbers.
  • Do the problem if you want to fix the minimum \(n\) numbers in each set out of \(2n\) numbers. Does it match your expectation?
  • Generalize and Degeneralize and make your own problem out of this. Comment it below. We will update it here if we think the problem is appropriate.
Categories
Calculus IIT JAM Statistics ISI M.Stat PSB

Telescopic Continuity | ISI MStat 2015 PSB Problem 1

This problem is a simple application of the sequential definition of continuity from ISI MStat 2015 PSB Problem 1 based on Telescopic Continuity.

Problem- Telescopic Continuity

Let \(f: R \rightarrow R\) be a function which is continuous at 0 and \(f(0)=1\)
Also assume that \(f\) satisfies the following relation for all \(x\) :
$$
f(x)-f(\frac{x}{2})=\frac{3 x^{2}}{4}+x
$$ Find \(f(3)\).

Prerequisites

Solution

$$
f(3)-f(\frac{3}{2})=\frac{3 \times 3^{2}}{4}+3
$$

$$
f(\frac{3}{2})-f(\frac{\frac{3}{2}}{2})=\frac{3 \times \frac{3}{2}^{2}}{4}+\frac{3}{2}
$$

$$
f(\frac{3}{2^2})-f(\frac{\frac{3}{2^2}}{2})=\frac{3 \times \frac{3}{2^2}^{2}}{4}+\frac{3}{2^2}
$$

\( \cdots \)

$$
f(\frac{3}{2^n})-f(\frac{\frac{3}{2^n}}{2})=\frac{3 \times \frac{3}{2^n}^{2}}{4}+\frac{3}{2^n}
$$

Add them all up. That’s the telescopic elegance.

$$
f(3)-f(\frac{3}{2^{n+1}})= \frac{3 \times 3^{2}}{4} \times \sum_{k = 0}^{n} \frac{1}{2^{2k}} + 3 \times \sum_{k = 0}^{n} \frac{1}{2^k} \rightarrow [*]
$$

Observe that \( a_n \to 0 \Rightarrow f(a_n) \to f(0) = 1\) since, \(f(x)\) is continuous at \(x=0\).

Hence take limit \( n \to \infty \) on \([*]\), and we get \( f(3) – f(0) = \frac{3 \times 3^{2}}{4} \times \frac{4}{3} + 3 \times 2 = 15 \).

Food for Thought

  • Find the general function from the given condition.
  • $$f(x)-f(\frac{x}{2})=g(x)$$ and g(x) is continuous, then prove that \(g(0) =0\).
  • What if \(g(x)\) is not continuous?
Categories
IIT JAM Statistics ISI M.Stat PSB Regression Techniques

Size, Power, and Condition | ISI MStat 2019 PSB Problem 9

This is a problem from the ISI MStat Entrance Examination, 2019. This primarily tests one’s familiarity with size, power of a test and whether he/she is able to condition an event properly.

The Problem:

Let Z be a random variable with probability density function

\( f(z)=\frac{1}{2} e^{-|z- \mu|} , z \in \mathbb{R} \)

with parameter \( \mu \in \mathbb{R} \). Suppose, we observe \(X = \) max \( (0,Z) \).

(a)Find the constant c such that the test that “rejects when \( X>c \)” has size 0.05 for the null hypothesis \(H_0 : \mu=0 \).

(b)Find the power of this test against the alternative hypothesis \(H_1: \mu =2 \).

Prerequisites:

  • A thorough knowledge about the size and power of a test
  • Having a good sense of conditioning whenever a function (like max()) is defined piecewise.

And believe me as Joe Blitzstein says: “Conditioning is the soul of statistics”

Solution:

(a) If you know what size of a test means, then you can easily write down the condition mentioned in part(a) in mathematical terms.

It simply means \( P_{H_0}(X>c)=0.05 \)

Now, under \( H_0 \), \( \mu=0 \).

So, we have the pdf of Z as \( f(z)=\frac{1}{2} e^{-|z|} \)

As the support of Z is \( \mathbb{R} \), we can partition it in \( \{Z \ge 0,Z <0 \} \).

Now, let’s condition based on this partition. So, we have:

\( P_{H_0}(X > c)=P_{H_0}(X>c , Z \ge 0)+ P_{H_0}(X>c, Z<0) =P_{H_0}(X>c , Z \ge 0) =P_{H_0}(Z > c) \)

Do, you understand the last equality? (Try to convince yourself why)

So, \( P_{H_0}(X >c)=P_{H_0}(Z > c)=\int_{c}^{\infty} \frac{1}{2} e^{-|z|} dz = \frac{1}{2}e^{-c} \)

Equating \(\frac{1}{2}e^{-c} \) with 0.05, we get \( c= \ln{10} \)

(b) The second part is just mere calculation given already you know the value of c.

Power of test against \(H_1 \) is given by:

\(P_{H_1}(X>\ln{10})=P_{H_1}(Z > \ln{10})=\int_{\ln{10}}^{\infty} \frac{1}{2} e^{-|z-2|} dz = \frac{e^2}{20} \)

Try out this one:

The pdf occurring in this problem is an example of a Laplace distribution.Look it up on the internet if you are not aware and go through its properties.

Suppose you have a random variable V which follows Exponential Distribution with mean 1.

Let I be a Bernoulli(\(\frac{1}{2} \)) random variable. It is given that I,V are independent.

Can you find a function h (which is also a random variable), \(h=h(I,V) \) ( a continuous function of I and V) such that h has the standard Laplace distribution?

Categories
Calculus IIT JAM Statistics ISI M.Stat PSB

Shift the Curves | ISI MStat 2019 PSB Problem 1

This problem is an easy application in calculus using the basic ideas of curve sketching. This is the problem 1 from ISI MStat 2019 PSB.

Problem- curve sketching

Let \(f(x) = x^{3}-3 x+k,\) where \(k\) is a real number. For what values of
\(k\) will \(f(x)\) have three distinct real roots?

Prerequisites

Solution

Science is all about asking proper questions. So, \(k\) is the variable here. So, ask the following question,

What role is \(k\) playing here? Let’s take \( k = 0\) and see what happens.

\( g(x) = x^{3}- 3x = x(x-\sqrt{3})(x+\sqrt{3})\).

We can easily draw the graph of this \(g(x)\). Let’s draw it. So, \(g(x)\) has roots as {\(-\sqrt{3}, 0, \sqrt{3}\)}.

curve sketching

Great, so addding \(k\) to \(g(x)\) will shift the graph upwards right?

curve sketching

Observe that if \(k\) \(\geq\) |lowest value of \(g(x)\) at the bump|, then \(f(x)\) will have less than three roots.

Similarly, observe that if \(k\) \(\leq\) – highest value of \(g(x)\) at the bump, then \(f(x)\) will have less than three roots.

curves
The arrows show the bumps.

So, let’s find them out. So, what is the mathematical significance of these bumps? They are the local maximum and minimum. How do we find them?

\(g'(x) = 0\), where \(g(x) = x^{3}- 3x\).

\( \Rightarrow 3x^2 – 3 = 0 \Rightarrow x = \pm 1\).

So, the minimum and the maximum values of \(g(x)\) are \(g(-1) = 2\) and \(g(1) = -2\).

Hence \( -2 < k < 2\).

Let’s see what happens at \( k = \pm 2\).

curves on graph

It is just that point, where the transitition for three roots to two roots occur and then to one root.

Observe that since, it is an odd degree, there will always be a reall root of the curve.

Stay Tuned! Stay Blessed!

Food for Thought ( Think with Pictures )

  • \(f(x)\) has \(n\) distinct roots \(\Rightarrow\) \(f'(x)\) has atleast \(n-1\) distinct roots.
  • Is the converse true? i.e. \(f'(x)\) has \(n-1\) distinct roots \(\overset{?}{\Rightarrow}\) \(f(x)\) has atleast \(n\) distinct roots. Can you investigate using the given function?
  • \(f'(x)\) has \(n-1\) distinct roots. Does there exist a \(k\) such that \(f(x)+k\) has atleast \(n\) distinct roots?

Stay Tuned! Stay Blessed!

Categories
IIT JAM Statistics ISI M.Stat PSB Probability

Conditions and Chance | ISI MStat 2018 PSB Problem 5

This problem is a cute application of joint distribution and conditional probability. This is the problem 5 from ISI MStat 2018 PSB.

Problem

Suppose \(X_{1}\) and \(X_{2}\) are identically distributed random variables, not necessarily independent, taking values in \(\{1,2\}\). If \(\mathrm{E}\left(X_{1} X_{2}\right)= \frac{7}{3} \) and \(\mathrm{E}\left(X_{1}\right) = \frac{3}{2},\) obtain the joint distribution of \(\left(X_{1}, X_{2}\right)\).

Prerequisites

Solution

This problem is mainly about crunching the algebra of the conditions and get some good conditions for you to easily trail your path to the solution.

Usually, we go forward starting with the distribution of \(X_1\) and \(X_2\) to the distribution of (\(X_1, X_2\)). But, we will go backward from the distribution of (\(X_1, X_2\)) to \(X_1\), \(X_2\) and \(X_1X_2\)with the help of conditional probability.

conditional probability

Now, observe \(p_{21} = p_{12}\) because \(X_1\) and \(X_2\) are identically distributed.

Let’s calculate the following:

  • \(P(X_1 = 1)\) and \(P(X_1 = 2)\) and \(E(X_1)\)
  • \(P(X_2 = 1)\) and \(P(X_2 = 2)\)
  • \(E(X_1X_2)\)

\(P(X_1 = 1 )= p_{11} + p_{12} = P(X_2 = 1)\)

\(P(X_1 = 2) = p_{12} + p_{22} = P(X_2 = 2)\)

\(E(X_1) = p_{11} + 3p_{12} + 2p_{22} = \frac{3}{2}\)

Now, \(X_1X_2\) can take values {\(1, 2, 4\)}.

\(X_1 = 1, X_2 = 1 \iff X_1X_2 = 1\) \( \Rightarrow P(X_1X_2 = 2) = p_{11}\).

\(X_1 = 2, X_2 = 2 \iff X_1X_2 = 4\) \( \Rightarrow P(X_1X_2 = 4) = p_{22}\).

\(X_1 = 1, X_2 = 1\) or \(X_1 = 2, X_2 = 1 \iff X_1X_2 = 2\) \( \Rightarrow P(X_1X_2 = 2) = 2p_{12}\).

\(E(X_1X_2) = p_{11} + 4p_{12} + 4p_{22} = \frac{7}{3}\).

Now, we need another condition, do you see that ?

\(p_{11} + 2p_{12} + p_{44} = 1\).

Now, you can solve it easily to get the solutions \( p_{11} = \frac{1}{3}, p_{12} = \frac{1}{6}, p_{22} =\frac{1}{3} \).

Food for Thought

Now, what do you think, how many expectation values will be required if \(X_1\) and \(X_2\) takes values in {1, 2, 3}?

What if \(X_1\) and \(X_2\) takes values in {\(1, 2, 3, 4, …, n\)}?

What if there are \(X_1, X_2, …., X_n\) taking values in {\(1, 2, 3, 4, …, m\)}?

This is just another beautiful counting problem.

Enjoy and Stay Tuned!

Categories
Functional Equations I.S.I. and C.M.I. Entrance IIT JAM Statistics ISI M.Stat PSB Probability

Application of Cauchy Functional Equations | ISI MStat 2019 PSB Problem 4

This problem is a beautiful application of the probability theory and cauchy functional equations. This is from ISI MStat 2019 PSB problem 4.

Problem – Application of Cauchy Functional Equations

Let \(X\) and \(Y\) be independent and identically distributed random variables with mean \(\mu>0\) and taking values in {\(0,1,2, \ldots\)}. Suppose, for all \(m \geq 0\)
$$
\mathrm{P}(X=k | X+Y=m)=\frac{1}{m+1}, \quad k=0,1, \ldots, m
$$
Find the distribution of \(X\) in terms of \(\mu\).

Prerequisites

  • Conditional Probability
  • Geometric Distribution
  • \(a, b, c, d\) are numbers such that \(ac = b^2\) & \(ad = bc\), then \(a, b, c, d\) are in geometric progression.

Solution

Let \( P(X =i) = p_i\) where $$\sum_{i=0}^{\infty} p_i = 1$$. Now, let’s calculate \(P(X+Y = m)\).

$$P(X+Y = m) = \sum_{i=0}^{m} P(X+Y = m, X = i) = \sum_{i=0}^{m} P(Y = m-i, X = i) = \sum_{i=0}^{m} p_ip_{m-i}$$.

$$P( X = k|X+Y = m) = \frac{P( X = k, X+Y = m)}{P(X+Y = m)} = \frac{P( X = k, Y = m-k)}{\sum_{i=0}^{m} p_ip_{m-i}} = \frac{p_kp_{m-k}}{\sum_{i=0}^{m} p_ip_{m-i}} = \frac{1}{m+1}$$.

Hence,$$ \forall m \geq 0, p_0p_m =p_1p_{m-1} = \dots = p_mp_0$$.

Thus, we get the following set of equations.

$$ p_0p_2 = p_1^2$$ $$ p_0p_3 = p_1p_2$$ Hence, by the thrid prerequisite, \(p_0, p_1, p_2, p_3\) are in geometric progression.

Observe that as a result we get \( p_1p_3 =p_2^2 \). In the line there is waiting:

$$ p_1p_4 = p_2p_3$$. Thus, in the similar way we get \(p_1, p_2, p_3, p_4\) are in geometric progression.

Hence, by induction, we will get that \(p_k; k \geq 0\) form a geometric progression.

This is only possible if \(X, Y\) ~ Geom(\( p\)). We need to find \(p\) now, but here \(X\) counts the number of failures, and \(p\) is the probability of success.

So, \(E(X) = \frac{1-p}{p} = \mu \Rightarrow p = \frac{1}{\mu +1}\).

Challenge Problem

So, can you guess, what it will be its continous version?

It will be the exponential distribution. Prove it. But, what exactly is governing this exponential structure? What is the intuition behind it?

The Underlying Mathematics and Intuition

Observe that the obtained condition

$$ \forall m \geq 0, p_0p_m =p_1p_{m-1} = \dots = p_mp_0.$$ can be written as follows

Find all such functions \(f: \mathbf{N}_0 \to \mathbf{N}_0\) such that \(f(m)f(n) = f(m+n)\) and with the summation = 1 restriction property.

The only solution to this geometric progression structure. This is a variant of the Cauchy Functional Equation. For the continuous case, it will be exponential distribution.

Essentially, this is the functional equation that arises, if you march along to prove that the Geometric Random Variable is the only discrete distribution with the memoryless property.

Stay Tuned!

Categories
Combinatorics IIT JAM Statistics ISI M.Stat PSB

Counting Double Subsets | ISI MStat 2014 Sample PSB Problem 3

This problem is an extension of the bijection principle idea used in counting the number of subsets of a set. This is ISI MStat 2014 Sample Paper PSB Problem 3.

Problem

Let \( S = \{1,2, \ldots, n\} \)
(a) In how many ways can we choose two subsets \(A\) and \(B\) of \(S\) so that \(B \neq \emptyset\) and \(B \subseteq A \subseteq S\) ?
(b) In how many of these cases is \(B\) a proper subset of \(A\) ?

Prerequisites

  • Generalization of the idea of counting the total number of subsets of a set.

Solution

It is the same idea as counting the total number of subsets of a set. We used coding schemes.

Coding Scheme

We need three parameters to take note

  • \(b\) if that element is in \(B \subseteq A\).
  • \(a\) if that element is extra in \(A\) and not in \(B\).
  • \(0\) if that element is not included in \(A\) hence not in \(B\).

Example

For \( S = \{1,2, 3, 4, 5, 6\} \).

The coding scheme \( (1, 2, 3, 4, 5, 6) = (a, b, 0, 0, a, a) \) means

\( B = \{ 2 \}, A = \{ 1, 2, 5, 6\}\).

The total number of ssuch strings without any restrictions on number of \(b\) or \(a\) = \(3^n\) since, for each of the \(n\) elements of \(S\), there are three options {\(a, b\), 0}.

The total number of cases with \(B = \emptyset\) = The total number of cases with zero \(b\) = \(2^n\), since for each of the \(n\) elements of \(S\), there are two options {\(a\), 0}.

The total number of cases \(B\) is not a proper subset of \(A\) = The total number of cases {\( A = B\)} = The total number of cases with zero \(a\) = \(2^n\), since for each of the \(n\) elements of \(S\), there are two options {\(b\), 0}.

(a)

We need to count how many such strings are there using atleast one \(b\).

The total number of strings using atleast one \(b\) =

the total number of cases without any restrictions – the total number of cases with zero \(b\).

= \(3^n – 2^n\)

(b)

We need to count how many such strings are there using atleast one \(a\) and one \(b\).

The total number of strings using atleast one \(a\) and one \(b\) =

The total number of strings using atleast one \(b\) – The total number of strings using atleast one \(b\) and zero \(a\)

= The total number of strings using atleast one \(b\) – The total number of strings using atleast one \(b\) out of {\(b, 0\)}

= \(3^n – 2^n\) – \( 2^n – 1\) = \(3^n – 2^{n+1} +1\)

Other Methods

You can also do it by using methods of Conditional Expectation and Smoothing method, taking a uniform distribution over \(S\). If you have done it in that way, let us know, we will add the solution to the post.

Stay Tuned! Stay Blessed!

Categories
IIT JAM Statistics ISI M.Stat PSB Probability

Elchanan Mossel’s Dice Paradox | ISI MStat 2018 PSB Problem 6

This problem from ISI MStat 2018 PSB (Problem 6) is called the Elchanan Mossel’s Dice Paradox. The problem has a paradoxical nature, but there is always a way out.

Problem

A fair 6 -sided die is rolled repeatedly until a 6 is obtained. Find the expected number of rolls conditioned on the event that none of the rolls yielded an odd number.

Prerequisites

  • Geometric Distribution
  • Conditional Probabilty
  • Conditional Expectation
  • Expectation Smooting Property \( E_X(E_Y(Y|X)) = E(Y)\)
  • Common Sense

Solution

The Wrong Solution

Let \(X_{1}, X_{2}, \cdots\) be the throws of a die. Let
$$
{T}=\min\{{n: X_{n}=6}\}
$$

Then \(T\) ~ Geo(\(p =\frac{1}{6}\))

But, here it is given that none of the rolls are odd numbers. So,

$$
{T}=\min\{{n: X_{n}=6} | X_n = \text{even}\} = \min\{{n: X_{n}=6} | X_n = \{2, 4, 6\}\}
$$

Then \(T\) ~ Geo(\(p =\frac{1}{3}\)) Since, there are three posibilities in the reduced (conditional) sample space.

So, \(E(T) =3\).

Obviously, this is false. But you are not getting why it is false right? Scroll Down!

Where it went wrong?

It went wrong in observing the given condition of the problem. Observe that it is given that none of the rolls are odd till the roll you got success, not for all the rolls beyond that also.

So, $$
{T}=\min\{{n: X_{n}=6} | X_n = \text{even}, n \leq T\} = \min\{{n: X_{n}=6} | X_n = \{2, 4, 6\}, n \leq T\}
$$

So, we are essentially seeing that the sample space didn’t get reduced all along, it got reduced till that point of the roll. This is where the paradox marches in.

We are thinking of the experiment as we are picking up only \( \{ 2, 4, 6\} \) in the experiment and rolling. No!

The Elegant One Liner Solution

The idea is to think from a different perspective as with the case of every elegant solution. Let’s reconstruct the experiment in a different way. It is like the following. Remember, we need to exclude the odd numbers, so just throw them away and start anew.

Idea

If you get \(\{1, 3, 5\}\), start counting the number of rolls again from the beginning. Stop when you get 6. This is the exact formulation of the waiting time to get a 6 without getting any odd numbers till that toss. We will show that our success is when we get \(\{1, 3, 5, 6\}\) in this experiment.

Mathematical Form

Let \(\tau\) be the time required to get an outcome different from \(\{2,4\}\) Then \(E(\tau | X_{\tau}=j)\) is independent of \(j\) for \(j \in \{1,3,5,6\}\) because it is same for all \( j\). Thus, by the smooting property of \(E\left(\tau | X_{\tau}=j\right)=E(\tau)\).

Observe, \(\tau\) ~ Geo( \( p = \frac{4}{6}\)). Hence, \( E(\tau) = \frac{3}{2}\).

The Bigger Bash Solution

\(T=\min \{n: X_{n}=6\}\)
We need to calculate \( \mathbb{E}(T | X_{1}, \cdots, X_T \in \{2,4,6\})\).

For that we need to find out the conditional probabilities \(\mathrm{P}\left(\mathrm{T}=\mathrm{k} | \mathrm{X}{1}, \cdots, \mathrm{X}{\mathrm{T}} \in{2,4,6}\right)\) and that is given by
$$
\frac{\mathrm{P}\left(\mathrm{T}=\mathrm{k} \cap\left(\mathrm{X}_{1}, \cdots, \mathrm{X}_{\mathrm{T}} \in \{2,4,6\}\right)\right)}{\mathrm{P}\left(\mathrm{X}_{1}, \cdots, \mathrm{X}_{\mathrm{T}} \in \{2,4,6\} \right)}=\frac{\mathrm{P}\left(X_{\mathrm{k}}=6, \mathrm{X}_{1}, \cdots, \mathrm{X}_{\mathrm{k}-1} \in \{2,4\} \right)}{\mathrm{P}\left(\mathrm{X}_{1}, \cdots, \mathrm{X}_{\mathrm{T}} \in \{2,4,6\} \right)}=\frac{1}{6}\left(\frac{1}{3}\right)^{\mathrm{k}-1} \frac{1}{\alpha}
$$
where \(\alpha=\mathrm{P}\left(\mathrm{X}_{1}, \cdots, \mathrm{X}_{\mathrm{T}} \in \{2,4,6\} \right)\) . Thus \(\mathrm{T} |\left(\mathrm{X}_{1}, \cdots, \mathrm{X}_{\mathrm{T}} \in \{2,4,6\} \right)\) follows a geometric distribution with parameter \(\frac{2}{3}\) and consequently its expectation is \(\frac{3}{2}\).

Stay Tuned! Stay Blessed!

Click here for Detailed Discussion

Simulation in Python

import random

times = 0 #number of times a successful (all-even) sequence was rolled
rolls = 0 #total of all number of rolls it took to get a 6, on successful sequences
curr = 0
alleven = True

for x in range(0, 100000):

  num = random.randint(1,6)
  if num % 2 != 0:
    alleven = False
  else:
    if num == 6:
      if alleven:
        times += 1
        rolls += curr + 1
      curr = 0
      alleven = True
    else:
      curr += 1

print(rolls * 1.0 / times)
#1.51506456241

Source: mathstackexachange

Stay Tuned! Stay Blessed!

Categories
Combinatorics I.S.I. and C.M.I. Entrance IIT JAM Statistics ISI M.Stat PSB

Non-Consecutive Selection | ISI MStat 2019 PSB Problem 3

This problem is a beautiful and simple application of the bijection principle to count the number of non-consecutive selection of integers in combinatorics from Problem 3 of ISI MStat 2019 PSB.

Problem – Non-Consecutive Selection

Elections are to be scheduled for any seven days in April and May. In how many ways can the seven days be chosen such that elections are not scheduled on two consecutive days?

Prerequisites

  • \(a < b\), then \(a\) and \(b+1\) are never consecutive.
  • Combination ( Choose Principle )
  • Bijection Principle

Solution

The problem is based on the first prerequisite mainly. That idea mathematicalizes the problem.

Out of the 61 days in April and May, we have to select 7 non-consecutive days. Let’s convert this scenario to numbers.

Out of {\(1, 2, 3, … , 61\)}, we have to select 7 non-consecutive numbers.

Lemma

\(y_1 < y_2 < y_3 < … < y_7\) are 7 non-consecutive numbers \( \iff\) \(y_i\) is of the form \( x_i + (i-1) \) where \(x_1 < x_2 < x_3 < … < x_7\).

For example

You select {1, 3, 4, 5, 6, 8}. You change it to {1, 3 + 1, 4 + 2 , 5 + 3, 6 + 4 , 8 + 5} = { 1, 4, 6, 8, 10 , 13}, which are never consecutive.

Essentially, we are counting the non-consecutive integers in a different way, which helps us to count them.

So, we have to choose \(x_1 < x_2 < x_3 < … < x_7\), where the maximum \(x_7 + (7-1) = x_7 + 6 \leq 61 \Rightarrow x_7 \leq 55\).

Hence, the problem boiled down to choosing \(x_1 < x_2 < x_3 < … < x_7\) from {\(1, 2, 3, … , 55\)}, which is a combination problem.

We can have to just choose 7 such numbers. The number of ways to do so is \( {55}\choose{7}\).