Timeline for A simple stochastic game
Current License: CC BY-SA 4.0
32 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| S Jan 25 at 8:01 | history | bounty ended | CommunityBot | ||
| S Jan 25 at 8:01 | history | notice removed | CommunityBot | ||
| Jan 22 at 9:46 | comment | added | Nate River | @PietroMajer Yes this is correct. Probabilists would call this a “Markov strategy”. | |
| Jan 22 at 8:02 | comment | added | Pietro Majer | I haven’t yet read carefully, but could you confirm: A strategy should only depend on the position and on the vector, right? I.e. a function $S:\Omega\times \mathbb S^1\to \{-1,1\}$ ? | |
| Jan 22 at 7:28 | answer | added | domotorp | timeline score: 1 | |
| Jan 17 at 8:19 | comment | added | Nate River | @FedorPetrov Yes, actually there is a theorem that says that if a random variable is adapted to $X$, then it can be written as a deterministic measurable function of $X$. So the two formulations are identical. | |
| Jan 17 at 7:46 | comment | added | Fedor Petrov | Yes, that's what I mean. So, we need a function from the set of pairs (current point, $\pm$ direction of the current step) to ($\pm 1$) which maximizes the expectation | |
| Jan 17 at 6:45 | comment | added | Nate River | @Fedor Petrov Hm, in this formulation, the strategy can depend on the previous moves, i.e. the choice of move at the $n$’th-step depends on the $X_1, \dots, X_n$. Thus it is itself a random variable since it is a function of random variables. The fact that it is adapted to the natural filtration of the $X_i$, however, means that it is “deterministic, once the previous moves are known”. | |
| Jan 17 at 6:40 | comment | added | Fedor Petrov | Why do you say that a strategy is a sequence of random $\pm 1$ variables? An optimal strategy is deterministic, is not it? | |
| S Jan 17 at 6:35 | history | bounty started | Nate River | ||
| S Jan 17 at 6:35 | history | notice added | Nate River | Draw attention | |
| Oct 20, 2022 at 12:32 | comment | added | Nate River | Uh that should read $f(x, y) := -\sup_S \mathbb E[\tau_S^{x, y}]$. | |
| Oct 20, 2022 at 11:31 | comment | added | Nate River | @usul Indeed, in fact we can prove these both by appealing to the so called “dynamic programming principle”. Such an $f$ exists in the explicit form $f(x, y) := -\mathbb \sup_{S} [\tau^{(x, y)}_S]$, where $S$ is a strategy, and $\tau^{(x, y)}_S$ denotes the exit time starting at $(x, y)$. Examining $f$ gives the myopic nature of the strategy. | |
| Oct 19, 2022 at 16:15 | comment | added | usul | (1) Surely the optimal strategy is myopic (i.e. only depends on the current point and not the history). (2) It also seems likely that there exists a function f(x,y), where x,y are horizontal,vertical displacement from the center, such that, given the choice between moving to points described by (x1,y1) or (x2,y2), the optimal choice is the point that minimizes f. Agree? | |
| Oct 19, 2022 at 7:45 | history | edited | Nate River | CC BY-SA 4.0 |
added 1 character in body
|
| S Oct 15, 2022 at 19:04 | history | bounty ended | CommunityBot | ||
| S Oct 15, 2022 at 19:04 | history | notice removed | CommunityBot | ||
| Oct 9, 2022 at 16:32 | history | edited | Nate River |
edited tags
|
|
| Oct 9, 2022 at 0:44 | comment | added | Nate River | @Steve Yes, it is finite using the reasoning suggested by Steven Stadnicki in the above comment. Namely you can bound the expectation by that of a geometrically distributed random variable. | |
| Oct 8, 2022 at 17:07 | comment | added | Steve | Do we know if the supremum is always finite? In particular, if the supremum were infinite for circles, then it would also be infinite for large enough squares using the same strategy. | |
| Oct 7, 2022 at 18:12 | comment | added | Steven Stadnicki | Because it took me a moment to convince myself: the finiteness argument is that there's a $\epsilon$ such that for any position $P$ of the runner, a positive fraction of movement vectors $x$ have both $P+x$ and $P-x$ at least $\epsilon$ further from the origin than $P$, and therefore for any distance $d$ a positive probability of getting a sequence of moves (of length $\lceil d/\epsilon\rceil$) that force the runner to distance $d$ from the center. | |
| Oct 7, 2022 at 18:02 | comment | added | Ronnie Pavlov | This is a bit naive, but maybe you can turn it into something useful. You can iteratively define regions $S_k$ where some $k$ vectors in a row could force you to exit. $S_1$ is all centers of line segments of length 2 with endpoints outside square, which seems to just be a quarter disc of radius 1 in each corner. Then $S_2$ is all centers of segments of length 2 with endpoints in $S_1$ or outside square, etc. One strategy is to minimize the index of the $S_i$ you enter. I think it optimizes something, but probably not expected exit time. It should coincide with optimal for circles at least. | |
| S Oct 7, 2022 at 17:33 | history | bounty started | Nate River | ||
| S Oct 7, 2022 at 17:33 | history | notice added | Nate River | Draw attention | |
| Oct 5, 2022 at 23:37 | comment | added | Nate River | Anyhow, in the case of a square, we now have two (symmetric) parameters to worry about - vertical and horizontal distance from the center. | |
| Oct 5, 2022 at 23:36 | comment | added | Nate River | @RonniePavlov Yes in the case of the circle, there is only the distance from the center as the sole invariant we need to care about. I was thinking that the expected number of moves to exit from being $r$ distance away from the center (given an optimal strategy) should be monotone decreasing in $r$, and hence the optimal move is always to go toward the center, or minimise distance from it rather. That said, I am uncertain as to whether it’s actually monotone for all $r$… | |
| Oct 5, 2022 at 23:34 | comment | added | Ronnie Pavlov | I guess if your shape is a circle, optimal strategy is the one to minimize distance from the center. (For a circle, by symmetry distance from center is all that matters, and there has to be some monotonicity/coupling argument implying that choosing smaller distance is always best.) For a square my feeling is that the geometry is going to make things horrible to deal with. A crazy conjecture is that minimizing $L^1$ distance from the center is optimal, but I doubt this is true (probably slightly higher $L^1$ distance along edge is better than slightly lower $L^1$ distance in a corner). | |
| Oct 5, 2022 at 21:23 | history | edited | Nate River | CC BY-SA 4.0 |
Corrected typo
|
| Oct 5, 2022 at 21:03 | history | edited | Nate River | CC BY-SA 4.0 |
edited body
|
| Oct 5, 2022 at 20:52 | history | edited | Nate River | CC BY-SA 4.0 |
added 486 characters in body
|
| Oct 5, 2022 at 17:28 | history | edited | Nate River | CC BY-SA 4.0 |
added 35 characters in body
|
| Oct 5, 2022 at 17:21 | history | asked | Nate River | CC BY-SA 4.0 |