Visualizing Online Auctions

Online auctions have been the subject of many empirical research efforts in the fields of economics and information systems. These research efforts are often based on analyzing data from Web sites such as eBay.com which provide public information about sequences of bids in closed auctions, typically in the form of tables on HTML pages. The existing literature on online auctions focuses on tools like summary statistics and more formal statistical methods such as regression models. However, there is a clear void in this growing body of literature in developing appropriate visualization tools. This is quite surprising, given that the sheer amount of data that can be found on sites such as eBay.com is overwhelming and can often not be displayed informatively using standard statistical graphics. In this article we introduce graphical methods for visualizing online auction data in ways that are informative and relevant to the types of research questions that are of interest. We start by using profile plots that reveal aspects of an auction such as bid values, bidding intensity, and bidder strategies. We then introduce the concept of statistical zooming (STAT-zoom) which can scale up to be used for visualizing large amounts of auctions. STAT-zoom adds the capability of looking at data summaries at various time scales interactively. Finally, we develop auction calendars and auction scene visualizations for viewing a set of many concurrent auctions. The different visualization methods are demonstrated using data on multiple auctions collected from eBay.com.     

Matrix realizations of littlewood—richardson sequences

In this paper we consider the problem of characterizing the invariant factors of three matrices A B, and C, such that AB — C Our matrices have entries over a principal ideal domain or over a local domain. In Section 2 we show that this problem is localizablc

The above problem lias a well-known solution in terms of Littlewood-Richardson sequences. We introduce the concept of a matrix realization of a Littlewood-Richardson sequence. The main result is an explicit construction of a sequence of matrices which realizes a previously given Littlewood Richardson sequence. Our methods offer a matrix theoretical proof of a well-known result of T, Klein on extensions of p-modules.     

Extending Mosaic Displays: Marginal,Conditional, and Partial Views of Categorical Data

Abstract

This article first illustrates the use of mosaic displays for the analysis of multiway contingency tables. We then introduce several extensions of mosaic displays designed to integrate graphical methods for categorical data with those used for quantitative data. The scatterplot matrix shows all pairwise (bivariate marginal) views of a set of variables in a coherent display. One analog for categorical data is a matrix of mosaic displays showing some aspect of the bivariate relation between all pairs of variables. The simplest case shows the bivariate marginal relation for each pair of variables. Another case shows the conditional relation between each pair, with all other variables partialled out. For quantitative data this represents (a) a visualization of the conditional independence relations studied by graphical models, and (b) a generalization of partial residual plots. The conditioning plot, or coplot shows a collection of partial views of several quantitative variables, conditioned by the values of one or more other variables. A direct analog of the coplot for categorical data is an array of mosaic plots of the dependence among two or more variables, stratified by the values of one or more given variables. Each such panel then shows the partial associations among the foreground variables; the collection of such plots shows how these associations change as the given variables vary.     

New approach to nonrepetitive sequences

A sequence is nonrepetitive if it does not contain two adjacent identical blocks. The remarkable construction of Thue asserts that three symbols are enough to build an arbitrarily long nonrepetitive sequence. It is still not settled whether the following extension holds: for every sequence of three‐element sets L₁,…,L_n there exists a nonrepetitive sequence s₁,…,s_n with s_i∈L_i. We propose a new non‐constructive way to build long nonrepetitive sequences and provide an elementary proof that sets of size 4 suffice confirming the best known bound. The simple double counting in the heart of the argument is inspired by the recent algorithmic proof of the Lovász local lemma due to Moser and Tardos. Furthermore we apply this approach and present game‐theoretic type results on nonrepetitive sequences. Nonrepetitive game is played by two players who pick, one by one, consecutive terms of a sequence over a given set of symbols. The first player tries to avoid repetitions, while the second player, in contrast, wants to create them. Of course, by simple imitation, the second player can force lots of repetitions of size 1. However, as proved by Pegden, there is a strategy for the first player to build an arbitrarily long sequence over 37 symbols with no repetitions of size greater than 1. Our techniques allow to reduce 37–6. Another game we consider is the erase‐repetition game. Here, whenever a repetition occurs, the repeated block is immediately erased and the next player to move continues the play. We prove that there is a strategy for the first player to build an arbitrarily long nonrepetitive sequence over 8 symbols. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012     

Visualization of Multivariate Density Estimates With Level Set Trees

This article presents a method for visualization of multivariate functions. The method is based on a tree structure—called the level set tree—built from separated parts of level sets of a function. The method is applied for visualization of estimates of multivarate density functions. With different graphical representations of level set trees we may visualize the number and location of modes, excess masses associated with the modes, and certain shape characteristics of the estimate. Simulation examples are presented where projecting data to two dimensions does not help to reveal the modes of the density, but with the help of level set trees one may detect the modes. I argue that level set trees provide a useful method for exploratory data analysis.     

A construction of binary Golay sequence pairs from odd‐length Barker sequences

Binary Golay sequence pairs exist for lengths 2, 10 and 26 and, by Turyn's product construction, for all lengths of the form 2^a10^b26^c where a, b, c are non‐negative integers. Computer search has shown that all inequivalent binary Golay sequence pairs of length less than 100 can be constructed from five “seed” pairs, of length 2, 10, 10, 20 and 26. We give the first complete explanation of the origin of the length 26 binary Golay seed pair, involving a Barker sequence of length 13 and a related Barker sequence of length 11. This is the special case m=1 of a general construction for a length 16m+10 binary Golay pair from a related pair of Barker sequences of length 8m+5 and 8m+3, for integer m≥0. In the case m=0, we obtain an alternative explanation of the origin of one of the length 10 binary Golay seed pairs. The construction cannot produce binary Golay sequence pairs for m>1, having length greater than 26, because there are no Barker sequences of odd length greater than 13. © 2009 Wiley Periodicals, Inc. J Combin Designs 17: 478–491, 2009     

The Mixturegram: A Visualization Tool for Assessing the Number of Components in Finite Mixture Models

Certain practical and theoretical challenges surround the estimation of finite mixture models. One such challenge is how to determine the number of components when this is not assumed a priori. Available methods in the literature are primarily numerical and lack any substantial visualization component. Traditional numerical methods include the calculation of information criteria and bootstrapping approaches; however, such methods have known technical issues regarding the necessary regularity conditions for testing the number of components. The ability to visualize an appropriate number of components for a finite mixture model could serve to supplement the results from traditional methods or provide visual evidence when results from such methods are inconclusive. Our research fills this gap through development of a visualization tool, which we call a mixturegram. This tool is easy to implement and provides a quick way for researchers to assess the number of components for their hypothesized mixture model. Mixtures of univariate or multivariate data can be assessed. We validate our visualization assessments by comparing with results from information criteria and an ad hoc selection criterion based on calculations used for the mixturegram. We also construct the mixturegram for two datasets.     

A survey of Skolem-type sequences and Rosa’s use of them

Let D be a set of positive integers. A Skolem-type sequence is a sequence of i ∈ D such that every i ∈ D appears exactly twice in the sequence at positions a _i and b _i , and |b _i − a _i | = i. These sequences might contain empty positions, which are filled with null elements. Thoralf A. Skolem defined and studied Skolem sequences in order to generate solutions to Heffter’s difference problems. Later, Skolem sequences were generalized in many ways to suit constructions of different combinatorial designs. Alexander Rosa made the use of these generalizations into a fine art. Here we give a survey of Skolem-type sequences and their applications. Supported by an NSERC Graduate fellowship. This work is in partial fulfillment of an M.Sc.     

Back to the Local Score in the Logarithmic Case: A Direct and Simple Proof

Let X ₁, ... , X _n be a sequence of i.i.d. integer valued random variables and H _n the local score of the sequence. A recent result shows that H _n is actually the maximum of an integer valued Lindley process. Therefore known results about the asymptotic distribution of the maximum of a weakly dependent process, give readily the expected result about the asymptotic behavior of the local score in the logarithmic case, with a simple way for computing the needed constants. Genomic sequence scoring is one of the most important applications of the local score. An example of an application of the local score on protein sequences is therefore given in the paper.     

Fast detection of common sequence structure patterns in RNAs

We developed a dynamic programming approach for computing common exact sequential and structural patterns between two RNAs, given their sequences and their secondary structures. An RNA consists of a sequence of nucleotides and a secondary structure defined via bonds linking together complementary nucleotides. It is known that secondary structures are more preserved than sequences in the evolution of RNAs.We are able to compute all patterns between two RNAs in time O(nm) and space O(nm), where n and m are the lengths of the RNAs. Our method is useful for describing and detecting local motifs. It is especially suitable for finding similar regions of large RNAs that do not share global similarities. An implementation is available in C++ and can be obtained by contacting one of the authors.     

Generalisations of disjunctive sequences

The present paper proposes a generalisation of the notion of disjunctive (or rich) sequence, that is, of an infinite sequence of letters having each finite sequence as a subword. Our aim is to give a reasonable notion of disjunctiveness relative to a given set of sequences F. We show that a definition like “every subword which occurs at infinitely many different positions in sequences in F has to occur infinitely often in the sequence” fulfils properties similar to the original unrelativised notion of disjunctiveness. Finally, we investigate our concept of generalised disjunctiveness in spaces of Cantor expansions of reals. (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

G-Frame and Riesz Sequences in Hilbert Spaces

G-frames generalize frames in Hilbert spaces. The literatures show that g-frames and frames share many similar properties, while they behave differently in redundancy and perturbation properties. Interestingly, g-frames have been extensively studied, but g-frame sequences have not. This problem is nontrivial since a g-frame and a frame both involve all vectors in the same Hilbert space, while a g-frame sequence and a frame sequence do not. They involve different linear spans. Using the synthesis and Gram matrix methods, we in this paper characterize g-frame sequences and g-Riesz sequences; obtain the Pythagorean theorem for g-orthonormal systems. These results recover several known results and lead to some new results on g-frames.     

Analysis of means approach in advanced designs

Analysis of means (ANOM), similar to Shewhart control chart that exhibits individual mean effects on a graphical display, is an attractive alternative mean testing procedure for the analysis of variance (ANOVA). The procedure is primarily used to analyze experimental data from designs with only fixed effects. Recently introduced, the ANOM procedure based on the q‐distribution (ANOMQ procedure) generalizes the ANOM approach to random effects models. This article reveals that the application of ANOM and ANOMQ procedures in advanced designs such as hierarchically nested and split‐plot designs with fixed, random, and mixed effects enhances the data visualization aspect in graphical testing. Data from two real‐world experiments are used to illustrate the proposed procedure; furthermore, these experiments exhibit the ANOM procedures' visualization ability compared with ANOVA from the point of view of the practitioner.     

Everywhere -repetitive sequences and Sturmian words

Local constraints on an infinite sequence that imply global regularity are of general interest in combinatorics on words. We consider this topic by studying everywhere α-repetitive sequences. Such a sequence is defined by the property that there exists an integer N≥2 such that every length-N factor has a repetition of order α as a prefix. If each repetition is of order strictly larger than α, then the sequence is called everywhere α⁺-repetitive. In both cases, the number of distinct minimal α-repetitions (or α⁺-repetitions) occurring in the sequence is finite.A natural question regarding global regularity is to determine the least number, denoted by M(α), of distinct minimalα-repetitions such that an α-repetitive sequence is not necessarily ultimately periodic. We call the everywhere α-repetitive sequences witnessing this property optimal. In this paper, we study optimal 2-repetitive sequences and optimal 2⁺-repetitive sequences, and show that Sturmian words belong to both classes. We also give a characterization of 2-repetitive sequences and solve the values of M(α) for 1≤α≤15/7.     

Infovis and Statistical Graphics: Different Goals,Different Looks

The importance of graphical displays in statistical practice has been recognized sporadically in the statistical literature over the past century, with wider awareness following Tukey's Exploratory Data Analysis and Tufte's books in the succeeding decades. But statistical graphics still occupy an awkward in-between position: within statistics, exploratory and graphical methods represent a minor subfield and are not well integrated with larger themes of modeling and inference. Outside of statistics, infographics (also called information visualization or Infovis) are huge, but their purveyors and enthusiasts appear largely to be uninterested in statistical principles.

We present here a set of goals for graphical displays discussed primarily from the statistical point of view and discuss some inherent contradictions in these goals that may be impeding communication between the fields of statistics and Infovis. One of our constructive suggestions, to Infovis practitioners and statisticians alike, is to try not to cram into a single graph what can be better displayed in two or more. We recognize that we offer only one perspective and intend this article to be a starting point for a wide-ranging discussion among graphic designers, statisticians, and users of statistical methods. The purpose of this article is not to criticize but to explore the different goals that lead researchers in different fields to value different aspects of data visualization.     

A remark on degree sequences of multigraphs

A sequence {d ₁, d ₂, . . . , d _n } of nonnegative integers is graphic (multigraphic) if there exists a simple graph (multigraph) with vertices v ₁, v ₂, . . . , v _n such that the degree d(v _i ) of the vertex v _i equals d _i for each i = 1, 2, . . . , n. The (multi) graphic degree sequence problem is: Given a sequence of nonnegative integers, determine whether it is (multi)graphic or not. In this paper we characterize sequences that are multigraphic in a similar way, Havel (Časopis Pěst Mat 80:477–480, 1955) and Hakimi (J Soc Indust Appl Math 10:496–506, 1962) characterized graphic sequences. Results of Hakimi (J Soc Indust Appl Math 10:496–506, 1962) and Butler, Boesch and Harary (IEEE Trans Circuits Syst CAS-23(12):778–782, 1976) follow.     

Genus polynomials and crosscap‐number polynomials for ring‐like graphs

An H‐linear graph is obtained by transforming a collection of copies of a fixed graph H into a chain. An H‐ring‐like graph is formed by binding the two end‐copies of H in such a chain to each other. Genus polynomials have been calculated for bindings of several kinds. In this paper, we substantially generalize the rules for constructing sequences of H‐ring‐like graphs from sequences of H‐linear graphs, and we give a general method for obtaining a recursion for the genus polynomials of the graphs in a sequence of ring‐like graphs. We use Chebyshev polynomials to obtain explicit formulas for the genus polynomials of several such sequences. We also give methods for obtaining recursions for partial genus polynomials and for crosscap‐number polynomials of a bar‐ring of a sequence of disjoint graphs.     

Matrix characterization of oscillation for double sequences

The notion of oscillation for ordinary sequences was presented by Hurwitz in 1930. Using this notion Agnew and Hurwitz presented regular matrix characterization of the resulting sequence space. The primary goal of this article is to extend this definition to double sequences, which grants us the following definition: the double oscillation of a double sequence of real or complex number is given P-lim sup_{(m,n)→∞;(α,β)→∞}|S _m,n -S _α,β |. Using this concept a matrix characterization of double oscillation sequence space is presented. Other implication and variation shall also be presented.      

Degree Sequences and the Existence of <Emphasis Type="Italic">k</Emphasis>-Factors

We consider sufficient conditions for a degree sequence π to be forcibly k-factor graphical. We note that previous work on degrees and factors has focused primarily on finding conditions for a degree sequence to be potentially k-factor graphical. We first give a theorem for π to be forcibly 1-factor graphical and, more generally, forcibly graphical with deficiency at most β ≥ 0. These theorems are equal in strength to Chvátal’s well-known hamiltonian theorem, i.e., the best monotone degree condition for hamiltonicity. We then give an equally strong theorem for π to be forcibly 2-factor graphical. Unfortunately, the number of nonredundant conditions that must be checked increases significantly in moving from k = 1 to k = 2, and we conjecture that the number of nonredundant conditions in a best monotone theorem for a k-factor will increase superpolynomially in k. This suggests the desirability of finding a theorem for π to be forcibly k-factor graphical whose algorithmic complexity grows more slowly. In the final section, we present such a theorem for any k ≥ 2, based on Tutte’s well-known factor theorem. While this theorem is not best monotone, we show that it is nevertheless tight in a precise way, and give examples illustrating this tightness.     

An Iterative Approach to Determining the Length of the Longest Common Subsequence of Two Strings

This paper concerns the longest common subsequence (LCS) shared by two sequences (or strings) of length N, whose elements are chosen at random from a finite alphabet. The exact distribution and the expected value of the length of the LCS, k say, between two random sequences is still an open problem in applied probability. While the expected value E(N) of the length of the LCS of two random strings is known to lie within certain limits, the exact value of E(N) and the exact distribution are unknown. In this paper, we calculate the length of the LCS for all possible pairs of binary sequences from N=1 to 14. The length of the LCS and the Hamming distance are represented in color on two all-against-all arrays. An iterative approach is then introduced in which we determine the pairs of sequences whose LCS lengths increased by one upon the addition of one letter to each sequence. The pairs whose score did increase are shown in black and white on an array, which has an interesting fractal-like structure. As the sequence length increases, R(N) (the proportion of sequences whose score increased) approaches the Chvátal–Sankoff constant a _c (the proportionality constant for the linear growth of the expected length of the LCS with sequence length). We show that R(N) is converging more rapidly to a _c than E(N)/N.