0
$\begingroup$

a. If $i$ distinct integers $r_1, r_2, \ldots,r_i$, i $\leq n$, are randomly selected (one after other) from n distinct integers, what is the probability that $r_1 < r_2 < \cdots < r_i$?

b. Does the probability you got in part a of the question change if < is replaced with $\leq$?

I know that a question similar to part 'a' of this question can be solved using the concept of Decision tree that orders the elements of the list, an application of which is to analyse the complexity of comparison-based sorting algorithm.

I came across a solution to part 'a' of the question that says the required probability is $C(n, i)/P(n,i)$, which is nothing but equal to the solution of the Decision tree based approach, which is $1/i!$.

What I don't understand is this - how $C(n,i)$ is equal to favourable number of outcomes and $P(n,i)$ is equal to total number of outcomes?


Figure: A decision tree for sorting three distinct elements.

A decision tree for sorting three distinct elements

Image taken from Discreet Mathematics and its Applications by Kenneth Rosen

$\endgroup$
6
  • $\begingroup$ What does $P(n,i)$ mean? $\endgroup$ Jan 21 at 18:48
  • $\begingroup$ I edited the question. P(n,i) is i-permutation of a set with n elements $\endgroup$ Jan 21 at 18:48
  • $\begingroup$ Yes. I suppose $C(n,i)$ means $\binom n i = \frac{n!}{i!(n-i)!}$. I don't know what you mean by $P(n,i)$. $\endgroup$ Jan 21 at 18:50
  • 2
    $\begingroup$ hint: every possible order of them is equally probable. $\endgroup$
    – lulu
    Jan 21 at 18:50
  • $\begingroup$ Not $1/n!$, but $1/i!$. $\endgroup$
    – Tavish
    Jan 21 at 18:58
1
$\begingroup$

For any given choice of $i$ integers from among the $n$ possible integers, only one permutation of these $i$ integers produces a valid result, because the $n$ integers are distinct.

There are $C(n,i)$ such choices of $i$ integers from among $n$ integers, and $P(n,i)$ permutations of $i$ integers from among $n$ integers.

$\endgroup$
10
  • $\begingroup$ Please, can you also explain it using a decision tree based approach. $\endgroup$ Jan 21 at 19:35
  • $\begingroup$ What is a decision tree based approach? $\endgroup$ Jan 21 at 19:36
  • $\begingroup$ suppose i is fixed to 3 and we don't have to choose i from among n distinct integers, then I can just make a binary tree and count the number of leaves which gives me the total number of outcomes. Among them only one is favourable. I am trying to extend this approach to when we have to choose i from among n distinct integers $\endgroup$ Jan 21 at 19:40
  • $\begingroup$ Do you want to count the number of solutions or devise an algorithm? I am still confused. Do you want to count it 'by cases'? You can totally do that, it's just more cumbersome. $\endgroup$ Jan 21 at 20:11
  • $\begingroup$ No, I don't want to devise an algorithm(write code or anything), I just want to convince myself by the graphical approach of constructing a tree. Something similar to the notorious "Monty Hall Three-Door Puzzle", that can be explained by constructing a tree. I just don't know how to construct one here. $\endgroup$ Jan 21 at 20:20
1
$\begingroup$

$C(n,i)$ chooses $i$ integers from $n$ integers without giving importance to their order. Given such a set of $i$ integers, we can first order them in ascending order, and then assign the corresponding values to $r_1,r_2\dots r_i$ so that $r_1 \lt r_2 \lt \dots \lt r_i $.

$P(n,i)$ counts the total ways. Why? The number of choices for $r_1$ is $n$, for $r_2$ is $n-1$ and so on. That gives $$n(n-1)(n-2)\dots (n-i+1)=\frac{n!}{(n-i)!} = P(n,i) $$

$\endgroup$
0
1
$\begingroup$

Approach 1:

If you take letters $a, b, c, d$, there are $4!$ orders possible.
$a \lt b \lt c \lt d$ is one of them.

Hence the desired probability $\displaystyle = \frac{1}{4!}$

Approach 2: Place ( $ \ $ a $ \ $ b $ \ $ c $ \ $ d $ \ $) first, and now start placing other $(n-4)$ letters in between. The first letter of $(n-4)$ has $5$ places available. Once you place the first letter, you now have $6$ places for the next letter and so on.

Total number of favorable arrangements $ = 5 \times 6 \times 7 ... \times n$. Divide this by $n!$ which is total number of unrestricted arrangements.

Approach 3 (same as approach 2): As the order is fixed, you cannot permute (a b c d) so the number of arrangements are $\frac{n!}{4!}$. Divide this by $n!$

$\endgroup$
4
  • $\begingroup$ Please, can you also explain it using a decision tree based approach $\endgroup$ Jan 21 at 19:50
  • $\begingroup$ Can your decision tree not have different orders of a b c d? If you count it should give you $24$ and one of them is the order that you want? $\endgroup$
    – Math Lover
    Jan 21 at 20:00
  • $\begingroup$ Yes, I agree. But then we have already chosen a b c d and then go on to construct the tree. So the total ordering possible is 4! and only one among them is the favourable outcome . My question is that how to construct a decision tree so that when we count the total outcomes, it turns out to be $P(n,i)$ and the favourable outcomes is $C(n, i)$ $\endgroup$ Jan 21 at 20:10
  • $\begingroup$ OK understand. For a general case like this, won't decision tree be very cumbersome? But at the same time, I acknowledge that I do not use decision tree much so I may be wrong. $\endgroup$
    – Math Lover
    Jan 21 at 20:21
1
$\begingroup$

The probability does change if you replace $<$ with $\leq$ and you're sampling from your set of $n$ distinct integers with replacement.

In this situation, the number of unordered samples of size $i$ becomes ${n+i-1 \choose i}$ while the number of ordered samples of size $i$ is $n^i$.

So the probability that $r_1\leq \ldots \leq r_i$ equals $\frac{{n+i-1 \choose i}}{n^i}$

$\endgroup$
0
0
$\begingroup$

Another approach for solving $a)$ and $b)$ is the following:

$a)$ (I assume the numbers are selected without replacement): Each sequence of $i$ numbers can be represented as a vector in $\{0,1\}^n$ with exactly $i$ coordinates being equal to $1$. For example, let $n=9$ and $i=4$, then $$1< 4< 5<8 \longleftrightarrow \{1,0,0,1,1,0,0,1,0\}\\ 2<3<7<9 \longleftrightarrow \{0,1,1,0,0,0,1,1,0\}\\ 5<6<7<8\longleftrightarrow \{0,0,0,0,1,1,1,1,0\}$$ This way, in order to create any feasible sequence we only have to choose the $i$ coordinates where the $1$s will be placed. This lead us to a probability of $$\dfrac{\dbinom{n}{i}}{n!/(n-i-1)!}.$$

$b)$ (I assume the numbers are selected with replacement): In order to solve $b)$ all we have to do is to represent each sequence as a vector in $\{0,\ldots,n\}^i$ and count how many of these vectors have the sum of their coordinates equal to $i$. For example, let $n=9$ and $i=4$, then $$1\leq 2\leq 2\leq 6 \longleftrightarrow \{1,2, 0,0,0,1,0,0,0\}\\3\leq 3\leq 3\leq 3 \longleftrightarrow \{0,0,4,0,0,0,0,0,0\}\\ 1\leq 4\leq 8\leq 9 \longleftrightarrow \{1,0,0,1,0,0,0,1,1\}$$ By using stars and bars we get that the probability of having a favourable sequence is $$\dfrac{\dbinom{n+i-1}{i}}{n^i}.$$

$\endgroup$
5
  • 1
    $\begingroup$ It is strange to assume that the procedure differs in the case b). In any case the given answer is wrong. Just check for $n=3,i=2$. $\endgroup$
    – user
    Feb 23 at 11:41
  • 1
    $\begingroup$ @user The number of $n-$ tuples whose sum is $i$ equals ${n + i -1 \choose i}$, not ${n+i-1 \choose i-1}$. If we have $n=3,i=2$ then $${n+i-1 \choose i}=6$$ which corresponds to the six numbers $$11,12,13,22,23,33$$ $\endgroup$ Feb 23 at 12:33
  • 1
    $\begingroup$ @MatthewPilling Yes, you correctly found the error. $\endgroup$
    – user
    Feb 23 at 12:37
  • $\begingroup$ @MatthewPilling True, thanks for the comment! $\endgroup$ Feb 23 at 14:17
  • $\begingroup$ @user I changed the assumption since $r$ could not be repeated in $a)$ but it could happen in $b)$. Anyways, the problem is not 100% accurate to me. It could be explained better imo. $\endgroup$ Feb 23 at 14:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.