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?
7
-
7$\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$– Meni RosenfeldCommented May 29, 2018 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$– Meni RosenfeldCommented May 30, 2018 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$– Meni RosenfeldCommented May 30, 2018 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$– Meni RosenfeldCommented Jun 1, 2018 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$– Meni RosenfeldCommented Jun 1, 2018 at 13:25
|
Show 2 more comments
2 Answers
$\begingroup$
$\endgroup$
1
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!}$.
-
$\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$– HenryCommented May 29, 2018 at 14:33
$\begingroup$
$\endgroup$
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).
