#March 7, 2013, C13.txt continuing gambling trees
Help13:=proc(): print(`RandGT(n,L), ExpV(G) ` ): 
print(`LeftComb(n), SubtractA(G,A), PGF(A,x), PGG(G,x) `):
print(`StPete(n)`):
end:
with(combinat):

#StPete(n): The gambling tree for the St. Petersburg
#casino
StPete:=proc(n) local i:
DressUp(LeftComb(n),[seq(2^i,i=1..n)]):

end:


#PGG(G,x): the prob. gen. function in x playing the
#gambling tree G
PGG:=proc(G,x):
 
if nops(G)=1 then
  RETURN(x^G[1]):
else
 RETURN(1/2*(PGG(G[1],x)+PGG(G[2],x))):
fi:



end:

#PGF(A,x): inputs a prob. dist in the format {[a,p]}
#meaning the prob. of getting outcome a is p,
#outputs the Prob. Gen. Function add(a[2]*x^a[1], a in A)
PGF:=proc(A,x) local a:

add(a[2]*x^a[1], a in A):

end:

#Subtact(G,A): Given a gambling tree G and a Euro
#amount A (the admission free) creates the net tree
SubtractA:=proc(G,A)

if  nops(G)=1 then
[G[1]-A]:
else
[SubtractA(G[1],A), SubtractA(G[2],A)]:
fi:
end:


#LeftComb(n): [[], LeftComb(n-1))]
LeftComb:=proc(n)
option remember:

if n=1 then
 RETURN([]):
else
 RETURN([ [], LeftComb(n-1)]):
fi:

end:



#RandGT(n,L) inputs a pos. integer and an increasing
#n-list of numbers outputs a randon gambling tree
#whose leaves (final possible outcomes
#in our casino) are a random permutation of L
RandGT:=proc(n,L) local T,L1:
if n<>nops(L) then
 print(`We messed up, sorry Tom Tyrrell`):
 RETURN(FAIL):
fi:

T:=RandBT(n):
L1:=randperm(L):
DressUp(T,L1):
end:

#ExpV(G): the expected gain playing the
#gambling tree G
ExpV:=proc(G):
 
if nops(G)=1 then
  RETURN(G[1]):
else
 RETURN(1/2*(ExpV(G[1])+ExpV(G[2]))):
fi:



end:



##old stuff from C12.txt
#March 4, 2013 Gambling (binary trees)

Help12:=proc(): print(` BT(n) , NuL(T) , DressUp(T,L) `): 
print(` C(n), RollLD(L) , RandBT(n) `):
end:

#BT(n): The set of all fulll binary trees
#every vertex has either TWO children or ZERO children
#(then it is called a leaf)
#with n leaves, in  the format
#Tree=[] or [T1,T2] (T1 and T2 are smaller trees)
BT:=proc(n) local k, S, S1,S2,t1,t2:
option remember:

if n=0 then
RETURN({}):
fi:

if n=1 then
 RETURN({ [ ] }):
fi:

S:={}:

for k from 1 to n-1 do
 S1:=BT(k):
 S2:=BT(n-k):
 S:=S union {seq(seq([t1,t2], t1 in S1), t2 in S2)}:
od:

S:

end:

#NuL(T): the number of leaves of T
NuL:=proc(T) option remember:

if T=[] then
  1:
else
  NuL(T[1])+NuL(T[2]):
fi:

end:




#DressUp(T,L): inputs a "naked" binary tree with
#n (say) leaves and a list of numbers and
#sticks the numbers in order from left to right
#For example
#DressUp([[],[[],[]]],[4,1,3]);
#should be [[4],[[1],[3]]]
DressUp:=proc(T,L) local k, T1, T2:

if nops(L)<>NuL(T) then
 RETURN(FAIL):
fi:

if nops(L)=1 then
 RETURN([L[1]]):
#wise-guy Jacob Baron claims (mathematically correctly
#but morally incorrectly) that [L[1]] is the same L
fi:

k:=NuL(T[1]):

T1:=DressUp(T[1],[op(1..k,L)]):

T2:=DressUp(T[2],[op(k+1..nops(L),L)]):

[ T1, T2]:
end:

#C(n): the number of full binary trees with n leaves
C:=proc(n) local k:
option remember:

if n=1 then
1:
else
 add(C(k)*C(n-k), k=1..n-1):
fi:

end:

#RollLD(L): inputs a list of NON-NEGATIVE
#integers and outputs an integer from 1
#nops(L) such that the prob. of getting i
#is L[i]/convert(L,`+`):

RollLD:=proc(L) local Tot,ra,j,i,m :

Tot:=convert(L,`+`):

j:=rand(1..Tot)():

for i from 1 to nops(L) while add(L[m],m=1..i)<j do od:
i:

end:

#RollLDTomasPrettyGood(L): inputs a list of NON-NEGATIVE
#integers and outputs an integer from 1
#nops(L) such that the prob. of getting i
#is L[i]/convert(L,`+`):
#Brilliant version of Tomas Vyskocil
RollLDPrettyGood:=proc(L) local N:
	N := [seq(i$L[i], i=1..nops(L))]:
	return N[rand(1..nops(N))()]:
end:


#RandBT(n): A uniformly random full buinary 
#tree with n leaves
RandBT:=proc(n) local L,k,i:

if n=1 then
  RETURN([]):
fi:

i:=RollLD([seq(C(k)*C(n-k), k=1..n-1)]):

[RandBT(i),RandBT(n-i)]:

end: