Information Theory Society

The Distinguished Lecturers program promotes:

Interest in information theory by supporting chapters who wish to invite prominent information theory researchers to give talks at their events. One of Claude Shannon’s best remembered “toys” was his maze-solving machine, created by partitions on a rectangular grid. A mechanical mouse was started at one point in the maze with the task of finding cheese at another point.

• Relays under the board guided successive moves, each of which were taken in the first open counterclockwise direction from the previous move.
• In belated honor of Shannon’s centenary and of amnesia in the mouse at age 70, we compare this deterministic search strategy with a random search requiring no memory. For simplicity, the rectangular grid with partitions is replaced by a finite connected graph.
• A maze is then a graph with some given destination node. The worst case required number of steps to find the cheese for deterministic searches and the expected number for random searches are remarkably similar, each being, for example, |E2||E2| taken over all graphs of |E||E| edges.
• Finally, we demonstrate a simple improvement to the above algorithms that generates an Eulerian cycle on the directed edges of GG, i.e., a walk on GG of 2|E|2|E| steps that traverses each edge in GG exactly once in each direction before returning to the starting point. The IEEE Information
• Theory Society is the premier professional society dedicated to the advancement of the mathematical underpinnings of information technology for the benefit of humanity. Information theory encompasses the processing, transmission, storage, and use of information, and the foundations of the communication process.

A maze is then a graph with some given destination node: The worst case required number of steps to find the cheese for deterministic searches and the expected number for random searches are remarkably similar, each being, for example, |E2||E2| taken over all graphs of |E||E| edges.

1. Finally, we demonstrate a simple improvement to the above algorithms that generates an Eulerian cycle on the directed edges of GG, i.e., a walk on GG of 2|E|2|E| steps that traverses each edge in GG exactly once in each direction before returning to the starting point. 
2. The IEEE Information Theory Society is the premier professional society dedicated to the advancement of the mathematical underpinnings of information technology for the benefit of humanity. 
3. Information theory encompasses the processing, transmission, storage, and use of information, and the foundations of the communication process.