Vittorio Bertocci

Scatter thoughts

4 years of blogging

4 years of blogging

  • Comments 2
As tradition requires (see exhibits a, b and c), here there's the canonical, eigencelebrative post about the fact that it's n years that I mantain this blog feed (where n=4). I could comment on how everything changed in this last 4 years, but for the time being I'll spare you :-) I'll just remark that the "useless" tag is being used much less than in the past, out of respect for the audience of the many aggregated feeds I'm included, but I don't know for how much longer I'll manage to restrain myself... you're warned >:)
  • Yes, 4 years is already some time of blogginf, information technology has changed much these years. When i started with software development (with http://www.netvance.at 1997) many things werde different. In the 1950s and 1960s, there was a considerable effort in information theory to find bounds, for any of various given channels, on the probability of error, Pe , of the best code of block length n and code rate R. For large block lengths, n, this entailed bounds on the function

    E(R) = lim -ln Pe(n, R)/n

    nTOINFTY

    (using lim sup and lim inf for upper and lower bounds as appropriate). Under certain simplistic ("very noisy") circumstances, the function E(R) attained the form shown in the figure: linear over a region from 0 to the a critical value called Rcrit, and then roughly parabolic over a region of rates from Rcrit to Shannon's capacity, C, at which point E(R) becomes 0. Many results of this type appear in the complete works of Claude Shannon, including his last papers [1967] on information theory, which were coauthored by Gallager and Berlekamp.

    Berlekamp [1968] studied a closely related problem, which was subsequently independently popularized by Stan Ulam and became known as "Ulam's problem", or "20 questions with lies". In this problem one player selects an object at random from a set of M possibilities. His opponent attempts to discover the object by asking n yes-no questions, sequentially. The answerer is permitted to lie up to e times. What values of M, n, and e, are wins for the selector, and which are wins for the questioner? Berlekamp essentially solved the problem for large values of the parameters. Let R = lg M/n, and let f = e/n. Then the boundary values lie on the curve f(R), which is depicted above. Although Berlekamp's paper was often cited in work on "Ulam's problem" in the 1980s and early 1990s, the last half of the paper was never carefully read. Ulam popularized two values of M, namely 1,000,000 and 220. For both of these values of M, for each e, Ray Hill subsequently determined the optimum value of n precisely. Des Jardins then extended these precise results much further. For many values of n and e, he was able to determine the maximum value of M to within one or two objects.

  • Usually ( 2004 , 2005 , 2006 , 2007 , 2008 ) in April I “celebrate” the anniversary of my blog creation

Page 1 of 1 (2 items)
Leave a Comment
  • Please add 3 and 7 and type the answer here:
  • Post