随机算法 (Fall 2011)/Problem set 2 and W.D. Hamilton: Difference between pages

From TCS Wiki
(Difference between pages)
Jump to navigation Jump to search
VisualWikitext
imported>Etone
 
imported>Macdonald-ross
(prose...)
 
Line 1: Line 1:
==Problem 1==
'''William Donald Hamilton''' [[Royal Society|FRS]] (1 August 1936 – 7 March 2000) was an [[English people|English]] [[evolutionary biology|evolutionary biologist]] whom [[Richard Dawkins]] praised as one of the greatest [[evolution]]ary theorists of the 20th century.<ref>[http://www.edge.org/3rd_culture/hamilton/hamilton_index.html Obituary by Richard Dawkins – ''The Independent'' – 10 March 2000]</ref>
Some known facts:
* Balls-into-bins: <math>m</math> balls are uniformly and independently thrown to <math>n</math> bins. If <math>m=\Theta(n)</math>, then the maximum load is <math>\Theta\left(\frac{\ln n}{\ln\ln n}\right)</math> with high probability.
* Power of two choices: <math>m</math> balls are sequentially thrown to <math>n</math> bins. For each ball, uniformly and independently choose random bins <math>i</math> and <math>j</math> (might be the same bin), and throw the ball to the currently less loaded bin among bin <math>i</math> and bin <math>j</math>. Assuming that <math>m=\Theta(n)</math>, after all <math>m</math> balls are thrown to bins, the maximum load is <math>\Theta\left(\ln \ln n\right)</math> with high probability.


Questions: Assume <math>n</math> balls and <math>n</math> bins. We throw the <math>n</math> balls sequentially.
Hamilton became famous through his [[Theory|theoretical]] work on [[kin selection]] and [[altruism]]. He explained its [[Genetics|genetic]] basis, and this was a key part of the gene-centered view of [[evolution]]. In doing this, he became one of the forerunners of [[sociobiology]], as popularized by [[E.O. Wilson]]. Hamilton was certainly a big influence on Dawkins. He also published important work on [[sex ratio]]s and the [[evolution of sex]]. From 1984 to his death in 2000, he was the [[Royal Society]] Research Professor at [[Oxford University]]. He died of [[malaria]] contracted in the [[Democratic Republic of the Congo]].
# If we throw the first <math>\frac{n}{2}</math> balls uniformly and then throw the rest balls as the way of power-of-two-choices, what is the asymptotic maximum load with high probability?
# For the <math>k</math>th ball, if <math>k</math> is even, we throw the ball to a uniform bin; and if <math>k</math> is odd, we throw the ball as the way of power-of-two-choices. What is the asymptotic maximum load with high probability?


== Problem 2==
== Hamilton's equation ==
# Generalize the LazySelect algorithm for the general selection problem: finding the <math>k</math>th smallest element in an array. Choose appropriate parameters to do the job.
Hamilton's equation describes whether or not a gene for altruistic behaviour will spread in a population.<ref>Hamilton W.D. 1996. ''Narrow roads of geneland: the collected papers of W.D. Hamilton'', vol 1. Freeman, Oxford.</ref> The gene will spread if '''r'''x'''b''' is greater than '''c''':
# Use the Chernoff bounds instead of Chebyshev's inequality in the analysis of the above algorithm and try to use a smaller number of random samples.
:<math>rb > c \ </math>   
where:
* <math>c \ </math> is the reproductive cost to the altruist,
* <math>b \ </math> is the reproductive benefit to the recipient of the altruistic behavior, and
* <math>r \ </math> is the probability, above the population average, of the individuals sharing an altruistic gene – the "degree of relatedness".


== Problem 3 ==
== Collected papers ==
;The Monte Carlo method for computing <math>\mathrm{e}</math>
Hamilton started to publish his collected papers starting in 1996, with short essays giving each paper context. He died after the preparation of the second volume, so the commentaries for the third volume came from his coauthors.


Suppose there are <math>n</math> peoples, each wearing a hat. We collect all their hats and randomly distribute the hats back to them, with each people receiving exactly one hat. We ask for the probability that none of the people receives his/her own hat. We denote this probability by <math>p(n)</math>
* Hamilton W.D. 1996. ''Narrow roads of gene land vol. 1: Evolution of social behaviour''. Freeman, Oxford. ISBN 0-7167-4530-5
* Hamilton W.D. 2002. ''Narrow roads of gene land vol. 2: Evolution of sex''. Oxford University Press, Oxford. ISBN 0-19-850336-9
* Hamilton W.D. 2005. ''Narrow roads of gene land, vol. 3: Last words'' (with essays by coauthors, ed. M. Ridley). Oxford University Press, Oxford. ISBN 0-19-856690-5


Formally, a '''permutation''' is a bijection <math>\pi:[n]\xrightarrow[\text{1-1}]{\text{onto}}[n]</math>. A '''fixed point''' for permutation <math>\pi</math> is an <math>i\in[n]</math> such that <math>\pi(i)=i</math>. Then <math>p(n)</math> is the probability that a uniformly random permutation has no fixed point. Such permutations are called '''derangements'''.
== References ==
{{Reflist}}


The derangement problem is taught in the undergraduate class [[组合数学 (Fall 2011)|Combinatorics]] at Nanjing University. See the [[组合数学 (Fall 2011)/Sieve_methods#Derangements|lecture notes]] for details. By the Principle of Inclusion-Exclusion (容斥原则), we know that <math>p(n)=\sum_{k=0}^n\frac{(-1)^k}{k!}</math>.
{{DEFAULTSORT:Hamilton, William Donald}}
 
[[Category:1936 births]]
Recall that due to Taylor's expansion <math>\mathrm{e}^{-1}=\sum_{k=0}^\infty\frac{(-1)^k}{k!}=p(\infty)</math>.
[[Category:2000 deaths]]
 
[[Category:English mathematicians]]
Now suppose you are given access to a balckbox <math>derange(n)</math> which given as input a number <math>n</math>, samples a uniform and independent permutation <math>\pi</math> of <math>[n]</math>, and returns true if <math>\pi</math> has no fixed point and false if otherwise.
[[Category:Geneticists]]
 
[[Category:English evolutionary biologists]]
Give a randomized algorithm <math>randE(\epsilon,\delta)</math>, whose inputs are <math>0<\epsilon<0.1</math> and <math>0<\delta<\frac{1}{2}</math>. The returned value of the algorithm should satisfy that
[[Category:Fellows of the Royal Society]]
:<math>\Pr[\mathrm{e}-\epsilon\le randE(\epsilon,\delta)\le\mathrm{e}+\epsilon]\ge1-\delta</math>.
 
* Your algorithm should make function calls to <math>derange(n)</math> as subroutine. Try to make both <math>n</math> and the number of times calling <math>derange(n)</math> as small as possible.
* Please give detailed analysis of your algorithm.

Latest revision as of 09:43, 22 December 2013

William Donald Hamilton FRS (1 August 1936 – 7 March 2000) was an English evolutionary biologist whom Richard Dawkins praised as one of the greatest evolutionary theorists of the 20th century.[1]

Hamilton became famous through his theoretical work on kin selection and altruism. He explained its genetic basis, and this was a key part of the gene-centered view of evolution. In doing this, he became one of the forerunners of sociobiology, as popularized by E.O. Wilson. Hamilton was certainly a big influence on Dawkins. He also published important work on sex ratios and the evolution of sex. From 1984 to his death in 2000, he was the Royal Society Research Professor at Oxford University. He died of malaria contracted in the Democratic Republic of the Congo.

Hamilton's equation

Hamilton's equation describes whether or not a gene for altruistic behaviour will spread in a population.[2] The gene will spread if rxb is greater than c:

[math]\displaystyle{ rb \gt c \ }[/math]

where:

  • [math]\displaystyle{ c \ }[/math] is the reproductive cost to the altruist,
  • [math]\displaystyle{ b \ }[/math] is the reproductive benefit to the recipient of the altruistic behavior, and
  • [math]\displaystyle{ r \ }[/math] is the probability, above the population average, of the individuals sharing an altruistic gene – the "degree of relatedness".

Collected papers

Hamilton started to publish his collected papers starting in 1996, with short essays giving each paper context. He died after the preparation of the second volume, so the commentaries for the third volume came from his coauthors.

  • Hamilton W.D. 1996. Narrow roads of gene land vol. 1: Evolution of social behaviour. Freeman, Oxford. ISBN 0-7167-4530-5
  • Hamilton W.D. 2002. Narrow roads of gene land vol. 2: Evolution of sex. Oxford University Press, Oxford. ISBN 0-19-850336-9
  • Hamilton W.D. 2005. Narrow roads of gene land, vol. 3: Last words (with essays by coauthors, ed. M. Ridley). Oxford University Press, Oxford. ISBN 0-19-856690-5

References

Template:Reflist

  1. ↑ Obituary by Richard Dawkins – The Independent – 10 March 2000
  2. ↑ Hamilton W.D. 1996. Narrow roads of geneland: the collected papers of W.D. Hamilton, vol 1. Freeman, Oxford.
Retrieved from "https://tcs.nju.edu.cn/wiki/index.php?title=随机算法_(Fall_2011)/Problem_set_2&oldid=7721"