Edgar Gilbert

Edgar Nelson Gilbert (July 25, 1923 – June 15, 2013) was an American mathematician and coding theorist, a longtime researcher at Bell Laboratories whose accomplishments include the Gilbert–Varshamov bound in coding theory, the Gilbert–Elliott model of bursty errors in signal transmission, and the Erdős–Rényi model for random graphs.

Biography

Gilbert was born in 1923 in Woodhaven, New York. He did his undergraduate studies in physics at Queens College, City University of New York, graduating in 1943. He taught mathematics briefly at the University of Illinois at Urbana–Champaign but then moved to the Radiation Laboratory at the Massachusetts Institute of Technology, where he designed radar antennas from 1944 to 1946. He finished a Ph.D. in physics at MIT in 1948, with a dissertation entitled Asymptotic Solution of Relaxation Oscillation Problems under the supervision of Norman Levinson, and took a job at Bell Laboratories where he remained for the rest of his career. He retired in 1996.[1][2]

He died following a fall in 2013 at Basking Ridge, New Jersey.[3]

Research

Coding theory

The Gilbert–Varshamov bound, proved independently in 1952 by Gilbert and in 1957 by Rom Varshamov,[4] is a mathematical theorem that guarantees the existence of error-correcting codes that have a high transmission rate as a function of their length, alphabet size, and Hamming distance between codewords (a parameter that controls the number of errors that can be corrected). The main idea is that in a maximal code (one to which no additional codeword can be added), the Hamming balls of the given distance must cover the entire codespace, so the number of codewords must at least equal the total volume of the codespace divided by the volume of a single ball.[5] For 30 years, until the invention of Goppa codes in 1982, codes constructed in this way were the best ones known.[6]

The Gilbert–Elliott model, developed by Gilbert in 1960 and E. O. Elliot in 1963,[7] is a mathematical model for the analysis of transmission channels in which the errors occur in bursts. It posits that the channel may be in either of two different states, with different error rates, that errors occur independently of each other once the state is known, and that the changes from one state to the other are governed by a Markov chain. It is "very convenient and often used" in the analysis of modern communications systems such as data links to mobile telephones.[8]

Probability theory

Central to the theory of random graphs is the Erdős–Rényi model, in which edges are chosen randomly for a fixed set of n vertices. It was introduced in two forms in 1959 by Gilbert, Paul Erdős, and Alfréd Rényi.[9] In Gilbert's G(n,p) form, each potential edge is chosen to be included in the graph or excluded from it, independently of the other edges, with probability p. Thus, the expected number of edges is pn(n − 1)/2, but the actual number of edges can vary randomly and all graphs have a nonzero probability of being selected. In contrast, in the G(n,M) model introduced by Erdős and Rényi, the graph is chosen uniformly at random among all M-edge graphs; the number of edges is fixed, but the edges are not independent of each other, because the presence of an edge in one position is negatively correlated with the presence of an edge in a different position. Although these two models end up having similar properties, the G(n,p) model is often more convenient to work with due to the independence of its edges.[10]

In the mathematics of shuffling playing cards, the Gilbert–Shannon–Reeds model, developed in 1955 by Gilbert and Claude Shannon[11] and independently in unpublished work in 1981 by Jim Reeds, is a probability distribution on permutations of a set of n items that, according to experiments by Persi Diaconis, accurately models human-generated riffle shuffles. In this model, a deck of cards is split at a point chosen randomly according to a binomial distribution, and the two parts are merged together with the order of merging chosen uniformly at random among all possible mergers. Equivalently, it is the inverse of a permutation formed by choosing independently at random for each card whether to put it into one of two piles (maintaining the original order of the cards within each pile), and then stacking the two piles on top of each other.[12]

Gilbert tessellations are a mathematical model of crack formation introduced by Gilbert in 1967.[13] In this model, fractures begin at a set of random points, with random orientations, chosen according to a Poisson process, and then grow at a constant rate until they terminate by running into previously formed cracks.[14]

Other contributions

Gilbert did important work on the Steiner tree problem in 1968, formulating it in a way that unified it with network flow problems.[15] In Gilbert's model, one is given a flow network in which each edge is given both a cost and a capacity, and a matrix of flow amounts between different pairs of terminal vertices; the task is to find a subnetwork of minimum cost whose capacities are sufficient to support a flow with the given flow amounts between any pair of terminals. When the flow amounts are all equal, this reduces to the classical Steiner tree problem.[16]

Gilbert discovered Costas arrays independently of and in the same year as Costas,[17] and is also known for his work with John Riordan on counting necklaces in combinatorics.[18] He has collaborated with Fan Chung, Ron Graham, and Jack van Lint on partitions of rectangles into smaller rectangles.[19]

References

  1. ↑ Author biography from Borst, S. C.; Coffman, E. G.; Gilbert, E. N.; Whiting, P. A.; Winkler, P. M. (2000), "Time-slot allocation in wireless TDMA", in Gelenbe, E., System Performance Evaluation: Methodologies and Applications, CRC Press, pp. 203–214, ISBN 978-0-8493-2357-7
  2. ↑ Edgar Nelson Gilbert at the Mathematics Genealogy Project
  3. ↑ "Edgar Nelson Gilbert Obituary: View Edgar Gilbert's Obituary by Star-Ledger". Obits.nj.com. Retrieved 2013-06-21.
  4. ↑ Gilbert, E. N. (1952), "A comparison of signalling alphabets", Bell System Technical Journal, 31: 504–522, doi:10.1002/j.1538-7305.1952.tb01393.x; Varshamov, R. R. (1957), "Estimate of the number of signals in error correcting codes", Dokl. Acad. Nauk SSSR, 117: 739–741
  5. ↑ Moon, Todd K. (2005), "The Gilbert–Varshamov Bound", Error correction Coding: Mathematical Methods and Algorithms, John Wiley and Sons, pp. 409–410, ISBN 978-0-471-64800-0
  6. ↑ Huffman, William Cary; Pless, Vera (2003), "The Gilbert–Varshamov Bound revisited", Fundamentals of Error-Correcting Codes, Cambridge University Press, p. 541, ISBN 978-0-521-78280-7
  7. ↑ Gilbert, E. N. (1960), "Capacity of a burst-noise channel", Bell System Technical Journal, 39: 1253–1265, doi:10.1002/j.1538-7305.1960.tb03959.x; Elliott, E. O. (1963), "Estimates of error rates for codes on burst-noise channels", Bell System Technical Journal, 42: 1977–1997, doi:10.1002/j.1538-7305.1963.tb00955.x
  8. ↑ Petrausch, Stefan; Sörgel, Wolfgang; Kaup, André (2004), "Serially connected channels: Capacity and video streaming application scenario for separate and joint channel coding", 5th International ITG Conference on Source and Channel Coding (SCC): January 14–16, 2004, Erlangen : Conference Record, Margret Schneider, pp. 271–278, ISBN 978-3-8007-2802-2
  9. ↑ Gilbert, E. N. (1959), "Random graphs", Annals of Mathematical Statistics, 30: 1141–1144, doi:10.1214/aoms/1177706098; Erdős, P.; Rényi, A. (1959), "On random graphs I" (PDF), Publicationes Mathematicae, 6: 290–297
  10. ↑ Watts, Duncan J. (2003), Small Worlds: The Dynamics of Networks Between Order and Randomness, Princeton Studies in Complexity, Princeton University Press, pp. 36–37, ISBN 978-0-691-11704-1
  11. ↑ Gilbert, E. N. (1955), Theory of Shuffling, Technical Memorandum, Bell Laboratories. As cited by Bayer & Diaconis (1992).
  12. ↑ Bayer, Dave; Diaconis, Persi (1992), "Tracking the dovetail shuffle to its lair", Annals of Applied Probability, 2 (2): 294–313, doi:10.1214/aoap/1177005705, JSTOR 2959752
  13. ↑ Gilbert, E. N. (1967), "Random plane networks and needle-shaped crystals", in Noble, B., Applications of Undergraduate Mathematics in Engineering, New York: Macmillan
  14. ↑ Gray, N. H.; Anderson, J. B.; Devine, J. D.; Kwasnik, J. M. (1976), "Topological properties of random crack networks", Mathematical Geology, 8 (6): 617–628, doi:10.1007/BF01031092; Schreiber, Tomasz; Soja, Natalia (2010). "Limit theory for planar Gilbert tessellations". arXiv:1005.0023Freely accessible.
  15. ↑ Gilbert, E. N. (1968), "Steiner minimal trees", SIAM Journal on Applied Mathematics, 16 (1): 1–29, doi:10.1137/0116001, JSTOR 2099400
  16. ↑ Hwang, Frank; Richards, Dana; Winter, Pawel (1992), The Steiner Tree Problem, Annals of Discrete Mathematics (North-Holland Mathematics Studies), 53, Elsevier, pp. 80–83, ISBN 978-0-444-89098-6
  17. ↑ An independent discovery of Costas arrays, Aaron Sterling, October 9, 2011.
  18. ↑ Gardner, Martin (2001), The colossal book of mathematics: classic puzzles, paradoxes, and problems : number theory, algebra, geometry, probability, topology, game theory, infinity, and other topics of recreational mathematics, W. W. Norton & Company, p. 18, ISBN 978-0-393-02023-6
  19. ↑ Chung, F. R. K.; Gilbert, E. N.; Graham, R. L.; Shearer, J. B.; van Lint, J. H. (1982), "Tiling rectangles with rectangles", Mathematics Magazine, 55 (5): 286–291, doi:10.2307/2690096
This article is issued from Wikipedia - version of the 5/10/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.