text:
Casa de la Playa - St Martin, St Martin
Bedrooms 3 (6 guests permitted) 4 (8 guests permitted) 5 (10 guests permitted)
$3,171.43 / Nt
Baie Longue Beach, St Martin
Casa de la Playa, St Martin. When planning your next visit to St. Martin, opt for luxury and amazing amenities by booking at the Villa Casa de la Playa - St Martin. This exclusive, five-bedroom gem is situated on one of the finest beaches on St Martin and features such an astonishing number of luxuries that you may decide to make it the sole purpose of your visit!
After all, it is a fully staffed property with private chef, housekeeper and grounds team to ensure your every need is attended. Then, there are the onsite amenities that range from your private, outdoor movie theater, your enormous pool terrace with expansive infinity edge pool and array of sun beds, your rooftop patio for endless sea and star gazing, and the vast gardens and grounds beautifully manicured and maintained. Naturally, the beach just below is also going to be tremendously appealing, particularly because it is the coveted Baie Longue Beach.
Then, there are the luxuries to be enjoyed inside! Begin beneath the extensive portico that runs the length of the terrace. Here you have formal al fresco dining, casual lounges and more. They all open into the enormous great room, decorated in a flawless blend of island and Colonial styles, and using lots of natural materials to pair beautifully with the stone floors, wooden ceilings and warm palette throughout. The great room offers a piano area, large lounges, and even a pool hall. It opens to the terrace and is a delight even if you are whipping up meals or snacks.
The bedrooms are a match to the luxury, spaciousness and beauty of the rest of the property. There are five of them, and each promises amazing ocean views and private terraces. The master suite is more than 800 square feet of opulent design and décor, featuring a king bed, a massive private bath with outdoor shower and Jacuzzi, and stunning décor. There are two double suites opening to their own terraces and featuring private baths. The fifth suite is a dual single suite with pool terrace access and a spacious, private bath.
To describe the Villa Casa de la Playa - St Martin as a complete destination on its own is an understatement. It is like a private resort with a flawless location, attentive services and gorgeous design and décor, ensuring it provides an unforgettable holiday for all.
The private chef will prepare 3 meals per day. The cost of food and beverage is not included. An advanced provisioning allowance of $4000 is required. Any unused portion of the advance will be refunded.
Lot Size: 3.4 acres Interior Area Size: 15000 ft²
Alan Nov, 2022
Great villa! Amazing amount of room for everyone to have a great time. Chef Alexis Chauvreau | Private Chef Sxm and his partner, Tessa were absolutely amazing!!! The best chef that we have ever had at a villa.
Isle Blue was referred to me by a friend who had booked a trip to Turks & Caicos and were very pleased with the results. Our experience with everyone at Isle Blue was great and they were all consummate professionals. Our villa in St Martin was amazing and all of the referrals they provided worked out amazingly well. My entire family had a fantastic vacation!
John Aug, 2021
Luxurious property, on the ocean, with every amenity. Excellent staff and memorable chef/service Highly recommended
William K. May, 2019
The villa is best in class. I was amazed by the architecture and attention to detail through out. It was perfect for our party of 8 (four adult couples). The staff was excellent. They were around just the right amount of time. The chef did an amazing job. We rented a car and went on several excursions. Lotterie Farm and Pinel Island were nice. My favorite was hanging out at the Sunset Bar and watching the planes land. Overall a very memorable trip. I was amazed at how much of the island has still not recovered from Irma. Still a lot of work to be done.
Bedroom 1: Master bedroom with a king-size bed, A/C, ceiling fan, TV, ocean view, walk-in closet, access to the pool terrace, and en-suite bathroom with Jacuzzi, outdoor shower, double vanity, and WC. 2 guests maximum.
Bedroom 2: Bedroom with a king-size bed, A/C, ceiling fan, ocean view, access to the pool terrace and en-suite bathroom shower, vanity, and WC. 2 guests maximum.
Bedroom 5: Bedroom with a king-size bed, A/C, ceiling fan, ocean view, access to the pool terrace and en-suite bathroom bathtub, shower, vanity, and WC. 2 guests maximum.
Exterior Access Bedrooms: 5
Golf (Nearby)
Jacuzzi/Whirlpool
Butler/Host
Chef : 3 meals per day
The French Chef cooks three meals per day (Cost of food & drinks additional). Food & Beverage Deposit $4000 per week due 10 days prior to arrival A waiter is available during meals only.
POOL (12m x 7m x 3.50 m (depth)) Expand
2023 Jan 8 to Apr 15 January 8, 2023 - April 15, 2023 (7 night minimum) 3 4 5 $4,409.29 $4,900.00 $5,442.86 $30,865.00 $34,300.00 $38,100.00
2023 Apr 15 to Dec 17 April 15, 2023 - December 17, 2023 (5 night minimum) 3 4 5 $3,171.43 $3,523.57 $3,914.29 $22,200.00 $24,665.00 $27,400.00
2023 Dec 17 to 2024 Jan 8 December 17, 2023 - January 8, 2024 (7 night minimum) 5 $10,100.00 $70,700.00
Weekly: $30,865.00
Daily: $10,100.00
Rates based on 10 guests.
Damage Deposit: US$ 4000
Airport pickup included
Provisions and groceries are not included
SPECIAL EVENTS Expand
Plan your dream destination wedding or special Caribbean event. The villa is available for wedding receptions and special events.
Maximum guests:
Maximum guests for cocktail event: 150 guests
Maximum guests for a seated dinner event: 100 guests
Rental rates:
The villa can be rented for a 24 hour period. Rates are as follows.
High Season Event Fee: $25,000
Low Season Event Fee: $25,000
Refundable security deposit: $10,000
*When the function takes place during the guest's weekly vacation rental the event rate will be reduced to $9,000.00.
All rates are quoted in US$ and are subject to an 10% Government Tax & Service. They include the private use of the villa for a 24 hour period for the function set up, the event itself and the clean up afterwards. They also include the services of the villa staff and all utilities (electricity, water, gas).
Accommodation and villa staff gratuities are not included. It is the responsibility of the guests and their event planner to arrange to have furniture removed, stored and returned to enable the event to take place at the villa.
Contact our villa specialists to assist you in selecting the perfect wedding venue for your special occassion.
Our concierge service will be delighted to assist with planning, logistics as well as catering and wedding planner referrals.
Rent a villa for 7 nights or more with a minimum weekly rate of $8000 and receive a complimentary rental car.
A Hyundai I10 is provided with an option to upgrade the car model for an additional charge.
Complimentary vehicle delivery to the villa is included.
Gas, taxes and insurance are excluded. Guest is responsible for returning the car to the airport office of the rental car company at the end of the stay or paying a pick-up fee. Upon villa confirmation, a redeemable promo code will be sent to the guest.
Blackout Dates: December 18, 2022 - January 8, 2023
Offer ends: January 31, 2023
Guest is responsible for gas, taxes and insurance | Offer includes only the base rate of rental car | Upgrades available for an additional charge | Offer cannot be combined with other offers | Offer based on availability | Minimum night stay required | Non-transferrable | No cash value | Guest is responsible for price difference on upgraded models | Guest is liable for damages, theft or injury resulting from use of rental car | Rental car must be reserved and coordinated by the concierge | Guest is responsible for ensuring adequate insurance coverage
Blue Beach
Blue Beach St Martin
"we really liked the villa. Found it to be clean, well stocked, etc."
Rosanna G
Filao


Saturday's Adelaide-Melbourne game in the Australian Baseball League produced four ejections of Bite and Aces personnel as HP Umpire Stewart Howe ejected Adelaide RF Michael Gettys and Pitching Coach Luke Prokopec in the 5th inning (both balls/strikes); Bite Manager Chris Adamson (HBP no-call) and Aces catcher Jake Romanski (Unsportsmanlike/NEC toward opposing dugout) in the 7th—all on separate incidents.
With one out and one on (R2) in the top of the 5th, Gettys took a 2-1 pitch from Aces pitcher Dushan Ruzic for a called second strike before subsequently flying out on a subsequent pitch; Gettys was ejected after returning from first base following the fly-out. Replays indicate the pitch was located near the outer edge of home plate (QOCU). At the time of Gettys' ejection, Adelaide was leading, 3-1.
With two out in the bottom of the 5th, Prokopec was ejected during a mound visit with pitcher Michael Gahan following a single by Aces batter Allan de San Miguel. At the time of Prokopec's ejection, Adelaide was leading, 3-1.
With none out and none on in the top of the 7th, Bite batter Stefan Welch took a 0-0 pitch from Aces pitcher Harrison Cooney for a called ball, having initially shown bunt. Replays indicate batter Welch did not attempt to strike the pitch, but do not conclusively indicate whether the batter was struck by the pitch; Manager Adamson was ejected arguing for a HBP call. At the time of Adamson's ejection, the game was tied, 4-4.
With one out and one on (R2), Bite batter Landon Hernandez hit a fly ball to Aces right fielder Garrison Schwartz, who caught the batted ball and threw to third base as Bite baserunner R2 Curtis Mead attempted to tag-up and advance from second, Schwartz's throw bouncing out of play and awarding Mead home plate. During the ensuing dead ball, Aces catcher Romanski became engaged with the Bite's third base dugout, after which Romanski was ejected. At the time of Romanski's ejection, Adelaide was leading, 5-4. Melbourne ultimately won the contest, 6-5.
Alternate Link (EJ-1): Gettys is ejected following his air out in the 5th inning (ABLTV, 1:32:17).
Alternate Link (EJ-2): Howe ejects Prokopec after breaking up mound visit in 5th (ABLTV, 1:45:24).
Alternate Link (EJ-3): Adamson is tossed when crew consultation doesn't go his way (ABLTV, 2:31:29).
Alternate Link (EJ-4): Romanski yells into opposing dugout and gets ejected (ABLTV, 2:35:04).


text:
\section{\@startsection {section}{1}{\z@}{-2.0ex plus
    -0.5ex minus -.2ex}{1.5ex plus 0.3ex minus .2ex}{\large\bf\raggedright}}
\makeatother
\def{}

\usepackage{latexsym}
\usepackage{graphicx}
\usepackage{amsmath}
\sloppy\lineskip=0pt

\def\,{\mskip 3mu} \def\>{\mskip 4mu plus 2mu minus 4mu} \def\;{\mskip 5mu plus 5mu} \def\!{\mskip-3mu}
\def\thinmuskip= 3mu plus 0mu minus 2mu \medmuskip=  4mu plus 2mu minus 2mu \thickmuskip=5mu plus 5mu minus 2mu{\thinmuskip= 3mu plus 0mu minus 2mu \medmuskip=  4mu plus 2mu minus 2mu \thickmuskip=5mu plus 5mu minus 2mu}
\def\thinmuskip= 0mu                    \medmuskip=  1mu plus 1mu minus 1mu \thickmuskip=2mu plus 3mu minus 1mu{\thinmuskip= 0mu                    \medmuskip=  1mu plus 1mu minus 1mu \thickmuskip=2mu plus 3mu minus 1mu}
\thinmuskip= 0mu                    \medmuskip=  1mu plus 1mu minus 1mu \thickmuskip=2mu plus 3mu minus 1mu
\def{}
\def\eqvsp\dispmuskip\begin{equation}}    \def\eeq{\eqvsp\end{equation}\textmuskip{\thinmuskip= 3mu plus 0mu minus 2mu \medmuskip=  4mu plus 2mu minus 2mu \thickmuskip=5mu plus 5mu minus 2mu\begin{equation}}    \def\eeq{\end{equation}\thinmuskip= 0mu                    \medmuskip=  1mu plus 1mu minus 1mu \thickmuskip=2mu plus 3mu minus 1mu}
\def\eqvsp\dispmuskip\begin{displaymath}}\def\eeqn{\eqvsp\end{displaymath}\textmuskip{\thinmuskip= 3mu plus 0mu minus 2mu \medmuskip=  4mu plus 2mu minus 2mu \thickmuskip=5mu plus 5mu minus 2mu\begin{displaymath}}\def\eeqn{\end{displaymath}\thinmuskip= 0mu                    \medmuskip=  1mu plus 1mu minus 1mu \thickmuskip=2mu plus 3mu minus 1mu}
\def\eqvsp\dispmuskip\begin{eqnarray}}    \def\eqa{\eqvsp\end{eqnarray}\textmuskip{\thinmuskip= 3mu plus 0mu minus 2mu \medmuskip=  4mu plus 2mu minus 2mu \thickmuskip=5mu plus 5mu minus 2mu\begin{eqnarray}}    \def\eqa{\end{eqnarray}\thinmuskip= 0mu                    \medmuskip=  1mu plus 1mu minus 1mu \thickmuskip=2mu plus 3mu minus 1mu}
\def\eqvsp\dispmuskip\begin{eqnarray*}}  \def\eqan{\eqvsp\end{eqnarray*}\textmuskip{\thinmuskip= 3mu plus 0mu minus 2mu \medmuskip=  4mu plus 2mu minus 2mu \thickmuskip=5mu plus 5mu minus 2mu\begin{eqnarray*}}  \def\eqan{\end{eqnarray*}\thinmuskip= 0mu                    \medmuskip=  1mu plus 1mu minus 1mu \thickmuskip=2mu plus 3mu minus 1mu}
\def\bmat#1{\left[ \begin{array}{#1}}
\def\end{array} \right]{\end{array} \right]}

\def\vspace{1.3ex plus 0.5ex minus 0.5ex}\noindent{\vspace{1.3ex plus 0.5ex minus 0.5ex}\noindent}
\newenvironment{keywords}{\centerline{\bf\small
Keywords}\begin{quote}\small}{\par\end{quote}\vskip 1ex}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{definition}[theorem]{Definition}
\newenvironment{proof}{\paradot{Proof}}{\hspace*{\fill}$\Box\quad$\\\vskip 1ex}
\def\paradot#1{\vspace{1.3ex plus 0.5ex minus 0.5ex}\noindent{\bfseries\boldmath{#1.}}}
\def\paranodot#1{\vspace{1.3ex plus 0.5ex minus 0.5ex}\noindent{\bfseries\boldmath{#1}}}
\def\toinfty#1{\stackrel{#1\to\infty}{\longrightarrow}}
\def\varepsilon{\varepsilon}
\def\epstr{\epsilon}
\def\hspace{-1em}{\hspace{-1em}}
\def\hspace*{\fill}$\Box\quad$\\{\hspace*{\fill}$\Box\quad$\\}
\def\fr#1#2{{\textstyle{#1\over#2}}}
\def\req#1{(\ref{#1})}
\defI\!\!R{I\!\!R}
\defI\!\!N{I\!\!N}
\defI\!\!B{I\!\!B}
\defZ\!\!\!Z{Z\!\!\!Z}
\def\qmbox#1{{\quad\mbox{#1}\quad}}
\def\e{{\rm e}}
\def\{0,1\}{\{0,1\}}
\def\vec{\boldsymbol}
\def\es{\phi}
\def\ell{\ell}
\def{\log_2}{{\log_2}}
\def\alpha{\alpha}
\def\kappa{\kappa}
\def\overline{\overline}
\def\bino#1#2{{\textstyle\binom{#1}{#2}}}
\def\doteq{\doteq}

\begin{document}

\title{\bf\huge\hrule height5pt \vskip 4mm
Equivalence of Probabilistic Tournament \\
and Polynomial Ranking Selection%
\vskip 4mm \hrule height2pt}

\author{
{\bf Kassel Hingee} \ -- \
\normalsize Department of Mathematics @
 Australian National University \ \ \ \ \ \ -- \
\texttt{hinkass@gmail.com}
\and
{\bf Marcus Hutter} --
\normalsize RSISE$\,$@$\,$ANU and SML$\,$@$\,$NICTA,
Canberra, ACT, 0200, Australia --
\texttt{marcus@hutter1.net}
}
\date{March 2008}

\maketitle

\begin{abstract}
\bf Crucial to an Evolutionary Algorithm's performance is its selection
scheme. We mathematically investigate the relation between
polynomial rank and probabilistic tournament methods which are
(respectively) generalisations of the popular linear ranking and
tournament selection schemes. We show that every probabilistic
tournament is equivalent to a unique polynomial rank scheme. In
fact, we derived explicit operators for translating between these
two types of selection. Of particular importance is that most linear
and most practical quadratic rank schemes are probabilistic
tournaments.
\end{abstract}

\section{Introduction}

\paradot{Evolutionary algorithms}
Evolutionary Algorithms (EAs) are probabilistic search algorithms
based on evolution \cite{Goldberg:89,Eiben:03}. They operate by
exploiting the information contained in a population  of possible
solutions (via similarities between individuals). The aim is to find
an individual that maximises (or minimises) an objective function,
which maps from individuals to the real line.
The population is transformed by first selecting individuals.
Mutation and/or recombination is then used to either replace a few
individuals from the population or create an entirely new
population.

\paradot{Standard selection methods}
The most prevalent methods for selecting individuals are
proportionate, linear rank, tournament, and truncation
\cite{Hutter:06fuo}. In proportionate selection individuals are
chosen with a probability proportional to their fitness (the value of
the objective function evaluated at the individual) \cite{Back1994}. A
common method to gain more control over selection pressure, is to scale the
fitness values before the selection is made \cite{Back1994}. Linear
ranking proceeds by ordering the population according to their
fitness. The chance that an individual is selected is then a linear
function of its (unique) rank \cite{Back1994}. Tournament selection
creates a tournament by randomly choosing $t$ individuals, the best
individual in the tournament is then selected. For truncation
selection the $k$ fittest individuals have uniform probability of
selection, while the remainder have zero chance of being selected.

The choice of selection scheme is crucial to algorithm performance.
If the selection pressure is too high then diversity of the
population decreases rapidly and the algorithm converges prematurely
to local optima or worse. With too little pressure there is not
enough push toward better individuals and the population takes too
long to converge. Many methods to choose or adapt the selection
pressure or avoid the problem otherwise have been invented (see
\cite{Hutter:06fuo} for some references). A particularly simple one
is fitness uniform selection, which uniformly selects a fitness
value, and then the individual with fitness closest to this value.

It is quite profitable to study selection schemes due to their
generality. They depend only on the set of fitness values and not on
the rest of the algorithm. Hence their behaviour can be studied in
isolation and the results applied to any evolutionary algorithm.
In this paper we introduce and study generalizations of rank and
tournament selection (both actually only depend on the rank and
not the absolute fitness value itself).

\paradot{Polynomial rank selection}
Linear ranking has a small range of selection pressures (from \cite{Back1994}, for a population of $n$ individuals the probability that the fittest individual is selected must be between $1/n$ and $2/n$),
but it has the flexibility of a real-valued parameter that can vary continuously (the slope
of the linear function). Ranking schemes
with high selection pressures, such as when the probability of
selection is an exponential function of the rank, have occasionally been
used \cite{Wieczorek2002}. It is natural then to generalise from linear to
polynomial functions to cover the instances where medium pressure is
required. Hence the probability of an individual with rank $k$ being
selected with a polynomial rank scheme of degree $d$ is:
\eqvsp\dispmuskip\begin{equation}}    \def\eeq{\eqvsp\end{equation}\textmuskip\label{eqPoly1}
  P(I=k)=\sum_{l=1}^{d+1} a_l k^{l-1}
\eeq
where $a_l\in I\!\!R$ are parameters defined by the algorithm
designer.
For simplicity we assume that selection is performed with
replacement and each individual has unique rank, however our results
still hold when there are ties in the rank. The only restriction on
the $a_k$ is that they must produce a proper probability
distribution, i.e.\ for a population of $n$ individuals: $P(I=k)\geq
0$ for all $k=1,2,...,n$ and $\sum_{k=1}^n P(I=k)=1$. Hence, while
the population is ordered, the schemes may favour low ranks, high
ranks or neither, depending on the choice of the $(a_l)$.

This selection method encompasses the low pressures of linear
schemes ($a_3=...=a_{d+1}=0$) and can give good approximations of
the high pressure exponential cases (via Taylor polynomials).
Furthermore the wealth of general knowledge about polynomials means
that while it has numerous parameters (coefficients of the
monomials), it is also easy to predict their impact.

\paradot{Probabilistic tournament selection}
Tournament selection has a large range \cite{Back1994}, but a
discrete parameter, leaving the possible selection pressures
somewhat restricted. This can be overcome by selecting
probabilistically from the tournament, rather than always choosing
the best in the tournament. However the extra parameters required
are not easy to understand. Their precise effect on the behaviour is
not at all obvious. Probabilistic Tournament selection still only
sorts $t\ll n$ individuals, making it much faster than any ranking
scheme.

Let $i_s$ be the (rank of the) individual in position
$s\in\{1,...,t\}$ of the rank-ordered tournament. We call $s$ the
\emph{seed} of $i$. Let $P(I_s=k)$ be the probability that seed $s$
has rank $k$. In any given tournament, the probability that the seed
$s$ individual is chosen will be a user defined constant $\alpha_s$.
Then the probability of an individual $k$ being selected through a
size $t$ probabilistic tournament is:
\eqvsp\dispmuskip\begin{equation}}    \def\eeq{\eqvsp\end{equation}\textmuskip\label{eqTourn1}
  P(I=k)=\sum_{s=1}^t \alpha_s P(I_s=k)
\eeq
Standard (deterministic) tournament always selects the individual of
highest rank in the tournament, i.e.\ $\alpha_1=1$ and $\alpha_2=..=\alpha_t=0$.

To ensure that choosing a winner from the tournament makes sense,
the $\alpha_s$ must satisfy the probability constraints $\alpha_s\geq
0\,\forall s$ and $\sum_{s=1}^t \alpha_s =1$. We assume that the
tournament is created by random selection \emph{with} replacement
and for now that each individual in the population has a unique
fitness. This defines $P(I_s=k)$ (Section \ref{secPST}). Note that
even if every individual in the population is unique, it is possible
for it to be repeated in the tournament.

\paradot{Previous work on the relation between rank and tournament selection}
In this paper we investigate the equivalence between the generalised
schemes \req{eqPoly1} and \req{eqTourn1} with the aim of providing a
scheme that combines the superior understanding of polynomial rank
with the speed of probabilistic tournament.

B\"{a}ck \cite{Back1994} found that an individual's chance of
selection in deterministic tournament selection is a polynomial,
hence each is equivalent to a polynomial rank selection method.
Wieczorek and Czech \cite{Wieczorek2002}, and Blickle
\cite{Blickle1995CA} arrived at the same conclusion using a
different method. So while the name `polynomial rank selection' is
new, its concept is fairly old.

The study of probabilistic tournaments isn't new either: Hutter
\cite[p.11]{Hutter:91cfs} proved that every size $2$ probabilistic
tournament is a linear rank scheme, and Goldberg \cite{Goldberg:91}
did the same but only for a continuous population.
Fogel \cite{Fogel:1988} applied to the traveling salesman problem, a
variation wherein each individual underwent numerous t=2
tournaments. The probability of winning each tournament was
dependent on the fitness of the individuals involved and the
individuals selected were those with the highest number of wins.

\paradot{Contents: Equivalence of polynomial rank and probabilistic tournament selection}
We extend these results by finding that every $t$ sized
probabilistic tournament is equivalent to a polynomial rank scheme
with a polynomial degree of $d=t-1$ or less (Section \ref{secPST}).
We continue on to show that the equivalence is unique (Section
\ref{secUnique}), and give an explicit expression for the inverse
map (Section \ref{secPtoT}). This allows the establishment of simple
criteria for polynomial rank schemes that are probabilistic
tournaments (Section \ref{secPisT}). Unfortunately not every
possible polynomial rank scheme satisfies the criteria, but most
(and in the limit of an infinite population, all) linear and most
``interesting'' quadratic ones are equivalent to probabilistic
tournaments. This is good enough for all practical purposes, if it
generalises to higher order polynomials.

\paradot{Notation}
Throughout the paper we use the following notation. If not otherwise
indicated, an index has the full range as defined in this table.

\begin{tabbing}
\hspace{2cm}         \= \hspace{11cm} \= \kill
{\bf Symbol }        \> {\bf Explanation}   \\[0.5ex]
$\delta_{ij}$        \> Kronecker symbol \\
                     \> ($\delta_{ij}=1$ for $i=j$ and $\delta_{ij}=0$ for $i\neq j$) \\[0.5ex]
$n$                  \> Number of individuals in the population\\
$i,j,k$              \> Rank (unique label) of individuals $\in\{1,...,n\}$ \\[0.5ex]
$\iota,\kappa$       \> Rank indices that only run from $1,...,t$\\
$p,q,r,s$            \> Seed index $\in\{1,...,t\}$\\
$I_s$                \> Rank of the individual with seed $s$\\
$I$                  \> Rank of the individual selected\\
$\pi_i=P(I=i)$       \> Probability that $i$ is selected \\[0.5ex]
$l$                  \> Polynomial coefficients index $\in\{1,...,d+1\}$\\[0.5ex]
$a_l$                \> Coefficients of $x^{l-1}$ for the polynomial\\
$\alpha_1, \alpha_2,...,\alpha_t$ \> Tournament selection coefficients\\
$x_i, \vec x, (x_i)$   \> Vector $\vec x=(x_i)=(x_1,...,x_t)$ \\[0.5ex]
$\Delta_m$           \> $m-1$ dimensional probability simplex \\[0.5ex]
\end{tabbing}

\section{Probability of Selection via a Tournament}\label{secPST}

In this section we find the probability of an individual being
successful (the winner) via tournament selection. This will provide
a formula for an equivalent ranking selection scheme. It is
sufficient to consider just one selection event in isolation, since
we consider selection with replacement.

We assume a population ${\cal P}$ consisting of $n$ individuals
$c_1,...,c_n$ with fitness $f_1,...,f_n$. Without loss of generality
we assume that they are ordered, i.e.\ $f(i)\geq f(j)$ for all $j\leq
i$. For now we also assume that all fitness values are different,
hence individual $c_i$ has rank $i$. The rank is all we need in the
following, and we will say ``individual $i$'', meaning ``individual
$c_i$''.

\begin{definition}[polynomial rank selection]\it
Polynomial $\vec a$-ranking selects individual $c_k$ from population
$\cal P$ with probability $P(I=k)=\sum_{l=1}^{d+1}a_l k^{l-1}$
\end{definition}

\begin{definition}[probabilistic tournament selection]\it
A probabilistic $\vec\alpha$-tournament selects $t$ individuals from
population $\cal P$ uniformly at random with replacement. Let
$c_{I_s}$ be the individual of rank $s$ in the tournament, called
seed $s$ (while it has rank $I_s$ in the population). Finally the
seed $s$ individual, $I_s$, is chosen with probability $\alpha_s=P(I=I_s)$
as the winner $I$.
\end{definition}

\begin{theorem}[tournament=polynomial]\label{thmPST}\it
Probabilistic $\vec\alpha$-tournament selection coincides with polynomial
$\vec a$-ranking (for $d=t-1$ and suitable $\vec a$).
\end{theorem}

\begin{proof}
We derive an explicit expression for the probability $\pi_k$ that
the tournament winner has rank $k$. Any seed $s$ may have rank $k$
($I_s=k$) and may be the winner ($I=I_s$), hence
\eqvsp\dispmuskip\begin{displaymath}}\def\eeqn{\eqvsp\end{displaymath}\textmuskip
  \pi_k \;\equiv\; P(I=k) \\
  \;=\; \sum_{s=1}^t P(I=I_s)P(I_s=k) \;=\; \req{eqTourn1}
\eeqn
where we have exploited that by definition the probability that $I=I_s$ is
independent of the rank $I_s=k$. $P(I_s=k)$ is the probability that
seed $s$ has rank $k$. It is difficult to formally derive an
expression for $P(I_s=k)$, but we can easily get it by considering
distribution functions. The probability of an individual selected
into the tournament having a particular rank is $1/n$, hence having
rank equal to or less than $k$ is $k/n$ and larger than $k$ is $1-k/n$.
Further, $I_r\leq k \wedge I_{r+1}>k$ if and only if $r$ seeds have
rank $\leq k$ and $t-r$ seeds have rank $>k$, hence
\eqvsp\dispmuskip\begin{displaymath}}\def\eeqn{\eqvsp\end{displaymath}\textmuskip
  P(I_r \leq k \wedge I_{r+1}>k) \;=\;
  \bino{t}{r} (\fr{k}{n})^r(1\!-\!\fr{k}{n})^{t-r}
\eeqn
since there are $\bino{t}{r}$ ways of choosing $r$ individuals with
rank $\leq k$ from $t$ individuals. The above expression is a
polynomial in $k$ of degree $t$. Together with
\eqvsp\dispmuskip\begin{displaymath}}\def\eeqn{\eqvsp\end{displaymath}\textmuskip
  P(I_s\leq k) \;=\; \sum_{r=s}^t P(I_r \leq k \wedge I_{r+1}>k),
\eeqn
we get the explicit expression
\eqvsp\dispmuskip\begin{eqnarray}}    \def\eqa{\eqvsp\end{eqnarray}\textmuskip\label{eqPIs}
  & & P(I_s=k) \;=\; P(I_s\leq k)-P(I_s\leq k-1)
\\ \nonumber
  & & =\; \sum_{r=s}^t \bino{t}{r}
           \big[(\fr{k}{n})^r(1\!-\!\fr{k}{n})^{t-r}
              - (\fr{k-1}{n})^r(1\!-\!\fr{k-1}{n})^{t-r}\big]
\eqa
Using the binomial theorem to find the $k^t$ and $k^{t-1}$
coefficients in the square brackets above reveals that the former
coefficients cancel out while the latter do not. This implies that $P(I_s=k)$
is a polynomial in $k$ of degree (at most) $t-1$, and thus the weighted average \req{eqTourn1} is as well.
Summing \req{eqTourn1} over the population yields $\sum_{k=1}^n
P(I=k)=1$, as it should, since the tournament coefficients are such
that some individual is always chosen.
Consequently, every tournament is a polynomial rank scheme of degree
at most $t-1$ (one can choose $\vec\alpha$ such that it is of lower
degree).
\end{proof}

\paradot{Examples}
Expression \req{eqPIs} can be rewritten as
\eqvsp\dispmuskip\begin{displaymath}}\def\eeqn{\eqvsp\end{displaymath}\textmuskip
  P(I_s=k) \;=\; \sum_{r=0}^{s-1} \bino{t}{r}
    \big[(\fr{k-1}{n})^r(1\!-\!\fr{k-1}{n})^{t-r}
       - (\fr{k}{n})^r(1\!-\!\fr{k}{n})^{t-r} \big]
\eeqn
which will be convenient in the following examples.
Standard tournament always selects $I_1$ ($\alpha_1=1$), hence \cite{Back1994}
\eqvsp\dispmuskip\begin{displaymath}}\def\eeqn{\eqvsp\end{displaymath}\textmuskip
  P(I=k) \;=\; P(I_1=k) \;=\; (1-\fr{k-1}{n})^t - (1-\fr{k}{n})^t
\eeqn
See Figure \ref{figtourndet}.
For $t=1$ there is no selection pressure, $P(I=k)=\fr1n$.
For $t=2$ we get
\eqvsp\dispmuskip\begin{displaymath}}\def\eeqn{\eqvsp\end{displaymath}\textmuskip
  P(I_1=k) = \fr{2n-2k+1}{n^2} \qmbox{and}
  P(I_2=k) = \fr{2k-1}{n^2}
\eeqn
Hence probabilistic tournaments of size 2 lead to
linear ranking \cite{Hutter:91cfs}
\eqvsp\dispmuskip\begin{eqnarray}}    \def\eqa{\eqvsp\end{eqnarray}\textmuskip\nonumber
  & & \hspace{-1em}\nq P(I\!=\!k) \;=\; \alpha_1 P(I_1\!=\!k)+\alpha_2 P(I_2\!=\!k) \;=\; a_1+a_2 k,
\\ \label{PIkt2}
  & & \hspace{-1em}\nq a_1=\fr1{n^2}[(2n+1)\alpha_1-\alpha_2], \qquad a_2 \;=\; \fr2{n^2}(\alpha_2-\alpha_1)
\eqa

\begin{figure}
\setlength{\unitlength}{1mm}
\begin{picture}(89,78)(-4,-1)
\put(0,0){\includegraphics[width=85mm]{tourndet}}
\put(-4,15.5){\large$t=1$}
\put(6.5,20){\large$t=2$}
\put(-4,31.5){\large$t=3$}
\put(-4,48){\large$t=5$}
\put(8,65){\large$t=8$}
\put(40,-1){\Large$x$\normalsize}
\end{picture}
\caption{\label{figtourndet}[tournament probabilities for large $n$] \it
Probability density $nP(I_1=xn)$ that the tournament winner has rank $xn$,
for tournament size $t=1,2,3,5,8$.}
\end{figure}

\paradot{Remark}
More interesting is actually the converse, replacing rank selections
by equivalent efficient tournaments. Before we can answer this, we
need to break down \req{eqPIs} into a product of simple regular
matrices.

\section{The Map from Tournament to Polynomial is Unique}\label{secUnique}

The next natural question is whether different tournament bias
$\vec\alpha$ implies different selection probability. It seems plausible
that the maps from tournaments $\vec\alpha$ to rank probabilities $\vec\pi$
and to polynomial coefficients $\vec a$ are injective, but the proof
is fairly involved. The good news is that construction in the proof
allows us to find a closed form expression for the desired inverse.
Let $\Delta_m=\{\vec x\inI\!\!R^m:x_i\geq 0\,\forall i,\sum_{i=1}^m
x_i=1\}$ be the $m-1$ dimensional probability simplex, i.e.\
$\vec\pi\in\Delta_n$ and $\vec\alpha\in\Delta_t$.

\begin{theorem}[tournament$\rightarrow$polynomial]\label{thmUnique}\it
The function $R:\Delta_t\to\Delta_n$ in \req{eqTourn1}, mapping
tournament probabilities $\vec\alpha$ to rank probabilities $\vec\pi$, is
total, linear, and injective:
\eqvsp\dispmuskip\begin{displaymath}}\def\eeqn{\eqvsp\end{displaymath}\textmuskip
  \pi_k=P(I=k)=\sum_{s=1}^t R_k^s\alpha_s, \qmbox{i.e.} \vec\pi=R\vec\alpha,
\eeqn
where $R_k^s=P(I_s=k)$ is defined in \req{eqPIs}. Matrix $R$ can
also be written as a product $R=\overline D P F C D = V N F C D = V T$
with matrices $\overline D$, $P$, $F$, $C$, $D$, $V$, and $N$ defined in
\req{defVinv}, \req{defP}, \req{defF}, \req{defC}, \req{defV},
\req{defQ}, and \req{defN}.
Similarly, the function $T:\Delta_t\toI\!\!R^t$, mapping $\vec\alpha$ to
polynomial coefficients $\vec a$, is unique, linear and injective:
\eqvsp\dispmuskip\begin{displaymath}}\def\eeqn{\eqvsp\end{displaymath}\textmuskip
  a_l=\sum_{s=1}^t T_l^s\alpha_s, \qmbox{i.e.} \vec a=T\vec\alpha,
\eeqn
where matrix $T = N F C D$.
\end{theorem}

\begin{proof}
Tournament always selects one individual from $\cal P$ as the
winner, hence $R\vec\alpha\in\Delta_n$ for every $\vec\alpha\in\Delta_t$. See
the proof of Theorem \ref{thmPST} for how to prove this formally.

\paradot{Matrices $H$ and $G$}
We now prove injectivity. With
\eqvsp\dispmuskip\begin{displaymath}}\def\eeqn{\eqvsp\end{displaymath}\textmuskip
  H_k^r := (\fr{k}{n})^r(1-\fr{k}{n})^{t-r}  \qmbox{and}
  G_k^r := \bino{t}{r}(H_k^r-H_{k-1}^r)
\eeqn
we can write \req{eqPIs} as
\eqvsp\dispmuskip\begin{equation}}    \def\eeq{\eqvsp\end{equation}\textmuskip\label{eqRsumG}
  R_k^s \;\equiv\; P(I_s=k) \;=\; \sum_{r=s}^t G_k^r
\eeq

\paradot{Einstein notation}
Einstein's sum convention will be convenient in the following
argument: When an index occurs repeatedly in the multiplication of
two objects, a sum over the index over its full range is implicitly
understood, e.g.\ $G_k^r D_r^s$ means $\sum_{r=1}^t G_k^r D_r^s$.

\paradot{Lower-triangular matrix $D$}
The lower-triangular matrix
\eqvsp\dispmuskip\begin{equation}}    \def\eeq{\eqvsp\end{equation}\textmuskip\label{defV}
  D_r^s:=\left\{ \begin{array}{rcl} 1 & \mbox{if} & s\leq r\\
                0 & \mbox{if} & s>r \end{array} \right.
\eeq
has the property that $\sum_{r=1}^t G_k^r D_r^s = \sum_{r=s}^t
G_k^r$. Using Einstein's sum convention this allows us to rewrite
\req{eqRsumG} as
\eqvsp\dispmuskip\begin{displaymath}}\def\eeqn{\eqvsp\end{displaymath}\textmuskip
  R_k^s = G_k^r D_r^s
\eeqn
i.e.\ as a product of an $n\times t$ matrix $G$ with a $t\times t$
matrix $D$.

\paradot{Inverse of $D$}
The ``inverse'' of $D$ is:
\eqvsp\dispmuskip\begin{equation}}    \def\eeq{\eqvsp\end{equation}\textmuskip\label{defVinv}
  \overline D_k^i
  \;:=\; \left\{ \begin{array}{rl}
   1 & \mbox{if } k=i\\
  -1 & \mbox{if } i=k-1\\
   0 &\mbox{otherwise}\end{array}
  \right\} \;=\; \delta_{k,i}-\delta_{k-1,i}
\eeq
This is a matrix with $1$ on the primary diagonal; $-1$ on the
diagonal that is below the primary diagonal; and $0$ otherwise.

\paradot{Decomposing $G$}
$G_k^r$ itself can actually be decomposed into $\overline D_k^i$ and
$H_i^q$ and a pure diagonal matrix
\eqvsp\dispmuskip\begin{equation}}    \def\eeq{\eqvsp\end{equation}\textmuskip\label{defC}
  C_q^r = \bino{t}{q}\delta_{q,r}
\eeq
comprised of the binomial coefficients:
\eqvsp\dispmuskip\begin{displaymath}}\def\eeqn{\eqvsp\end{displaymath}\textmuskip
  G_k^r \;=\; (H_k^q-H_{k-1}^q)C_q^r
        \;=\; \overline D_k^i H_i^q C_q^r
\eeqn
(note that $\overline D$ is the inverse of an $n\times n$ sized D matrix
here).

\paradot{Decomposing $H$ into $P$ and $F$}
We can decompose $H_i^q$ further be using the binomial identity:
\eqvsp\dispmuskip\begin{eqnarray*}}  \def\eqan{\eqvsp\end{eqnarray*}\textmuskip
  H_i^q &=& (\fr{i}{n})^q(1-\fr{i}{n})^{t-q} \\
  &=& \textstyle (\fr{i}{n})^q\sum_{s=1}^{t-q}\bino{t-q}{s}(\fr{-i}{n})^{t-q-s} \\
  &=& \textstyle \sum_{s=1}^{t-q}(-)^{t-q-s}\bino{t-q}{s}(\fr{i}{n})^{t-s}\\
  &=& \textstyle \sum_{p=q}^t(-)^{p-q}\bino{t-q}{t-p}(\fr{i}{n})^p
\eqan
So $H_i^q=P_i^p F_p^q$, where $P$ is a matrix
of monomials:
\eqvsp\dispmuskip\begin{equation}}    \def\eeq{\eqvsp\end{equation}\textmuskip\label{defP}
  P_i^p:=(\fr{i}{n})^p,
\eeq
and $F$ is a lower-triangular matrix composed of various binomials:
\eqvsp\dispmuskip\begin{equation}}    \def\eeq{\eqvsp\end{equation}\textmuskip\label{defF}
  F_p^q:=\left\{ \begin{array}{cl}
   (-)^{p-q}\bino{t-q}{t-p} & \mbox{if } q\leq p \\
                0 & \mbox{otherwise} \end{array}\right.
\eeq
\paradot{Matrices $N$, $V$, and $R$}
Putting everything together we have
\eqvsp\dispmuskip\begin{displaymath}}\def\eeqn{\eqvsp\end{displaymath}\textmuskip
  R_k^s \;=\; \overline D_k^i P_i^p F_p^q C_q^r D_r^s
\eeqn
The (linear) map $R_k^s$ is a polynomial in $k$ of degree (at most)
$t-1$. We can find its coefficients by rewriting
\eqvsp\dispmuskip\begin{eqnarray}}    \def\eqa{\eqvsp\end{eqnarray}\textmuskip\label{VPeqQN}
  \overline D_k^i P_i^p
  &=& P_k^p-P_{k-1}^p
  \;=\; (\fr{k}{n})^p-(\fr{k-1}{n})^p
\\ \nonumber
  &=& \sum_{l=1}^p k^{l-1}(-)^{p-l}\bino{p}{l-1}(\fr1n)^p
  \;=\; V_k^l N_l^p
\eqa
where
\eqvsp\dispmuskip\begin{eqnarray}}    \def\eqa{\eqvsp\end{eqnarray}\textmuskip\label{defQ}
  V_k^l &:=& k^{l-1}, \qmbox{and}
\\ \label{defN}
N_l^p &:=& \left\{\begin{array} {cr} (-)^{p-l}\bino{p}{l-1}(\fr1n)^p & l\leq p\\
0 & \mbox{otherwise}\end{array} \right.
\eqa
Hence we get the alternative representation
\eqvsp\dispmuskip\begin{equation}}    \def\eeq{\eqvsp\end{equation}\textmuskip\label{eqRalt}
  \pi_k=R_k^s\alpha_s \;=\; V_k^l N_l^p F_p^q C_q^r D_r^s\alpha_s
\eeq

\paradot{Injective}
Matrices $D$, $\overline D$, and $F$ are lower-triangular matrices with
1 in the diagonal, and hence are invertible (thus injective). $C$ is diagonal and $N$
upper triangular, both nowhere zero on the diagonal, hence
invertible too. The first $t$ rows of $V$ map from a set of $t$
coefficients $\vec b$ to the polynomial $p(x)=\sum_{l=1}^t b_l
x^{l-1}$ evaluated at $x=1,2,3,...,t$. A degree $t-1$ polynomial
like $p$ is uniquely determined by $t$ image points
(see Appendix),
hence $V$ is injective. Similarly for P or exploit $P_k^l=k
V_k^l(\fr1n)^l$ (no summation). This proves that $R$ is injective.

\paradot{Matrix $T$}
Combining the map from $\vec a$ to $\vec\pi$
\eqvsp\dispmuskip\begin{displaymath}}\def\eeqn{\eqvsp\end{displaymath}\textmuskip
  \pi_k \equiv P(I=k)
  = \sum_{l=1}^t a_l k^{l-1}
  = V_k^l a_l
  \qmbox{i.e.} \vec\pi=V\vec a,
\eeqn
with $a_l=T_l^s\alpha_s$ we get
\eqvsp\dispmuskip\begin{displaymath}}\def\eeqn{\eqvsp\end{displaymath}\textmuskip
  \pi_k = V_k^l T_l^s\alpha_s
\eeqn
Comparing this with \req{eqRalt} and using injectivity of $V$ we see
that
\eqvsp\dispmuskip\begin{equation}}    \def\eeq{\eqvsp\end{equation}\textmuskip\label{defT}
  T_l^s \;=\; N_l^p F_p^q C_q^r D_r^s
\eeq
which is injective, since $N$, $F$, $C$, and $D$ are invertible.
\end{proof}

\paradot{Discussion}
Given a Polynomial Rank scheme it is possible and easy (using
computer software) to find if it is equivalent to a probabilistic
tournament (and get the corresponding parameters) by applying the
inverse of $T$ to $\vec a$. If the output satisfies the probability
requirements $\vec\alpha\in\Delta_t$, then it is indeed a probabilistic
tournament.

\section{Map from Polynomial Ranking to Tournaments}\label{secPtoT}

We now derive explicit expressions for the really interesting
converse of map $T$, which allows replacement of inefficient
rank selections by equivalent efficient tournaments.
From the last section we know that the inverse exists.

\begin{theorem}[polynomial$\rightarrow$tournament]\label{thmTtoP}\it
The function $\overline T:I\!\!R^t\toI\!\!R^t$,
mapping polynomial coefficients $\vec a$ to
tournament parameters $\vec\alpha$ is linear
\eqvsp\dispmuskip\begin{displaymath}}\def\eeqn{\eqvsp\end{displaymath}\textmuskip
  \alpha_s=\sum_{l=1}^t\overline T_s^l a_l, \qmbox{i.e.} \vec\alpha=\overline T\vec a
\eeqn
where matrix $\overline T=T^{-1}=\overline D\,\overline C\,\overline F\,\overline N$, with
$\overline D$, $\overline C$, $\overline F$, $\overline N$
defined in \req{defVinv}, \req{defCinv},
\req{defFinv}, \req{defNinv}.
$\vec a$-polynomial ranking
can be implemented as an $\vec\alpha$-tournament if and only if, $\vec\alpha=\overline T\vec a\in\Delta_t$.
\end{theorem}

\paradot{Inverse matrices}
In the following $P$ and $V$ respectively denote the upper $t\times t$ submatrix
of $P$ and $V$. The inverse matrices are as follows
\eqvsp\dispmuskip\begin{eqnarray}}    \def\eqa{\eqvsp\end{eqnarray}\textmuskip\label{defCinv}
  \overline C_r^q &:=& \delta_{r,q}/\bino{t}{r}
\\ \label{defFinv}
  \overline F_q^r &:=& \bino{t-r}{t-q} \mbox{ if } r\leq q \mbox{ and 0 else}
\\ \label{defNinv}
  \overline N_p^l &=& \overline P_p^\iota D_\iota^\kappa V_\kappa^l
\\ \label{defPinv}
  \overline P_l^\kappa &:=& n^l\overline V_l^\kappa\fr1\kappa \qquad\mbox{(no summation)}
\eqa
The inverse of the diagonal matrix $C$ is obvious.
The expression for $\overline P$ immediately follows from
$P_\kappa^l=\kappa V_\kappa^l(\fr1n)^l$ (no summation).

$F_p^q\overline F_q^r=0$ for $r>p$ (since then either $r>q$ or $q>p$) and
for $r\leq p$ we have
\eqvsp\dispmuskip\begin{eqnarray*}}  \def\eqan{\eqvsp\end{eqnarray*}\textmuskip
  F_p^q\overline F_q^r
  &=& \textstyle\sum_{q=r}^p (-)^{p-q}\bino{t-q}{t-p}\bino{t-r}{t-q}
\\
  &=& \textstyle\bino{t-r}{t-p}\sum_{q=r}^p \bino{p-r}{q-r}(-)^{p-q}
  \;=\; \delta_{p,r}
\eqan
The first equality is by definition, the second equality is a simple
reshuffling of factorials, and the last equality follows from the
well-known binomial identity $\sum_{i=0}^m(-)^i\binom{m}{i}=0$ for
$m\geq 1$. This proves that $\overline F$ is the inverse of $F$.

Unfortunately we were not able to invert $N$ directly, although $N$
seems similar to (the transpose of) $F$. So we used relation
\req{VPeqQN} to invert $N$ in \req{defNinv}. But now we need the
inverse of $P$, which can be reduced by \req{defPinv} to the inverse
of $V$.

\paradot{Inverse of $V$}
The most difficult matrix to invert is $V$. This special Vandermonde
matrix $V$ can be written as a product of a lower $L$ and
upper-triangular matrix $U$, whose inverses are \cite{Turner:66}:
\eqvsp\dispmuskip\begin{eqnarray*}}  \def\eqan{\eqvsp\end{eqnarray*}\textmuskip\label{defQinv}
  \overline V_l^\kappa &:=& \overline U_l^s \overline L_s^\kappa
\\
  \overline L_s^\kappa &:=& {(-)^{s-\kappa}\over (s-\kappa)!(\kappa-1)!} \mbox{ for } s\geq \kappa \mbox{ and 0 else}
\\
  \overline U_l^s &:=& S_s^{(l)} \mbox{ = Stirling numbers of the first kind}
\eqan
The Stirling numbers $S_s^{(l)}$ numbers are defined as the coefficients of the
polynomial $x(x-1)...(x-s+1)$, i.e.\ by
\eqvsp\dispmuskip\begin{displaymath}}\def\eeqn{\eqvsp\end{displaymath}\textmuskip
  \sum_{l=0}^s S_s^{(l)} x^l = {x!\over(x-s)!} \qmbox{and} S_s^{(l)}=0 \mbox{ for } l>s
\eeqn
There are many ways to compute $S_s^{(l)}$, e.g.\ recursively by
$S_{s+1}^{(l)}=S_s^{(l-1)}-s S_s^{(l)}$ or directly
\cite[p.824]{Abramowitz:74}.
For $r\geq \kappa$ we get
\eqvsp\dispmuskip\begin{eqnarray*}}  \def\eqan{\eqvsp\end{eqnarray*}\textmuskip
  V_r^l\overline V_l^\kappa
  &=& \sum_{l=1}^t r^{l-1}\sum_{s=\kappa}^l
    {S_s^{(l)}(-)^{s-\kappa}\over (s-\kappa)!(\kappa-1)!}
\\
  &=& \sum_{s=\kappa}^t {[\sum_{l=1}^s r^{l-1}S_s^{(l)}] (-)^{s-\kappa}\over (s-\kappa)!(\kappa-1)!}
\\
  &=& \sum_{s=\kappa}^t {[(r-1)...(r-s+1)] (-)^{s-\kappa}\over (s-\kappa)!(\kappa-1)!}
\\
  &=& \bino{r-1}{\kappa-1}\sum_{s=\kappa}^r\bino{r-\kappa}{r-s}(-)^{s-\kappa} \;=\; \delta_{\kappa,r}
\eqan
The case $r<\kappa$ is similar. This shows that $\overline V$ is the inverse of
(the first $t$ rows of) $V$.

\paradot{Linear ranking example}
For $t=d+1=2$ we can compute the matrices by hand. This list of
(reduced) matrices is a useful sanity check for the reader's
own implementation:
\eqvsp\dispmuskip\begin{displaymath}}\def\eeqn{\eqvsp\end{displaymath}\textmuskip
\begin{array}{ll}
        F = \bino{\;\;1\,0}{-1\,1},\;\;
  \overline F = \bino{1\,0}{1\;1}, & \hspace{-1em}
        H = \fr1{n^2}\bino{n-1\,2n-4\,3n-9\;\cdots\;\; 0}{\quad 1\quad\;\; 4\quad\;\; 9\quad\cdots\;\; n^2}\!^\top
\\[3pt]
        C = \bino{2\;0}{0\,1},\quad
  \overline C = \fr12\bino{1\,0}{0\,2}, &
        G = \fr1{n^2}\bino{n-1\,n-3\,\cdots\,-1+n}{\quad 1\quad 3\quad\cdots\;2n-1}\!^\top
\\[3pt]
        N = \fr1{n^2}\bino{n\,-1}{0\;\;2}, &
  \overline N = \fr{n}2\bino{2\;1}{0\,n}
\\[3pt]
        P = \fr1{n^2}\bino{n\,2n\,3n\,\cdots\,n^2}{1\;\;4\;\;9\;\,\cdots\,n^2}\!^\top, &
  \overline P = \fr{n}2\bino{\;\;4\;\;-1}{-2n\;\;n}
\\[3pt]
        V = \bino{1\,1\,\cdots\,1}{1\,2\,\cdots\,n}\!^\top, &
  \overline V = \bino{\;\;2\,-1}{-1\;\;1}
\\[3pt]
        T = \fr1{n^2}\bino{2n+1\,-1}{-2\quad 2}, &
  \overline T = \fr{n}4\bino{2\quad 1\quad\!}{2\,2n+1}
\\[3pt]
  \overline U = \bino{1\,-1}{0\;\;1},\quad
  \overline L = \bino{\;\;1\,0}{-1\,1}, &
        R = \fr1{n^2}\bino{2n-1\,2n-3\,\cdots\quad 1\quad}{\quad 1\quad\; 3\;\;\cdots\;2n-1}\!^\top
\end{array}
\eeqn
We see that $\vec\pi=R\vec\alpha$ and $\vec a=T\vec\alpha$ coincide with
\req{PIkt2}, as they should.

\paradot{Computational complexity}
Together this allows us to compute $\vec\alpha$ from $\vec a$ and vice versa
in time $O(t^2)$ and $\vec\pi$ from $\vec\alpha$ in time $O(nt)$. Once
$\vec\alpha$ is known, tournament selection needs only time $O(t)$ per winner
selection.

\section{What Polynomial Selection Schemes are Tournaments?}\label{secPisT}
Theorem \ref{thmTtoP} does not give us conditions under which the
resulting tournament parameters $\vec\alpha=\overline T\vec a$ are valid. We look for such conditions so that we can reliably change/create tournament schemes in the more understandable set of polynomial rank schemes. Without these conditions there can be no guarantee that whatever created would be a probabilistic tournament.

\paradot{Range of linear ranking}
Let us first consider the case of linear ranking ($d=1$),
\eqvsp\dispmuskip\begin{displaymath}}\def\eeqn{\eqvsp\end{displaymath}\textmuskip
  P(I=k)=a_1+a_2 k
\eeqn
We want to find the range of $a_1$ and $a_2$
for which this is a proper probability distribution in $\Delta_n$.
The sum-constraint leads to
\eqvsp\dispmuskip\begin{displaymath}}\def\eeqn{\eqvsp\end{displaymath}\textmuskip
  1 = \sum_{k=1}^n P(I=k)
    = a_1 n+a_2 \fr12 n(n+1)
\eeqn
\eqvsp\dispmuskip\begin{equation}}    \def\eeq{\eqvsp\end{equation}\textmuskip\label{a1froma2}
  \Longrightarrow\quad
  a_1=\fr1n[1-\fr12 a_2(n^2+n)]
\eeq
Next are the positivity constraints $P(I=k)\geq 0\,\forall k$.
A linear function is $\geq 0$ if and only if it is $\geq 0$ at its
ends, i.e.\ $P(I=1) \geq 0$ and $P(I=n)\geq0$.
Inserting \req{a1froma2} into these constraints yields:
\eqvsp\dispmuskip\begin{eqnarray*}}  \def\eqan{\eqvsp\end{eqnarray*}\textmuskip
  P(I=1) &\equiv& a_1+a_2 \;\;\geq 0 \quad\iff\quad a_2 \;\leq\; \fr{2}{n^2-n}
\\
  P(I=n) &\equiv& a_1+a_2n \geq 0 \quad\iff\quad a_2 \geq -\fr{2}{n^2-n}
\eqan
So the possible linear rank schemes are those with
\eqvsp\dispmuskip\begin{equation}}    \def\eeq{\eqvsp\end{equation}\textmuskip
  |a_2|\leq \fr{2}{n^2-n}
  \qmbox{and} a_1 \mbox{ satisfying \req{a1froma2}} \label{LinRang}
\eeq

\paradot{Range of tournament size 2}
The example \req{PIkt2} shows that size $t=2$ probabilistic
$\vec\alpha$-tournaments have $a_2=2(\alpha_2-\alpha_1)/n^2$. Since $\vec\alpha\in\Delta_2$,
$a_2$ has range $-\fr2{n^2}...\fr2{n^2}$. As it should be, this is a
subset of the possible linear rank schemes. Hence the linear rankings
that are probabilistic tournaments are those with
\eqvsp\dispmuskip\begin{equation}}    \def\eeq{\eqvsp\end{equation}\textmuskip
  |a_2| \;\leq\; \fr2{n^2}
  \qmbox{and} a_1 \mbox{ given by \req{a1froma2}} \label{BinRang}
\eeq
This is slightly narrower than $|a_2|\leq\fr2{n^2-n}$, i.e.\ there
are some rankings that are not probabilistic tournaments. On the
other hand, $\fr2{n^2-n}/\fr2{n^2}$ tends to 1 as $n$ grows, hence
for $n$ large (e.g.\ about 100) nearly all linear rankings can be
translated into probabilistic tournaments. The coverage
is good enough for all practical purposes.

\paradot{The general case}
A probabilistic selection scheme is completely determined by
$\vec\pi$, different $\vec\pi$ correspond to different selection
schemes, and every $\vec\pi\in\Delta_n$ is a valid selection scheme.
Hence, $\Delta_n$ is the set of all possible probabilistic selection
schemes.
The set of (valid) size $t$ tournament schemes is
\eqvsp\dispmuskip\begin{displaymath}}\def\eeqn{\eqvsp\end{displaymath}\textmuskip
  R\Delta_t \;:=\; \{\vec\pi=R\vec\alpha:\vec\alpha\in\Delta_t\} \;\subset\; \Delta_n
\eeqn
Since $R$ is injective, this is a $t-1$ dimensional irregular
simplex embedded in the $n-1$ dimensional simplex $\Delta_n$.

The set of (incl.\ invalid) degree (up to) $t-1$ polynomial ranking schemes is
\eqvsp\dispmuskip\begin{displaymath}}\def\eeqn{\eqvsp\end{displaymath}\textmuskip
  VI\!\!R^t \;:=\; \{\vec\pi=V\vec a:\vec a\inI\!\!R^t\} \;\not\subseteq\; \Delta_n
\eeqn
This is a $t$-dimensional hyperplane. Only $\vec\pi$ in $\Delta_n$ are
valid, hence $VI\!\!R^t\cap\Delta_n$ is the set of (valid) polynomial
ranking schemes. The intersection of a simplex with a plane gives a
closed, bounded, convex polytope, in our case of dimension $t-1$.
The Krein-Milman Theorem \cite[p.707]{Edwards1965} says that for a
closed, bounded, convex subset $A$ of $I\!\!R^t$ with a finite number
of extreme points (=corners), $A$ is the convex hull of the extreme
points of $A$. Hence the extreme points of $VI\!\!R^t\cap\Delta_n$
completely characterize/define the set.

If/since we are not concerned with the covering of
$VI\!\!R^t\cap\Delta_n$ in $\Delta_n$ itself, we can study the covering
in the lower-dimensional polynomial coefficient space $I\!\!R^t$.
The set=polytope of all polynomial coefficients $\vec a$ that lead to valid
selection probabilities is
\eqvsp\dispmuskip\begin{displaymath}}\def\eeqn{\eqvsp\end{displaymath}\textmuskip
  \overline V\Delta_n \;:=\; \{\vec a\inI\!\!R^t: V\vec a\in\Delta_n\}
\eeqn
while the set=simplex of coefficients reachable by tournaments is
\eqvsp\dispmuskip\begin{displaymath}}\def\eeqn{\eqvsp\end{displaymath}\textmuskip
  T\Delta_t \;:=\; \{ \vec a=T\vec\alpha: \vec\alpha\in\Delta_t\} \;\subset\; \overline V\Delta_n
\eeqn

These sets are the images of $VI\!\!R^t\cap\Delta_n$ and the simplex
$\Delta_t$ under $\overline V$ and $T$ respectively. These maps are
injective (Section \ref{secPtoT}) so  $\overline V\Delta_n$ and
$T\Delta_t$ are completely determined by their extreme points. The
extreme points of $\Delta_t$ are just the conventional $I\!\!R^t$
basis vectors $\vec e_s$, so $T\Delta_t$ is the convex hull of $\{T(\vec
e_s):s=1,...,t\}$. The polytope $VI\!\!R^t\cap\Delta_n$ can be quite
complex, and finding the extreme points daunting. This is
essentially what we did for the $t=2$ case in the above paragraphs.

We estimated the proportion of degree $t-1$ polynomials covered by
$T\Delta_t$ for various $t$ using a Monte-Carlo
algorithm\footnote{The $t=2$ case was calculated directly from
\req{LinRang} and \req{BinRang}}   (Table \ref{AreaCov}). It shows
that for $n\geq100$, practically all linear rank schemes are
probabilistic tournaments.

Nothing concrete can be concluded about the coverage for $t=4,5$.
Table \ref{AreaCov} only suggests that the number of $t-1$ degree
polynomials equivalent to $t$-sized tournaments decreases as $t$
increases.

\paradot{Tournament size 3}
In the $t=3$ case we can extend our knowledge by finding $\overline
V\Delta_n$ graphically. The restriction  $\sum_{k=1}^n \pi_k=1$
means that the $k^2$ coefficient $a_3$, is completely determined by
$a_1$ and $a_2$.
\eqvsp\dispmuskip\begin{equation}}    \def\eeq{\eqvsp\end{equation}\textmuskip a_3=\frac{1}{\sum_{k=1}^n k^2}\left(1-n a_1 -\fr12 n(n+1)a_2\right)
  \label{t3plane}
\eeq
Hence $\overline V \Delta_n$ is a 2 dimensional hyperplane. $P(I=k)\geq
0$ for each $k$ defines a set of halfspaces:
$\{(a_1,a_2,a_3):a_1+a_2 k+a_3 k^2\geq0\}$; $\overline V\Delta_n$ is
their intersection (over $k$)  restricted to the plane given by
\req{t3plane}.

$T\Delta_3$ is simply a filled triangle with corners $\{T(\vec
e_s):s=1,2,3\}$.  Comparison with $\overline V\Delta_n$ (Figures
\ref{pic3}, \ref{pic20} and \ref{pic300})
suggests that the coverage of $T\Delta_3$ is stable for
$n\rightarrow \infty$. Hence for large populations about a third of
the quadratic polynomials can be written as size-$3$ probabilistic
tournaments.

In practice, selection schemes with probability monotonically
increasing with fitness are used. So not the whole of $\overline
V\Delta_n$ is interesting, but only the subset of monotonically
increasing or possibly decreasing probabilities on $\{1,2,...,n\}$
(light grey in figures \ref{pic3}, \ref{pic20} and \ref{pic300}).
The remainder of  $\overline V\Delta_n$ is composed of schemes
that favour the middle ranks or both high and low
ranked individuals (dark grey).

Any polynomial scheme $P(I=k)=a_1+a_2 k+\frac{1}{\sum_{i=1}^n
i^2}\left(1-n a_1 -\fr12 n(n+1)a_2\right)k^2$ is a
parabola\footnote{We temporarily consider k to range over the real
line}, so it is symmetric about it's stationary point, $x_{st.pt.}$.
Hence $P(I=k)$ is monotonic on $\{1,2,...,n\}$ if and only if
$x_{st.pt.}$ lies outside the interval $(1+\frac12,n-\frac12)$.

i.e.
\eqvsp\dispmuskip\begin{displaymath}}\def\eeqn{\eqvsp\end{displaymath}\textmuskip x_{st.pt.}=\frac{-a_2}{1-n a_1 -\fr12
  n(n+1)a_2}\left(\sum_{i=1}^n i^2\right) \leq 1+\frac12
\eeqn
\emph{OR}
\eqvsp\dispmuskip\begin{displaymath}}\def\eeqn{\eqvsp\end{displaymath}\textmuskip
  x_{st.pt.}\geq n-\frac12
\eeqn

Figure \ref{pic300} suggests that these regions of usefulness
effectively lie entirely in $T\Delta_3$ for $n\geq 300$. Hence for
sufficiently large $n$ the most useful degree 2 polynomial schemes
are perfectly reproduced by some probabilistic tournament.

An example of a less applicable selection scheme is the polynomial
given by $a_1=0.01$ and $a_2=-1\times 10^{-4}$ (which lies in the
dark grey region). It favours both high ranks and low ranks (Figure
\ref{notinT}) and any algorithm using this scheme will spend half of
the time searching in the wrong place. However it is still usable
(like in fitness uniform selection \cite{Hutter:06fuo}).

The points $p_1$, $p_2$ ... are extreme points of $\overline V\Delta_n$.
They indicate that the range of $a_3$ values is significantly
smaller than the range of $a_2$ (which in turn has a smaller range
than $a_1$).

$\overline V\Delta_n$ being the intersection of a finite number of
halfspaces and planes means its boundary is actually a series of
straight lines. $\overline V\Delta_n$ appears curved in figures
\ref{pic20} and \ref{pic300} simply due to the many halfspaces that
are involved.

\begin{table}
\eqvsp\dispmuskip\begin{displaymath}}\def\eeqn{\eqvsp\end{displaymath}\textmuskip
\begin{array}{|c|c|c|c|c|c|}
\hline
 & \mathbf{n=4} & \mathbf{n=10} & \mathbf{n=20} & \mathbf{n=100} & \mathbf{n=300}\\ \hline
 \mathbf{t=2} & 0.7500 & 0.9000 & 0.9500 & 0.9900 & 0.9967\\\hline
\mathbf{t=3} & 0.270& & 0.348 &0.342&0.332\\ \hline
\mathbf{t=4}&  & 0.12 & 0.15 & 0.16 &\\ \hline
\mathbf{t=5} & &0.02 & & &\\ \hline
\end{array}
\eeqn
\caption{fraction of possible $t-1$ degree polynomials that can be represented as $t$-sized probabilistic tournaments}
\label{AreaCov}
\end{table}

\begin{figure}
\setlength{\unitlength}{1.1mm}
\begin{picture}(80,74)(-4,0)
\put(0,0){\includegraphics[width=90.2mm]{4Toutline}}
\put(12.8,61){$p\,_1$}
\put(13.8,63){\vector(1,1){5}}
\put(71,22){$p\,_2$}
\put(71,23){\vector(-4,-1){5}}
\put(71,13){$p\,_3$}
\put(71,14){\vector(-4,0){5}}
\put(35,26){$p\,_4$}
\put(37,28){\vector(1,1){5}}
\put(38,0){\Large$a_1$\normalsize}
\put(-4,40){\Large$a_2$\normalsize}
\end{picture}
\caption{\label{pic3}[$n=4,t=3$] \it The shaded region is the set of possible
polynomials, whilst the light grey area is the set of the most useful polynomials. The triangle is the boundary of the set
that can be written as $t=3$ tournaments. At $p_1$: $a_3\doteq -0.246$. At $p_2$: $a_3\doteq 0.159$. At $p_3$: $a_3\doteq 0.236$. At $p_4$: $a_3\doteq 0.023$. }
\end{figure}

\begin{figure}
\setlength{\unitlength}{1mm}
\begin{picture}(87,79)(-5,-3)
\put(0,0){\includegraphics[width=82mm]{20Toutline}}
\put(12,64){$p\,_1$}
\put(13,66){\vector(1,1){5}}
\put(73.5,12.5){$p\,_2$}
\put(73.5,13.5){\vector(-4,1){5}}
\put(14.5,48){$p\,_3$}
\put(16.5,50){\vector(4,1){5}}
\put(41,-3){\Large$a_1$\normalsize}
\put(-5,40){\Large$a_2$\normalsize}
\end{picture}
\caption{\label{pic20}[$n=20$,$t=3$] \it The shaded region is the set of possible
polynomials, whilst the light grey area is the set of the most useful polynomials. The triangle is the boundary of the set
that can be written as $t=3$ tournaments. At $p_1$: $a_3\doteq -8.56 \times 10^{-4}$. At $p_2$: $a_3\doteq 1.08\times 10^{-3}$. At $p_3$: $a_3\doteq 1.91\times 10^{-4}$.}
\end{figure}

\begin{figure}
\setlength{\unitlength}{1.05mm}
\begin{picture}(85,81)(-3,-2)
\put(0,0){\includegraphics[width=86.1mm]{300Toutline}}
\put(6,75){\large $\times 10^{-5}$\normalsize}
\put(18,71){$p\,_1$}
\put(17.5,71){\vector(-4,-1){5}}
\put(73,10){$p\,_2$}
\put(73,11){\vector(-4,0){6}}
\put(9,44.2){$p\,_3$}
\put(10,46.2){\vector(1,2){2}}
\put(38,-2){\Large$a_1$\normalsize}
\put(-3,40){\Large$a_2$\normalsize}
\end{picture}

\caption{\label{pic300}[$n=300$,$t=3$] \it The shaded region is the set of possible
polynomials, whilst the light grey area is the set of the most useful polynomials. The triangle is the boundary of the set
that can be written as $t=3$ tournaments. At $p_1$: $a_3\doteq -2.18\times 10^{-7}$. At $p_2$: $a_3\doteq 3.53\times 10^{-7}$. At $p_3$: $a_3\doteq 1.21\times 10^{-7}$.}
\end{figure}

\begin{figure}
\includegraphics[width=\columnwidth]{notinT3}
\caption{\label{notinT} [n=300] The polynomial $y=0.01-10^{-4}x+2.781\times 10^{-7}x^2$. This is an example of a usable quadratic polynomial that is not equivalent to a probabilistic tournament.}
\end{figure}

\section{Discussion/Conclusions}

\paradot{Rank ties}
Individuals with the same fitness lead to ties in the ranking.
If we break ties (arbitrarily but consistently), our theorems still
apply. The disadvantage is that the selection probability for two
individuals with the same fitness may not be the same. We can fix
this problem by breaking ties (uniformly) at random.
For instance, given a population of 3 individuals with two of them
having the same fitness, this results in effective selection
probabilities $\pi_1^{e\!f\!f}=\pi_1$ and
$\pi_2^{e\!f\!f}=\pi_3^{e\!f\!f}=\fr12(\pi_2+\pi_3)$.

\paradot{Further work}
Investigation of the set of possible polynomials with degree $d\geq
3$ will be helpful for those applications requiring higher selective
pressures. Furthermore, finding the proportion that are equivalent
to probabilistic tournaments may provide a reliable method for
making high-degree polynomial rank schemes more efficient.

Tournaments of size $t\ll n$ are significantly faster than ranking
schemes, so it would be beneficial to obtain a thorough
understanding of how many polynomial rank schemes are equivalent to
$t>d+1$ sized probabilistic tournaments.

\paradot{Conclusion}
We have found a strong connection between polynomial ranking and
probabilistic tournament selection.

We derived an explicit operator (\ref{defT}) that maps any
probabilistic tournament to its equivalent polynomial ranking
scheme, which is unique and always exists. Polynomial rank schemes
thus encompass linear ranking and deterministic (normal) tournament
selection, leaving designers with one less selection method (but
more parameters) to worry about.

Unfortunately, turning polynomial rank schemes into equivalent
probabilistic tournaments is not so straightforward. Only about a
third of the possible quadratic polynomials can be written as
size-$3$ probabilistic tournaments.

However, nearly all linear rank schemes have an equivalent size-$2$
probabilistic tournament. Hence nearly all can be made faster by
simply rewriting the scheme as a probabilistic tournament.

Furthermore, almost all the practical quadratic polynomials are
equivalent to some $t=2$ tournament. This is a good indication for
the investigation of $t>3$.

redpajama_set_name: RedPajamaArXiv


HomeRecovering a debt in Panama? Read this.
Recovering a debt in Panama? Read this.
We regularly collect overdue invoices in Panama, on behalf of collection agencies, international financial institutions and export companies.
Panama is in several ways different from surrounding countries in Latin America, because of the particular nature of Panama's economy. It is an open economy, dollarized (which means that the dollar is the official currency), with a favorable tax climate for foreign investors, and a well-functioning professional infrastructure.
However, often, collecting an outstanding debt or overdue invoices in Panama is a challenge. Here is why.
Protective privacy laws: how to get info on a debtor?
First of all, it is extremely difficult to obtain official information about companies incorporated in Panama. Privacy laws are strict and very protective of companies and individuals doing business in Panama. When collecting a debt, without proper information it might be difficult to locate a debtor, or obtain contact details or up-to-date financial information on a debtor company or individual.
Secondly, as Panama is a very populair offshore location, with many businesses incorporating companies in Panama for privacy protection or tax reasons, the actual beneficial owners of a your Panama-based debtor company may in reality be located outside Panama. This means that although you are looking in Panama to collect a debt, and address your letters and notices of default, or other formal debt collection notifications to the debtor company in Panama, in reality you will have to find ways to contact the beneficial owners of the debtor company and try to negotiate amicably, as legal proceedings against an offshore company in Panama is often not feasible or economically attractive.
Thirdly, when you contact the debtor company in Panama in an attempt to collect a debt, you will often find yourself communicating with a so called "registered agent" in Panama (often a law firm) with (very) limited powers and who cannot and will not provide any substantial information or answers. The registered agent will pass the information and notices on to the beneficial owners of the Panama-based debtor company, and they will and often cannot do anything more. On the other hand, they will and cannot provide you (under Panama's privacy laws) with names and contact details of the beneficial owners.
Protective privacy laws, the actual location of the beneficial owners as opposed to the Panama-based debtor company, and the involvement of a registered agents may make it challenging to collecting a debt in Panama. However, understanding Panama's economy and corporate structures, having professionals locally and having the relationships with local law firms and registered agents can make the difference. We have succesfully collected in Panama and would be happy to assist you as well.
If you are interested in learning more or discussing issues that rise when attempting to collect an international debt in Panama, or in general you would like to know more about debt collection in Latin America & the Caribbean, please connect with Cobroamericas on Linked-In or follow us on Twitter.


text:
package PreOrderInOrderBinaryTree;

/**
 * Author: Alex Yang
 * Date: 1/30/15
 * Dependencies:
 * - N/A
 * Description:
 * - Given preorder and inorder traversal of a tree, construct the binary tree.

 Note:
 You may assume that duplicates do not exist in the tree.
 * Solution:
 * - Similar to this: https://oj.leetcode.com/discuss/12179/my-accepted-java-solution
 * - Essentially, what happens is we grab the first element of the preorder array because we know that is the root.  We use this data to split the inorder array into two halves by finding that element.
 * - This is because everything on the left of the root in an inorder must be less than, everything on the right must be greater than. (if we are imagining a BST)
 *
 * - ENTER SEARCH LEFT PHASE:
 *
 * - Now, add ONE to prestart.  This is because the element directly after in the preorder traversal must be the left child. if there is one.  if there is NOT, then INSTART and INEND will cause the left side to return null. Why? when you searched for the INORDERROOT, it exited immediately or didnt find it. This implies that there are NO children to the left of the INORDERROOT position!
 *
 * - We set the bounds to search the left half of the inorder array.  We do this by searching from INSTART to INORDERROOT - 1 similar to binary search.
 *
 * - Now, finally, we recurse and do this process again.
 *
 * - ENTER SEARCH RIGHT PHASE:
 * - To recurse on the right side is a bit trickier.  Searching the right side is exactly the same as the left, but setting PRESTART properly is the tricky part.  How do we know which element in the preorder traversal is the right child for the current root?
 * - In a preorder traversal, assuming the first node is the root. All left elements will come consecutively after, then all right elements.  So, what we want to do here is to find and set PRESTART at the FIRST right element.
 *
 * - To calculate this we do PRESTART - INSTART + INORDERROOT + 1
 * - PRESTART is where we currently are.
 * - we do INORDERROOT - INSTART, this will give us JUST the offset of how many left elements were found during the inorderroot search phase.
 * - We know that we need to move the prestart pointer forward that many times to hit the first right element.
 *
 * recurse down the right, rinse and repeat!
 *
 */
public class Solution {
  public TreeNode buildTree(int[] preorder, int[] inorder, int preStart, int inStart, int inEnd) {
    if (preStart >= preorder.length || inStart > inEnd) return null;

    TreeNode root = new TreeNode(preorder[preStart]);

    int inOrderRoot = 0;
    for (int i = inStart; i <= inEnd; i++) {
      if (inorder[i] == root.val) {
        inOrderRoot = i;
        break;
      }
    }

    root.left = buildTree(preorder, inorder, preStart + 1, inStart, inOrderRoot - 1);
    root.right = buildTree(preorder, inorder, preStart + (inOrderRoot - inStart) + 1, inOrderRoot + 1, inEnd);
    return root;
  }

  public TreeNode buildTree(int[] preorder, int[] inorder) {
    return buildTree(preorder, inorder, 0, 0, inorder.length - 1);
  }
}

class TreeNode {
  int val;
  TreeNode left;
  TreeNode right;
  TreeNode(int x) {
    val = x;
  }
}

redpajama_set_name: RedPajamaGithub


text:
New Vision TV TV API
UK TV Times API
http://tv.apixml.net/api.aspx?action=program&channelid=4b912698f956beff33f8a0974e294339
Latest news bulletin focusing on political, social and economic developments in Pakistan and around the globe. The show also features significant news stories from around the globe.
20200121120000 +0000 to 20200121120500 +0000
News summary focusing on political, social and economic developments in Pakistan as well as featuring current and significant news stories from around the globe.
A dedicated sports show which covers all that is happening in the international and national sports arenas.
Hosted by Madiha Naqvi and Shafaat Ali, this programme features a combination of news, a story of the day, and covers important issues with key figures from around the world.
Off The Record With Kashif Abbasi
A tri-weekly programme that talks about current political issues and policies of Pakistan.
It's all about power play when it comes to politics. Arshad Sharif takes a serious stance on various issues with his in-depth and hard-hitting questioning.
A round-up programme of political and current affairs.
Zimaydar Kaun
This programmes sees reporters expose corruption within society in real-life sting operations.
A news programme hosted by Sabir Shakir and Chaudhry Ghulam Hussain

redpajama_set_name: RedPajamaCommonCrawl


Technology has expanded our overall mobility, yet it has taken over functions that formerly demanded physical effort from us. Wobble Stool reduces the archetype of a chair into an abstract shape that can never fall.
By doing so, Wobble looks at the possibility to bring active movement and play back into our everyday life and routines.
The Wobble Stools are created for the Dutch Invertuals Exhibition "Take Away".


Can Theresa May win over Labour voters?
Theresa May is trying to charge to the centre ground of politics and is asking Labour voters who are not particularly happy with Jeremy Corybn's leadership to meet her there. She is trying to style herself as the leader of a "decent, moderate and patriotic" party that the public can get behind.
She wrote in The Observer that she wanted the Conservatives to "be a party for the whole country", though she would do well to remember one of the key points of democracy is that no single political organisation is able to represent the interests of an entire country. There are people in the UK who will not benefit from Tory policies and likely will never believe that situation could change.
Many Labour voters are young and it is one of the key demographics where the Tories are lagging behind. While many people shift politically to the right as they get older and richer it cannot be taken as a guarantee that the youth of today will eventually come round to the Conservatives.
Many among the younger generations say they will never vote Tory and attempts to win them round have come off as insincere. There is a difference between a politician wanting your vote and wanting what's best for you, much of the youth of today simply don't believe a Conservative prime minister will ever genuinely have their best interests at heart.
A recent survey by YouGov found that 21 per cent of people who voted for Labour in the 2017 general election don't know who they would choose if another vote was held tomorrow, while 31 per cent held an unfavourable view of Corbyn. Perhaps May thinks she can win over those voters who backed Labour last time but are unsure of the direction the party is currently headed in.
However, the statistics suggest that she is in charge of the wrong party if she wants to win over wavering Labour voters. Only 10 per cent of Labour voters have any sort of favourable view of May and just three per cent say they would now vote for the Tories in the event of another election. There's enough "don't knows" in the Labour camp to significantly damage the party if they all decided to vote for someone else but almost nothing to suggest that they'd look to the Tories as a credible alternative.
There is also the question of what Tory supporters would make of her attempts to court Labour votes. While they would likely love a situation where they gain large amounts of support at the expense of their biggest opponents those votes aren't going to come without some enticing policies. Tory voters might want the increase in support but would probably not approve of the shift in policy needed to win them over.


We are a boutique global Leadership Coaching company.
Our clients are leaders from all over the world.
They take the road less travelled, connect with their core and lead at their best.
Leadership is a way for individuals and groups to become more of who they are, and contribute in a greater way.
Our work transcends industries, cultures and nationalities.
Nobody becomes a better leader by listening to slide presentations.
Our practices combine conceptual wisdom, experiential learning and pragmatic action.
We co-create them with you for maximum fit, learning, and impact.
Our work is informed by a variety of disciplines including business administration, organizational development, leadership studies, mindfulness, embodied leadership, theatre acting, creativity, shamanic studies and others.


Among the several dozen species of lady beetles in New York state, C-9 was the clear choice in 1989 because it had been -— and was assumed still to be -— the most common lady beetle in New York and the northeastern United States. It ranged across the United States and through southern Canada. However, several recent [as of 2003] surveys in New York and the Northeast in general have not recovered any individuals of C-9 ... It is now clear that C-9 occupies only a tiny fraction of its former range in North America.
Many entomologists suspect that introduced lady beetles, such as the seven-spot (Coccinella septempunctata) and Asian multi-colored (Harmonia axyridis) lady beetles, played a role in C-9''s disappearance. ... Qualitatively, several native lady beetle species have declined as first the seven-spot and then the Asian multi-colored lady beetles established and rose to prominence. Introduced species may also replace each other, as the Asian multi-colored lady beetle's arrival seems to have led to the seven-spot lady beetle becoming increasingly rare.
We can hope that the decline of C-9 and several other conspicuous coccinellids will lead to a greater focus on this valuable family. To call attention to their plight, listing the species as ""endangered" in New York state and ""threatened" at the national levels is warranted. This is a task that the Xerces Society will be undertaking in the coming months. Other native lady beetles have similar habitat requirements and probably suffer from similar limiting factors, so efforts to survey for and conserve C-9 should prove useful for a suite of species. What began as a simple letter from a student to a state assemblyman has resulted in a greater awareness of the threats to apparently ubiquitous creatures often assumed to be safe from the pressures of environmental change.
Here's how we can "right the wrong": instead of introducing a bill to gloss over the extirpation of a species, let's reintroduce and restore C. novemnotata to New York State. Then our state insect would be a symbol to aspire to, and not simply an "error."
Albany Times-Union, June 19, 2006: Spot news: pink may oust nine scoops the New York Times, both on the date, and on reporting the full story.
Xris, thanks for the comment about bees over at my place.
Susan: Sorry, I didn't know my blog's font size was so small. I've also had problems with tiny fonts on various blogs. I use Firefox as my browser, and had set the default and minimum font sizes to something readable for me.
The style I'm using is not mine. It's a common one on Blogger. Several gardening blogs use it. I've modified it slightly, in part to try to fix the font size! I'll take a look at the style settings and see if I can find the problem.
What browser do you use? There may be some settings which will ensure readable type.
Susan: Try it now. I found the style was setting the default font size to "x-small" (extra-small). Not good! I changed it to explicitly use the default value of "medium".
Please let meknow if this fixes it for you.
PS: Blogger itself sets the default font size WAY too small. I find I have to keep increasing the font size in b logger to make things readable.


text:
JNF presence in S. America perpetuates Palestine injustice
By: Rahela Mizrahi \ The Electronic Intifada
JNF website
Without any sense of irony, lands of destroyed Palestinian villages have been expropriated by the Jewish National Fund (JNF) and dedicated to revolutionary South American heroes of liberation.
Since its inception in 1901, the JNF has been a key player in the dispossession of Palestinians and the colonization of their homeland. As Uri Davis notes in his book Apartheid Israel, the 1953 Jewish National Fund Law and the 1961 Covenant between the government of Israel and the JNF are central to the Israeli legal apartheid system that "nationalizes" privately-owned Palestinian property.
Despite this history, JNF has offices in the capitals of Bolivia and Venezuela where they raise funds to further entrench a racist system and to erase the signs of Israel's double crime: the ethnic cleansing of Palestine and the demolition of the Arab Jewish communities all over the Arab world and the transfer of Jews of Arab origin to Palestine by means of deception and terror.
After demolishing most of the Palestinian villages in the territory now called Israel, the Zionist movement housed the transferred Jews of Arab origin in some of the villages and the JNF employed them in the planting of pine forests over the ruins of the Palestinian villages.
Together, the Jewish National Fund Law and the Covenant define 93 percent of the entire territory that Israel occupied in 1948 as "national lands" legally designated for those persons who are defined under the laws of the State of Israel as "Jews." This effectively places these lands off limits to the indigenous Palestinian population, carrying out a sort of legal ethnic cleansing. In addition, the JNF has been instrumental in veiling the ruins of many, if not most, of the Palestinian localities ethnically cleansed by the Israeli army in the course of and in the wake of the 1948 war. According to Uri Davis, it accomplishes this task by planting forests and developing recreational facilities on the lands they have cleansed, and over their remains.
A prime example of the double crime being committed by the Zionists is Eshtaol Forest. Most of the Eshtaol Forest covers the lands of the two Palestinian villages: Islin, where 280 inhabitants used to live, and Ishwa, formerly home to 680 Palestinians. The inhabitants of these lands were expelled by the Harel Brigade of the Palmach militia, which departed from Kibbutz Zoraa the morning of 18 July 1948. The Eshtaol forest also resides on the lands of two other villages: Beit Mahsir, where 2,620 inhabitants were expelled on 11 May 1948, and Beit Susin, where 230 inhabitants were expelled on 20 April 1948.
In Eshtaol Forest, there stand three courts. The first one is dedicated to the memory of Simon Bolivar, the revered 19th century liberator of Latin America from European colonialism; it stands on the land of the village Ishwa. The other two courts are dedicated to another liberator of Latin America from the same period, General Jose de San Martin; they stand on the land of Beit Mahsir.
Moshav (the Zionist term for village) Eshtaol, built on the ruins of Ishwa, is a village of immigrants from Yemen, who were transferred by the Zionist movement to Palestine right after the 1948 ethnic cleansing. In the transfer camp in Sana, Yemen's capital, the Zionist Agency looted more then 50 tons of the Yemeni Jewish community's ancient sacred books and manuscripts and many tons of goldsmithing, a craft in which they specialized. In the transfer camp, children were kidnapped and were delivered to European Jewish families for adoption. Once in Moshav Eshtaol, and in the neighboring Moshav, Yishi, which has an identical story, the community succeeded in restoring a part of life as it was in Yemen.
The return of the Palestinian refugees to their land does not necessarily mean another dispossession of this community. On the contrary, it may provide an opportunity to establish neighborhood relationships that will fix the wrongs that were done both to the Palestinian refugees and Jews from Arab countries by a European settler-colonial movement. Meanwhile, it would fortify the culture of the Yemeni Jewish community of Moshav Eshtaol and Moshav Yishi, which were always fed by Arab and Muslim civilizations in their country of origin. It might also serve to strengthen their Arab dialect of Hebrew, a dialect and culture under threat of extermination by the Israeli Zionist Ashkenazi establishment.
Only when these historic injustices are rectified, can the use of these revolutionary heroes' names be justified. Until that time, those concerned with social justice should pressure the governments of Venezuela and Bolivia to kick the JNF out of their cities.
Rahela Mizrahi has a degree in fine arts from the Betzalel Academy in Jerusalem and is currently completing her second degree, writing on the "Patterns of Expropriation, Conversion, and Appropriation of Palestinian Heritage through Israeli Art" at Tel Aviv University. A version of this essay was originally published by the International anti-Zionist Network: http://www.ijsn.net/398/.
Link at electronicintifada Website
More about... Jewish National Fund (JNF)
More about... Afforestation
Related Villages
More about... Ishwa'
More about... Bayt Mahsir
More about... Bayt Susin
More about... 'Islin


text:
Bottle gourd (Calabash) Nutrition facts
Bottle gourd or calabash is a delicately flavored, Cucurbita family vegetable. It is one of the chief culinary vegetables in many tropical and temperate regions around the world.
Botanically, calabash belongs to the broader Cucurbitaceae (gourd) family of plants, in the genus: Lagenaria. Scientific name: Lagenaria siceraria (Molina) Standl. Some of the common names are white-flower gourd, upo-squash (Filipino), long-squash, etc., in the west and doodhi or lauki in the Indian subcontinent.
Bottle gourd. Round and pear-shaped fruits are known as calabash in the west.
Bottle gourd is a fast-growing, annual climber (vine) that requires adequate sunlight for flowering and fruiting. It can be grown in a wide range of soils and need trellis support for a spread.
Its intensely branched stems bear musky, deep green, broad leaves just similar as that in pumpkins, and white, monoecious flowers in the summer. After about 75 days from the plantation, young, tender, edible fruits evolve that will be ready for harvesting.
Bottle gourds come in a wide range of shapes and sizes. The fruit features oval, pear-shaped, or elongated and smooth skin that is light green. In the case of round or pear-shaped calabash, their surface is marked by inconspicuous ridges that run lengthwise. Internally, its flesh is white, spongy, and embedded with soft, tiny seeds. As the fruit begins to mature, its seeds gradually grow similar to as that in honeydew melons.
Health benefits of Bottle gourd
Bottle gourd is one of the lowest-calorie vegetables- carrying just 14 calories per 100 g. It is one of the vegetables recommended by dieticians in weight-control programs.
Fresh gourds contain small quantities of folates, contain about 6 µg/100g (Provide just 1.5% of RDA). Folate helps reduce the incidence of neural tube defects in newborns when taken by anticipant mothers during their early months of pregnancy.
Fresh calabash gourd is a modest source of vitamin-C (100 g of raw fruit provides 10 mg or about 17% of RDA). Vitamin-C is one of the powerful natural antioxidants that help scavenge harmful free radicals
Calabash facilitates easy digestion and movement of food through the bowel until it is excreted from the body. Thus, it helps in relieving indigestion and constipation problems.
Aslo, the vegetable is also a modest source of thiamin, niacin (vitamin B-3), pantothenic acid (vitamin B-5), pyridoxine (vitamin B-6), and minerals such as calcium, iron, zinc, potassium, manganese, and magnesium.
Its tender leaves and tendrils are also edible; indeed carry higher concentrations of vitamins and minerals than the bottle gourd fruit.
Bottle gourd (white flowered Calabash) (Lagenaria siceraria),
fresh, raw, Nutritive value per 100 g
(Source: USDA National Nutrient database)
Energy 14 Kcal <1%
Carbohydrates 3.39 g 2.5%
Protein 0.62 g 1%
Total Fat 0.02 g 0.5%
Dietary Fiber 0.5 g 1%
Folates 6 µg 1.5%
Niacin 0.320 mg 2%
Pantothenic acid 0.152 mg 3%
Pyridoxine 0.040 mg 3%
Riboflavin 0.022 mg 2%
Thiamin 0.029 mg 2.5%
Vitamin A 16 IU 0.5%
Vitamin C 10.1 mg 17%
Potassium 150 mg 3%
Copper 0.034 mg 4%
Iron 0.20 mg 2.5%
Magnesium 11 mg 3%
Manganese 0.089 mg 4%
Phosphorus 13 mg 2%
Selenium 0.2 mg <1%
Zinc 0.70 mg 6.5%
Bottle gourds can be available around the season in the regions wherever suitable conditions for their growth exist. In the markets, look for fresh produce featuring tender, medium size, uniform, light green color fruit. Take a close look at its stem, which may offer a valuable hint whether the produce is fresh or aged.
Avoid those with oversize, mature, yellow-discoloration, cuts, and bruise on their surface. Tiny spots on the surface, however, would not lessen their quality.
At home, store them in the refrigerator set at adequate humidity where they stay fresh for 3-4 days.
Bottle gourd cut sections. Note for ice-white, spongy flesh, and tiny, soft seeds.
Bottle gourd is one of the most common vegetables in continuous use since ancient times. To prepare, wash the fruit in cold water and dry mop using a soft cloth or paper towel. Trim its top end in case of round or pear-shaped calabash and either end in case of an elongated gourd. Peeling may not be required in the case of tender fruits. Chop the fruit into uniform chunks for even cooking.
Fresh calabash is used in a variety of stews, curries, sweet recipes across the world. In the Indian subcontinent where it is popularly known as lauuki, employed in the preparation of sabzi, sambar, chutney, soup, raita, etc.
In India and Pakistan, its flesh is used to prepare a mouth-watering sweet dish, lauki-ki-halwa.
In Africa, where it is thought to have taken its origin, calabash is used in stews with meat, poultry, and seafood.
Ginisang-upo (sauteed bottle gourd) is a popular stir-fried dish among the Filipinos.
In India, bottle gourd juice is consumed for its little known health benefits in traditional meidcines.
The gourd is known as yugao in Japanese, where its white flesh shaved into thin strips 3 cm wide and 3 mm thick, then either dried in the sun or dehydrated to prepare Kanpyō (かんぴょう or 干瓢). Kanpyō strips used in sushi rolls in place of nori.
Some bottle gourds develop naturally occurring cucurbitacins in excess amounts under environmental adversities and may accumulate terpenoid toxic compounds such as cucurbitacin B, D, G, H, etc.
Bottle gourd poisoning occurs when a bitter fruit is consumed either raw or juiced. Incidents of serious illness and death have been reported in India after drinking bitter bottle gourd juice for its purported health benefits. Symptoms may include vomiting, stomachache, diarrhea and can occur within minutes of ingestion of toxic juice which may follow serious illnesses like bleeding from the gut, shock, and death.
ICMR (Indian Council of Medical Research) recommends the following guidelines regarding bottle gourd consumption to the public:
1. Taste a small piece of bottle gourd before extracting the whole fruit juice to ensure that it is not bitter. If found so, then discard the whole fruit.
2. Bitter bottle gourd juice should not be consumed at all.
3. Do not mix bottle gourd juice with any other juice.
4. In case of discomfort after consumption (nausea, vomiting, diarrhea, or any feeling of uneasiness), the person should be immediately taken to a nearby hospital. (Medical disclaimer).
Also read ≻≻
≺≺ Ash gourd (Chinese winter melon) nutrition facts.
≺≺ Snake gourd (Chichinda) nutrition facts.
≺≺ Bitter gourd (bitter melon) nutrition facts.
≺≺ Ivy gourd (kundru) nutrition facts.
≺≺ Pointed gourd (parwal) nutrition facts.
≺≺ Ridge gourd (Luffa) nutrition facts.
≺≺ Back to Vegetables from Bottle gourd nutrition. Visit here for an impressive list of vegetables with complete illustrations of their nutrition facts and health benefits.
≺≺ Back to Home page.
Indian Journal of Medical Research (IJMR)- Assessment of effects on health due to consumption of bitter bottle gourd (Lagenaria siceraria) juice.
Plants for a future-Lagenaria siceraria.
USDA National Nutrient Database.
Bok choy ≺ Prev Next ≻ Broccoli


text:
Cañones is a census-designated place  in Rio Arriba County, New Mexico, United States. Its population was 118 as of the 2010 census. Cañones had a post office until it closed on January 3, 2002.

Demographics

2020 Census
The town had 85 people in the 2020 census.

Description

The origins of the community trace back to 1766, when Juan Pablo Martín Serrano was awarded the Polvadera Grant. Serrano was a wealthy military veteran with a large family, and established a seasonal rancho in the canyon, raising livestock, farming the canyon bottom, and trading with the Utes. Permanent settlement seems to have begun with Juan Bautista Valdez, who bought a grant at the present location of Cañones in 1807.

Cañones was visited by anthropologists Paul Kutsche and John R. Van Ness in the 1960s, who considered the community typical of what they called the Rio Arriba subculture of Hispanic New Mexico. They concluded that this subculture was characterized by communal land grants, small economies, campanilismo (community spirit), and a fair degree of social equality.

During the time Kutsche and Van Ness were guests in the community, the state closed the one-room school and ordered the children to attend school in Coyote, which meant busing the students several miles over a very bad road. The parents refused en masse to send their children to school in Coyote, and the subsequent legal battle seems to have revolved around the issue of whether the parents were acting on legitimate concerns for their children's safety or were using the children to pressure the state into building a better road into the community. The parents were fined for truancy, but the community now has an acceptable paved road.

The ruins of Tsiping or Tsi'pinouinge, is found on Pueblo Mesa just south of Cañones. The settlement was active during the Classic stage, between 1200 CE and 1325 CE, and at its peak the settlement had 335 to 400 ground floor rooms and sixteen kivas surrounding a central plaza. Visitors to the ruins are encouraged to approach along a trail from Polvadera Mesa rather than through Cañones, out of respect for the privacy of the residents.

See also

 List of census-designated places in New Mexico

References

External links

Census-designated places in New Mexico
Census-designated places in Rio Arriba County, New Mexico

redpajama_set_name: RedPajamaWikipedia


text:
Q: Volume control for chinese lightsaber I've got a cheap chinese lightsaber and want to make some adjustments to it. The item looks great but its volume is too loud and my neighbours get mad when I switch it on. It doesn't have any way to control it. I contacted the seller and confirmed that there was no internal control.
I'm not an expert in electronics, I only know basic teoric concepts and how to use a soldering gun.  My first idea was to install a potentiometer between the control board and the speaker, because there is some space behind the speaker, but after I searched this site I discovered it was a bad idea, that the sound will be distorted, the amplifier could break and there would be unnecessary power consumption in the resistance. At least that is what I understood.
I've tried to locate the amplifier, but it doesn't seem easy to make mods to the PCB, as it is really small and it fits in the hilt without much free space.
So the question is, considering that controlling the volume at the amplifier input is not an easy option, and that the system itselt is not a Hi-Fi and small distortions could be accepted, will installing a potentiomenter be dangerous and break the amplifier? What about a voltage divider?
If the risk is too high, could I simply take the speaker off? Altghough I think it can sound silly asking this, I read in another question that it could break the amplifier too, due to infinite resistance. I really don't know if that responses only related to guitar amplifiers or if it applies to small ones.
The speaker specs are 8 Ohm 2 W, 20 mm in diameter, while the battery is 3.7 V 2000 mAh.

The cables on the left down corner of the PCB go to the speaker; the right side ones go to the leds. I cannot extract the PCB more than that without cutting any cable, I hope this helps.
Thank you in advance.

A: For that kind of gadget, it's almost certain that the amplifier is a class D.
Therefore you can simply add a resistor in series with the speaker and this should do the trick. The bigger the resistor the lower the volume. This should not damage the amplifier. Just make sure that you are using a resistor with a decent power rating.

redpajama_set_name: RedPajamaStackExchange


SOLOS was founded in 1987 by JoAnn Chavez and Pat O'Brien who each lost sons to suicide in the mid 1980's. They met each other while attending grief support groups in San Antonio but found that the unique experiences and difficulties faced by survivors of suicide were not being met by any of those groups. This spurred JoAnn and Pat to form SOLOS and the group has been meeting regularly since then. Initial attendance at meetings was sparse but increased as word spread through the community that there was a group specifically tailored to helping the survivors of loved ones' suicides. JoAnn was a frequent guest lecturer and facilitator trainer for the American Foundation for Suicide Prevention, the San Antonio Police Department, and the University of Texas, San Antonio.
We lost JoAnn on March 31, 2009 after a brave fight with cancer. We lost Pat on January 25, 2013. These women dedicated themselves to helping others in the San Antonio area. We continue their legacy of compassionate support to as we give of ourselves to continue helping others affected by the tradegy of suicide. on.
SOLOS meets the first and third Wednesday evening of each month from 7:00 to 8:30 at the Ecumenical Center for Religion and Health. Meetings that fall on a Federal holiday are not held. Click on the map below for turn-by-turn directions to the center.
please call 911 or the National Suicide Hotline at 1-800-273-8255 (TALK).


[LONDON] European shares rallied near 11-month highs on Friday after a strong week, helped by gains among media companies after a takeover bid ignited Sky's shares, though Italian banks were under pressure.
The STOXX 600 marked its fifth session of straight gains up 1 per cent, its best week since January 2015.
The standout performer on the pan-European index was Britain's Sky which soared more than 26 per cent after Twenty-First Century Fox Inc approached the pay-TV group with a US$14.1 billion takeover bid.
Sky's shares posted their biggest-ever one-day gain, and Europe's Media index jumped 4.5 per cent, its best day since May 2010.
Equities got a boost on Thursday after the European Central Bank said it would scale back its monthly asset purchases, a surprise move that lifted euro zone bond yields, which in turn are seen as helping reduce pressure on bank profits.
However, Europe's basic resources index fell 1 per cent and Europe's banking index retreated 0.7 per cent as profit-taking kicked in after the index's best week in five years.
Italian banks were the biggest laggards, with Monte dei Paschi's shares plummeting more than 10 per cent after the ECB rejected the bank's request for more time to raise capital, virtually erasing all gains made this week on bets a way could be found to rescue the ailing lender, even involving state aid.
"A state intervention in Monte Paschi could entail heavy losses for shareholders but also hurt bondholders. If retail investors do get hurt too there could be a loss of confidence in the system and litigation risks would increase," said Angelo Menzella, portfolio manager and analyst at JCI Capital.
Such expectations helped shrug off concerns over political instability after Prime Minister Matteo Renzi's resignation on the back of a resounding defeat on Sunday in a referendum on his plans for constitutional reform.
Banca Popolare di Milano dropped 4.3 per cent, and Banco Popolare was also down 3.9 per cent.
UniCredit fell 2.3 per cent. Italy's largest lender is set to announce next week the country's biggest bank share issue, which could be worth up to 13 billion euros according to sources. "In Italy, virtually no bad loans have been written off at all ... and that is really difficult to get any economic momentum going when your banking sector is still seized up," Ed Smith, asset allocation strategist at Rathbones, said.
Elsewhere on the broader market, Amsterdam-based digital security company Gemalto rose 6.3 per cent after agreeing to buy 3M's identity-management business for US$850 million.
Among other strong gainers, cable company Altice rose 5.3 per cent after saying it was exploring the possibility of listing a minority stake in its US subsidiary.
Europe's healthcare index rose 3.2 per cent, among the top sectoral gainers, having been out of favour recently on concerns over pricing pressure in the United States.


School Superintendent Charles E. Gobron will go to Southborough's Annual Town Meeting Monday, April 11, and let the voters decide on the ultimate fate of the school budgets.
Region – The first official day of summer has brought extreme heat and humidity to the region. The city of Marlborough has set up three cooling center for residents searching for relief from the oppressive weather. The centers are located at - Marlborough Police Station Lobby - 355 Bolton St.; Marlborough Council on Aging Auditorium - 250 Main St.; and the Marlborough Hospital- UMass -157 Union St. cafeteria until 7 p.m. and lobby until 8 p.m.