"So basically,when it comes to saving lives, docs are three times more likely to recommend a screening test based on irrelevant data than they are to recommend it based on relevant data. I’m bracing myself for the hate mail, but this is part of the reason why I’m skeptical that just providing docs with more evidence will change the way they practice. Most docs just aren’t trained to understand this stuff."

e multi-armed bandit problem is a popular model for studying exploration/exploitation trade-off in sequential decision problems. Many algorithms are now available for this well-studied problem. One of the earliest algorithms, given by W. R. Thompson, dates back to 1933. This algorithm, referred to as Thompson Sampling, is a natural Bayesian algorithm. The basic idea is to choose an arm to play according to its probability of being the best arm. Thompson Sampling algorithm has experimentally been shown to be close to optimal. In addition, it is efficient to implement and exhibits several desirable properties such as small regret for delayed feedback. However, theoretical understanding of this algorithm was quite limited. In this paper, for the first time, we show that Thompson Sampling algorithm achieves logarithmic expected regret for the multi-armed bandit problem. More precisely, for the two-armed bandit problem, the expected regret in time $T$ is $O(frac{ln T}{Delta} + frac{1}{Delta^3})$. And, for the $N$-armed bandit problem, the expected regret in time $T$ is $O([(sum_{i=2}^N frac{1}{Delta_i^2})^2] ln T)$. Our bounds are optimal but for the dependence on $Delta_i$ and the constant factors in big-Oh.

"In probability theory, the coupon collector's problem describes the "collect all coupons and win" contests. It asks the following question: Suppose that there are n coupons, from which coupons are being collected with replacement. What is the probability that more than t sample trials are needed to collect all n coupons? An alternative statement is: Given n coupons, how many coupons do you expect you need to draw with replacement before having drawn each coupon at least once. The mathematical analysis of the problem reveals that the expected number of trials needed grows as Θ(nlog(n)). For example, when n = 50 it takes about 225 trials to collect all 50 coupons."

"…While several practical uses of the method have been proposed in Monte Carlo applications, these require an implementation framework that is flexible, general and efficient. We present such a framework for functions that are either strictly linear, concave, or convex on the unit interval using a series of envelope functions defined through a cascade, and show that this method not only greatly reduces the number of input bits needed in practice compared to other currently proposed solutions for more specific problems, but can easily be coupled to more asymptotically efficient methods to allow for theoretically strong results."

"Wigmore’s technique, like probability itself, is both wide-ranging and tediously painstaking; his book was popular only among insomniac judges. But now that computers can take on the numerical drudgery, it is proving its worth in just such tangled cases as Sacco’s and Vanzetti’s. The legal scholars Joseph Kadane and David Schum have applied a sophisticated extension of Wigmore’s method to the vast body of evidence from the case. Theirs is a remarkable achievement; their charts retain all the original complexities: the facts withheld or perverted, the hearsay, the lies told and disavowed on both sides, the charged political atmosphere of eighty years ago. They never discount a fact, no matter how far-fetched; they  simply give it its due weight in their dynamic structure.

Their conclusion?  Unjust though it is to summarize a book in a sentence, the balance of probability seems to favor the view expressed long ago by one of the defendants’ close companions: “everyone in the Boston anarchistic circle knew that Sacco was guilty and that Vanzetti was innocent as far as the actual participation in the killing.” So, there it is: whichever side our political instincts favor, we are destined to be half wrong.

Vanzetti’s last words were: "I wish to forgive some people for what they are now doing to me."  If we were all willing to make the extra effort to work out the probabilities, perhaps we might not need forgiveness so often."

"At the most fundamental level, computers are an assembly of gates that are used to perform the basic operations required to execute a program. For problems in the probability domain, even the values used in these most basic operations are not constrained to be either a 0 or a 1. Instead, the basic gates must determine the probability that a bit is a 1, or the probability that it is a 0.
Lyric’s gates are designed to model relationships between probabilities natively in the device physics. For this reason, Lyric can perform mathematical operations in the probability domain with just a handful of transistors – creating power and area savings of more than 10X over traditional implementations."

"Whereas a conventional NAND gate outputs a "1" if neither of its inputs match, the output of a Bayesian NAND gate represents the odds that the two input probabilities match. This makes it possible to perform calculations that use probabilities as their input and output."

"…The intrinsic underlying structure of the system is modeled by an epsilon-machine and its causal states. The decisional states are the emerging patterns corresponding to the utility function. In a complex systems perspective, these patterns thus form a partition of the lower-level system states that is defined according to the higher-level user's knowledge. The transitions between these decisional states correspond to events that lead to a change of decision. An algorithm is provided so as to estimate the states and their transitions from data. Application examples are given for hidden model reconstruction, cellular automata filtering, and edge detection in images."

"Object orientation provides a flexible framework for the implementation of the convolution of arbitrary distributions of real-valued random variables.
We discuss an algorithm which is based on the Discrete Fourier Transformation and its fast computability via the Fast Fourier Transformation. It directly applies to lattice-supported distributions. In the case of continuous distributions an additional discretization to a linear lattice is necessary and the resulting lattice-supported distributions are suitably smoothed after convolution."

"Since multivariate Boltzmann samplers can be obtained in any situation where the distribution is well-concentrated, one may envision extensions to other classes, including constrained trees, permu- tations with a fixed number of cycles, functional graphs with a controlled number of components.…"

"We describe von Neumann's elegant idea for sampling from the exponential distribution, Forsythe's generalization for sampling from a probability distribution whose density has the form exp(-G(x)), where G(x) is easy to compute (e.g. a polynomial), and my refinement of these ideas to give an efficient algorithm for generating pseudo-random numbers with a normal distribution. Later developments are also mentioned."

"We aren't enchanted by Bayesian methods merely because they're beautiful. The beauty is a side effect."