<title>Search process evaluation for a hierarchical menu system by Markov chains</title>

When computers are used to execute tasks, it is often necessary for the user to locate a target item in a menu or a list. For example, users of word processors and spreadsheet applications select appropriate commands in a hierarchical menu to display dialog boxes and edit file or table attributes. To locate the desired information on the World Wide Web, users select the most appropriate candidate out of those presented by a search engine, and proceed through a series of hyperlinks that appear to be related to the task. This paper applies a cognitive model of the user's item selection process to the task of target search in a hierarchical menu system that contains one or more of the following four operations: (1) item selection on the basis of similarity to the task, (2) consideration in various ways of the selection history when making the next selection, (3) backtracking when an appropriate item is not present among those selectable at a given point in time, and (4) abandoning the task unachieved. We model this selection process with Markov chains. We calculate the probability that task goals are achieved and the average number of selections to make until the task goals are achieved. Finally we use these results to propose a method of evaluating the structures of hierarchical menus and links on a website.