\documentclass[10pt]{article}
\usepackage{fullpage}
\usepackage{setspace}
\usepackage{parskip}
\usepackage{titlesec}
\usepackage[section]{placeins}
\usepackage{xcolor}
\usepackage{breakcites}
\usepackage{lineno}
\usepackage{hyphenat}
\PassOptionsToPackage{hyphens}{url}
\usepackage[colorlinks = true,
linkcolor = blue,
urlcolor = blue,
citecolor = blue,
anchorcolor = blue]{hyperref}
\usepackage{etoolbox}
\makeatletter
\patchcmd\@combinedblfloats{\box\@outputbox}{\unvbox\@outputbox}{}{%
\errmessage{\noexpand\@combinedblfloats could not be patched}%
}%
\makeatother
\usepackage[round]{natbib}
\let\cite\citep
\renewenvironment{abstract}
{{\bfseries\noindent{\abstractname}\par\nobreak}\footnotesize}
{\bigskip}
\titlespacing{\section}{0pt}{*3}{*1}
\titlespacing{\subsection}{0pt}{*2}{*0.5}
\titlespacing{\subsubsection}{0pt}{*1.5}{0pt}
\usepackage{authblk}
\usepackage{graphicx}
\usepackage[space]{grffile}
\usepackage{latexsym}
\usepackage{textcomp}
\usepackage{longtable}
\usepackage{tabulary}
\usepackage{booktabs,array,multirow}
\usepackage{amsfonts,amsmath,amssymb}
\providecommand\citet{\cite}
\providecommand\citep{\cite}
\providecommand\citealt{\cite}
% You can conditionalize code for latexml or normal latex using this.
\newif\iflatexml\latexmlfalse
\providecommand{\tightlist}{\setlength{\itemsep}{0pt}\setlength{\parskip}{0pt}}%
\AtBeginDocument{\DeclareGraphicsExtensions{.pdf,.PDF,.eps,.EPS,.png,.PNG,.tif,.TIF,.jpg,.JPG,.jpeg,.JPEG}}
\usepackage[utf8]{inputenc}
\usepackage[ngerman,english]{babel}
\begin{document}
\title{Random sampling}
\author[1]{Riccardo Rigon}%
\affil[1]{University of Trento}%
\vspace{-1em}
\date{\today}
\begingroup
\let\center\flushleft
\let\endcenter\endflushleft
\maketitle
\endgroup
\sloppy
My own intuition says that in probability theory the concept of random
sampling is not contemplated. Randomness is used by probability theory
but is not implied by its axioms. Randomly literally means that there is
no law (expressed in equations) or algorithm (expressed in actions or
some programing code) that connects one pick to another. The pick of set
elements do not have to be obtained by subsequent action: they can be
concurrent instead. Besides, they do not need to be independent, in the
sense of probabilistic dependence. They can depend on each other while
this dependence does ~not imply causation (in the sense that one implies
the other).
I am supported in this
by~\href{https://en.wikipedia.org/wiki/Judea_Pearl}{Judea
Pearl}~{[}1{]}~when he stresses that probability is about
``association'' not ``causality'' (which is, in a sense, the reverse of
randomness):~An associational concept is any relationship that can be
defined in terms of a joint distribution of observed variables, and a
causal concept is any relationship that cannot be defined from the
distribution alone. Examples of associational concepts are: correlation,
regression, dependence, conditional independence, like-lihood,
collapsibility, propensity score, risk ratio, odds ratio,
marginalization,~conditionalization, ``controlling for,'' and so on.~
Examples of causal concepts are:randomization, influence, effect,
confounding, ``holding constant,'' disturbance, spurious correlation,
faithfulness/stability, instrumental variables, intervention,
explanation, attribution, and so on. The former can, while the latter
cannot be defined in term of distribution functions." He also writes:
``~Every claim invoking causal concepts must rely onsome premises that
invoke such concepts; it cannot be inferred from, or even defined in
terms statistical associations alone.''
I felt initially kind of wrong in thinking this. however
\href{https://en.wikipedia.org/wiki/Random_sequence}{wikipedia} also
comes to my direction:
"\href{https://en.wikipedia.org/wiki/Probability_axioms}{Axiomatic
probability theory}~deliberately~avoids a definition of a random
sequence.\href{https://en.wikipedia.org/wiki/Random_sequence\#cite_note-2}{{[}2{]}}~Traditional
probability theory does not state if a specific sequence is random, but
generally proceeds to discuss the properties of random variables and
stochastic sequences assuming some definition of randomness.
The~\href{https://en.wikipedia.org/wiki/Nicolas_Bourbaki}{Bourbaki
school}~considered the statement ``let us consider a random sequence''
an~\href{https://en.wikipedia.org/wiki/Abuse_of_terminology}{abuse of
language}.\href{https://en.wikipedia.org/wiki/Random_sequence\#cite_note-3}{{[}3{]}}"
The same Wikipedia explains very clearly which is the state of art of
randomness concept but, for a more interested reader, the educational
review paper by Volchan {[}4{]}, is certainly interesting and
informative.
I report from Wikipedia the current state of art for the extractions of
random sequences:~
\par\null
"Three basic paradigms for dealing with random sequences have now
emerged:\href{https://en.wikipedia.org/wiki/Random_sequence\#cite_note-10}{{[}5{]}}
\begin{itemize}
\tightlist
\item
The~\emph{frequency / measure-theoretic}~approach. This approach
started with the work of Richard von Mises and Alonzo Church. In the
1960s Per Martin-L\selectlanguage{ngerman}öf noticed that the sets coding such frequency-based
stochastic properties are a special kind
of~\href{https://en.wikipedia.org/wiki/Measure_zero}{measure
zero}~sets, and that a more general and smooth definition can be
obtained by considering all effectively measure zero sets.
\end{itemize}
\begin{itemize}
\tightlist
\item
The~\emph{complexity / compressibility}~approach. This paradigm was
championed by A. N. Kolmogorov along with contributions Levin
and~\href{https://en.wikipedia.org/wiki/Gregory_Chaitin}{Gregory
Chaitin}. For finite random sequences, Kolmogorov defined the
``randomness'' as the entropy,
i.e.~\href{https://en.wikipedia.org/wiki/Kolmogorov_complexity}{Kolmogorov
complexity}, of a string of length K of zeros and ones as the
closeness of its entropy to K, i.e. if the complexity of the string is
close to K it is very random and if the complexity is far below K, it
is not so random.
\end{itemize}
\begin{itemize}
\tightlist
\item
The~\emph{predictability}~approach. This paradigm was due
to~\href{https://en.wikipedia.org/wiki/Claus_P._Schnorr}{Claus P.
Schnorr}~and uses a slightly different definition of
constructive~\href{https://en.wikipedia.org/wiki/Martingale_(probability_theory)}{martingales}~than
martingales used in traditional probability
theory.\href{https://en.wikipedia.org/wiki/Random_sequence\#cite_note-11}{{[}11{]}}~Schnorr
showed how the existence of a selective betting strategy implied the
existence of a selection rule for a biased sub-sequence. If one only
requires a recursive martingale to succeed on a sequence instead of
constructively succeeds on a sequence, then one gets the recursively
randomness
concepts.~\href{https://en.wikipedia.org/wiki/Yongge_Wang}{Yongge
Wang}~showed\href{https://en.wikipedia.org/wiki/Random_sequence\#cite_note-12}{{[}12{]}}\href{https://en.wikipedia.org/wiki/Random_sequence\#cite_note-13}{{[}13{]}}~that
recursively randomness concept is different from Schnorr's randomness
concepts.
\end{itemize}
In most cases, theorems relating the three paradigms (often equivalence)
have been
proven.\href{https://en.wikipedia.org/wiki/Random_sequence\#cite_note-14}{{[}}7\href{https://en.wikipedia.org/wiki/Random_sequence\#cite_note-14}{{]}}"
In summary we have to grow quite complicate if we want to understand
what real randomness is.~ Once clarified what it is, we can have the
problem to assess what can be a random arrangement for an arbitrary set
of objects, say~\(\Omega\). Taking example of the algorithms
used to get a given random sequence of~ numbers from a give
distribution, we can observe that probability itself can be used to
infer the random sequence of a set from a random sequence in {[}0,1{]}
by inverting the probability~\(P\).
Random sampling is significant when the set of the domain is subdivided
into disjoint parts: a partition. Therefore
\par\null
\textbf{Definition}: Given a set (having the structure of
a~\(\sigma\)-algebra)~\(\Omega\) let a partition of
~\(\Omega\), denoted as:~
\par\null
${\mathcal P }(\Omega):=\{ x | \cup_{x \in \mathcal P} x = \Omega\, {\rm{and}}\ \forall y,z \in \Omega,\, y\cap z = \emptyset \}$
Through probability \(P\) defined over
\par\null
${\mathcal P} (\Omega) $
each element~\(x\) of the set is mapped into the closed
interval {[}0,1{]} and it is guaranteed that~
$P[\cup_{x \in \mathcal P} x] = 1$
There is not necessarily an ordering in the partition of $\Omega$ but we can arbitrarily arrange the set and associate each of its element with a subset of [0,1] of Lesbesgue measure (a.k.a. length) corresponding to its probability. By using the arbitrary order of the partition, we can at the same time build the (cumulative) probability.
By arranging or re-arranging the numbers in [0,1], we thus imply (since $P$ is bijective) a re-arrangement of the set ${\mathcal P} (\Omega)$.
{\bf Definition}: we call sequence of elements in ${\mathcal P} (\Omega)$, denoted as $\mathcal S$ a numerable set of elements in ${\mathcal P} (\Omega)$:
$${\mathcal S} := \{ x_1 \cdot \cdot \cdot\}$$
\textbf{Definition}: we call a sequence a random sequence~~if it ha no
description shorter that itself via a universal Turing machine (or
equivalently we can adopt one of the other two definition proposed above
\par\null
{\bf Theorem}: A random sequence of integers, through inverting the probability P, defines a random sequence on the set ${\mathcal P} (\Omega)$.
The prof is trivial. If there is a law that connects elements in ${\mathcal P} (\Omega)$ then through the probability $P$ a describing law is obtained also for the random sequence in [0,1], which is, therefore no more random.
So randomness of any set on which is defined a probability can be seen
as defining a random sequence in {[}0,1{]}.
\par\null
\textbf{References~}~
1.Pearl, J. (2009). Causal inference in statistics: An
overview.~\emph{Statistics Surveys},~\emph{3}(0), 96--146.
http://doi.org/10.1214/09-SS057
\par\null\par\null\par\null\par\null\par\null
\selectlanguage{english}
\FloatBarrier
\end{document}