Real analysis and argmax

In this post I give a proof of an exercise of real analysis that has found an application to statistical mode estimation (see the Remark below). I wish to thank gerard0, remarque, and La vieille for their contribution.

Proposition. Let f be an upper-semicontinuous map from [a, b] (a < b) to \mathbb{R}_+. Suppose that there is a unique \theta \in \mathrm{arg max} f (f(\theta) = \sup_{x \in [a, b]} f(x)). Then for every continuous map \psi : [a, b] \mapsto \mathbb{R} we have

\displaystyle \frac{\int_a^b f(t)^n \psi(t) \, dt}{\int_a^b f(t)^n \, dt} \rightarrow_{n \rightarrow \infty} \psi(\theta).

Proof. First remark that the uniqueness of \theta implies that f is not identically zero. We denote by u_n the sequence at stake. We are looking for an upper bound of

\displaystyle u_n - \psi(\theta) = \frac{\int_a^b f(t)^n (\psi(t) - \psi(\theta)) \, dt}{\int_a^b f(t)^n \, dt}.

So let \epsilon > 0. The map \psi is continuous (at \theta) so there exists an open interval I containing \theta such that | \psi(t) - \psi(\theta) | \leq \epsilon for all t \in I. Defining M = \sup_{t \in [a, b]} \psi(t) we obtain

\displaystyle | u_n - \psi(\theta) | \leq \epsilon + 2 M \frac{\int_J f(t)^n \, dt}{\int_a^b f(t)^n \, dt},

where J denotes the compact subset [a, b] \setminus I. It remains to show that the ratio \frac{\int_J f(t)^n \, dt}{\int_a^b f(t)^n \, dt} tends to 0. But it is a well known result (see e.g. here for a proof relying on Chebyshev’s inequality) that

\displaystyle \left(\int_a^b f(t)^n \, dt \right)^{1/n} \rightarrow \sup_{t \in [a, b]} f(t) = f(\theta),

and similarly

\displaystyle \left(\int_J f(t)^n \, dt \right)^{1/n} \rightarrow \sup_{t \in J} f(t) =: f(\theta_1).

(The existence of \theta_1 is ensured by the upper-semicontinuity of f and the compactness of J.) This implies that

\displaystyle \log \frac{\int_J f(t)^n \, dt}{\int_a^b f(t)^n \, dt} \sim n \log \alpha,

where \alpha is the ratio f(\theta_1)/f(\theta), which is strictly less than 1 by uniqueness of \theta. Thus, n \log \alpha tends to -\infty, and so does \log \frac{\int_J f(t)^n \, dt}{\int_a^b f(t)^n \, dt}. This shows that \frac{\int_J f(t)^n \, dt}{\int_a^b f(t)^n \, dt} tends to 0, and concludes the proof.

Remark. Suppose that f is actually an upper-semicontinuous probability density with a unique mode \theta. Taking \psi : t \mapsto t the previous result states that

\displaystyle \theta = \lim_{n \rightarrow \infty} E[X_n],

where, for each n, X_n is a random variable with density f^n / \int f(t)^n \, dt. This result is at the core of the mode estimator proposed by Grenander (1965).

References.

Grenander, Ulf (1965). Some direct estimates of the mode. Ann. Math. Statist. 36:131-138

Axiomatique des ensembles bornés

J’aime beaucoup les axiomatiques élégantes en mathématiques, comme peuvent l’être celles d’espace topologique, d’espace uniforme ou d’espace de convexité. Il est également possible d’axiomatiser la notion d’ensemble borné, c’est-à-dire d’abstraire les propriétés des ensembles bornés.

Sur un ensemble E, on appelle bornitude ou plus communément bornologie une famille \mathcal{B} de parties de E vérifiant les propriétés suivantes :

  • toute partie finie est dans \mathcal{B} ;
  • toute partie d’une partie qui est dans \mathcal{B} est dans \mathcal{B} ;
  • l’union de deux parties qui sont dans \mathcal{B} est dans \mathcal{B}.

S’il n’y a pas d’ambiguïté, les éléments de \mathcal{B} peuvent être appelés les parties bornées. Le couple (E, \mathcal{B}) est appelé espace bornologique.

Étant donné qu’une intersection quelconque de bornologies est une bornologie, on peut considérer la bornologie engendrée par une famille de parties.

Si f est une fonction de E dans E', et que E' est muni d’une bornologie \mathcal{B}', on peut munir E de la bornologie f^{-1}(\mathcal{B}') définie par

f^{-1}(\mathcal{B}') = \{ B \subset E : f(B) \in \mathcal{B}'\}.

Il semble intéressant de coupler la notion de bornologie avec celle d’espace topologique. On dit qu’une bornologie sur un espace topologique est elle-même topologique si la fermeture d’une partie bornée est bornée. Ainsi, l’ensemble des parties relativement compactes d’un espace topologique est une bornologie topologique, que l’on peut appeler la bornologie de Heine–Borel. Également, si f : E \rightarrow E' est continue, et que \mathcal{B}' est une bornologie topologique sur E', alors f^{-1}(\mathcal{B}') est une bornologie topologique sur E.

Si l’on dit qu’un espace topologique muni d’une bornologie \mathcal{B} est localement borné si pour tout ouvert G et tout x \in G il existe un ouvert borné B tel que x \in B \subset G, alors on a la première proposition suivante :

Proposition. Soit E un espace topologique, et \mathcal{B} une bornologie (pas nécessairement topologique) sur E. Si E est localement borné, alors toute partie (relativement) compacte de E est bornée.

Preuve. Soit K une partie compacte. Si x \in K, il existe une partie ouverte bornée B_x telle que x \in B_x car E est localement borné. Donc K est recouvert par la famille ouverte (B_x)_{x \in K}, et comme K est compact il existe une partie finie F de K telle que K \subset \bigcup_{x \in F} B_x. Ce dernier ensemble est borné en tant qu’union finie de parties bornées, donc K est borné.

A suivre…

How long does a `War’ last?

We all have played the card game called ‘War‘ at least once and know from experience that it can last much too long (often, both players agree to stop before the legal end of the game). But how long actually?

This is the question that came (back) to my mind while playing with my 3 year old son a variant of the game.
So I decided to write some R code and simulate enough games to make up my mind.

I do not need to adopt any convention here (such as a convention on what happens if a player runs out of cards during a war), since I am not interested in the winner, but only in the number of unitary moves; this number will give me a proxy of the total duration of the game. I define a unitary move as the number of cards played by one player during one move. So if there is a war during a move, the number of unitary moves will be at least equal to three.

First, I need to simulate one move. This is the purpose of the function ‘PlayWar1’.

PlayWar1 = function(deck1, deck2, faceUpCards = c(), faceDownCards = c(), iter = 1)
{
# This function simulates one move of 'War'.
# Because of the nature of 'War', this function is recursive.
#
# Arguments:
#   deck1:         numeric vector, the deck of Player 1
#   deck2:         numeric vector, the deck of Player 2
#   faceUpCards:   numeric vector, the cards that are shown by both players
#   faceDownCards: numeric vector, the cards that remain hidden during a war
#   iter:          integer, the number of iterations
#
# Value: a list consisting of the updated values of 'deck1', 'deck2',
#   'faceUpCards', 'faceDownCards', 'iter' at the end of the move.

  n1 = length(deck1)
  n2 = length(deck2)

  if (n1 > 0 & n2 > 0) {

    ## Each player reveals the top card of his/her deck
    faceUpCards = c(deck1[1], deck2[1], faceUpCards)
    deck1 = deck1[-1]
    deck2 = deck2[-1]

    ## Player 1 wins
    if (faceUpCards[1] > faceUpCards[2]) {
      deck1 = c(deck1, sample(c(faceDownCards, faceUpCards)))
      faceUpCards = faceDownCards = c()

    ## Player 2 wins
    } else if (faceUpCards[2] > faceUpCards[1]) {
      deck2 = c(deck2, sample(c(faceDownCards, faceUpCards)))
      faceUpCards = faceDownCards = c()

    ## 'War'
    } else {

      n1 = length(deck1)
      n2 = length(deck2)

      if (n1 > 0 & n2 > 0) {
        faceDownCards = c(deck1[1], deck2[1], faceDownCards)
        deck1 = deck1[-1]
        deck2 = deck2[-1]

        r = Recall(deck1, deck2, faceUpCards, faceDownCards, iter = iter + 2)
        deck1 = r[[1]]
        deck2 = r[[2]]
        faceUpCards = r[[3]]
        faceDownCards = r[[4]]
        iter = r[[5]]
      }
    }
  }

  return(list(deck1, deck2, faceUpCards, faceDownCards, iter))
}

Then I can define a game as a succession of moves with the function ‘PlayWar’. This function has two arguments, which characterize the deck in terms of height and width.

PlayWar = function(height = 13, width = 4)
{
# This function simulates one game of 'War'.
#
# Arguments:
#   height:   integer, the number of cards per colour
#   width: integer, the number of colours of the card game (usually fours,
#     namely spades, hearts, diamonds, and clubs)
#
# Value: the number of unitary moves, understood as a proxy of the duration
#   of the game.

  ## Create the deck
  game = rep(1:height, width)

  ## Shuffle cards
  game = sample(game)

  ## Give cards to each player
  deck1 = game[1:(length(game)/2)]
  deck2 = game[(length(game)/2+1):length(game)]

  ## Counter
  i = 0

  ## While someone has cards, the game goes on
  while(length(deck1) > 0 & length(deck2) > 0) {
    p = PlayWar1(deck1, deck2, c(), c())
    deck1 = p[[1]]
    deck2 = p[[2]]
    i = i + p[[5]]
  }

  ## Proxy of the duration of the game
  return(i)
}

It now remains to try this out:

set.seed(17)
N = 10000
d1 = sapply(1:N, FUN = function(i) PlayWar(13,4))
range(d1) # min = 38, max = 4102

In this simulation I obtain a maximum of 4102 unitary moves! In the variant played with my son, the deck is made of six ‘colours’, with six cards of each colour.

d2 = sapply(1:N, FUN = function(i) PlayWar(6,6))
range(d2) # min = 18, max = 1220

I can draw the densities of the duration in the 13-4 and 6-6 situations with the following code (that uses package ‘ggplot2’):

data = data.frame(duration = c(d1,d2), type = c(rep("13-4", N), rep("6-6",N)))
ggplot2::ggplot(data, aes(duration, fill = type)) + geom_density(alpha = 0.2)

Density

Next step: fit a probability distribution to these durations!

ADDED LATER: See this post on MathOverflow for a thorough discussion on the same topic.

Toute fonction continue n’est-elle pas mesurable ?

Une question m’intrigue en ce moment, à la suite d’un article récemment posté sur arXiv où j’utilise la tribu d’un Borel d’un espace non-séparé.

Il est habituel de définir la tribu de Borel \mathcal{B}(X) d’un espace topologique X comme la \sigma-algèbre engendrée par les ouverts. C’est d’ailleurs la définition fournie aujourd’hui par Wikipedia.
Quand X est séparé (Hausdorff), elle permet de faire des parties compactes des ensembles mesurables (puisqu’alors tout compact est fermé), ce qui est plutôt désirable.

Mais que se passe-t-il si X n’est pas séparé ?

Les espaces sobres, que l’on rencontre par exemple en géométrie algébrique ou en informatique théorique, sont des cas classiques d’espaces non-séparés. Définir leur tribu de Borel comme ci-dessus ne permet pas d’inclure les parties compactes (ou compactes saturées).

Il est alors d’usage de redéfinir la tribu de Borel \mathcal{B}(X) comme la \sigma-algèbre engendrée par les ouverts et les parties compactes saturées. Je rappelle qu’une partie est saturée si elle coïncide avec l’intersection des ouverts la contenant. Dans le cadre des espaces non-séparés, les compacts saturés ont de meilleures propriétés que les simples parties compactes, notamment en vertu du théorème de Hofmann–Mislove. Celui-ci nous apprend que, dans un espace sobre X, les filtres Scott-ouverts d’ouverts de X sont en correspondance bijective avec les compacts saturés de X.

Problème.
Avec cette nouvelle définition des boréliens, il n’est plus évident que toute fonction continue soit mesurable !

Aussi surprenant que cela paraisse, il n’y a pas trace d’une telle question dans la littérature.
Ce qui m’intéresse alors est non seulement de trouver un contre-exemple, mais aussi de mettre au jour une condition nécessaire et suffisante sur l’espace Y (respectivement sur l’espace X) pour que toute fonction continue de X dans Y soit mesurable pour tout X (respectivement pour tout Y).

J’ai posté la question sur ce forum sans grand succès. Mais cela m’a permis de réfléchir un peu plus à la question.

Notons déjà que f est mesurable si et seulement si f^{-1}(\uparrow y) est mesurable pour tout y \in Y, si l’on note \uparrow y l’intersection des ouverts de Y contenant y.
L’ensemble \uparrow y est compact saturé et un élément y' est dans \uparrow y si et seulement si y \leq y', où \leq est le préordre de spécialisation de l’espace topologique Y.

Ainsi, si Y est T_1, tout ensemble \uparrow y est réduit au singleton \{ y \}, et ce singleton est fermé, donc la fonction f est mesurable.

Egalement, si Y est à base dénombrable de voisinages (first-countable en anglais), alors tout \uparrow y peut s’écrire comme une intersection dénombrable d’ouverts, donc à nouveau f est mesurable.

Enfin si f est une application ouverte et bijective, alors l’image réciproque de \uparrow y est de la forme \uparrow x pour un x \in X, donc f est mesurable.

Peut-on trouver d’autres situations où les choses se passent bien ?