Press "Enter" to skip to content

Month: October 2012

The ballot theorem

A random walk loop of length 1000

The classical ballot theorem states that in an election with two candidates \( {A} \) and \( {B} \) in which \( {A} \) obtains \( {a} \) votes and B obtains \( {b \leq a} \) votes, the probability that \( {A} \) stays above \( {B} \) during the counting of the votes is \( {(a-b)/(a+b)} \). In probabilistic terms, setting \( {n=a+b} \) and \( {k=a-b} \), if \( {{(S_n)}_{n\geq0}} \) is a simple random walk on \( {\mathbb{Z}} \), i.e. \( {(S_{n+1}-S_n)_{n\geq0}} \) are i.i.d. \( {\pm1} \) Bernoulli r.v. taking the value \( {+1} \) with probability \( {p\in(0,1)} \) and \( {-1} \) with probability \( {1-p} \), then

\[ \mathbb{P}(S_1>0,\ldots,S_n>0|S_0=0,S_n=k)=\frac{k}{n}. \]

A proof. Let \( {P_{n,k}} \) be the set of paths of length \( {n} \) of the simple random walk starting from \( {0} \) and ending at \( {k} \), and let \( {P^+_{n,k}} \) be the set of such paths staying positive. Note that \( {0\leq k\leq n} \) and \( {n-k} \) is odd. We have

\[ \mathbb{P}(S_1>0,\ldots,S_n>0|S_0=0,S_n=k) =|P^+_{n,k}|\frac{p^a(1-p)^b}{\mathbb{P}(S_n=k|S_0=0)}. \]

On the other hand, \( {\mathbb{P}(S_n=k|S_0=0)=|P_{n,k}|p^a(1-p)^b} \) and thus

\[ \mathbb{P}(S_1>0,\ldots,S_n>0|S_0=0,S_n=k) =\frac{|P^+_{n,k}|}{|P_{n,k}|} \]

which remarkably does not depend on \( {p} \). We also have

\[ |P_{n,k}|=\binom{a+b}{a}=\binom{n}{(n+k)/2} \]

and in particular \( {|P_{n+1,k+1}|=|P_{n,k+2}|+|P_{n,k}|} \). The ballot theorem states that

\[ |P^+_{n,k}|=\frac{k}{n}|P_{n,k}|=\frac{a-b}{a+b}\binom{a+b}{a}. \]

To prove the ballot theorem, one may observe by a simple analysis of the last step that \( {|P^+_{n,k}|} \) satisfies to the same recurrence relation as \( {|P_{n,k}|} \), namely

\[ |P^+_{n+1,k+1}|=|P^+_{n,k+2}|+|P^+_{n,k}|. \]

This leads by induction on \( {n} \) to \( {n|P^+_{n,k}|=k|P_{n,k}|} \), and we are done.

A combinatorial proof. There is actually an elegant proof of the ballot theorem due to Désiré André. Namely, \( {P_{n-1,k-1}} \) is in bijection with the set of elements of \( {P_{n,k}} \) starting with an increment \( {-1} \). On the other hand, this set is itself in bijection with the set of elements of \( {P_{n,k}\setminus P^+_{n,k}} \) starting with an increment \( {+1} \) (it suffices to reflect the path before reaching zero). It follows then that \( {|P_{n,k}|-|P^+_{n,k}|=2|P_{n-1,k-1}|} \), and thus \( {|P^+_{n,k}|=(k/n)|P_{n,k}|} \). This combinatorial trick provides also the famous Catalan number formula:

\[ \mathbb{P}(S_1>0,\ldots,S_{2n-1}>0|S_0=0,S_{2n}=0)=\frac{1}{n+1}\binom{2n}{n}. \]

Universal statement. Set \( {p=1/2} \). It can be shown that for every \( {k\in\mathbb{Z}} \),

\[ \mathbb{P}(S_n=k|S_0=0)=n^{-1/2}\varphi(n^{-1/2}k)+o(n^{-1/2}) \]

where \( {\varphi(t)=(2\pi)^{-1/2}e^{-\frac{1}{2}t^2}} \) is the density of the standard Gaussian law \( {\mathcal{N}(0,1)} \). This follows for instance from the de Moivre-Laplace theorem, which is a local central limit theorem for Bernoulli random variables. As a consequence, from the ballot theorem, for some constants \( {C_2\geq C_1>0} \), as \( {n\gg1} \) with \( {k=\mathcal{O}(\sqrt{n})} \),

\[ C_1\frac{k}{n^{3/2}} \leq \mathbb{P}(L_n(0)=0,S_n=k|S_0=0) \leq C_2\frac{k}{n^{3/2}}. \]

where \( {L_n(x)=\mathbf{1}_{\{S_1=x\}}+\cdots+\mathbf{1}_{\{S_n=x\}}} \) is the local time in \( {x} \) up to time \( {n} \). This type of statement can be extended to sums of i.i.d. lattice random variables, and even to more general random variables.

Some further reading. The ballot theorem goes back at least to Bertrand (1887), and is discussed in the Probability Theory classical books of Feller and of Shiryaev for instance. There are many variants and extensions, see for example the article Ballot theorems, old and new, by Addario-Berry and Reed (2007).

Leave a Comment

Determinant of block matrices

Matrix

This is a tiny followup of a previous post on nonlinear formulas in linear algebra. Let us consider a block matrix \( {M} \) of size \( {(n+m)\times(n+m)} \) of the form

\[ M= \begin{pmatrix} A & B \\C & D \end{pmatrix} \]

where \( {A,B,C,D} \) are \( {n\times n} \), \( {n\times m} \), \( {m\times n} \), \( {m\times m} \). If \( {D} \) is invertible then

\[ \det(M)=\det(A-BD^{-1}C)\det(D). \]

This follows immediately from the identity (mentioned in Wikipedia)

\[ \begin{pmatrix} A & B \\ C & D \end{pmatrix} \begin{pmatrix} I & 0 \\ -D^{-1}C & I \end{pmatrix} = \begin{pmatrix} A-BD^{-1}C & B \\ 0 & D \end{pmatrix} \]

(the determinant of a block triangular matrix is the product of the determinants of its diagonal blocks). If \( {m=n} \) and if \( {C},{D} \) commute then \( {\det(M)=\det(AD-BC)} \). Note that \( {A-BD^{-1}C} \) is the Schur complement of \( {A} \) in \( {M} \). Similar formulas are derived in arXiv:1112.4379 for the determinant of \( {nN\times nN} \) block matrices formed by \( {N^2} \) blocks of size \( {n\times n} \).

3 Comments

Emacsulation

GNU EmacsFor typesetting mathematics, I am used to use the LaTeX document preparation system with the AUCTeX package for the GNU Emacs editor, and the GNOME Evince viewer, provided by Debian. Here is my modest init file: dot-emacs.el. It features synctex forward and inverse search (without focus problems) and many other goodies. Feel free to use it and to improve it!

Wikipedia provides a rich list of LaTeX editors. By curiosity, you may try from time to time some of these editors. Even if they have made huge progresses, I still believe personally that Emacs is the best to date, due to its versatility: within the editor, one can open a remote file using SSH, one can search for bibtex entries from arXiv or MathSciNet, one can play with Octave, etc.

PS: EMACSulation is the name of an old series of articles by Eric Marsden in the Linux Gazette.

;;;
;;; Djalil's GNU Emacs .emacs.el init file, dated 2013-05. 
;;; Tested with Emacs 23 and 24, Auctex 11.86, Evince 3.4
;;; With Auctex 11.87, reverse/forward search is almost built-in (with bugs)
;;; Debian: apt-get install wmctrl auctex preview-latex 
;;;
(add-to-list 'load-path "~/S/elisp")
(setq custom-file "~/.emacs.cu")
;;;
(setq locale-coding-system 'utf-8)
(set-selection-coding-system 'utf-8)
(prefer-coding-system 'utf-8)
(set-default-font "DejaVu Sans Mono-16")
;;;
(require 'jka-compr) ; Read compressed files
(require 'paren)     ; Visual matching () {} [] 
;; s-region.el and pc-select are obsolete.
;;  They are superseded by shift-select-mode enabled by default in 23.1.
;(require 's-region)  ; Copy/Cut/Paste with Shift/Delete/Insert
;;;
(put 'eval-expression 'disabled nil)
(put 'erase-buffer 'disabled nil)
(put 'narrow-to-region 'disabled nil)
;;;
(custom-set-variables 
 '(column-number-mode t)
 '(default-major-mode 'text-mode)
 '(delete-selection-mode t)
 '(dired-listing-switches "-alF")
 '(dired-ls-program "/bin/ls")
 '(fill-column 78)
 '(global-font-lock-mode t)
 '(indent-tabs-mode nil)
 '(iso-accents-customize french)
 '(line-number-mode t)
 '(resize-minibuffer-mode t)
 '(search-highlight t)
 '(sentence-end-double-space nil)
 '(show-paren-mode t)
 '(show-paren-ring-bell-on-mismatch t)
 '(show-paren-style 'mixed)
 '(tab-width 4)
 '(tool-bar-mode nil)
 '(transient-mark-mode t)
)
;;;
;;; I don't remember who wrote this useful function...
;;;
(defun match-paren (arg)
  " Go to the matching parenthesis if on parenthesis otherwise insert %."
  (interactive "p")
  (cond ((looking-at "\\s\(") (forward-list 1) (backward-char 1))
        ((looking-at "\\s\)") (forward-char 1) (backward-list 1))
        (t (self-insert-command (or arg 1)))))
;;;
;;; Keys
;;;
(define-key global-map [(%)] 'match-paren)
(define-key global-map [(f1)] 'help)
(define-key global-map [(f2)] 'run-octave)
(define-key global-map [(f3)] 'font-lock-mode)
(define-key global-map [(f4)] 'ispell-change-dictionary)
(define-key global-map [(next)] '(lambda ()(interactive)(scroll-up 25)))
(define-key global-map [(prior)] '(lambda ()(interactive)(scroll-down 25)))
(define-key global-map [(control home)] 'beginning-of-buffer)
(define-key global-map [(control end)] 'end-of-buffer)
(define-key global-map [(meta backspace)] 'undo)
(define-key global-map [(meta return)] 'eshell)
;(define-key global-map [(delete)] 'delete-char)
;;;
;;; Bibretrieve allows to fetch Bibtex entries from MathSciNet or arXiv
;;; Get if from http://www.emacswiki.org/emacs/download/bibretrieve.el
;;;
(autoload 'bibretrieve "bibretrieve" "Search for BibTeX entries on the web" t) 
(setq bibretrieve-backends '(("mrl" . 10) ("arxiv" . 5)))
;;;
;;; LaTeX: AUCTeX, Bibcite, RefTeX, etc
;;;
(require 'tex-site)
(load-library "auctex")
(load-library "preview-latex") 
(load "server")
(unless (server-running-p) (server-start))
(if window-system (require 'font-latex))
(autoload 'turn-on-bib-cite "bib-cite")
(custom-set-variables
 '(TeX-auto-save t)
 '(TeX-master nil)
 '(TeX-parse-self t)
 '(TeX-source-specials-mode t)
 '(bib-cite-use-reftex-view-crossref t)
 '(reftex-enable-partial-scans t)
 '(reftex-insert-label-flags (quote (t t)))
 '(reftex-plug-into-AUCTeX t)
 '(reftex-save-parse-info t)
 '(reftex-label-alist 
   (quote (("thm" ?h "th:" "~\\ref{%s}" nil ("thm" "th.")) 
           ("defn" ?d "def:" "~\\ref{%s}" nil ("defn" "def.")) 
           ("lem" ?l "lem:" "~\\ref{%s}" t ("lem" "lem.")))))
 '(reftex-use-multiple-selection-buffers t))
(add-hook 'LaTeX-mode-hook 'turn-on-auto-fill)
(add-hook 'LaTeX-mode-hook 'turn-on-bib-cite)
(add-hook 'LaTeX-mode-hook 'turn-on-reftex)
(add-hook 'LaTeX-mode-hook 'font-lock-mode)
(add-hook 'LaTeX-mode-hook 'imenu-add-menubar-index)
(add-hook 'LaTeX-mode-hook 'my-LaTeX-keys)
(defun my-LaTeX-keys ()
  (define-key LaTeX-mode-map [down-mouse-3] 'imenu)
  (define-key LaTeX-mode-map [(f7)] 'preview-buffer)
  (define-key LaTeX-mode-map [(f8)] 'preview-clearout-buffer)
  (define-key LaTeX-mode-map [(f9)] 'TeX-command-master)
  (define-key LaTeX-mode-map [(f10)] 'TeX-next-error)
  (define-key LaTeX-mode-map [(f12)] 'TeX-toggle-debug-bad-boxes)
  (define-key LaTeX-mode-map [(print)] 'preview-buffer)
  (define-key LaTeX-mode-map [(control B)] 'bibretrieve)
  (define-key LaTeX-mode-map [(control C)] 'reftex-citation)
  (define-key LaTeX-mode-map [(control R)] 'reftex-reference))
(add-hook 'server-switch-hook 'raise-frame)
;;
;; Forward/inverse search using Evince (based on dbus, needs also wmctrl)
;; Forward: C-c C-v 
;; Inverse: Ctrl - Left Mouse Button
;;
(add-hook 'LaTeX-mode-hook 'TeX-PDF-mode)
(setq TeX-source-correlate-method 'synctex) ; instead of source-specials 
(add-hook 'LaTeX-mode-hook 'TeX-source-correlate-mode)
;;
;; Forward search.
;;
(defun un-urlify (fname-or-url)
  "Transform file:///absolute/path into /absolute/path"
  ;; Limited support for special characters"
  (if (string= (substring fname-or-url 0 8) "file:///")
      (url-unhex-string (substring fname-or-url 7))
    fname-or-url))
;;
(defun urlify-escape-only (path)
  "Handle special characters for urlify"
  (replace-regexp-in-string " " "%20" path))
;;
(defun urlify (absolute-path)
  "Transform /absolute/path to file:///absolute/path"
  ;; Limited support for special characters"
  (urlify-escape-only 
   (concat "file://" 
           (file-truename 
            (concat default-directory absolute-path)))))
;;
(if (require 'dbus "dbus" t) 
    (progn
      ;; universal time, need by evince
      (defun utime ()  
        (let ((high (nth 0 (current-time)))
              (low (nth 1 (current-time))))
          (+ (* high (lsh 1 16) ) low)))
      ;;
      (defun auctex-evince-forward-sync (pdffile texfile line)
        (let ((dbus-name
               (dbus-call-method 
                :session
                "org.gnome.evince.Daemon"  ; service
                "/org/gnome/evince/Daemon" ; path
                "org.gnome.evince.Daemon"  ; interface
                "FindDocument"
                (urlify pdffile)
                t ; Open a new win if file not opened.
                )))
          (dbus-call-method 
           :session
           dbus-name
           "/org/gnome/evince/Window/0"
           "org.gnome.evince.Window"
           "SyncView"
           (urlify-escape-only texfile)
           (list :struct :int32 line :int32 1)
           (utime)))
        ;DC: bring the window to the foreground and give it the focus 
        (call-process "wmctrl" nil nil nil "-R" pdffile)) 
      ;;
      (defun auctex-evince-view ()
        (let ((pdffile (concat (TeX-master-file TeX-output-extension)))
              (texfile (buffer-file-name))
              (line (line-number-at-pos)))
          (auctex-evince-forward-sync pdffile texfile line)))
      ;; New view entry: Evince via D-bus.
      (setq TeX-view-program-list '())
      (add-to-list 'TeX-view-program-list
                   '("EvinceDbus" auctex-evince-view))
      ;; Prepend Evince via D-bus to program selection list
      ;; overriding other settings for PDF viewing.
      (setq TeX-view-program-selection '())
      (add-to-list 'TeX-view-program-selection
                   '(output-pdf "EvinceDbus"))))
;;
;; Inverse search.
;;
(if (require 'dbus "dbus" t) 
    (progn
      ;;
      (defadvice raise-frame (after make-it-work (&optional frame) activate)
        "Work around some bug? in raise-frame/Emacs/GTK/Metacity/something.
         Katsumi Yamaoka http://article.gmane.org/gmane.emacs.devel:39702"
        (call-process 
         "wmctrl" nil nil nil "-i" "-R"
         (frame-parameter (or frame (selected-frame)) 'outer-window-id)))
      ;;
      (defun auctex-evince-inverse-sync (file linecol timestamp)
        (let ((buf (get-file-buffer (un-urlify file)))
              (line (car linecol))
              (col (cadr linecol)))
          (if (null buf)
              (message "Sorry, %s is not opened..." file)
            (switch-to-buffer buf)
            (goto-line (car linecol))
            (unless (= col -1)
              (move-to-column col))
            (raise-frame))))
      ;; 
      (dbus-register-signal 
       :session 
       nil 
       "/org/gnome/evince/Window/0"
       "org.gnome.evince.Window" 
       "SyncSource"
       'auctex-evince-inverse-sync)))
;;;
;;; Tramp 
;;;
(require 'tramp)
(setq tramp-default-method "scp")
;;; 
;;; Octave mode
;;;
(autoload 'octave-mode "octave-mod" nil t)
(setq auto-mode-alist
      (cons '("\\.m$" . octave-mode) auto-mode-alist))
(add-hook 'octave-mode-hook
          (lambda ()
            (abbrev-mode 1)
            (auto-fill-mode 1)
            (if (eq window-system 'x)
                (font-lock-mode 1))))
(add-hook 'inferior-octave-mode-hook
          (lambda ()
            (turn-on-font-lock)
            (define-key inferior-octave-mode-map [up]
              'comint-previous-input)
            (define-key inferior-octave-mode-map [down]
              'comint-next-input)))
;;;
;;
;; Credits
;;
;; http://dud.inf.tu-dresden.de/~ben/evince_synctex.tar.gz
;; http://tex.stackexchange.com/questions/29813/setup-synctex-with-emacs
;; http://coderuins.wordpress.com/2011/10/04/using-synctex-with-emacs-and-evince-3-2/
;; http://www.mail-archive.com/auctex@gnu.org/msg04175.html
;;
;;; EOF.
1 Comment