Dgdrxrt

How can I protect witches in combat who wear limited clothing?

How to delete random line from file using Unix command?

Why can't devices on different VLANs, but on the same subnet, communicate?

How to stretch delimiters to envolve matrices inside of a kbordermatrix?

What information about me do stores get via my credit card?

ipsec, esp: Which key is used to generate the HMAC

how can a perfect fourth interval be considered either consonant or dissonant?

Working through the single responsibility principle (SRP) in Python when calls are expensive

How did the audience guess the pentatonic scale in Bobby McFerrin's presentation?

How to test the equality of two Pearson correlation coefficients computed from the same sample?

How to politely respond to generic emails requesting a PhD/job in my lab? Without wasting too much time

What aspect of planet Earth must be changed to prevent the industrial revolution?

Match Roman Numerals

Why is superheterodyning better than direct conversion?

Why does the Event Horizon Telescope (EHT) not include telescopes from Africa, Asia or Australia?

How to pronounce 1ターン?

Why not take a picture of a closer black hole?

Can a 1st-level character have an ability score above 18?

Would an alien lifeform be able to achieve space travel if lacking in vision?

The following signatures were invalid: EXPKEYSIG 1397BC53640DB551

Keeping a retro style to sci-fi spaceships?

system() function string length limit

How many people can fit inside Mordenkainen's Magnificent Mansion?

How to copy the contents of all files with a certain name into a new file?

Computing expected minimum of stopping time and n with simple random walk

0

$begingroup$

Let $(S_n)$ be an elementary random walk, ie. $S_n = sum_i=1^n X_i$ where $P(X_i = 1) = P(X_i = -1) = frac12$.

Let $T = inf n : S_n in -2,2$. $T$ is clearly a stopping time and is almost surely finite. We use the notation $T land n$ to mean $minT,n$.

I need to prove that $E(T land n) = 4P(T leq n) + K$, where $K$ is an error term that is bounded by $P(T > n)$.

I've tried the following so far:

$$
E[T land n] = E[T mathbb1_T leq n + n mathbb1_T > n]
= E[T mathbb1_T leq n] + nP(T > n)
$$

But I can't work out how to proceed. The second term on the RHS is $nP(T>n)$ which is not bounded by $P(T > n)$, and I can't see where the factor of $4$ could come from.

probability probability-theory martingales random-walk

share|cite|improve this question

edited Mar 31 at 14:31

D G

asked Mar 31 at 13:37

D GD G

1629

$endgroup$

add a comment | 

0

$begingroup$

Let $(S_n)$ be an elementary random walk, ie. $S_n = sum_i=1^n X_i$ where $P(X_i = 1) = P(X_i = -1) = frac12$.

Let $T = inf n : S_n in -2,2$. $T$ is clearly a stopping time and is almost surely finite. We use the notation $T land n$ to mean $minT,n$.

I need to prove that $E(T land n) = 4P(T leq n) + K$, where $K$ is an error term that is bounded by $P(T > n)$.

I've tried the following so far:

$$
E[T land n] = E[T mathbb1_T leq n + n mathbb1_T > n]
= E[T mathbb1_T leq n] + nP(T > n)
$$

But I can't work out how to proceed. The second term on the RHS is $nP(T>n)$ which is not bounded by $P(T > n)$, and I can't see where the factor of $4$ could come from.

probability probability-theory martingales random-walk

share|cite|improve this question

edited Mar 31 at 14:31

D G

asked Mar 31 at 13:37

D GD G

1629

$endgroup$

add a comment | 

$begingroup$

Let $(S_n)$ be an elementary random walk, ie. $S_n = sum_i=1^n X_i$ where $P(X_i = 1) = P(X_i = -1) = frac12$.

Let $T = inf n : S_n in -2,2$. $T$ is clearly a stopping time and is almost surely finite. We use the notation $T land n$ to mean $minT,n$.

I need to prove that $E(T land n) = 4P(T leq n) + K$, where $K$ is an error term that is bounded by $P(T > n)$.

I've tried the following so far:

$$
E[T land n] = E[T mathbb1_T leq n + n mathbb1_T > n]
= E[T mathbb1_T leq n] + nP(T > n)
$$

But I can't work out how to proceed. The second term on the RHS is $nP(T>n)$ which is not bounded by $P(T > n)$, and I can't see where the factor of $4$ could come from.

probability probability-theory martingales random-walk

share|cite|improve this question

edited Mar 31 at 14:31

D G

asked Mar 31 at 13:37

D GD G

1629

$endgroup$

share|cite|improve this question

edited Mar 31 at 14:31

D G

asked Mar 31 at 13:37

D GD G

1629

share|cite|improve this question

edited Mar 31 at 14:31

D G

asked Mar 31 at 13:37

D GD G

1629

asked Mar 31 at 13:37

D GD G

1629

asked Mar 31 at 13:37

D GD G

1629

1 Answer
1

active

oldest

votes

0

$begingroup$

The key was to consider the Martingale $M_n = S_n^2 - n$. Applying the optional stopping theorem to the stopped Martingale $M_n land T$ gives that

$$0 = EM_0 = EM_T land n = ES_T land n - E[T land n]$$

and solving $ES_T land n$ by considering cases.

share|cite|improve this answer

answered Mar 31 at 14:50

D GD G

1629

$endgroup$

add a comment | 

Your Answer

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3169404%2fcomputing-expected-minimum-of-stopping-time-and-n-with-simple-random-walk%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

0

$begingroup$

The key was to consider the Martingale $M_n = S_n^2 - n$. Applying the optional stopping theorem to the stopped Martingale $M_n land T$ gives that

$$0 = EM_0 = EM_T land n = ES_T land n - E[T land n]$$

and solving $ES_T land n$ by considering cases.

share|cite|improve this answer

answered Mar 31 at 14:50

D GD G

1629

$endgroup$

add a comment | 

0

$begingroup$

The key was to consider the Martingale $M_n = S_n^2 - n$. Applying the optional stopping theorem to the stopped Martingale $M_n land T$ gives that

$$0 = EM_0 = EM_T land n = ES_T land n - E[T land n]$$

and solving $ES_T land n$ by considering cases.

share|cite|improve this answer

answered Mar 31 at 14:50

D GD G

1629

$endgroup$

add a comment | 

$begingroup$

The key was to consider the Martingale $M_n = S_n^2 - n$. Applying the optional stopping theorem to the stopped Martingale $M_n land T$ gives that

$$0 = EM_0 = EM_T land n = ES_T land n - E[T land n]$$

and solving $ES_T land n$ by considering cases.

share|cite|improve this answer

answered Mar 31 at 14:50

D GD G

1629

$endgroup$

share|cite|improve this answer

answered Mar 31 at 14:50

D GD G

1629

answered Mar 31 at 14:50

D GD G

1629

answered Mar 31 at 14:50

D GD G

1629