9
votes
Optimal stopping in red vs black card game deck of 52 cards
Let $v(r,b)$ be the expected value of the game for the player, assuming optimal play, if the remaining deck has $r$ red cards and $b$ black cards.
Then $v(r,b)$ satisfies the recursion
$$
v(r,b) =
\...
- 59.5k
4
votes
Accepted
Deriving of optimal decision boundary of two Gaussians
The approach is correct and the solution is almost correct.
$$\begin{aligned}
x^2-2x\mu_1+\mu_1^2&=x^2-2x\mu_2+\mu_2^2
\\\iff 2x(\mu_2-\mu_1)&=\mu_2^2-\mu_1^2
\\\iff x^*&=\dfrac{\mu_2+\...
- 1,111
4
votes
Accepted
Proving a (Representing Utility) Function is Continuous
This answer is for proving $\alpha(x)$ is continuous on $\mathbb{R}^L_+$. Before we proceed, we need a proposition:
Proposition$\quad$ Consider a sequence $\{x_n\}$ on $X$. Suppose $\{x_n\}$ lies in ...
- 56
3
votes
Sum of two stopping times is a stopping time?
There is a brief proof in the book ``S. W. He et al., Semimartingale Theory and Stochastic Calculus, CRC Press Inc, 1992.''(p.84, Th.3.7.(3)).
The proof is based on following fact(Th.3.7.(1)): If $S$...
- 5,451
3
votes
Sum of two stopping times is a stopping time?
Nates' answer is on the right track but assumes right continuity. The definition of stopping time is $\{\sigma \le t\}\in \mathcal{F}_t$ (instead of $\{\sigma < t\}\in \mathcal{F}_t$). Stefan's ...
- 2,037
3
votes
Gittins Index for a simple example
Gittins indices are hard to compute. This paper offers a good overview of various algorithms:
http://www.ece.mcgill.ca/~amahaj1/projects/bandits/book/2013-bandit-computations.pdf
- 41
3
votes
How we decide for a given context free grammar generate an infinite number of strings?
One way of determining whether a given context-free grammar $G$ produces an infinite language is this:
Find a grammar $G^+$ with $L(G^+) = L(G)$ such that $G'$ has no rules on the form $A \to \...
- 688
3
votes
Accepted
Non-Optimality of First-Fit-Decreasing Algorithm for Bin Packing
Consider a bin size of 10 with item sizes 5, 4, 3, 2, 2, 2, 2, 2. This could be partitioned into two bins (5, 3, 2 and 4, 2, 2, 2) but the First-Fit-Decreasing method would require 3 bins, since it ...
- 32.3k
3
votes
Optimal strategy in a number-picking game against a perfect logician?
I assume each player is aiming to maximize their own chance of winning (and that tying does not count as winning for either player). Then one possible Nash equilibrium for the game appears to be for ...
- 1,217
2
votes
Von Neumann–Morgenstern independence axiom vs. Savage independence theorm
This answer corrects my previous answer (almost 10 years old) which misleadingly compared Vnm's model with a state-dependent model, as opposed to Savage's model which the OP asks about.
The difference ...
- 2,484
2
votes
Listing possible decision functions and their meanings
I figured that in $d(X)$, $X$ must represent the number of heads/successes/wins you get for a $\operatorname{Bin}(2,p)$.
- 21
2
votes
Accepted
Have there been any attempts to unify statistics and decision theory into a single framework that refrains from estimating probabilities?
One basic distinction in decision theory maps onto something roughly like the distinction you have in mind.
Objective decision theory (e.g. von Neumann & Morgenstern) addresses problems in which ...
- 1,174
2
votes
Basic concept of utility: utility of expected value vs expected utility
This situation can happen when an individual is risk adverse. Take for example a fair coin flip bet--if heads, the person wins 1 dollar, if tails, the person loses a dollar. Let's say for this ...
- 8,239
2
votes
Accepted
Which route is better for a Neutral-risk person?
Based on what's being described here, you have already solved the problem.
https://en.wikipedia.org/wiki/Risk_neutral
Risk-neutral people don't worry about the uncertainty involved, they just ...
- 555
2
votes
Is the halting problem also undecideable for turing machines always writing a $1$ on the tape?
Yes, the problem is decidable. With a few tricks, it may even be possible to find an algorithm polynomial in $Q$, the number of states in the machine, though in the rest of this answer I'll just prove ...
- 17.8k
2
votes
Can the halting problem for bounded Turing machines be efficiently decided?
I would say that as with most of these kinds of halting/busy beaver problems, both approaches (pure analysis and simulation) will prove to be useful.
Yes, for some machines you can determine their ...
- 102k
2
votes
What are some natural ways to compare random variables?
In contrast to real numbers there exists no all-purpose total order on random variables. This is why it is so hard to say something in general and might be the reason why your question has received so ...
- 2,747
2
votes
Accepted
Log utility function and the St. Petersburg paradox
My guess would be numerical methods. For example, in Python I get the following results, using a sort of binary search to hone in on the value of $c$ that makes the expected value near-$0$:
...
- 4,951
2
votes
Decision theory vs. Game theory?
I agree with @Trurl's comment on this. Decision theory is more a component of optimal control theory rather than game theory. In control theory you have an environment you are navigating through to ...
- 416
2
votes
Does the von Neumann-Morgenstern utility theorem work for infinitely many outcomes?
It is not fully clear to me what the question is, but there is a huge literature on versions of the von Neumann and Morgenstern utility representation on infinite sets. The most common approach is to ...
- 5,508
2
votes
Accepted
Game theory - How was the table of decision analysis formulation constructed?
The $6$ was included. If the company sells $10,000$ with a variable profit of $600$ each they make $6$ million, but the fixed cost is $6$ million, so the profit is $0$. If they sell $100,000$, the ...
- 379k
2
votes
Accepted
Understanding a part of the theorem from Ferguson's book
Since $b_0=\inf B$, there exists a sequence $(\beta_n)_{n\geq 1}$ of elements of $B$ such that $\lim_n\beta_n = b_0$. As in the book, write $\beta_n = \sum_{j=1}^k p_jy_j^{(n)}$ where $(y_1^{(n)},\...
- 36k
2
votes
Accepted
Solving an optimal stopping problem with pulling a card of a certain color
You can prove by induction that the value of the game is always the current proportion of red cards, and you obtain this value whether you stop or continue, so it doesn’t matter when you stop.
- 240k
2
votes
Can we make a voting system where it is cryptographically hard to find a dictator
After reading some of the literature mentioned in the comments, I am convinced that my original question was flawed. Specifically, I accept that there is no way to meet the first two fairness criteria ...
- 335
2
votes
Accepted
Does this proof of a voting related lemma work? if so, how?
It would be more clear if we separated out the claim into two parts:
If $v$ is decisive for $(a,b)$ and $c$ is any third candidate, then $v$ is decisive for $(a,c)$.
If $v$ is decisive for $(a,b)$ ...
- 146k
2
votes
Accepted
"Markov Decision Process" with target states and shortest path as only constraints
Your approach looks reasonable if you set $R=1$ for transitions from transient to target states, $R=0$ for all other transitions, and $\gamma>0$. Because your state space and action sets are ...
- 48.2k
2
votes
Finding stable sets from a graph
I don't know what you mean by "a set of connected vertices". A stable set (independent set) is simply a set of pairwise nonadjacent vertices. For example, in the given graph, $\{A, C, D, E, ...
- 2,726
2
votes
Accepted
Example where r.v. $X_2$ stochastically dominates $X_1$ but $P(X_1 > X_2) \geq 0.95$
Let $X_2$ be a discrete uniform distribution over the set $\{1, \cdots, n\}$, and define
$$X_1=X_2+1 \text{ if } X_2= 1, \cdots, n-1$$
$$X_1=1 \text{ if } X_2=n.$$
Indeed, $X_1$ is obtained by a ...
- 10.2k
2
votes
Accepted
Infinite sum $\sum_{t=c}^{n-1}(\frac{1}{t^2-1})$ as part of cardinal payoff variant
$$
\begin{align}
\sum_{t=c}^{n-1}\frac1{t^2-1}
&=\frac12\sum_{t=c}^{n-1}\left(\frac1{t-1}-\frac1{t+1}\right)\tag{1a}\\
&=\frac12\left(\frac1{c-1}+\frac1c-\frac1{n-1}-\frac1n\right)\tag{1b}
\...
- 349k
1
vote
Accepted
Proving that the language is not recursive enumerable
The language above defines the set of Turing machines which never halt on any input. Note, this is the same thing as visiting a state an infinite number of times, assuming that the number of states ...
- 4,749
Only top scored, non community-wiki answers of a minimum length are eligible