Solved – How to calculate the probability that the randomly chosen function will be strictly increasing

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?

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!}$.

Similar Posts:

Rate this post

Leave a Comment