Hacker News new | past | comments | ask | show | jobs | submit login

Oh my god it's the golden ratio! That's so cool!

EDIT: I'll show my work, rot13'd...

Jr pna cnenzrgrevmr n fgengrtl ol n guerfubyq g: gur inyhr gung gur svefg qenj arrqf gb or yrff guna va beqre gb pubbfr gb qenj ntnva. Hfvat guerfubyq g, gur cebonovyvgl bs trggvat yrff guna g vf g^2 orpnhfr lbh unir gb qenj orybj gur guerfubyq gjvpr va n ebj. Gung chgf gur cebonovyvgl bs raqvat hc nobir gur guerfubyq ng 1-g^2.

Gur cebonovyvgl vf havsbez nobir naq orybj gur guerfubyq fb gur cebonovyvgl qvfgevohgvba bs lbhe ahzore vf:

    cqs(k) = { g vs k<g ryfr g+1 }
(Gur g+1 vf sebz fbyivat gb znxr gur vagrteny sebz 0 gb 1 or 1.)

Fnl lbhe bccbarag hfrf fgengrtl h naq lbh hfr fgengrtl g. Gura jr jnag gb znkvzvmr gur cebonovyvgl gung K~cqs(g) vf terngre guna L~cqs(h). Zngurzngvpn jvyy gryy hf gung vs jr nfx yvxr fb:

    q[g_] := CebonovyvglQvfgevohgvba[Vs[k<g, g, g+1], {k,0,1}]

    Fvzcyvsl[
      Cebonovyvgl[k<l, {Qvfgevohgrq[k, q[g]], 
                        Qvfgevohgrq[l, q[h]]}], 
      0<g<1 && 0<gh<1]
Gung tvirf hf gur cebonovyvgl gung g orngf h yvxr fb:

    c[h_,g_] := Cvrprjvfr[{
      {(1+g-(1+g+g^2)*h+(1+g)*h^2)/2,  h>g},
      {(1+g-g^2+(g-g^2-1)*h+g*h^2)/2,  h<g},
      {((g^2-1)^2-g*(g^2-2)*h)/2,      h==g}}]
Abj jr jnag gur g gung znkvzvmrf gung sbe n tvira h, juvpu jr trg ol gnxvat gur qrevingvir jvgu erfcrpg gb g, frggvat vg gb mreb, naq fbyivat sbe g:

    Fvzcyvsl[Fbyir[Q[c[g, h], g] == 0, g], 0<h<1]
Fb abj jr unir gur orfg erfcbafr gb na neovgenel fgengrtl g:

    oe[g_] := Cvrprjvfr[{
      {(1+g+g^2)/(2+2*g), g<(Fdeg[5]-1)/2},
      {(1-g+g^2)/(2*g),   g>(Fdeg[5]-1)/2}}]
Vs lbh cybg gung lbh frr gung gur orfg erfcbafr vf nyjnlf orgjrra .5 naq .618. Vs lbhe bccbarag nyjnlf xrrcf gurve svefg qenj gura lbh fubhyq hfr n guerfubyq bs .5. (Fnzr vs gurl nyjnlf gnxr gur frpbaq qenj bs pbhefr.)

Ohg gurl jba'g qb gung. Vs gurl hfr n guerfubyq bs 1/2 gurzfrys gura oe[1/2] == 7/12. Ohg gurl jba'g qb gung rvgure. Jung jr jnag bs pbhefr vf gur svkrq cbvag, vr, gur Anfu rdhvyvoevhz, jurer oe[g]==g. Gung, boivbhf va gur cybg, vf g = (Fdeg[5]-1)/2 nxn gur tbyqra engvb!




There is another way to do it, without integrals and convolutions. Say player A has threshold a and player B has threshold b, a <= b. Write 3x3 table of Player A win probabilities for ranges 0 to a, a to b, and b to 1. It will have 1/2 on the diagonal, 1 below, 0 above.

After some simplification, total Player A win probabilty is (-ba^2 + (b^2-b+1)a +(b^2-b+1))/2. Find a that maximizes this probability for any given b by taking the derivative and setting it to 0, which would be a = (b^2-b+1)/2b.

The game is symmetric, so at Nash equilibrium a==b. Now solve a = (a^2-a+1)/2a to get the golden ratio.

The lift over naive 0.5 threshold is very small, though, less than 1%.


This... rings so right... but me and probably many other programmers here lack the math to see the explanation immediately in front of our eyes when we hear the answer. Can you please elaborate?

Edit: thanks. This is convincing, but... given that we're looking for a fixed point of a process like... [bah, I lack words to describe a vague, non-rigorous intuition]... I expect that there is a convincing one-sentence explanation that also shows it to be the golden ratio. Am I wrong? Can anyone give a simpler explanation?


Your intuition is better than mine! I crunched it out (just now edited my answer to show how) but still have no intuitive sense of why it should be the golden ratio. Would love to hear some intuition for that!


Saying "It's intuitive to me that this answer someone worked out and told me is correct" is cheating.

But generally...

The process is something like:

If you choose 0.5, then 0.625 beats you because that is the expected average of someone redrawing below 0.5. If you choose 0.625, then 0.617[2] beats you because that is the expected average of someone redrawing below 0.625. If you choose 0.618, then 0.6182 beats you...

Lets ignore those numbers for a moment and focus on the process: "Given a number to redraw below, redraw below the expected value of redrawing below that number".

Trying to find a fixed point for this kind of process, the golden ratio has some kind of... mythological fit? Like, I've heard so many stories like this that ended up with a formula involving the golden ratio...

I wouldn't necessarily expect the answer to be phi, but I would so not be surprised to find it to be some formula involving phi, a rational factor, and maybe pi (just because I have absolutely no intuition for which series happen to sum to rational factors of pi).

[2] I'm getting these numbers by simulation, it's too late for me here in Israel to do math


OK I almost got it (edit: rot13 isn't very good at scrambling one-variable equations, so read at your peril, spoilers ahead):

Jr'er ybbxvat sbe n svkrq cbvag bs "vs gur bccbarag pubbfrf gb erqenj orybj k, jr erqenj orybj uvf rkcrpgrq inyhr".

V gevrq gb qrevir gur sbezhyn sbe uvf rkcrpgrq inyhr n srj gvzrf naq nyjnlf tbg pbashfrq ba jurer V fubhyq hfr k, jurer (1-k) naq jurer 0.5, fb riraghnyyl V gevrq qrevivat gur fcrpvny pnfr jurer k=0.625 naq gung jnf rnfvre:

(1-0.625) [bqqf bs abg qenjvat ntnva] * (1 + 0.625) / 2 [rkcrpgrq inyhr va guvf pnfr] + 0.625 [bqqf bs erqenjvat] * 1 / 2 [rkcrpgrq inyhr va guvf pnfr]

Fb va trareny vg jbhyq or:

s(k) = (1 - k)(1 + k) / 2 + k / 2

Gur svkrq cbvag vf jura s(k) = k, be

(1 - k)(1 + k) / 2 + k / 2 = k

naq...

uggc://jjj.gvtre-nytroen.pbz/qevyy/(1-k)(1_k)/2_k/2=k/

Guvf tvirf n pybfr rabhtu nafjre? Fb V cebonoyl unir fbzr fznyy zvfgnxr ohg unir gur evtug vaghvgvba?

V arrq gb tb gb fyrrc, fb V'yy yrnir vg sbe gur vagrearg gb svaq zl fznyy zvfgnxr, nffhzvat gung'f jung vg vf, naq V pbafvqre zl rkcynangvba orggre orpnhfr vg erdhverf bayl uvtufpubby-yriry zngu :-)


why do you seek the fixed point and not the k value that maximizes s(k) = (1 - k)(1 + k) / 2 + k / 2 ?


s(k) is the function for "The number I should choose if my opponent chooses k" [1]. We arrived at the formula by asking "what is the best number for us to choose assuming our opponent chooses k?".

Now, obviously a smart opponent would not choose a number k where k != s(k), because s(k) would be a better choice. So the only numbers it makes sense for him to choose would be fixed points of s(k), points where k = s(k). And the smartest thing for me to do in that case would be to choose s(k), which just so happens to be equal to k.

[1] which may be more or less than s(k), e.g. if my opponent chooses to always redraw, i.e. k=1, it should be the same as if he chooses to never redraw, k=0, and we expect for both cases s(k)=0.5 < 1 (and it indeed is)


Why do you bring up expected value in the calculation. You may end up with the right result, but there's no good justification for why expected value should come into play.


Indeed it is!




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: