text:
### Посредника берут в дело;pdf

```Original citation:
Dyer, M., Goldberg, Leslie Ann, Greenhill, C., Istrate, G. and Jerrum, M. (2000)
Convergence of the iterated prisoner's dilemma game. University of Warwick.
Department of Computer Science. (Department of Computer Science Research Report).
(Unpublished) CS-RR-376
Permanent WRAP url:
http://wrap.warwick.ac.uk/61133
The Warwick Research Archive Portal (WRAP) makes this work by researchers of the
University of Warwick available open access under the following conditions. Copyright ©
and all moral rights to the version of the paper presented here belong to the individual
author(s) and/or other copyright owners. To the extent reasonable and practicable the
material made available in WRAP has been checked for eligibility before being made
available.
Copies of full items can be used for personal research or study, educational, or not-forprofit purposes without prior permission or charge. Provided that the authors, title and
full bibliographic details are credited, a hyperlink and/or URL is given for the original
metadata page and the content is not changed in any way.
A note on versions:
The version presented in WRAP is the published version or, version of record, and may
[email protected]
http://wrap.warwick.ac.uk/
Convergene of the Iterated Prisoner's Dilemma
Game
Martin Dyer
y
Leslie Ann Goldberg
Gabriel Istrate
{
z
Catherine Greenhill
Mark Jerrum
x
k
Otober 23, 2000
Abstrat
We onsider a stohasti proess based on the iterated prisoner's dilemma
game. During the game, eah of n players has a state, either ooperate or defet.
The players are onneted by an \interation graph". During eah step of the
proess, an edge of the graph is hosen uniformly at random and the states of
the players onneted by the edge are modied aording to the Pavlov strategy.
The proess onverges to a unique absorbing state in whih all players ooperate.
We prove two onjetures of Kittok: The onvergene rate is exponential in n
when the interation graph is a omplete graph, and it is polynomial in n when
the interation graph is a yle. In fat, we show that the rate is O(n log n) in the
latter ase.
1 Introdution
In a two-player prisoner's dilemma game [1, 8℄, eah player may hoose to ooperate or to
defet. If both players ooperate, they eah reeive a reward of R points. If both players
defet, they eah reeive only P points. If exatly one player ooperates, he reeives
S points while his opponent reeives T points. The parameters satisfy T > R > P > S
This
work was supported in part by the EPSRC Researh Grant \Sharper Analysis of Randomised
Algorithms: a Computational Approah" and by the ESPRIT Projets RAND-APX and ALCOM-FT.
y Shool of Computing, University of Leeds, Leeds LS2 9JT, United Kingdom, email:
dyeromp.leeds.a.uk
z Department of Computer Siene, University of Warwik, Coventry CV4 7AL, United Kingdom,
email: leslieds.warwik.a.uk
x Department of Mathematis and Statistis, University of Melbourne, Parkville VIC 3502, Australia,
email: sgms.unimelb.edu.au Supported by an Australian Researh Counil Postdotoral Fellowship
{ Center for Nonlinear Siene and CIC-3 Division, Los Alamos National Laboratory, Mail Stop
B258, Los Alamos, NM 87545, email: istratelanl.gov
k Shool of Computer Siene, University of Edinburgh, King's Building, Edinburgh EH9 3JZ, United
Kingdom, email: mrjds.ed.a.uk
1
and 2R > T + S . Thus, in a single round, it is best for eah player to defet even though
this is not globally optimal. In the iterated prisoner's dilemma game, rounds are played
repeatedly and players may base their deisions on the outomes of previous rounds.
Empirial evidene indiates that an eetive strategy for this game is the so-alled
\Pavlov" strategy: If a player is \rewarded" with T or R points during a given round,
then he repeats his previous move next time. If he is \punished" with P or S points
then he does not repeat his previous move. A small ase analysis reveals that the Pavlov
strategy an also be stated as follows: A player ooperates if and only if he has made
the same hoie as his opponent during the previous round.
Kittok [4℄ studied the Pavlov strategy in a distributed setting: n players are onneted by an \interation graph". During a round of the game, an edge of the graph is
seleted uniformly at random. The two players onneted by the edge play one round,
using the Pavlov strategy. That is, if a player agreed with his (previous) opponent last
time he was hosen to play, then he ooperates this time. Otherwise he defets. As long
as the interation graph is onneted, the game onverges to a unique absorbing state
in whih every player ooperates. Kittok was interested in determining the absorbtion
time | that is, the time required to reah the absorbing state. He provided empirial
evidene for the onjeture that the absorbtion time is exponential in n if the graph is
the omplete graph, and polynomial in n if the graph is a yle. In this note, we prove
Kittok's onjetures.
The basi method whih we use to prove both theorems is to dene an appropriate
potential funtion so that the progress of the Pavlov proess may be ompared to that of
a one-dimensional random walk. See, for example, [5℄. Similar tehniques are often used
to analyse the mixing time of Markov hains via oupling arguments. In the oupling
ontext, the observed state spae is taken to be the set of pairs of Markov-hain states,
and the potential funtion is dened to be the distane between the states in the pair,
with respet to some metri. See, for example, [6, 7, 2, 3℄.
1
2
2 Preliminaries
We are given a population of n 4 players situated at the verties of a onneted graph
Eah player has an initial state X (i) 2 f 1; 1g. The 1 values enode the
deision \ooperate" and are referred to as pluses. The 1 values enode the deision
\defet" and are referred to as minuses. During eah step of the Pavlov proess, we
G = (V; E ).
1 Axelrod
[1℄ hosted a omputer tournament in whih strategies proposed by game theorists were
played against eah other. Surprisingly, a simple Markovian strategy won the tournament. That is, the
winning strategy has the property that the deision of a given player in a given round depends only
on the outome of the previous round, and not on the rest of the history of the game. Nowak and
Sigmund [8℄ did a omputational study of all suh Markovian strategies, and found the Pavlov strategy
to be \best".
2 Kittok's paper is desribed using AI language, but the iterated prisoner's dilemma strategy that
he studies (whih he alls the zero-memory HCR strategy) is preisely the Pavlov strategy. For more
information about the ontext of Kittok's work and the HCR generalisation of the Pavlov strategy,
see Shoham and Tennenholtz's paper [9℄.
2
hoose a pair fi; j g 2 E uniformly at random and replae X (i) and X (j ) by X (i)X (j ).
The state X with X (i) = 1 for all v 2 V is an absorbing state of this proess. If G
ontains no isolated verties then X is the unique absorbing state and there exists a
sequene of moves whih an transform X to X , for every X 2 f1; 1gV .
We are interested in the absorbtion time ; that is, the time required for the Pavlov
proess to reah the absorbing state. We investigate two families of graphs, namely
yles and omplete graphs. Using a oupon-olletor-like argument, Shoham and Tennenholtz [9℄ proved that, for a large lass of strategies, the absorbtion time for both of
these families is (n log n). We prove the following theorems, showing that the Pavlov
proess has optimal absorbtion time when G is a yle, and exponential absorbtion time
when G is a omplete graph.
Let G be a yle on n verties and let " > 0 be given. With probability at
", the Pavlov proess reahes the absorbing state in
Theorem 1
least
1
49 n log 49n
2
94"
steps.
Theorem 2 Let Tn denote the absorbtion time of Pavlov proess on the graph Kn starting from a onguration X0 with at most 0:61n pluses. Then there exists a onstant > 1
suh that with probability 1 o(1) we have Tn n .
3 Optimal absorbtion on yles
Let G be a yle on the the vertex set [n℄ = f0; : : : ; n 1g. That is, G has n edges
fi; i + 1g for 0 i < n. Here, and throughout the paper, addition and subtration on
verties is performed modulo n.
We dene a potential funtion : f1; 1g ! R to measure the distane of a given
state X from the absorbing state X . First, we must introdue some terminology. Let
X 2 f1; 1g be given. A run in X is an interval [i; j ℄ where 0 i; j < n, suh that
V
V
X (`) =
1 for ` = i; i + 1; : : : ; j 1; j and X (i 1) = 1, X (j + 1) = 1. (It is possible
to have j < i, sine we are working modulo n.) Clearly all runs are disjoint. We an
dene the set R(X ) of all runs in X . By onvention, the all-minuses onguration is
not onsidered a run, sine it has no bordering pluses.
Suppose that r = [i; j ℄. The length of the run r, denoted by `(r), equals the number
of minuses in the run. We will refer to a run of length ` as an `-run. A 1-run will also
be alled a singleton and a 2-run will also be alled a pair. Then the potential funtion
is given by
(X ) = j fi : X (i) = 1g j + jR(X )j + j fr 2 R(X ) : r is a singletong j
+ Æ j fr 2 R(X ) : r is a pairg j:
3
The parameters , and Æ will be set below. Note that a singleton is a barrier to
absorbtion sine a singleton minus annot be hanged to a plus in one step. The singleton
must rst beome part of a longer run. So we set > 0 to penalise singletons. On the
other hand, pairs give the opportunity for two minuses to be hanged at one step. Thus
pairs are helpful, and we reet this by setting Æ < 0. We also set > 0. Clearly
(X ) = 0 for any values of , , Æ sine X (i) = 1 for all i, and R(X ) = ;. For
to be a well-dened potential funtion, we must also show that (X ) > 0 whenever
X 6= X . This is ahieved if 2 < Æ < 0, sine there an be at most half as many pairs
in X as there are minuses.
3.1
The analysis
We now analyse the Pavlov proess using the potential funtion . Let X 2 f1; 1gV
be xed. Clearly if X = X there is nothing to prove. So, suppose that X ontains
at least one minus. Let X be the result of performing one step of the proess from
starting point X . We will nd an upper bound for E [ (X ) (X )℄.
Note that eah edge overlaps at most one run in R(X ), and that there are ` + 1
edges whih overlap a given `-run. Speially, if r = [i; j ℄ then these `(r) + 1 edges are
0
0
0
1
0
1
0
0
fi 1; ig ; : : : ; fj; j + 1g :
Let L(X ) be dened by
0
X
L(X0 ) =
r
(`(r) + 1):
2R(X0 )
Then L(X ) equals the number of edges whih overlap some run in X . Denote by
[ (X ) (X ) j e℄ the value of (X ) (X ) given that the edge e has been hosen
by the Pavlov proess in step 1. Let r be an `-run and let
0
E
1
0
0
1
0
X
(r ) =
E
(X ) j e℄ :
[ (X )
1
0
e overlaps r
By denition we have
E
[ (X )
1
X
(X )℄ = n1 E [ (X )
0
(X ) j e℄ ;
1
2
0
e E
sine there are n edges in G. When X ontains both pluses and minuses we an also
state that
X
(r );
E [ (X )
(X )℄ = n1
0
1
0
r
2R(X0 )
sine runs are disjoint and an edge whih does not overlap a run makes no hange to
X . Let M = M (X ) be dened by
(r )
M = max
j r 2 R( X ) :
`(r) + 1
0
0
0
4
That is, M is the maximum over all runs of the average ontribution of eah edge in that
run. The way in whih M will be used is desribed below. We ignore two ongurations:
the all-pluses onguration X , and the all-minuses onguration. The latter is treated
separately in Setion 3.2.
Suppose that X0 ontains both pluses and minuses. With M,
as above, we have
ML(X0 )
E [ (X1 )℄ 1 + (X )n (X0):
0
Lemma 1
. From above, we have
and L dened
Proof
E
[ (X )
1
(X )℄ = n1
0
n1
We an rearrange this inequality to give
[ (X )℄ 1
r
2R(X0 )
X
2R(X0 )
ML(X0 )
n
=
E
X
(X0) + MLn(X0 )
(r )
(`(r) + 1)M
r
=
(X0 )
1 + ML
(X0)n
(X );
0
as stated.
Suppose that the values of , , Æ ould be set to ensure that M < 0. Then, by
Lemma 1, the value of dereases in expetation at every step. This will be used in
Setion 3.2 to alulate an upper bound for the absorbtion time of the Pavlov proess.
Let r = [i; j ℄ be a run. Then there are two outer rim edges assoiated with r, namely
fi 1; ig and fj; j + 1g. If r has length at least 3 then there are also two inner rim
edges assoiated with r, namely fi; i + 1g and fj 1; j g. If r is a singleton then there
are no inner rim edges, while if r is a pair [i; i + 1℄ then there is a unique inner rim edge
fi; i + 1g. All other edges whih overlap r are stritly inside the interval [i; j ℄, and we
all these edges internal edges.
Suppose that there are two runs in R(X ) whih are only separated by a single plus,
i.e. [i; j ℄ and [j + 2; k℄ for some i, j , k. Then there are two edge hoies fj; j + 1g and
fj + 1; j + 2g whih ause the two runs to merge (note that these edges are both outer
rim edges for the runs whih they overlap). For simpliity, we will rst assume that there
are no edge hoies whih ause runs to merge. That is, in Lemma 2 we assume that
all adjaent runs in R(X ) are separated by at least two pluses. By arefully hoosing
values for , and Æ in this ase, we show that M is negative: speially M = 1=14.
In Lemma 3 we return to ongurations whih ontain adjaent runs separated by a
single plus.
0
0
5
Before presenting Lemma 2, we make a few general remarks. When all adjaent runs
are separated by at least two pluses, hoosing an outer rim edge will always ause r to
inrease in length by 1, introduing an extra minus. Similarly, hoosing an inner rim
edge will always ause r to derease in length by 2, hanging two minuses to pluses.
When the length of r is small there might be additional eets from these four edges,
as we shall see. When any internal edge is hosen, the run r is split into two runs whih
are separated by two pluses. If the two runs have length k and ` we say that this edge
hoie produes a (k; `)-split.
We an now prove that M is negative for ertain xed values of , and Æ, when X
ontains both pluses and minuses and all adjaent runs are separated by at least two
pluses.
0
Lemma 2 Let X0 ontain both pluses and minuses, and suppose that adjaent runs in
X0 are separated by at least two pluses. Then setting = 27=14, = 4=7 and Æ = 4=7
we obtain M = 1=14.
. We will onsider runs r of dierent lengths in turn, and alulate (r)=(`(r)+1)
in eah ase. Then M is the maximum of these values.
Proof
A 1-run.
Let r be a 1-run [i; i℄. The only edges whih overlap r are the outer rim edges
fi 1; ig and fi; i + 1g. When either of these edges are hosen, a vertex adjaent to
the 1-run hanges from a plus to a minus. This introdues an extra minus and hanges
a 1-run (singleton) to a 2-run (a pair), without hanging the total number of runs.
Therefore
(r )
1:
=
1
+Æ =
(1)
2
7
Suppose that r = [i; i + 1℄. There are 3 edges whih overlap r. When either
of the outer rim edges fi 1; ig or fi + 1; i + 2g are hosen the 2-run beomes a 3-run,
introduing an extra minus and deleting a pair. There is only one inner rim edge, the
edge fi; i + 1g. When this edge is hosen, both minuses in the pair beome pluses. Here
we lose two minuses and delete a pair, dereasing the number of runs by 1. Adding
these ontributions and dividing by 3 we nd that
+ 3Æ
1:
(r) 2(1 Æ ) (2 + + Æ )
=
=
=
(2)
3
3
3
14
A 2-run.
Suppose that r = [i; i + 2℄. There are 4 edges whih overlap r, namely the
two outer rim edges and the two inner rim edges. Choosing an outer rim edge turns the
3-run into a 4-run, introduing an extra minus. Choosing an inner rim edge turns the
3-run into a 1-run. Hene
(r) 2 + 2( 2 + )
1+ = 3 :
=
=
(3)
4
4
2
14
6
A 3-run.
Suppose that r = [i; i + 3℄ for some i. There are 5 edges whih overlap
r. Choosing an outer rim edge auses r to inrease in length by 1, introduing a new
minus. Choosing an inner rim edge auses the length of r to derease by 2: in this ase
this introdues a new pair. Finally, there is one internal edge fi + 1; i + 2g. Choosing
this edge produes a (1; 1)-split. This introdues two singletons and inreases the total
number of runs by 1, while removing two minuses. Adding these ontributions together
and dividing by 5, we obtain
(r) 2 + 2( 2 + Æ ) + ( 2 + + 2 )
4 + + 2 + 2Æ = 29 :
=
=
(4)
5
5
5
70
A 4-run.
Let r = [i; i + 4℄ for some i. There are six edges whih overlap r. Choosing
an outer rim edge auses r to inrease in length by 1. Choosing an inner rim edge
auses the length or r to derease by 2. There are two internal edges, fi + 1; i + 2g
and fi + 2; i + 3g. Choosing either of these edges produes a (1; 2)-split, deleting two
minuses, introduing a singleton and a pair, as well as inreasing the number of runs
by 1. Adding the ontributions from all of these edges together, and dividing by 6, we
obtain
3+++Æ = 5 :
(r) 2 4 + 2( 2 + + + Æ )
=
=
(5)
6
6
3
14
A 5-run.
Let r = [i; i + 5℄. There are 7 edges whih overlap r. If an outer rim edge is
hosen then r inreases in length by 1. If an inner rim edge is hosen then r dereases in
length by 2. There are 3 internal edges. Choosing fi + 1; i + 2g or fi + 3; i + 4g produes
a (1; 3)-split, dereasing the number of minuses by 2 while inreasing the number of
singletons and the number of runs by 1. Finally, hoosing the edge fi + 2; i + 3g produes
a (2; 2)-split, dereasing the number of minuses by 2, inreasing the number of runs by
1 and the number of pairs by 2. Combining this information we nd that
(r) 2 4 + 2( 2 + + ) + ( 2 + + 2Æ )
8 + 3 + 2 + 2Æ = 31 : (6)
=
=
7
7
7
98
A 6-run.
An
`-run,
where
`
7. Now suppose that r = [i; j ℄ is an `-run for some ` 7.
Choosing either of the two outer rim edges auses r to inrease in length by 1. Choosing
either of the two inner rim edges auses r to derease in length by 2. There are 4 internal
edges whih need areful analysis. Choosing either fi + 1; i + 2g or fj 2; j 1g produes a (1; ` 3)-split, introduing a singleton and inreasing the number of runs by 1,
while dereasing the number of minuses by 2. Similarly, hoosing either fi + 2; i + 3g or
fj 3; j 2g produes a (2; ` 4)-split, introduing a pair and inreasing the number
7
of runs by 1, while dereasing the number of minuses by 2. There are ` 7 other internal
edges whih split r into pairs of runs, eah of length at least 3. In eah ase, the number
of minuses dereases by 2 while the number of runs inreases by 1, but the numbers of
singletons and pairs are unhanged. We obtain
2 4 + 2( 2 + + ) + 2( 2 + + Æ) + (` 7)( 2 + )
(r )
=
`+1
`+1
4
6 2 2Æ
= 2
`+1
1
12 :
= 14
(7)
7(` + 1)
Now M is equal to the maximum of the right hand sides of (1){(7). It is easy to
verify that the maximum is 1=14, as stated.
For the remainder of this setion, the values of = 27=14, = 4=7 and Æ = 4=7
are xed. These values were hosen without explanation for use in the proof of Lemma 2
above. They were originally derived by setting = 2 , = 1=2 + and Æ = , and
hoosing to minimize M . The interested reader an easily verify that = 1=14 is the
optimal hoie.
We now show that the value M = 1=14 an still be used in Lemma 1 even when
the initial onguration has adjaent runs whih are separated by a single plus.
Suppose that X0 2 f1;
onlusion of Lemma 1 holds with
Lemma 3
1g
ontains both pluses and minuses. Then the
M
1:
= 14
. By Lemma 2, we have M = 1=14 whenever no two adjaent runs in X are
separated by a single plus. So now suppose that there are exatly s distint values
i 2 f0; : : : ; n 1g suh that X (i 1) = 1, X (i) = 1 and X (i + 1) = 1, where
s 1. We will all suh an i a rim vertex. Dene a new yle G0 = (V 0 ; E 0 ) from G by
splitting the vertex i into two new verties, i0 and i00 , for eah rim vertex i. Thus G0 is a
graph on n + s verties. Let the edges of G0 be obtained from the edges of G by deleting
the edges fi 1; ig, fi; i + 1g and adding the edges fi 1; i0g, fi0 ; i00g, fi0 ; i + 1g, for
eah rim vertex i. Thus G0 forms a yle on n + s verties. Construt the onguration
X 0 2 f1; 1gV from X by replaing the single plus at i by two pluses on i0 , i00 , for
eah rim vertex i. That is, let
Proof
0
0
0
0
0
0
(
X 0 (j )
X0 0 (j ) =
if j is unprimed,
otherwise:
1
8
0
By denition, X 0 has no two adjaent runs separated by a single plus. Note also that
L(X 0 ) = L(X ). Let X 0 be the result of running the Pavlov proess for one step from
X 0 . Combining Lemma 1 and Lemma 2, we see that
L(X 0 )
0
0
E [ (X )
(X )℄ 14(n + s) :
Suppose that we ould show that
0
0
0
1
0
1
X
2
E
[ (X 0 )
0
0
[ (X )
( X ) j e℄ :
1 X E [ (X 0 )
n + s e2E G
X
E [ (X )
n +1 s
e2E G
( X 0 ) j e℄
0
E
2
1
0
(8)
e E (G)
e E (G0 )
Then we would have
E
X
(X 0 ) j e℄ 1
[ (X 0 )
(X 0)℄ =
1
0
1
(
0
0
)
( X ) j e℄
1
=
n
(
n+s
E
0
)
[ (X )
(X )℄ :
1
0
From this we ould onlude that
n
[ (X 0) (X 0)℄
L(X 0 )
14(n + s)
= 14(L(nX+)s) :
Multiplying this inequality through by (n + s)=n proves the lemma. Hene it suÆes to
establish (8).
It is not diÆult to see that any edge whih does not overlap a rim vertex in X
makes the same ontribution in both the primed and unprimed settings. For these edges
e belong to both E (G) and E (G0 ), and
n+s
E
(X )℄ [ (X )
1
0
E
1
0
0
0
0
E
[ (X 0 )
(X 0) j e℄ = E [ (X )
1
0
(X ) j e℄ :
1
0
Therefore, to prove (8) it suÆes to prove that Y 0 > Y for all rim verties i, where
Y
= E [ (X )
1
(X ) j fi 1; ig℄ + E [ (X )
0
1
(X ) j fi; i + 1g℄
0
and
Y 0 = E [ (X1 0 )
(X 0 ) j fi 1; i0 g℄ + E [ (X 0)
0
1
9
(X 0 ) j fi00; i + 1g℄ :
0
(Clearly the edge fi0; i00 g makes no ontribution to E [ (X 0) (X 0)℄.) Let r and r
be the two runs whih are separated by i in X , and dene a and b by
1
0
1
2
0
a = j fj
2 f1; 2g j rj is a singletong j and b = j fj 2 f1; 2g j rj is a pairg j:
Then 0 a + b 2. Consider hoosing either fi 1; i0g or fi00 ; i + 1g for X 0. Clearly
0
either hoie will ause a minus to be introdued. For a of these hoies a singleton is
removed and a pair is reated, while for b of these hoies a pair is removed. Therefore
Y0 =2
a + aÆ
bÆ:
Now onsider hoosing either fi 1; ig or fi; i + 1g in X . The expeted hange of is
idential for either hoie. Choosing either of these edges introdues a minus, dereases
the number of runs by 1, and deletes all singletons or pairs whih are present in X .
The merged run whih is reated has length `(r ) + `(r ) + 1 3, so no singletons or
pairs are reated. Therefore
0
0
1
Y
= 2(1
2
bÆ ):
a
Hene, using the values of , and Æ we obtain
Y0
Y
= 2 + a( + Æ) + bÆ 2( + Æ) > 0;
proving the lemma.
3.2
Bounding the absorbtion time
P
We have xed = 27=14, = 4=7, Æ = 4=7. Reall that L(X ) = r2R X0 (`(r) + 1).
Combining Lemmas 1, 2, 3 we obtain
L(X )
E [ (X )℄ 1 14 (X )n (X );
(9)
for all X whih ontain both pluses and minuses. We need the following result.
0
0
1
0
(
)
0
0
Lemma 4
Let X
2 f1; 1gV
and let , L be as dened above. Then
(X ) 7L(4X )
if X ontains both pluses and minuses, while
for all X
6= X .
47 (X ) 7n
14
4
10
(10)
. First suppose that X ontains both pluses and minuses. Let (r) denote the
potential of the run r, for all r 2 R(X ). That is,
Proof
8
>
<1 + + if r is a singleton,
(r) = >2 + + Æ if r is a pair,
:
`(r) + otherwise.
Clearly
X
(X ) =
r
2R(X )
(r ):
It is not diÆult to hek that the inequality
(r ) 7
`(r) + 1 4
holds, with equality if and only if r is a singleton. Hene
X
X 7(`(r ) + 1)
7L(X ) ;
(X ) =
(r ) =
4
4
r 2R X
r 2R X
(
)
(
)
as stated. Now L(X ) denotes the number of edges whih overlap some run in X . Sine
there are at exatly n edges in G, it follows that
(X ) 74n
whenever X ontains both pluses and minuses. Sine the all-minuses onguration has
potential n, this proves the upper bound in (10). Finally, note that
(r) 47
14 ;
with equality if and only if r is a pair. Therefore the lowest potential of all ongurations
with both minuses and pluses is obtained on any onguration whih ontains a unique
run, this unique run being a pair. The all-minuses onguration has potential n, but we
have assumed that n is at least 4. This proves the lower bound in (10).
Combining (9) and the upper bound given in (10), we an
onlude that
2
E [ (X )℄ 1 49n (X )
(11)
for all X whih ontain both pluses and minuses. However, (11) also holds for the
all-minuses onguration, as follows. Let X~ be the all-minuses onguration, dened
by X~ (i) = 1 for all i. Let X~ be the result of running the Pavlov proes for one step
from X~ . No matter whih edge is hosen, the number of minuses dereases by 2 and the
Proof of Theorem 1.
1
0
0
0
1
0
11
h
i
(X~ )
(X~ ) = 2 = 1=14.
number of runs inreases from 0 to 1. Therefore E
Sine (X~ ) = n, we onlude that
h
i 1
2
~
~
E
(X ) = 1 14n (X ) < 1 49n (X~ );
as laimed.
So now let X 2 f1; 1gV satisfy X 6= X . Starting from X , run the Pavlov proess
for t steps and let the resulting state be Xt . By applying (11) iteratively t times we
obtain
t
t
2
2
E [ (Xt )℄ 1 49n
(X ) 1 49n 74n ;
1
0
0
1
0
0
0
0
0
0
using the rst statement of Lemma 4 for the last inequality. Let " > 0 be given. Let
= 47"=14. Whenever
7n
49
t n log
2
4
we have E [ (Xt )℄ . Using (10), any nonzero value of must be at least 47=14.
Applying Markov's Lemma, we have
47
Prob [ (Xt) 6= 0℄ = Prob (Xt) 14 14
47 = ":
This ompletes the proof.
4 Exponential absorbtion on the omplete graph
In this setion we prove Theorem 2, showing that the absortion time of the Pavlov
proess is exponential on the omplete graph Kn.
We will use the notation Xt 2 f1; 1gn to refer to a onguration after t steps of the
Pavlov proess. Let Nt be the number of nodes in Xt with label 1. Clearly Xt is equal
to the all-pluses absorbing state if and only if Nt = n. We will assume that N 0:61n.
The basis of our proof is the observation that the proess Nt is simple to analyse, even
if the proess Xt is not. Let pt , qt denote the labels of the two nodes hosen at step t.
Then the transition probabilities of Nt are given by the following rule:
0
Nt+1
8
< Nt
1 if ptqt = 1 (probability Nt(n Nt )= n );
if pt = qt = 1 (probability N = n ); = : Nt
Nt + 2 if pt = qt = 1 (probability n N = n ):
2
t
2
2
t
2
Let I denote the interval [0:61n; 0:7n℄.
12
2
Suppose that N 2 I. Let T = min ft > j N 62 I g. Then the proess
N ; : : : ; NT is stohastially dominated by the proess Q ; : : : ; QT where Qt is the simple
Markov hain in whih Q = N and for t ,
Lemma 5
Qt+1
8
< Qt
= : Qt
1
Qt + 2
with probability 0:35;
with probability 0:49;
with probability 0:16:
Proof. For t 2 [; T
1℄, the pair (Nt ; Qt ) an be hosen from the following joint
distribution whih satises Nt Qt .
8
(Nt 1; Qt 1) with probability 0:35;
>
>
>
>
with probability Nt (n Nt)= n 0:35;
< (Nt 1; Qt )
with probability [ N + n N ℄= n 0:16;
(Nt ; Qt ) = > (Nt ; Qt )
>
(
Nt ; Qt + 2)
with
probability
0
:16 n N = n ;
>
>
:
(Nt + 2; Qt + 2) with probability n N = n :
Note that the probabilities are all between 0 and 1 sine Nt 2 I .
+1
+1
+1
t
t
+1
2
2
2
t
2
t
2
2
2
2
To nish, we just need one more lemma. We show that if Qt is in the lower half of
the interval I , then it is very likely to exit I by dropping below 0:61n (rather than by
rising above 0:7n).
Lemma 6
Suppose that 0:61n Qt
0:65n for some t. Dene T
T = min ft0 > t j Qt 62 I g :
by
0
There exists a onstant d > 1 suh that
Prob [QT < 0:61n℄ 1
d n:
.
P
Let M = 3n. For every m 2 [1; : : : ; M ℄, let xm = Qt m Qt m and Sm = mi xi .
The random variables fxm g are independent of eah other sine, for all m, the variable
xm is fully determined by the random hoie made by the Markov hain Q at time
t + m. By denition, Qt m = Qt + Sm . Note that E[Sm ℄ = 0:03m. Using the value
of E[SM ℄, we nd that Prob(SM 0:04n) is equal to Prob(SM E[SM ℄ + 0:05n). By
a Cherno-Hoeding bound, this is at most exp( 2(0:05n) =(9M )), whih is less than
(1=2)d n if d is hosen to be suÆiently lose to 1. Similarly,
Proof
+
+
1
+
2
M
X
Prob(Sm 0:05n) m=1
M
X
Prob(Sm E[Sm℄ + 0:05n)
m=1
<
M
X
exp( 2(:05n) =(9m))
2
m=1
(1=2)d
13
n
;
=1
by hoosing d even loser to 1, if neessary. Thus, with probability at least 1
every m 2 [1; : : : ; M ℄ we have
Qt+m
and
Qt+M
d
n
, for
= Qt + Sm < 0:65n + 0:05n = 0:7n
= Qt + SM < 0:65n 0:04n = 0:61n:
To omplete the proof of Theorem 2, note that every time the hain enters the
interval I from below, the probability that it exits out the top of the region (rather than
the bottom) is at most d n. Thus, the probability that the hain reahes absorbtion in
as few as ((d + 1)=2)n visits to the region is at most
d+1
2d
n
= o(1):
5 Other topis
Several issues remain for further study. A natural extension of our results would be
to investigate the Pavlov proess for other families of graphs. Two other ases seem
partiularly interesting: degree-bounded trees and random graphs. Another possible
ingredient to our model is random noise (or player mistakes). The importane of this
parameter has been previously reognized in [8℄.
Referenes
[1℄ R. Axelrod, The Evolution of Cooperation, Basi Books, New York, 1984.
[2℄ C. Cooper and A. Frieze, Mixing properties of the Swendsen-Wang proess on lasses
of graphs, Random Strutures and Algorithms 15 (1999) 242{261.
[3℄ M. Dyer and C. Greenhill, On Markov hains for independent sets, Journal of Algorithms, 35 (2000) 17{49.
[4℄ J. E. Kittok, Emergent onventions and the struture of multi-agent systems, in
L. Nadel and D. Stein, eds., 1993 Letures in Complex systems: the proeedings of
the 1993 Complex systems summer shool, Santa Fe Institute Studies in the Sienes
of Complexity Leture Volume VI, Santa Fe Institute, Addison-Wesley, 1995.
[5℄ B. Hajek, Hitting-time and oupation-time bounds implied by drift analysis with
appliations, Adv. Appl. Prob. 14 (1982) 502{525.
14
[6℄ M. Luby, D. Randall and A. Sinlair, Markov hain algorithms for planar lattie strutures, Proeedings of the Symposium on Foundations of Computer Siene
(IEEE) 36 (1995) 150{159.
[7℄ M. Luby and E. Vigoda, Approximately ounting up to four, Proeedings of the ACM
Symposium on the Theory of Computing 29 (1997) 682{687.
[8℄ M. Nowak and K. Sigmund, A strategy of win-stay, lose-shift that outperforms titfor-tat in the Prisoner's Dilemma game, Nature 364 (1993), pp. 56-58.
[9℄ Y. Shoham and M. Tennenholtz, On the emergene of soial onventions: modelling,
analysis and simulations, Artiial Intelligene, 94 (1997), pp. 139{166.
15
```


text:
This function computes the density of a multivariate normal distribution.

## Usage

dmvnorm(x, mean, Sigma, log = FALSE)

## Arguments

x

A quantile vector of length n.

mean

The mean vector of length n.

Sigma

The covariance matrix of dimension n x n.

log

A boolean, if TRUE the logarithm of the density value is returned.

## Value

The density value.

## Examples

x = c(0,0)
mean = c(0,0)
Sigma = diag(2)
dmvnorm(x = x, mean = mean, Sigma = Sigma)
#> [1] 0.1591549
dmvnorm(x = x, mean = mean, Sigma = Sigma, log = TRUE)
#> [1] -1.837877

format: plain


text:
# Arpit has some marbles in his bag .He puts half of the marbles in a jar and one-sixth in his pocket . If total marbles are 10 more than twice of the remaining marbles in the bag, then find the number of marbles in the jar.

• 1
What are you looking for?


text:
# Math Help - Arithmetic Sequence

1. ## Arithmetic Sequence

For a positive integer, consider the arithmetic sequence:

n, n+19, n+38, n+57,.......

The number 2013 may or may not belong to the sequence. What is the smallest positive integer n such that 2013 does belong to the sequence?

A) 4 B) 7 C) 11 D) 14 E) 18

2. ## Re: Arithmetic Sequence

Originally Posted by ConnieLam
For a positive integer, consider the arithmetic sequence:

n, n+19, n+38, n+57,.......

The number 2013 may or may not belong to the sequence. What is the smallest positive integer n such that 2013 does belong to the sequence?

A) 4 B) 7 C) 11 D) 14 E) 18

This sequence is $\{x: x=n+19k, k\in \mathbb{N}$

Divide 2013 by 19 to get

$2013 = 105 \times 19 +18$

Thus 18 will be the smallest $n$ such that 2013 is an element of the sequence.

3. ## Re: Arithmetic Sequence

use formula for AP

a(m)=a+(m-1)d
=n+(m-1)19
now here we have to find n
so here if m=106
(m-1)*19=1995
and a(m)=2013 so m=106
if m=107 n=-1 which is not possible
so n=18


text:
The FHD/εppsilon Epoch of Reionisation power spectrum pipeline
Abstract Epoch of Reionisation (EoR) data analysis requires unprecedented levels of accuracy in radio interferometer pipelines. We have developed an imaging power spectrum analysis to meet these requirements and generate robust 21 cm EoR measurements. In this work, we build a signal path framework to mathematically describe each step in the analysis, from data reduction in the Fast Holographic Deconvolution (FHD) package to power spectrum generation in the ε ppsilon package. In particular, we focus on the distinguishing characteristics of FHD/ ε ppsilon: highly accurate spectral calibration, extensive data verification products, and end-to-end error propagation. We present our key data analysis products in detail to facilitate understanding of the prominent systematics in image-based power spectrum analyses. As a verification to our analysis, we also highlight a full-pipeline analysis simulation to demonstrate signal preservation and lack of signal loss. This careful treatment ensures that the FHD/ ε ppsilon power spectrum pipeline can reduce radio interferometric data to produce credible 21 cm EoR measurements.
Authors:
; ; ; ; ; ;
Award ID(s):
Publication Date:
NSF-PAR ID:
10203525
Journal Name:
Publications of the Astronomical Society of Australia
Volume:
36
ISSN:
1323-3580
2. ABSTRACT We quantify the effect of radio frequency interference (RFI) on measurements of the 21-cm power spectrum during the Epoch of Reionization (EoR). Specifically, we investigate how the frequency structure of RFI source emission generates contamination in higher order wave modes, which is much more problematic than smooth-spectrum foreground sources. Using a relatively optimistic EoR model, we find that even a single relatively dim RFI source can overwhelm the EoR power spectrum signal of $\sim 10\, {\rm mK}^2$ for modes $0.1 \ \lt k \lt 2 \, h\, {\rm Mpc}^{-1}$. If the total apparent RFI flux density in the final power spectrum integration is kept below 1 mJy, an EoR signal resembling this optimistic model should be detectable for modes $k \lt 0.9\, h\, {\rm Mpc}^{-1}$, given no other systematic contaminants and an error tolerance as high as 10 per cent. More pessimistic models will be more restrictive. These results emphasize the need for highly effective RFI mitigation strategies for telescopes used to search for the EoR.


text:
011-40705070  or
Select Board & Class
• Select Board
• Select Class

General Instructions:

(i) All questions in both sections are compulsory. However, there is internal choice in some questions.

(ii) Marks for questions are indicated against each question.

(iii) Question No.1-5 and 16-20 are very short answer questions carrying 1 mark each. They are required to be answered in one sentence.

(iv) Question No.6-8 and 21-23 are short answer questions carrying 3 marks each. Answers to them should not normally exceed 60 words each.

(v) Question No.9-11 and 24-26 are also short answer questions carrying 4 marks each. Answers to them should not normally exceed 70 words each.

(vi) Question No.12-15 and 27-30 are long answer questions carrying 6 marks each. Answers to them should not normally exceed 100 words each.

(vii) Answers should be brief and to the point and the above word limit be adhered to as far as possible.

Question 1
• Q1

Define market demand.    (1)

VIEW SOLUTION

• Q2

Average revenue and price are always equal under : (choose the correct alternative)   (1)

(a) perfect competition only
(b) monopolistic competition only
(c) monopoly only
(d) all market forms

VIEW SOLUTION

• Q3

State any one feature of oligopoly.    (1)

VIEW SOLUTION

• Q4

The demand of a commodity when measured through the expenditure approach is inelastic. A fall in its price will result in : (choose the correct alternative)   (1)

(a) no change in expenditure on it.
(b) increase in expenditure on it.
(c) decrease in expenditure on it.
(d) any one of the above.

VIEW SOLUTION

• Q5

As we move along a downward sloping straight line demand curve from left to right, price elasticity of demand : (choose the correct alternative)   (1)

(a) remains unchanged
(b) goes on falling
(c) goes on rising
(d) falls initially then rises

VIEW SOLUTION

• Q6

Explain the problem of 'what to produce.'     (3)

VIEW SOLUTION

• Q7

Show that demand of a commodity is inversely related to its price.     (3)

Explain with the help of utility analysis.

Or

Why is an indifference curve negatively sloped? Explain.

VIEW SOLUTION

• Q8

State the meaning and properties of production possibilities frontier.   (3)

VIEW SOLUTION

• Q9

A consumer consumes only two goods. Explain the conditions of consumer's equilibrium using utility analysis.  (4)

VIEW SOLUTION

• Q10

Explain the 'free entry and exit of firms' feature of monopolistic competition.    (4)

VIEW SOLUTION

• Q11

State different phases of the law of variable proportions on the basis to total product. Use diagram.  (4)

Or

Explain the geometric method of measuring price elasticity of supply. Use diagram.

VIEW SOLUTION

• Q12

Given below is the cost schedule of a product produced by a firm. The market price per unit of the product at all levels of output is Rs. 12. Using marginal cost and marginal revenue approach, find out the level of equalibrium output. Give reasons for your answer:    (6)

 Output (Units) 1 2 3 4 5 6 Average Cost (Rs.) 12 11 10 10 10.4 11

VIEW SOLUTION

• Q13

When price of a commodity X falls by 10 per cent, its demand rises from 150 units to 180 units. Calculate is price elasticity of demand. How much should be the percentage fall in its price so that its demand rises from 150 to 210 units?    (6)

VIEW SOLUTION

• Q14

X and Y are complementary goods. The price of Y falls. Explain the chain of effects of this change in the market of X.

Or

Explain the chain of effect of excess demand of a good on it equilibrium price.   (6)

VIEW SOLUTION

• Q15

Complete the following table :    (6)

 Output units Total cost Rs. Average variable cost Rs. Marginal cost Rs. Average fixed cost Rs. 0 30 1 ... ... 20 ... 2 68 ... ... ... 3 84 18 ... ... 4 ... ... 18 ... 5 125 19 ... 6

VIEW SOLUTION

• Q16

Give the meaning of involuntary unemployment.  (1)

VIEW SOLUTION

• Q17

What is revenue deficit?  (1)

VIEW SOLUTION

• Q18

The ratio of total deposits that a commercial bank has to keep with Reserve Bank of India is called : (choose the correct alternative)  (1)

(a) Statutory liquidity ratio

(b) Deposit ratio

(c) Cash reserve ratio

(d) Legal reserve ratio

VIEW SOLUTION

• Q19

Give the meaning of balance of payments.  (1)

VIEW SOLUTION

• Q20

Aggregate demand can be increased by : (choose the correct alternative)  (1)

(a) increasing bank rate

(b) selling government securities by Reserve Bank of India

(c) increasing cash reserve ratio

(d) none of the above

VIEW SOLUTION

• Q21

Distinguish between final goods and intermediate goods. Give an example of each.  (3)

VIEW SOLUTION

• Q22

Explain the basis of classifying taxes into direct and indirect tax. Give examples.  (3)

VIEW SOLUTION

• Q23

Explain the store of value function of money.  (3)

Or

State the meaning and components of money supply.

VIEW SOLUTION

• Q24

Explain 'banker to the government' function of the central bank.  (4)

Or

Explain the role of reverse repo rate in controlling money supply.

VIEW SOLUTION

• Q25

Explain how government budget can be used to influence distribution of income?  (4)

VIEW SOLUTION

• Q26

An economy is in equilibrium. From the following data about an economy, calculate investment expenditure:  (4)

(i) Income = 10000

(ii) Marginal propensity to consume = 0.9

(iii) Autonomous consumption = 100

VIEW SOLUTION

• Q27

Assuming that increase in investment is Rs. 800 crore and marginal propensity to consume is 0.8, explain the working of multiplier.  (6)

VIEW SOLUTION

• Q28

Why does the demand for foreign currency fall and supply rises when its price rises? Explain.  (6)

VIEW SOLUTION

• Q29

Calculate (a) national income (b) net national disposable income:  (6)

 Rs. in crores (i) Net factor income to abroad (–) 50 (ii) Net indirect taxes 800 (iii) Net current transfers from rest of the world 100 (iv) Net imports 200 (v) Private final consumption expenditure 5000 (vi) Government final consumption expenditure 3000 (vii) Gross domestic capital formation 1000 (viii) Consumption of fixed capital 150 (ix) Change in stock (–) 50 (x) Mixed income 4000 (xi) Scholarship to students 80

VIEW SOLUTION

• Q30

Explain 'non-monetary exchanges' as a limitation of using gross domestic product as an index of welfare of a country.  (6)

Or

How will you treat the following while estimating domestic product of a country? Give reasons for your answer:

(a) Profits earned by branches of country's bank in other countries

(b) Gifts given by an employer to his employees on independence day

(c) Purchase of goods by foreign tourists

VIEW SOLUTION

Board Papers 2014, Board Paper Solutions 2014, Sample Papers for CBSE Board, CBSE Boards Previous Years Question Paper, Board Exam Solutions 2014, Board Exams Solutions Maths, Board Exams Solutions English, Board Exams Solutions Hindi, Board Exams Solutions Physics, Board Exams Solutions Chemistry, Board Exams Solutions Biology, Board Exams Solutions Economics, Board Exams Solutions Business Studies, Maths Board Papers Solutions, Science Board Paper Solutions, Economics Board Paper Solutions, English Board Papers Solutions, Physics Board Paper Solutions, Chemistry Board Paper Solutions, Hindi Board Paper Solutions, Political Science Board Paper Solutions, Answers of Previous Year Board Papers, Delhi Board Paper Solutions, All India Board Papers Solutions, Abroad/Foreign Board Paper Solutions, cbse class 12 board papers, Cbse board papers with solutions, CBSE solved Board Papers, ssc board papers.


text:
# regression methods in biostatistics datasets

Some are available in Excel and ASCII ( .csv) formats and Stata (.dta).Methods for retrieving and importing datasets may be found here.If you need one of the datasets we maintain converted to a non-S format please e-mail mailto:charles.dupont@vanderbilt.edu to make a request. \frac{ \partial \ln L(p)}{\partial p} &=& \sum_i y_i \frac{1}{p} + (n - \sum_i y_i) \frac{-1}{(1-p)} = 0\\ \end{eqnarray*}\], $\begin{eqnarray*} That is, the odds of survival for a patient with log(area+1)= 1.90 is 2.9 times higher than the odds of survival for a patient with log(area+1)= 2.0.). The problem with this strategy is that it may be that the 75 subjects Bruno knows are already included in the 85 that Sage knows, and therefore, Bruno does not provide any knowledge beyond that of Sage. We applied three types of methods to these two datasets. This course provides basic knowledge of logistic regression and analysis of survival data. \end{eqnarray*}$ It seems that a transformation of the data is in place. p-value &=& P(\chi^2_1 \geq 190.16) = 0 We can output the deviance ( = K - 2 * log-likelihood) for both the full (maximum likelihood!) p(x=1.75) &=& \frac{e^{22.7083-10.6624\cdot 1.75}}{1+e^{22.7083 -10.6624\cdot 1.75}} = 0.983\\ A short summary of the book is provided elsewhere, on a short post (Feb. 2008). \end{eqnarray*}\]. BIC: Bayesian Information Criteria = $$-2 \ln$$ likelihood $$+p \ln(n)$$. $\begin{eqnarray*} The logistic regression model is correct! \mathrm{logit}(p(x_1, x_2) ) &=& \beta_0 + \beta_1 x_1 + \beta_2 x_2\\ We will study Linear Regression, Polynomial Regression, Normal equation, gradient descent and step by step python implementation. The explanatory variable of interest was the length of the bird. Applied Logistic Regression is an ideal choice." \[\begin{eqnarray*} Ramsey, F., and D. Schafer. \mathrm{logit}(p) = \ln \bigg( \frac{p}{1-p} \bigg) \mbox{old} & \mbox{65+ years old}\\ \end{cases} The datasets below will be used throughout this course. \end{eqnarray*}$ While a first course in statistics is assumed, a chapter reviewing basic statistical methods is included. Supplemented with numerous graphs, charts, and tables as well as a Web site for larger data sets and exercises, Biostatistical Methods: The Assessment of Relative Risks is an excellent guide for graduate-level students in biostatistics and an invaluable reference for biostatisticians, applied statisticians, and epidemiologists. \end{eqnarray*}\], $\begin{eqnarray*} A Receiver Operating Characteristic (ROC) Curve is a graphical representation of the relationship between. 0 &=& (1-p) \sum_i y_i + p (n-\sum_i y_i) \\ Being underspecified is the worst case scenario because the model ends up being biased and predictions are wrong for virtually every observation. This method of estimating the parameters of a regression line is known as the method of least squares. \mbox{deviance} = \mbox{constant} - 2 \ln(\mbox{likelihood}) A: Let’s say we use prob=0.25 as a cutoff: \[\begin{eqnarray*} Bayesian and Frequentist Regression Methods (Springer Series in Statistics) - Kindle edition by Wakefield, Jon. Decide on the type of model that is needed in order to achieve the goals of the study. Note 3 gives the probability of failure. Continue removing variables until all variables are significant at the chosen. &=& -2 \ln \bigg( \frac{L(p_0)}{L(\hat{p})} \bigg)\\ The validation set is used for cross-validation of the fitted model. L(\underline{y} | b_0, b_1, \underline{x}) &=& \prod_i \frac{1}{\sqrt{2 \pi \sigma^2}} e^{(y_i - b_0 - b_1 x_i)^2 / 2 \sigma}\\ x_1 &=& \begin{cases} \end{eqnarray*}$, $\begin{eqnarray*} H_0: && \beta_1 =0\\ Note that the opposite classifier to (H) might be quite good! \[\begin{eqnarray*} where $$\nu$$ is the number of extra parameters we estimate using the unconstrained likelihood (as compared to the constrained null likelihood). Wand. \[\begin{eqnarray*} Below I’ve given some different relationships between x and the probability of success using $$\beta_0$$ and $$\beta_1$$ values that are yet to be defined. To maximize the likelihood, we use the natural log of the likelihood (because we know we’ll get the same answer): x &=& - \beta_0 / \beta_1\\ There’s not a data analyst out there who hasn’t made the mistake of skipping this step and later regretting it when a data point was found in error, thereby nullifying hours of work. \end{eqnarray*}$, $\begin{eqnarray*} There might be a few equally satisfactory models. \beta_0 + \beta_1 x &=& 0\\ Recall how we estimated the coefficients for linear regression. &=& \mbox{deviance}_0 - \mbox{deviance}_{model}\\ \end{eqnarray*}$, $\begin{eqnarray*} \hat{p(x)} &=& \frac{e^{22.708 - 10.662 x}}{1+e^{22.708 - 10.662 x}}\\ Ours is called the logit. \beta_{1s} &=& \beta_1 + \beta_3 With two consultants you might choose Sage first, and for the second option, it seems reasonable to choose the second most knowledgeable classmate (the second most highly associated variable), for example Bruno, who knows 75 topics. \end{cases} \mbox{simple model} &&\\ \mbox{specificity} &=& 61 / 127 = 0.480, \mbox{1 - specificity} = FPR = 0.520\\ The odds ratio $$\hat{OR}_{1.90, 2.00}$$ is given by p(k) &=& 1-(1-\lambda)^k\\ Not logged in A brief introduction to regression analysis of complex surveys and notes for further reading are provided. Linear Regression Datasets for Machine Learning. x_1 &=& \begin{cases} where $$y_1, y_2, \ldots, y_n$$ represents a particular observed series of 0 or 1 outcomes and $$p$$ is a probability $$0 \leq p \leq 1$$. &=& \mbox{deviance}_{null} - \mbox{deviance}_{residual}\\ The participants are postmenopausal women with a uterus and with CHD. It gives you a sense of whether or not you’ve overfit the model in the building process.) H_0: && \beta_1 =0\\ &=& -2 \ln \bigg( \frac{L(p_0)}{L(\hat{p})} \bigg)\\ \mbox{specificity} &=& 120/127 = 0.945, \mbox{1 - specificity} = FPR = 0.055\\ e^{\beta_1} &=& \bigg( \frac{p(x+1) / [1-p(x+1)]}{p(x) / [1-p(x)]} \bigg)\\ \end{eqnarray*}$, $\begin{eqnarray*} The table below shows the result of the univariate analysis for some of the variables in the dataset. Model building is definitely an art." \mbox{old OR} &=& e^{0.2689 + -0.2505} = 1.018570\\ p(x) = \frac{e^{\beta_0 + \beta_1 x}}{1+e^{\beta_0 + \beta_1 x}} (SBH). P(X=1 | p = 0.9) &=& 0.0036 \\ How is it interpreted? It turns out that we’ve also maximized the normal likelihood. &=& \mbox{deviance}_{null} - \mbox{deviance}_{residual}\\ \mbox{old OR} &=& e^{0.2689 + -0.2505} = 1.018570\\ \hat{OR}_{1.90, 2.00} = e^{-10.662} (1.90-2.00) = e^{1.0662} = 2.904 &=& p^{y_1}(1-p)^{1-y_1} p^{y_2}(1-p)^{1-y_2} \cdots p^{y_n}(1-p)^{1-y_n}\\ 1 - p(x) = \frac{1}{1+e^{\beta_0 + \beta_1 x}} “Snoring as a Risk Factor for Disease: An Epidemiological Survey” 291: 630–32. That is because age and smoking status are so highly associated (think of the coin example). Consider the following data set collected from church offering plates in 62 consecutive Sundays. \end{eqnarray*}$, $\begin{eqnarray*} L(\hat{\underline{p}}) > L(p_0) An Introduction to Categorical Data Analysis. Statistics for Biology and Health &=& \sum_i y_i \ln(p) + (n- \sum_i y_i) \ln (1-p)\\ where $$\nu$$ represents the difference in the number of parameters needed to estimate in the full model versus the null model. The logistic regression model is a generalizedlinear model. \end{eqnarray*}$, $\begin{eqnarray*} This is done by specifying two values, $$\alpha_e$$ as the $$\alpha$$ level needed to enter the model, and $$\alpha_l$$ as the $$\alpha$$ level needed to leave the model. Regardless, we can see that by tuning the functional relationship of the S curve, we can get a good fit to the data. \beta_1 &=& \mathrm{logit}(p(x+1)) - \mathrm{logit}(p(x))\\ \ln L(\underline{p}) &=& \sum_i y_i \ln\Bigg( \frac{e^{b_0 + b_1 x_i}}{1+e^{b_0 + b_1 x_i}} \Bigg) + (1- y_i) \ln \Bigg(1-\frac{e^{b_0 + b_1 x_i}}{1+e^{b_0 + b_1 x_i}} \Bigg)\\ advantage of integrating multiple diverse datasets over analyzing them individually. \end{eqnarray*}$, $\begin{eqnarray*} Start with the full model including every term (and possibly every interaction, etc.). Recall, when comparing two nested models, the differences in the deviances can be modeled by a $$\chi^2_\nu$$ variable where $$\nu = \Delta p$$. \mbox{young, middle, old OR} &=& e^{ 0.3122} = 1.3664\\ \ln (p(x)) = \beta_0 + \beta_1 x Where $$p(x)$$ is the probability of success (here surviving a burn). 3rd ed. Also problematic is that the model becomes unnecessarily complicated and harder to interpret. \mbox{middle} & \mbox{45-64 years old}\\ 5, 6 Undetected batch effects can have major impact on subsequent conclusions in both unsupervised and supervised analysis. A first idea might be to model the relationship between the probability of success (that the patient survives) and the explanatory variable log(area +1) as a simple linear regression model. Before we do that, we can define two criteria used for suggesting an optimal model. A better strategy is to select the second not by considering what he or she knows regarding the entire agenda, but by looking for the person who knows more about the topics than the first does not know (the variable that best explains the residual of the equation with the variables entered). Consider false positive rate, false negative rate, outliers, parsimony, relevance, and ease of measurement of predictors. $$e^{\beta_1}$$ is the odds ratio for dying associated with a one unit increase in x. The general linear regression model, ANOVA, robust alternatives based on permutations, model building, resampling methods (bootstrap and jackknife), contingency tables, exact methods, logistic regression. Bayesian and Frequentist Regression Methods Website. In general, the method of least squares is applied to obtain the equation of the regression line. \end{eqnarray*}$, $\begin{eqnarray*} For logistic regression, we use the logit link function: We see above that the logistic model imposes a constant OR for any value of $$X$$ (and not a constant RR). Y &\sim& \mbox{Bernoulli}(p)\\ Tied pairs occur when the observed survivor has the same estimated probability as the observed death. Over 10 million scientific documents at your fingertips. p(x=1.75) &=& \frac{e^{22.7083-10.6624\cdot 1.75}}{1+e^{22.7083 -10.6624\cdot 1.75}} = 0.983\\ and reduced (null) models. Select the models based on the criteria we learned, as well as the number and nature of the predictors. Let’s say this is Sage who knows 85 topics. \end{eqnarray*}$ &=& \sum_i (Y_i - (b_0 + b_1 X_i))^2 B: Let’s say we use prob=0.7 as a cutoff: $\begin{eqnarray*} Example 5.4 Suppose that you have to take an exam that covers 100 different topics, and you do not know any of them. \[\begin{eqnarray*} &=& -2 \Bigg[ \ln \bigg( (0.25)^{y} (0.75)^{n-y} \bigg) - \ln \Bigg( \bigg( \frac{y}{n} \bigg)^{y} \bigg( \frac{(n-y)}{n} \bigg)^{n-y} \Bigg) \Bigg]\\ p(x) &=& \beta_0 + \beta_1 x However, the scatterplot of the proportions of patients surviving a third-degree burn against the explanatory variable shows a distinct curved relationship between the two variables, rather than a linear one. This new book provides a unified, in-depth, readable introduction to the multipredictor regression methods most widely used in biostatistics: linear models for continuous outcomes, logistic models for binary outcomes, the Cox model for right-censored survival times, repeated-measures models for longitudinal and hierarchical outcomes, and generalized linear models for counts and other outcomes. Note 4 Every type of generalized linear model has a link function. They are: Decide which explanatory variables and response variable on which to collect the data. \end{eqnarray*}$, $\begin{eqnarray*} 2012. \end{eqnarray*}$ 0 & \text{otherwise} \\ The big model (with all of the interaction terms) has a deviance of 3585.7; the additive model has a deviance of 3594.8. \end{cases} This dataset includes data taken from cancer.gov about deaths due to cancer in the United States. \end{eqnarray*}\], $\begin{eqnarray*} Multivariable logistic regression. We can show that if $$H_0$$ is true, OR &=& \mbox{odds dying if } (x_1, x_2) / \mbox{odds dying if } (x_1^*, x_2^*) = \frac{e^{\beta_0 + \beta_1 x_1 + \beta_2 x_2}}{e^{\beta_0 + \beta_1 x_1^* + \beta_2 x_2^*}}\\ How do we model? (The fourth step is very good modeling practice. x_2 &=& \begin{cases} Graduate Prerequisites: The biostatistics and epidemiology MPH core course requirements and BS723 or BS852. &=& -2 [ \ln(0.0054) - \ln(0.0697) ] = 5.11\\ Maximum likelihood estimates are functions of sample data that are derived by finding the value of $$p$$ that maximizes the likelihood functions. Using the burn data, convince yourself that the RR isn’t constant. &=& \frac{1+e^{b_0}e^{b_1 x}e^{b_1}}{e^{b_1}(1+e^{b_0}e^{b_1 x})}\\ Evaluate the selected models for violation of the model conditions. Introductory course in the analysis of Gaussian and categorical data. G &=& 525.39 - 335.23 = 190.16\\ http://www.r2d3.us/visual-intro-to-machine-learning-part-1/. \end{eqnarray*}$. It is quite common to have binary outcomes (response variable) in the medical literature. \beta_{1f} &=& \beta_1\\ Not affiliated Hulley, S., D. Grady, T. Bush, C. Furberg, D. Herrington, B. Riggs, and E. Vittinghoff. John Wiley; Sons, New York. \end{eqnarray*}\], $\begin{eqnarray*} We will use the variables age, weight, diabetes and drinkany. What does it mean that the interaction terms are not significant in the last model? http://statmaster.sdu.dk/courses/st111. If classifier randomly guess, it should get half the positives correct and half the negatives correct. Or, we can think about it as a set of independent binary responses, $$Y_1, Y_2, \ldots Y_n$$. \end{eqnarray*}$, $\begin{eqnarray*} \end{eqnarray*}$. They also show that these regression methods deal with confounding, mediation, and interaction of causal effects in essentially the same way. Part of Springer Nature. This service is more advanced with JavaScript available, Part of the Using the additive model above: -2 \ln \bigg( \frac{\max L_0}{\max L} \bigg) \sim \chi^2_\nu The second type is MetaLasso, and our proposed method is as the third type. Sage. In many situations, this will help us from stopping at a less than desirable model. && \\ GLM: g(E[Y | X]) = \beta_0 + \beta_1 X \mbox{& a loglikelihood of}: &&\\ P( \chi^2_1 \geq 5.11) &=& 0.0238 \end{eqnarray*}\] Y_i \sim \mbox{Bernoulli} \bigg( p(x_i) = \frac{e^{\beta_0 + \beta_1 x_i}}{1+ e^{\beta_0 + \beta_1 x_i}}\bigg) © 2020 Springer Nature Switzerland AG. \hat{OR}_{1.90, 2.00} = e^{-10.662} (1.90-2.00) = e^{1.0662} = 2.904 L(\hat{\underline{p}}) > L(p_0) We are going to discuss how to add (or subtract) variables from a model. This method follows in the same way as Forward Regression, but as each new variable enters the model, we check to see if any of the variables already in the model can now be removed. $\begin{eqnarray*} A large cross-validation AUC on the validation data is indicative of a good predictive model (for your population of interest). If it guesses 90% of the positives correctly, it will also guess 90% of the negatives to be positive. If there are too many, we might just look at the correlation matrix. The training set, with at least 15-20 error degrees of freedom, is used to estimate the model. The course will cover extensions of these methods to correlated data using generalized estimating equations. \frac{p(x)}{1-p(x)} = e^{\beta_0 + \beta_1 x} \end{eqnarray*}$ RSS &=& \sum_i (Y_i - \hat{Y}_i)^2\\ \end{eqnarray*}\] \end{cases}\\ RSS &=& \sum_i (Y_i - \hat{Y}_i)^2\\ We can estimate the SE (Wald estimates via Fisher Information). Datasets Most of the datasets on this page are in the S dumpdata and R compressed save() file formats. \end{eqnarray*}\], $\begin{eqnarray*} \[\begin{eqnarray*} &=& \bigg( \frac{1}{2 \pi \sigma^2} \bigg)^{n/2} e^{\sum_i (y_i - b_0 - b_1 x_i)^2 / 2 \sigma}\\ \mbox{interaction model} &&\\ e^{0} &=& 1\\ Faculty in UW Biostatistics are developing new statistical learning methods for the analysis of large-scale data sets, often by exploiting the data’s inherent structure, such as sparsity and smoothness. Contains notes on computations at the end of most chapters, covering the use of Excel, SAS, and others. Don’t worry about building the model (classification trees are not a topic for class), but check out the end where they talk about predicting on test and training data. p(x) &=& 1 - \exp [ -\exp(\beta_0 + \beta_1 x) ] But if the new exam asks different questions about the same material, you would be ill-prepared and get a much lower mark than with a more traditional preparation. We use cookies on Kaggle to deliver our services, analyze web traffic, and improve your experience on the site. The method was based on multitask regression model enforced with sparse group \[\begin{eqnarray*} (see log-linear model below, 5.1.2.1 ). \[\begin{eqnarray*} The second half introduces bivariate and multivariate methods, emphasizing contingency table analysis, regression, and analysis of variance. For now, we will try to predict whether the individuals had a medical condition, medcond. \end{eqnarray*}$, $\begin{eqnarray*} Consider looking at all the pairs of successes and failures. (Agresti 1996) states that the likelihood-ratio test is more reliable for small sample sizes than the Wald test. 1 & \mbox{ smoke}\\ Dunn. To build a model (model selection). 0 & \text{otherwise} \\ \mbox{sensitivity} &=& TPR = 265/308 = 0.860\\ \[\begin{eqnarray*} The logistic regression model is overspecified. Both techniques suggest choosing a model with the smallest AIC and BIC value; both adjust for the number of parameters in the model and are more likely to select models with fewer variables than the drop-in-deviance test. However, within each group, the cases were more likely to smoke than the controls. Generally, extraneous variables are not so problematic because they produce models with unbiased coefficient estimators, unbiased predictions, and unbiased variance estimates. 1995. 1985. \[\begin{eqnarray*} One idea is to start with an empty model and adding the best available variable at each iteration, checking for needs for transformations. P(X=1 | p = 0.5) &=& 0.25\\ G &=& 3597.3 - 3594.8 =2.5\\ \end{eqnarray*}$ && \\ Note that the x-axis is some continuous variable x while the y-axis is the probability of success at that value of x. biostat/vgsm/data/hersdata.txt, and it is described in Regression Methods in Biostatistics, page 30; variable descriptions are also given on the book website http://www.epibiostat.ucsf.edu/biostat/ vgsm/data/hersdata.codebook.txt. \end{eqnarray*}\], $\begin{eqnarray*} \end{eqnarray*}$, $\begin{eqnarray*} x_2 &=& \begin{cases} \end{eqnarray*}$ That is, a linear model as a function of the expected value of the response variable. &=& \bigg( \frac{1}{2 \pi \sigma^2} \bigg)^{n/2} e^{\sum_i (y_i - b_0 - b_1 x_i)^2 / 2 \sigma}\\ \hat{RR}_{1, 2} &=& 1.250567\\ Recall that logistic regression can be used to predict the outcome of a binary event (your response variable). \mbox{young OR} &=& e^{0.2689 + 0.2177} = 1.626776\\ Though it is important to realize that we cannot find estimates in closed form. P(X=1 | p = 0.9) &=& 0.0036 \\ \mbox{interaction model} &&\\ The methods introduced include robust estimation, testing, model selection, model check and diagnostics. (Technometrics, February 2002) "...a focused introduction to the logistic regression model and its use in methods for modeling the relationship between a categorical outcome variable and a … p_0 &=& \frac{e^{\hat{\beta}_0}}{1 + e^{\hat{\beta}_0}} Cengage Learning. \end{eqnarray*}\]. Is a different picture provided by considering odds? Suppose that we build a classifier (logistic regression model) on a given data set. What does that even mean? Robust Methods in Biostatistics proposes robust alternatives to common methods used in statistics in general and in biostatistics in particular and illustrates their use on many biomedical datasets. Randomly divide the data into a training set and a validation set: Using the training set, identify several candidate models: And, most of all, don’t forget that there is not necessarily only one good model for a given set of data. \end{cases} We’d like to know how well the model classifies observations, but if we test on the samples at hand, the error rate will be much lower than the model’s inherent accuracy rate. \end{eqnarray*}\], $\begin{eqnarray*} For control purposes - that is, the model will be used to control a response variable by manipulating the values of the predictor variables. Note that tidy contains the same number of rows as the number of coefficients. Fan, J., N.E. If you set it to be large, you will wander around for a while, which is a good thing, because you will explore more models, but you may end up with variables in your model that aren’t necessary. 1 & \text{for always} \\ (Think about Simpson’s Paradox and the need for interaction.). This new book provides a unified, in-depth, readable introduction to the multipredictor regression methods most widely used in biostatistics: linear models for continuous outcomes, logistic models for binary outcomes, the Cox model for right-censored survival times, repeated-measures models for longitudinal and hierarchical outcomes, and generalized linear models for counts and other outcomes. $$\beta_0$$ now determines the location (median survival). 0 & \mbox{ don't smoke}\\ augment contains the same number of rows as number of observations. Another strategy for model building. Therefore, if its possible, a scatter plot matrix would be best. 1 & \text{for often} \\ \hat{p} &=& \frac{ \sum_i y_i}{n} 2nd ed. Because we will use maximum likelihood parameter estimates, we can also use large sample theory to find the SEs and consider the estimates to have normal distributions (for large sample sizes). \mathrm{logit}(p(x)) &=& \beta_0 + \beta_1 x\\ Unsurprisingly, there are many approaches to model building, but here is one strategy, consisting of seven steps, that is commonly used when building a regression model. The general linear regression model, ANOVA, robust alternatives based on permutations, model building, resampling methods (bootstrap and jackknife), contingency tables, exact methods, logistic regression. \end{eqnarray*}$, Our new model becomes: H_0:&& p=0.25\\ In fact, usually, we use them to test whether the coefficients are zero: $\begin{eqnarray*} -2 \ln \bigg( \frac{\max L_0}{\max L} \bigg) \sim \chi^2_\nu \mbox{specificity} &=& 92/127 = 0.724, \mbox{1 - specificity} = FPR = 0.276\\ \[\begin{eqnarray*}GLM: g(E[Y | X]) = \beta_0 + \beta_1 X\end{eqnarray*}$where $$g(\cdot)$$is the … If you could bring only one consultant, it is easy to figure out who you would bring: it would be the one who knows the most topics (the variable most associated with the answer). \ln[ - \ln (1-p(k))] &=& \ln[-\ln(1-\lambda)] + \ln(k)\\ gamma: Goodman-Kruskal gamma is the number of concordant pairs minus the number of discordant pairs divided by the total number of pairs excluding ties.


text:
# Let’s Add Some More Noise

Like in my yesterday’s post mentioned, there are more kinds of noise. So let’s first load today’s picture and then add some multiplicative noise!

library(jpeg)
pigeonBW <- pigeon[,,1]
plot(as.raster(pigeonBW))

Oh look it’s a pigeon on a lantern. I wonder what this little guy was thinking? But let’s not dwell on this. Rather let’s think how we can scramble up this picture!
I will first try multiplicative normal distributed noise, which is pretty straight forward, if you followed yesterday’s post.

set.seed(1)
pigeonNormalNoise <- pigeonBW * (1 + rnorm(length(pigeonBW), sd = sd(pigeonBW)))
pigeonNormalNoise[pigeonNormalNoise > 1] <- 1
pigeonNormalNoise[pigeonNormalNoise < 0] <- 0
plot(as.raster(pigeonNormalNoise))

Can you see the difference to the additive noise from yesterday? Indeed the darker areas of the pictures seem nearly untouched from the noise. That’s because the intensity of the noise is now dependent on the intensity of the pixel. And intensity is what dark pixels are lacking… So to speak.

But it’s really annoying and redundant to have to write the same stuff over and over again, isn’t it? So let’s do, what a Computer Scientist is best in. Let’s generalize some methods.
But where to start?

In my view it would be useful to have some kind of an (black and white) image class, which saves the image and operations on it. Hence the process would also be reproducible, which is always nice.

imageBW <- setClass("imageBW", slots=list(original="matrix", current="matrix", operations="list"))
imageBWFromJpeg <-function(pathToJpeg){
require(jpeg)
imageBW <- image[,,1]
return(new("imageBW", original = imageBW, current = imageBW, operations = list()))
}
plot.imageBW <- function(object){
plot(as.raster(object@current))}

As an illustration I also overwrote the default plot function. This makes our lives even easier. In the next step I’ll implement the different noise functions. There are probably more generalized ways of doing so, but for now this will suffice. I also haven’t come up with a good way of storing the done operations yet. So I’ll probably also do that another day.

cropPixels<- function(object){
object@current[object@current > 1] <- 1
object@current[object@current < 0] <- 0
return(object)
}
slot(object, "current") <- slot(object, "current") +
runif(length(slot(object, "current")), min = -1, max = 1)
return(cropPixels(object))
}
addNormalNoise <- function(object, sd = NULL){
if(is.null(sd)){
object@current <- object@current + rnorm(length(object@current), sd = sd(object@current))
}else{
object@current <- object@current + rnorm(length(object@current), sd = sd)
}
return(cropPixels(object))
}
multiplyUnifNoise <- function(object){
object@current <- object@current * (1 + runif(length(object@current), min = -1, max = 1))
return(cropPixels(object))
}
multiplyNormalNoise <- function(object, sd = NULL){
if(is.null(sd)){
object@current <- object@current * ( 1 + rnorm(length(object@current),
sd = sd(object@current)))
}else{
object@current <- object@current * ( 1 + rnorm(length(object@current),
sd = sd))
}
return(cropPixels(object))
}

For the future I would also like to have this working with infix operators. Meaning that I could do stuff like image <- image + normalNoise(...) or image <- image * (1 + normalNoise(...)) so that I have a neat little grammar for working with images. However for the moment those functions will do the job. Now let us make use of the newly implemented methods and add a lot of noise to the picture.

image <- imageBWFromJpeg("pigeon.jpg")
image <- multiplyUnifNoise(image)


text:
BarCamp 2017

the unconference in Harrisburg, PA

This is random notes gathered while attending the Harrisburg BarCamp 2017.

Small Data, Big Results

http://noboundsdigital.com

Problems with big data, example of being marketed to a product/service even when the data is incorrect. (new baby marketing when family lost the child)

Big Data is often dumb data, . . .

October 14, 2017

Using Jekyll: Step 0

The very start of learning Jekyll along with a few struggles.

Over the past year I have been hearing about Jekyll as a simple solution for creating static content for a websites/blogs without having to worry about a database. I think today is the day I actually do something about this and get something up and running.

Step -1

As I do with most things I dive right in (sometimes reading . . .

March 27, 2016

Hello AngularJs 2

C_LOG_32

I have been doing angular development for almost two years now building/maintaining an online banking application. We first started off with version 1 of angularjs and slowly upgraded to 1.2.8 which currently is considered legacy . We need to make the movement to push forward now that we "officially" dropped support of IE8 (people . . .

January 04, 2016

Drawing Scratchy

C_LOG_31

Tonight it was time to draw again which I haven't done in quite a few days. Continuing with my Simpsons sketches I drew Scratchy.

January 02, 2016

Pi with RealVNC

bonus action shot of VsCode, C_LOG_30

I was always unsure about using tightvncserver, it worked but got a strange error when remotely connecting to my pi. I might have had it configured wrong but decided to try out another package. Before I can do any of this I need to disable and remove tightvnc from running on startup which brought me to this answer.

stop the service
. . .

December 31, 2015

Random Pi/Linux Learning

randr? C_LOG_29

Tonight I was feeling scatter brained on what to learn about and came up with a few random ideas which so far were unsuccessful.

• I tried building vscode on a raspberry pi inspired by Marc Gravell. I was able to clone the repository, install the dependencies and build it with the appropriate --arch= armhf flag.
• The gulp . . .

December 30, 2015

Homebridge -> pi-switch

Putting it all together, C_LOG_28

Tonight I put it all together to make a working homebridge setup on the pi to control the relay.

pi-switch-plugin
I took my led plugin and adjusted it so it behaves like a switch.

var request = require("request");
var Service, Characteristic;

module.exports = function(homebridge) {
Service =  . . .

December 29, 2015


text:
# A language which does term inference

Many strongly typed languages like OCaml do type inference. That is, even though they’re strongly typed, you don’t have to explicitly say what the type of everything is since a lot of the time the compiler can figure it out by itself. For example, if you define a function which takes an x and adds it to 3, the compiler will figure out that x is an int. (It couldn’t be a float, since it was added to 3 and not 3.0.)

But it often seems like the compiler should be able to infer not just the types of expressions, but the expressions themselves! For example, if the compiler infers that the type of some function f is (int -> int) -> (int list) -> int list (i.e., f is a higher-order function which takes a function from int to int, a list of ints, and produces a list of ints), then f is very probably the map function, defined informally by

map g [x_1;...;x_n] = [g x_1;...;g x_n].

Therefore, if the compiler determines that some expression has that type, and the user has somehow omitted the actual function definition, why not allow the compiler to infer what the expression is?

I made a stab at implementing this type of idea in a toy language I call TermInf (apologies for the weird hosting: I don’t have another hosting service at the moment). It’s a modification of the toy language Poly from Andrej Bauer’s Programming Language Zoo. You’ll need OCaml to compile it. Please feel free to alert me to any bugs or to tell me that my code is horrible.

More details below.

The basic idea is really simple: For any expression e, the expression {e} is also an expression. The compiler will infer the type t1 of e and the type t2 that {e} has to be. It will search for a sequence of coercions taking t1 to t2 and if there is a unique one, it will replace {e} with that sequence of coercions applied to e.

Which functions are coercions is determined by the user; functions can be declared to be coercions or removed from the list of coercions at any point.

I can think of at least three ways this would be useful.

1. Automatically coercing from one base type to another

This is actually the least interesting of the three, but it serves to illustrate how TermInf works.

You can use $show_coercions to show all the current coercions. The identity function id is always a coercion. TermInf. Press Ctrl-D to exit. TermInf>$show_coercions
id

Let’s define a new coercion from bool to int.

TermInf> let_coercion bool_to_int = fun x -> if x then 1 else 0
val bool_to_int : bool -> int
TermInf> $show_coercions bool_to_int id  Now we can use the coercion. TermInf> {true} + 7 - : int = 8  In that instance, the interpreter could determine that the type of {true} had to be int, since it was added to 7. In the following instance, the interpreter can’t determine type of {true}. TermInf> {true} Problem with term inference.  But we can always explicitly give a type to any expression, so we can use that to tell the type-inferer what the type of {true} is. TermInf> {true} : bool - : bool = true TermInf> {true} : int - : int = 1  2. Lifting functions We can view the function List.map as a coercion, taking a function 'a -> 'b to a function 'a list -> 'b list. TermInf> let_coercion map = rec map is fun f -> fun l -> match l with [] -> [] | x::ll -> (f x)::(map f ll) val map : ('a -> 'b) -> 'a list -> 'b list TermInf>$show_coercions
map
bool_to_int
id

Now we can try it out.

TermInf> let square = fun x -> x * x
val square : int -> int
TermInf> ({square} 3) : int
- : int = 9
TermInf> ({square} [1;2;3]) : int list
- : int list = 1 :: 4 :: 9 :: []
TermInf> ({square} [[1;2];[5;6;7]]) : int list list
- : (int list) list = (1 :: 4 :: []) :: (25 :: 36 :: 49 :: []) :: []

Note that in our case, we had to explicitly tell the interpreter what the return type was, although presumably in practice the interpreter or compiler would usually be able to infer it.

The idea is that we can change the basic structure of the thing passed to {square}, and the term inferer will adapt. Note that in the third case, the term inferer iterated map to produce the required (int list list -> int list list) type.

We can similarly look inside the structure of pairs.

TermInf> let_coercion map_pair = fun f -> fun x -> (f (fst x), f (snd x))
val map_pair : ('a -> 'b) -> 'a * 'a -> 'b * 'b
TermInf> ({square} [(1,2);(3,4)]) : (int * int) list
- : (int * int) list = (1, 4) :: (9, 16) :: []
TermInf> ({square} ([1;2],[3;4])) : (int list) * (int list)
- : int list * int list = (1 :: 4 :: [], 9 :: 16 :: [])

Essentially all variants of map can be added. For example, the function mapi : ((int * 'a) -> 'b) -> 'a list -> 'b list where the function takes the index of the list element can be added. Then the term-inferer will determine which version of map (or sequence of versions of map) is needed based on the function given to it.

3. Term inference in conjunction with phantom types.
I put just enough type aliasing in TermInf to allow you to use phantom types. (For a great introduction to phantom types, see this blog post).

Here’s an example of how type aliasing works in TermInf:

TermInf> type hidden = int
TermInf> let f = (fun x -> x + 7) : hidden -> hidden
val f : hidden -> hidden
TermInf> let x = 3 : hidden
val x : hidden
TermInf> f x
- : hidden = 10
TermInf> f 3
The types hidden and int are incompatible

Something we might like to do with phantom types is have the type system do a static dimensional analysis on our program. Here’s an attempt to do that:

TermInf> type meters
TermInf> type gallons
TermInf> type 'a units = int
TermInf> let add = (fun x -> fun y -> x + y) : 'a units -> 'a units -> 'a units
val add : 'a units -> 'a units -> 'a units
TermInf> let times = (fun x -> fun y -> x * y) : 'a units -> 'b units -> ('a * 'b) units
val times : 'a units -> 'b units -> ('a * 'b) units
TermInf> let one_gal = 1 : gallons units
val one_gal : gallons units
TermInf> let one_m = 1 : meters units
val one_m : meters units

Then we have the following correct behavior:

TermInf> add one_gal one_gal
- : gallons units = 2
TermInf> times one_gal one_m
- : (gallons * meters) units = 1
The types gallons and meters are incompatible

But the following is not correct:

TermInf> let x = times one_gal one_m
val x : (gallons * meters) units
TermInf> let y = times one_m one_gal
val y : (meters * gallons) units
The types gallons and meters are incompatible

Of course, the problem is that the interpreter doesn’t know that units commute.
But we can fix this with coercions.

TermInf> let_id_coercion commute = id : ('a * 'b) units -> ('b * 'a) units
val commute : ('a * 'b) units -> ('b * 'a) units
- : (gallons * meters) units = 2

We’ve declared commute to be an identity coercion (by using let_id_coercion instead of let_coercion) to help the interpreter when it’s deciding if a term inference is unique or not.

Note that we don’t use term inference on both x and y, because then it couldn’t determine what type to give it.

TermInf> add {x} y
- : (meters * gallons) units = 2
Problem with term inference.

This version of commute will just commute the two units at the top level, but there are a finite number of identity coercions that you can define that will give you associativity and commutativity (and inverses, if you want). Thus, the type system will be able to perform a static dimensional analysis on your program.

Edit: I should note that I left out several details about how this actually works. For example, the interpreter doesn’t search through all sequences of coercions, since there are infinitely many (and the problem of deciding if there is a unique one between any two given types is undecidable in general). Instead it limits itself to sequences of coercions whose type is never “bigger” that the starting type or the goal type, where “bigger” is defined by a straightforward length function.

## 7 thoughts on “A language which does term inference”

1. Using the Curry-Howard correspondence we see that what you are doing is automated theorem proving for (intuitionistic) propositional calculus. That is, the type is a statement which you want to prove, and the term is the proof you are looking for. Proofs in intuitionistic propositional calculus have normal forms, so you can look for a normal form proof. One possible reference where you can read about this is Troelstra & Scwichtenberg’s “Basic Proof Theory” (I might have gotten the title wrong, but the authors are correct).

2. Hi Andrej,

What I’m doing isn’t exactly a proof search in intuitionistic propositional logic in two ways: First, the stored coercions (non-logical axioms, if you’re thinking about it as a proof search) are allowed to have polymorphic types. Second, the interpreter doesn’t take the intuitionistic axioms for granted: for example, it won’t deduce the coercion fst: ('a * 'b) -> 'a on its own. The only thing it tries are applications. (The second difference was mostly for my convenience.) Also, it doesn’t just look for a proof in normal form, it tries to make sure that it’s unique.

But those are minor differences and you can indeed recast its search as a restricted intuitionistic proof search, although one which is undecidable since you have infinitely many non-logical axioms due to polymorphism.

I was originally thinking about having the compiler or interpreter infer an expression for a given type, and I first tried an intuitionistic proof search. This had a problem though, since when inferring a term with type 'a -> ('a * 'b -> 'a) -> 'b list -> 'a (which is intended to be fold_left), a perfectly good intuitionistic proof would have you simply throw away all but the first argument and return that.

Something that works, though, is to use linear logic instead of intuitionistic logic. You interpret * as $\otimes$, and let list be a constructor such that $A\text{ list}$ is equivalent to $A \oplus (A\otimes A\text{ list})$. Now, you have to require the programmer to annotate the type with $!$‘s somehow, but under suitable hypotheses, there is only one proof of $A \rightarrow !(A\otimes B\rightarrow A) \rightarrow (A \text{ list})\rightarrow A$, and it corresponds under Curry-Howard to fold_left, and similarly for map, etc. By the way, I’m using $\rightarrow$ for linear implication since I’m not sure how to get the actual symbol.

This currently seems impractical to me, though, for a couple of reasons, one of which is that the generated programs could easily be inefficient whereas if you have the user define coercions, they can make the functions as efficient as they like.

3. I see. Well, it’s a nice idea and you’ve clearly thought about it carefully. I would just add that having infinitely many axioms does not automagically give you undecidability. Your axioms are nicely structured (they are just parametrized by types), so possibly you can answer many interesting questions about them.

The idea with linear logic is neat. To circumvent the problem with guessing where the bangs should go, you could use relevant logic instead: it requires that every hypothesis be used at least once (programmers don’t write functions which accept useless arguments). This would also prevent a projection a*b->a from being deduced, although I am not sure whether this is good or bad. The trick then would be to find a proof which uses every hypothesis at least once, and as few times as possible. Can that give you anything interesting?

4. I think we talked about this over the Summer, but I never followed up. In any case, I’m very curious about the connection with linear logic. I have a bunch of questions…

It seems to me that you’re using intuitionistic linear logic. In particular, you probably don’t have an interpretation of “par” (distinct from $\oplus$).

I can make sense of 1 as the empty list, do you have an interpretation for 0 (other than “fail”)?

Doesn’t the list constructor behave just like the exponential “!”? Wouldn’t it make sense to identify the two?

5. Andrej: I’ll have to look into relevant logic; I know nothing about it presently. In my current way of thinking, I do sometimes want to throw away a hypothesis (either to infer a projection (which I am, like you, not sure is a good thing to allow) or, for example, in the case of map where the list argument is empty you do not use the function argument), but that’s certainly not necessary and it’s quite possible relevant logic gives the framework I need.

François: I don’t have an interpretation for par, and it also turned out that I didn’t need $\&$. (This is in reference to my last comment; the posted compiler doesn’t use linear logic at all.) I don’t have interpretation for 0 (and, embarrassingly, I never really understood the distinction in linear logic either). The list constructor behaves a lot like ? (in that, if you have ?A as a resource, your opponent gets to choose how many A’s you have, and you can produce a ?A by bundling up as many A’s as you want), but I think that you can’t view the A’s you get from a ?A as coming with an order, although I could be wrong.
In any case, I think that if you want to interpret constructors more general than “list”, it will not be easy to interpret them as exponentials.

I hope everything’s going great in Michigan!

6. Michigan is great! I’m having a good time in Ann Arbor.

The close connection with linear logic is starting to become clearer.

I think & could be useful as an alternate product. You could then derive the projection fst: ('a & 'b) -> 'a as well as the diagonal diag: 'a -> ('a & 'a). The idea is that & is a “lazy” product, whereas * is an “eager” product.

The same distinction applies to ! and ?. They are both similar storage constructors, but ! is “eager” while ? is “lazy”. Lists make sense to me, but I can see that the implicit order could lead to problems. Some kind of reference types would also make sense, but I find this interpretation very sketchy and undesirable.

As for the units, 1 is pretty clearly the empty list. I couldn’t make much sense of $\top.$ As for 0 and $\bot,$ the axiom $\bot \vdash$ suggests that $\bot$ is “failure” and the axiom $\Gamma,0 \vdash A$ suggests that 0 is “void”. I don’t know if you really want partial functions, but $\bot$ would be one way to explicitly allow for that. I don’t know if 0 is desirable, but I’m pretty confident it can’t hurt.

Of course, adding too many features will lead to undecidability. I wonder where the line is…

7. Using & to get projections is a good idea. I had actually kind of stopped thinking about the linear logic side of things once I decided that it wouldn’t make for a practical implementation, but now that it’s come up again, it seems theoretically quite interesting to me.
I’m not sure if using & to get the diagonal function would work out though: if you used the diagonal function to get an a&a from an a, you would probably want to use both a‘s (since otherwise, why did you apply the diagonal function in the first place?), but you can’t, by the definition of &.


text: Title Characterization of stereoisomeric $\alpha$-methylene-$\gamma$-lactone furanosidic derivatives by direct chemical ionization mass spectrometry and liquid secondary ion mass spectrometry with tandem mass spectrometry Characterization of stereoisomeric $\alpha$-methylene-$\gamma$-lactone furanosidic derivatives by direct chemical ionization mass spectrometry and liquid secondary ion mass spectrometry with tandem mass spectrometry Author Borges, C. Ferreira, M.A.A. Claeys, M. Faculty/Department Faculty of Pharmaceutical, Biomedical and Veterinary Sciences. Pharmacy Publication type article Publication 1996 London , 1996 Subject Chemistry Source (journal) Rapid communications in mass spectrometry. - London Volume/pages 10(1996) :7 , p. 757-766 ISSN 0951-4198 ISI A1996UN19400004 Carrier E Target language English (eng) Full text (Publishers DOI) Affiliation University of Antwerp Abstract Several furanosidic derivatives have been found to have biological activity and have been used both as fungicides and plant growth regulators. In particular, those carbohydrate derivatives that contain the alpha-methylene-gamma-lactone unit have interesting potential applications, The present study deals with the mass spectrometric characterization of furanosidic compounds having a alpha-methylene-gamma-lactone unit, using different ionization techniques: chemical ionization mass spectrometry and liquid secondary ion mass spectrometry together with metastable ion analysis and high-energy collision-induced dissociation, The objective of this study was to determine the influence on the respective fragmentation patterns of structural differences present in the stereoisomers. Common fragmentation differences relate to the extent of the loss of water which occurs together with the loss of acetone and to the formation of C7H7+ ions. E-info https://repository.uantwerpen.be/docman/iruaauth/d6e876/b702396.pdf http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:A1996UN19400004&DestLinkType=RelatedRecords&DestApp=ALL_WOS&UsrCustomerID=ef845e08c439e550330acc77c7d2d848 http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:A1996UN19400004&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=ef845e08c439e550330acc77c7d2d848 http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:A1996UN19400004&DestLinkType=CitingArticles&DestApp=ALL_WOS&UsrCustomerID=ef845e08c439e550330acc77c7d2d848 Handle


text:
# How can I write the bottom line in the equation?

Hello everyone, I want to write this equation in LaTeX, but I can't get the equation starting with H1 to the bottom line. I would be very happy if you could help with this.

    {{\mathcal{H}}_{0}}:y\left[ n \right]=w\left[ n \right]\ n=1,2,\ \ldots ,\ N
\\  {{\mathcal{H}}_{1}}:y\left[ n \right]=x\left[ n \right]+w\left[ n \right]\ n=1,2,\ \ldots ,\ N

You can use the split environment. I took the liberty to remove the unnecessary \left \right pairs, and simplified a bit your code:

\documentclass{article}
\usepackage{amsmath}

\begin{document}

$$\begin{split} \mathcal{H}_{0}:y[n] & =w[n],\quad n=1,2,\ \ldots ,\ N \\ \mathcal{H}_{1}:y[ n] & =x[n]+w[n],\quad n=1,2,\ \ldots ,\ N \end{split}$$

\end{document}

• Thank you both very much. Sep 3 at 22:10
• @ZangLi Thank you for your green check mark ...but with a lot of sincerity it is of Bernard. Please, can you switch it to Bernard? Thank you very much. Sep 3 at 22:26

If you compile this:

\documentclass{article}
\usepackage{amsmath}
\begin{document}
\begin{aligned} {{\mathcal{H}}_{0}}&:y\left[ n \right]=w\left[ n \right]\ n=1,2,\ \ldots ,\ N\\ {{\mathcal{H}}_{1}}&:y\left[ n \right]=x\left[ n \right]+w\left[ n \right]\ n=1,2,\ \ldots ,\ N \end{aligned}
\end{document}

then you get this:

• Thank you very much. Sep 3 at 22:10

Another possibility it is to use array enviroment. I have build this MWE looking your image and I have used the same fonts.

\documentclass[a4paper,12pt]{article}
\usepackage{newtxtext,newtxmath}
\usepackage{amsmath}
\DeclareMathAlphabet{\pazocal}{OMS}{zplm}{m}{n}
\begin{document}
$$\begin{array}{ll} \pazocal{H}_{0}\colon y[n]&=w[n],\quad n=1,2,\ldots, N \\ \pazocal{H}_{1}\colon y[n]&=x[n]+w[n],\quad n=1,2,\ldots, N \end{array}$$

\end{document}