How to Lose with Least Probability,
Robery Chen, Burton Rosenberg
arXiv:1112.2117v2 [math.PR] at http://arxiv.org/abs/1112.2117,
9 December 2011.
Abstract:
Two players alternate tossing a biased coin where the probability of
getting heads is p. The current player is awarded alpha points for tails
and alpha+beta for heads. The first player reaching n points wins.
For a completely unfair coin the player going first certainly wins.
For other coin biases, the player going first has the advantage, but the
advantage depends on the coin bias. We calculate the first player's advantage
and the coin bias minimizing this advantage.
ArXiv
On the first occurrence of strings,
Robert Chen, Alan Zame, and Burton Rosenberg
The Electronic Journal of Combinatorics,
16 (1), Feb 27, 2009. R29.
Abstract:
We consider a game in which players select strings over {0,1}
and observe a series of fair coin tosses, interpreted as a string
over {0,1}. The winner of this game is the player whose
string appears first. For two players public knowledge of the
opponent's string leads to an advantage. In this paper, results
for three players are presented.
It is shown that given the choices of the first two players,
a third string can always be chosen with probability of winning
greater than 1/3. It is also shown that two players can chose
strings such that the third player's probability of winning is
strictly less than the greater of the other two player's
probability of winning, and that whichever string is chosen,
it will always have a disadvantage to one of the two other
strings.
PDF
Optimal exercise of russian options in the binomial model,
Robert W, Chen,
Burton Rosenberg,
Computational Finance and its Applications,
WIT Press (2006) pp 171-181.
Abstract:
The Russian Option is a two-party contract
which creates a liability for the option seller to pay the
option buyer an amount equal to the maximum
price attained by a security over a specific time
period, discounted for the option's age.
The Russian option was proposed by Shepp and Shiryaev.
Kramkov and Shiryaev first examined the option in the binomial model.
We improve upon their results and give a near-optimal algorithm
for price determination.
Specifically, we prove that the optimal exercising
boundary is monotonic and give an O(N) dynamic programming
algorithm to construct the boundary,
where N is the option expiration time.
The algorithm also computes the option's value at time zero in
time O(N) and the value at all of the O(N3) nodes
in the binomial model in time O(N2).
PDF
Errata
Powerpoint
Inferring model parameters in markets with collars,
Robert Chen,
Burton Rosenberg,
Yi-Tsung Lee,
Computational Finance and its Applications,
WIT Press (2004) 167-175.
Abstract:
Security prices are set by a continuous auction
which can be modeled by a random walk.
For many exchanges, there is a general free-flow of price
information resulting in stock prices which can be modeled by a
random walk following a Weiner-Levy process.
However many markets have collars which will not let prices
move too rapidly. In this paper we present methods for estimating
the volatility of the underlying price data when the true price
information is obscured by such collars.
Numerical simulations are presented which demonstrate and contrast
the methods.
PDF
Full Paper in PDF
Fast nondeterministic recognition of contex-free languages using
two queues,
Burton Rosenberg,
Information Processing Letters 67
(1998) 91-93.
Abstract: We show how to accept a context-free language
nondeterministically in O(n log n) time on a two-queue machine.
PDF
PS
A secretary problem with two decision makers,
Robert Chen, Burton Rosenberg and Larry Shepp,
Journal of Applied Probability 34 (1997) 1068-1074.
Abstract: Applicants of similar qualifications
are on an interview list and their salary demands are from a
known and continuous distribution. Two managers will interview
them one at a time, deciding to hire or pass.
In this paper, we derive the optimal
strategies to maximize the probability that the applicant hired demands
less salary than the applicant hired by the other manager.
PDF
PS
Simplex Range Reporting on a Pointer Machine,
Bernard Chazelle and Burton Rosenberg,
Computational Geometry: Theory and Applications 5 (1996) 237-247.
Abstract:
We give a lower bound on the following problem, known as
simple range reporting: Given a collection P of n points in d-space
and an arbitrary simplex q, find all points in P intersect q.
It is understood that P is fixed and can be preprocessed ahead of
time, while q is a query that must be answered on-line.
We consider data structures for the problem which can be modeled
on a pointer machine and whose query time is bounded by
O(n^delta+r), where r is the number of points to be reported
and delta is an arbitrary fixed real. We prove that any such
data structure of that form must occupy space
Omega{n^(d(1-delta)-epsilon)},
for any fixed epsilon>0. This lower bound is tight within a
factor of n^epsilon.
PDF (missing figures)
PS
The Web learning pages,
Burton Rosenberg, unpublished manuscript, April 1995.
Abstract:
The Web Learning Pages is a project to reinforce and accelerate
classroom learning in the Department of Mathematics and Computer
Science at the University of Miami. The doctrine followed by these
pages is that Web information is of a new and unusual type:
partly static, like a book, and partly real-time, like a conversation.
We are trying to exploit this transitional nature of the Web
for more effective and efficient teaching.
PDF (missing figures)
PS (Figure 1)
PS (Figure 2)
Two experiments in the stability of stock statistics,
Burton Rosenberg,
Third International Conference on Artificial Intelligence
Applications on Wall Street (1995), 182-187.
Abstract:
This paper announces support in the form of the Spearman rank
correlation test for the hypothesis: stock variance is a stable
commodity, but the covariance of stocks varies randomly.
Among the consequence of this hypothesis are:
Simulating a stack by queues,
Burton Rosenberg, Proceedings of the XIX
Latinamerican Conference on Computer Science 1 (1993), 3-13.
Abstract:
We explore the complexity relationships between finite automata endowed
with various data structures as auxiliary stores. It is shown that
queue automata, finite state machines with one or more queues,
are Turing Equivalent. A finite automata with two stacks can simulate
a (one) queue automata in constant amortized time per operation
simulated. The converse question, simulating a (one) stack machine
by a queue machine is not satisfactorily resolved. We give an O(n log n)
amortized cost solution using a generalized queue automata.
PS
Constraint programming and graph algorithms,
Michel Gangnet and Burton Rosenberg,
Annals of Mathematics and Artificial Intelligence, 8:3-4(1993).
Abstract:
A constraint system includes a set of variables and a set of
relations among these variables, called constraints. The solution
of a constraint system is an assignment of values to variables so that all,
or many, of the relations are made true. A simple and efficient method
for constaint resolution has been proposed in the work of Bjorn N.
Freeman-Benson, John Maloney, and Alan Borning. We show how their method
is related to the classical problem of graph matching, and from this
connection we derive new resolution algorithms.
PS
Lower bounds on simplex range reporting on a pointer machine,
Bernard Chazelle and Burton Rosenberg,
Nineteenth International Colloquium on Automata, Languages
and Programming, LNCS 623 (1992), 439--449.
Abstract:
We give a lower bound on the following problem, known as
simple range reporting: Given a collection P of n points in d-space
and an arbitrary simplex q, find all points in P intersect q.
It is understood that P is fixed and can be preprocessed ahead of
time, while q is a query that must be answered on-line.
We consider data structures for the problem which can be modeled
on a pointer machine and whose query time is bounded by
O(n^delta+r), where r is the number of points to be reported
and delta is an arbitrary fixed real. We prove that any such
data structure of that form must occupy space
Omega{n^(d(1-delta)-epsilon)},
for any fixed epsilon>0. This lower bound is tight within a
factor of n^epsilon.
PDF (no figures)
PS
The complexity of computing partial sums off-line,
Bernard Chazelle and Burton Rosenberg,
International Journal of Computational Geometry and Applications
1:1 33--45 (1991).
Abstract:
Given an array A with n entries in an additive semigroup,
and m intervlas of the form I=[i,j], where
0 < i < j <= n, we show that the computation
A[i]+...+A[j] for all I_i requires
Omega(n + m alpha(m,n)) semigroup additions. Here, alpha
is the functional inverse of Ackermann's function. A matching upper
bound has already been demonstrated.
PS
Lower Bounds in Geometric Searching,
Burton Rosenberg, Department of Computer Science, Princeton University
CS-TR-343-91 (1991). PhD Thesis. Advisor: Bernard Chazelle.
Computing partial sums in multidimensional arrays,
Bernard Chazelle and Burton Rosenberg,
Fifth Annual ACM Symposium on Computational Geometry
(1989) 131--139.
PS
Survey of NC problems,
Burton Rosenberg,
Master of Science Thesis, Columbia University, (1986).
Abstract:
An overview of the class of log-depth, polynomial sized
circuit complexity. The addition circuit presented in section
3.2 is original work.
PDF
Reversibility in computer architecture,
Burton Rosenberg,
Bachelor of Science Thesis, M.I.T. (1980).
Abstract:
The natural environment of a few generations ago is being
replaced with an environment of technology.In that these
technologies are mass produced, this constitutes a powerful
and unrecognized form of controlled media.
Preface.