5
$\begingroup$

Consider the set of all functions from $\{1,2,...,m\}$ to $\{1,2,...,n\}$, where $n > m$. If a function is chosen from this set at random, what is the probability that it will be strictly increasing?

$\endgroup$
7
  • 6
    $\begingroup$ @Carl: The question is perfectly clear. Given a set $X$ to be the domain and a set $Y$ to be the codomain, you can certainly talk about the set of all functions from $X$ to $Y$. This set is often denoted $Y^X$. In the OP, $X$ and $Y$ are finite, so $Y^X$ is finite as well ($|Y^X|=|Y|^{|X|}=n^m$), and you can talk about choosing from it uniformly randomly. $\endgroup$ May 29 '18 at 12:24
  • 1
    $\begingroup$ @Carl: The language was exact. For some reason you're having difficulty parsing it. I don't know if it's because you're rusty on the language of set theory or something else. One common construction is: Given sets $X$ and $Y$, a function from $X$ to $Y$ is a set $f$ of ordered pairs $(x,y)$ where $x\in X$,$y\in Y$, such that for every $x\in X$ there is some $y\in Y$ so that $(x,y)\in f$, and if $(x_1,y_1)\in f, (x_2,y_2)\in f$ then $x_1\neq x_2$ or $y_1=y_2$. You can show that if $X=\{1,2,\ldots,m\}$ and $Y=\{1,2,\ldots,n\}$, then there are $n^m$ such functions; $\binom n m$ are increasing. $\endgroup$ May 30 '18 at 22:56
  • 1
    $\begingroup$ e.g., for $m=n=2$, there are 4 functions from $\{1,2\}$ to $\{1,2\}$. The set of all such functions is $\{\{(1,1),(2,1)\},\{(1,1),(2,2)\},\{(1,2),(2,1)\},\{(1,2),(2,2)\}\}$. If you choose uniformly randomly from it, you have a probability of 25% of choosing a strictly increasing one (the only one is $\{(1,1),(2,2)\}$). $\endgroup$ May 30 '18 at 23:02
  • 1
    $\begingroup$ @Carl: We're not talking about set functions. A set function takes a set as an input. We're talking about a function that takes a positive integer at most $m$ as input, and gives a positive integer at most $n$ as output. (Positive integers can be constructed as sets, but not necessarily). In other words, the domain is the set $\{1,2,\ldots, m\}$ and the codomain is the set $\{1,2,\ldots, n\}$. In other words, it's a function from $\{1,2,\ldots, m\}$ to $\{1,2,\ldots, n\}$. $\endgroup$ Jun 1 '18 at 13:24
  • 1
    $\begingroup$ @Carl: As you said, and as is clear from the definition I gave above, given a function $f:\{1,2,\ldots,m\}\to\{1,2,\ldots,n\}$, for every $1\le i\le m$ there is exactly one $1\le j\le n$ such that $f(i)=j$. Or, to use, the construction of functions as a set of ordered pairs, for every $1\le i\le m$ there is exactly one $1\le j\le n$ such that $(i,j)\in f$. $\endgroup$ Jun 1 '18 at 13:25
14
$\begingroup$

Let us pick $m$ elements from $\{1,\dotsc,n\}$, let us call these $a_1 < a_2 < \dotsc , a_m$. Clearly these define a strictly increasing function $f$ from $\{1,\dotsc,m\} \to \{1,\dotsc,n\}$ via the rule $f(i) = a_i$. Furthermore, any strictly increasing function defined on the above sets is of this form.

Hence there are exactly ${n \choose m}$ strictly increasing functions. On the other hand, in total there are $n^m$ functions mapping between these two sets. Assuming that by "random" the OP means the uniform measure on the $n^m$ functions above, then the probability of picking a strictly increasing function is:

$$ \frac{{n \choose m}}{n^m} $$

For example, for $n >> m$, an application of Stirling's approximation, shows that the RHS is $ \approx \frac{1}{m!}$.

$\endgroup$
1
  • $\begingroup$ $\frac{1}{m!}$ would be exactly correct if you wanted to know what proportion of 1-1 injective functions were strictly increasing. For $n \gg m^2$ the vast majority of all functions are 1-1 injective $\endgroup$
    – Henry
    May 29 '18 at 14:33
2
$\begingroup$

Let $S(n,m)$ be the number of sub-arrays $1 \leqslant k_1 < k_2 < \cdots < k_m \leqslant n$ containing $m$ integer values that are increasing and are bounded by the values one and $n$. This binary function is well-defined for all integers $1 \leqslant m \leqslant n$, giving a triangular array of values. With a simple combinatorial argument$^\dagger$ we can establish the following recursive equations that define this binary function:

$$S(n+1,m) = S(n,m) + S(n,m-1) \quad \quad \quad \quad S(n,1) = n.$$

Solving this recursive equation gives us the explicit formula:

$$S(n,m) = {n \choose m} = \frac{n!}{m!(n-m)!}.$$

(There are other combinatorial arguments that also lead you to this result. For example, choosing an increasing function is equivalent to choosing $m$ values in the co-domain, which are then placed in increasing order.) Now, to get the result we need to be clear on exactly how a "random function" on this domain and co-domain is chosen. The simplest specification is to say that each possible mapping is chosen with equal probability, which means that there are $n^m$ equiprobable functions. Hence, the probability of interest is:

$$\mathbb{P}(\text{Increasing Function}) = \frac{n!}{m!(n-m)! \cdot n^m}.$$

Taking a first-order Stirling approximation for large $n$ gives $\mathbb{P}(\text{Increasing Function}) \approx 1/m!$, which is a very crude estimate that is suitable when $n$ is substantially larger than $m$. So basically, we see that once the co-domain in this problem is large, the probability of getting an increasing sequence at random is small; this accords with intuition.


$^\dagger$ If $m=1$ then we have only a single value in the mapping and every mapping to any of the $n$ places gives an increasing map. We therefore have $S(n,1)=n$ for all $n \in \mathbb{N}$. Moreover, the number of sub-arrays $S(n+1,m)$ includes all sub-arrays where the values occurs in the first $n$ places (there are $S(n,m)$ of these) and all the sub-arrays where the last value occurs in the last place and the remaining values occur before this (there are $S(n,m-1)$ of these).

$\endgroup$

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.