Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Setup. Let casisno generate a color: black or red with equal probability.

Let client try to guess the color. If guess is correct - he earns 1 coin from casino, if not - he gives one to casino. If he loses all his coins he stops the game.

Assume that client comes to casino with just 1 coin, while casino has infinite number of coins.


"Paradox" and informal question A small paradox is that casino does not win, while clients do lose. The cheating is that win and loss are in different senses (look below). Nevertheless it is somewhat contrintuitive for me, and some others, so the informal question is - can you give an intuitive exlanation.


Formal questions. Part A. Client's loss quantitatively.

(1) A numerical experiment suggests that probabilty of client to lose behaves like $P_{loss}(T) = 1 - .8/\sqrt T $ (approximately). $T$ is "time" - number of times we play. What is true formula ? Can one explain in simple way at least this $\sqrt T$ ?

(2) Average time to lose seems to behave like $ .8 \sqrt T $. (Averaging is taken over all "loss-trajectories"). What is true formula ? Can one explain in simple way at least this $\sqrt T$ ? Numerically I see $.8$ in both formulas - is it correct ?

Theory Background What I call "client's loss" is usually called "hitting time for a random walk". For $T=\infty$ the distribution of hitting time is known to be Levy distribution (thanks to D. Zare for comment). However this fact does not seem to imply the answer to my question, since I am interested in finite "T", while result is about $T=\infty$.

Part B. Casino does not win.

We can cosider the casino profit (number of coins it earned/lossed from the client) after time "T". It is a random variable.

"Fact" E(Profit) = 0, for all "T". ("E" is expectation value).

I think it follows from the arguments One can earn nothing on the Brownian motion, true ?, but if someone can propose very simple argument, I would be very thankful.


"Paradox" To conclude we see that sooner or later clients will leave all their coins at casino. So it may seems that casino should win. But "fact" above says that expectation value of casino's profit is equal to zero. There is something contrintuitive, is not it ?


PS

I guess the questions are simple for experts in probability, but I do not think it is reason not to post it here. This is completely rewritten version of previos question.

Matlab code

tStart = tic; 

%T = 5000;
tVec = 500:500:10000; 
cnt = 0;
for T= tVec
    cnt = cnt + 1;
    HitCount = 0;
    HitTime = 0;
    for trial = 1:100000
        %v=2*randi(2,T)-3; % generate random walk's increments - vector of length "T" with random +1 and -1 
        s = 0;
        for l=1:T
            s = s +  (2*randi(2,1)-3); % generate random walk
            %s = sum(v(1:l));
            if (s<= -1 ) %check does not Hites "-1"
                HitCount = HitCount + 1; HitTime = HitTime + l; break; % calculate how many times it Hites out of many trials
            end;
        end;

    end;
    resultingProbability(cnt) = HitCount/ trial;
    averageHitTime(cnt) = HitTime/ HitCount;
    fprintf(1,'HitHitTime/sqrt(T) =%f', averageHitTime(cnt)/sqrt(T));
    fprintf(1,'(1- HitProb)*sqrt(T) =%f, \n', averageHitTime(cnt)/sqrt(T));

    fprintf(1,'Passed Secs  %f \n',  toc(tStart)  );
end;

loglog(tVec, averageHitTime );
figure
loglog(tVec, 1-resultingProbability );
share|improve this question
1  
Keeping it to the random walk case, you can observe that of the paths that touch -1, half will end below and half above. Of the paths that end below, by "continuity" of the paths, you can conclude that they touched -1. So the probability of striking -1 in the interval from [0,T] is just twice the probability that W(T) <= -1. Now you can read off whatever you'd like. This is called the reflection principle, and it also allows you to reason about Brownian motion, but requires a little more care to apply there. –  Josh Shadlen Jun 11 '13 at 17:22
3  
By the way, there are exact formulas for all of the quantities you ask about here in the case of Brownian motion. Look up "Levy's arcsine law" or read any textbook treatment of the zeroes of Brownian motion. –  Josh Shadlen Jun 11 '13 at 17:24
2  
At Northwestern we used Lawler's "Introduction to Stochastic Processes" with our undergrads and found the treatment of this stuff to be pretty good. Anyway, feel free to drop me an email about this stuff, I like talking about it -- first.last@gmail.com. PS You should probably migrate this question to MSE. –  Josh Shadlen Jun 11 '13 at 17:44
2  
The first hitting time of a Brownian motion with $0$ drift follows a Lévy distribution. en.wikipedia.org/wiki/L%C3%A9vy_distribution –  Douglas Zare Jun 12 '13 at 6:21

1 Answer 1

up vote 4 down vote accepted

By the reflection method, the number of ways to reach $a$ wins and $b \le a$ losses without the losses ever exceeding the number of wins is ${a+b \choose b}-{a+b \choose b-1}$, and the probability is the count times $2^{-(a+b)}$. The probability that you have not lost by time T is the sum of these probabilities so that $a=T-b$, which telescopes:

$$\begin{eqnarray} & &\sum_{b=0}^{\lfloor T/2 \rfloor} \bigg({T \choose b} - {T\choose b-1}\bigg) 2^{-T}\newline &=& \bigg(-{T \choose -1} + {T \choose 0} - {T \choose 0} + {T \choose 1} - ... + {T \choose \lfloor T/2 \rfloor }\bigg)2^{-T} \newline &=&{T \choose \lfloor T/2 \rfloor }2^{-T}.\end{eqnarray}$$

By Stirling's formula, $ {T \choose \lfloor T/2 \rfloor }2^{-T}\sim \sqrt{\frac{2}{\pi T}}$. The $0.8$ you observed from simulations was an approximation to $\sqrt{2/\pi}=0.797885.$


The number of ways to lose in exactly $2t+1$ steps is the $t$th Catalan number, so the probability of losing in exactly $2t+1$ steps is $p(2t+1) = \frac{1}{(t+1)}{2t \choose t}2^{-(2t+1)}$.

The conditional expectation of the time to lose given that you lose by a constant time $T$ is $n(T) = \sum_{t \lt T/2} \frac{2t+1}{(t+1)}{2t \choose t}2^{-(2t+1)}$ divided by the total probability of losing by time $T$, $d(T) = \sum_{t \lt T/2} \frac{1}{(t+1)}{2t \choose t}2^{-(2t+1)}$ which we estimated above as $1 - \sqrt{\frac{2}{\pi T}} \sim 1$.

Since $\frac{2t+1}{t+1} = 2 - \frac{1}{t+1}$,

$\begin{eqnarray}n(T) &=& \sum_{t \lt T/2} (2-\frac{1}{t+1}){2t \choose t}2^{-(2t+1)}\newline &=&\bigg(\sum_{t \lt T/2} {2t \choose t}2^{-2t}\bigg) - d(n) \end{eqnarray}$

Mathematica finds that this sum is $-1 + \frac{2r+3}{2^{2r+2}} {2r+2\choose r+1}$ where $r=\lfloor T/2 \rfloor$, which is easy to prove by induction. Stirling's formula says $n(T) \sim \sqrt{\frac{2T}{\pi}} = 0.797885 \sqrt T.$ As an alternative, we could apply Stirling's formula to the last sum, and then change the sum to an integral to get $n(T) \sim \int_0^{T/2} \sqrt{\frac{2}{\pi 2x}}dx = \frac{2 \sqrt{x}}{\sqrt{\pi}}\bigg|_0^{T/2} = \sqrt \frac{2T}{\pi}.$

share|improve this answer
    
Cool!!! Thank you very much. I am still curious, is there a way to see $\sqrt(T)$ in "one word" from purely probabilistic argument ? E.g. If we have a Wiener process (continuous limit of random walks) is this combinatorial argument the only way to see the answer ? –  Alexander Chervov Jun 27 '13 at 6:10
1  
A one word proof? Perhaps in German. I think you can read the asymptotics off of the Lévy distribution without using a combinatorial argument. –  Douglas Zare Jun 27 '13 at 7:16
    
if we consider a Wiener process, will these formulas become exact ? not approximate ? I mean: Wiener is limit of random walk, as you showed my formulas are approximates for exact for random walks, it might be two limits correspond to each other. (Of course, there should be variance of Wiener in formulas). –  Alexander Chervov Jul 4 '13 at 11:40
    
The probability would be outside $[0,1]$ while the conditional expected stopping time would be greater than $T$ for small $T$, so these can't be exact. –  Douglas Zare Jul 5 '13 at 18:35

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.