Question

A rectangular array of mn numbers arranged in n rows, each consisting of m columns, is said to contain a saddle point if there is a number that is both the minimum of its row and the maximum of its column. For instance, in the array 1 32 0 −2 6 .5 12 3 the number 1 in the first row, first column is a saddle point. The existence of a saddle point is of significance in the theory of games. Consider a rectangular array of numbers as described previously and suppose that there are two individuals—A and B—who are playing the following game: A is to choose one of the numbers 1, 2, ... , n and B one of the numbers 1, 2, ... , m. These choices are announced simultaneously, and if A chose i and B chose j, then A wins from B the amount specified by the number in the ith row, jth column of the array. Now suppose that the array contains a saddle point—say the number in the row r and column k—call this number xrk. Now if player A chooses row r, then that player can guarantee herself a win of at least xrk (since xrk is the minimum number in the row r). On the other hand, if player B chooses column k, then he can guarantee that he will lose no more than xrk (since xrk is the maximum number in the column k). Hence, as A has a way of playing that guarantees her a win of xrk and as B has a way of playing that guarantees he will lose no more than xrk, it seems reasonable to take these two strategies as being optimal and declare that the value of the game to player A is xrk. If the nm numbers in the rectangular array described are independently chosen from an arbitrary continuous distribution, what is the probability that the resulting array will contain a saddle point?

Short answer

The required probability is$p=\frac{1}{n+m-1}$

Step-by-step solution

Content Introduction

Define random variables $X_{i,j}$ and say that the mark the number on position $(i,j)$, where $i=1,...,n$and$j=1,...,m.$

We are given that these variables are all equally distributed and that they are independent. Because of the symmetry, we can consider what is the probability that the number on position $(1,1)$is a saddle point.

Content Explanation

The number of saddle point if and only if it is minimum of its rows and maximum of its column.

$$\begin{gathered} X_{1,1}\le X_{i,j},j=1,.....,m \\ {X}_{1,1}\ge X_{i,1},i=1,.....,n \end{gathered}$$

So, we are looking $n+m-1$variables and we want the probability that the certain variable is placed nth in order if we order them in a row. Because of the symmetry, we know that the probability for the event is

$p=\frac{1}{n+m-1}$

since all variables are equally like to be nth ordered variable.