Probability Problems 02
Table of Contents
Fair Duel
This problem can be solved using markov chain or recursive probability. For the MC solution, name the following states: S, the next shoot is from Smith; E, Smith wins, B: next shoot is from Brown, L: Smith losses. Denote the probability of starting from state S to state E be $\mu_s$. Obviously, $\mu_L=0$ and $\mu_e=1$. Then the following process are standardized.
The second approach is also straightforward. If Smith and Brown both fail their shoots, then the game starts again, Smith still has $E$ prob to win.
Gambling in a Company
1. What is the expected number of rounds to the end of the game?
2. What the probability that the $i^{\text {th }}$ gambler ends up with all the money?
3. For $n=3$, what is the expected number of rounds till the first loser quits the game?
First, let’s us review the classic gambler’s ruin problem. Suppose a gambler has $v$ amount of money, and targets at $u+v$ as winning. If $S_0$ is his initial capital, then $S_n$ is a martingale. Denote $N$ as the stopping time, then $S^2_N - N$ is also a martingale (find proofs in Greek Book). Then the probability of him winning is $\frac{v}{u+v}$, the expected number of steps to stop is $uv$.
With this background knowledge, it is easier to solve this. Imagine each player is combating all the others, then this problem is just a simple gambler’s ruin problem. Do the same for all $n$ players, each of them own $a_i$ capital and target at $a-a_i$. Then he expects to stop at $a_i(a-a_i)$ rounds. For the whole company, then
$$ E(R)=\frac{1}{2} \sum_{i=1}^{n} a_{i}\left(a-a_{i}\right) $$Consider $a$ players with 1 dollar each. Before the first round, the probability of winning the game is uniform among the players: $\frac{1}{a}$. Partition the players into $n$ teams, so that the $i^{\text {th }}$ team has $a_{i}$ members/dollars. Then the probability of the $i^{\text {th }}$ team (i.e., gambler) winning the game is $p_{i}=a_{i} \cdot \frac{1}{a}=\frac{a_{i}}{a}$.
Or view this player is playing against all the others, then following the conclusion of gambler’s ruin, the probability is the same as the above.
N Normal RVs
This problem is independent to the distribution type.
The game ends after exactly $n$ steps if and only if the first $n-1$ samples are in increasing order, and the last sample is not. There are $(n-1)!$ combinations but only one case to be increasing. And the last sample has $\frac{n-1}{n}$ probability not to be the highest. So overall, the probability for the game ends at $n$ is $\frac{n-1}{n !}$.
The game can only stop when $n\ge2$, so the expectation is
$$ \sum_{n=2}^{\infty} n\times\frac{n-1}{n !}=\sum_{n=2}^{\infty} \frac{1}{(n-2) !}=\sum_{k=0}^{\infty} \frac{1}{k !}=e $$As we need to remember that, the Talor’s expansion
$$ e^{x}=\sum_{n=0}^{\infty} \frac{x^{n}}{n !} $$N Normal RVs: follow up
Average Length of the Longest Segment
https://math.stackexchange.com/questions/14190/average-length-of-the-longest-segment
We are able to derive the expected length of any $k-th$ largest segment. Denote the split points as $X_1,X_2,\dots, X_{n-1}$. And the segments $V_1, V_2,\dots,V_n$. We can assume that the first segment $V_1$ is the smallest one without loss of generality.
Expected length of the smallest
To derive the $P(V_1>x)$, we need all the other segments including $V_2, \dots, V_n$ to be larger than $x$ also. Treat the $x$ as the baseline value of each segments, and $1-nx$ will be the remaining length of the rope that we need to further split into $n-1$ segments to compensate for the longer segments. Since each points are uniforms, the probability that they lie on the remaining rope is $(1-nx)^{n-1}$.
In a three segments case, we first view the rope having $x,x,x,1-3x$ segments. the $1-3x$ parts will be further split into two segments and added up two the second and third $x$.
Use a variation of expectation formula, we are able to get,
$$ E\left[V_{1}\right]=\int_0^{\infty} P\left(V_{1}>x\right) d x=\int_0^{1 / n}(1-n x)^{n-1} d x=\frac{1}{n^2} $$Expected length of the longest
Once you get the smallest, then the problem can be solved recursively. As the second smallest will be the smallest now. The expected length will be $\frac{1}{n^2}+\frac{1-n(1/n^2)}{(n-1)^2}$ by adding the expected smallest segments from the $1-nx$ rope.
Solve the problem recursively, and you will find that the $k-th$ largest segment has the expectation of $\frac{1}{n}(\frac{1}{n}+\frac{1}{n-1}+\dots\frac{1}{k})$.
Win 2 More Games
1. What is the probability that team $A$ wins the series?
2. What if the rule changes to whoever gets two consecutive winnings first will win, what is the probabilty of $A$ wins?
Part 1
Solve a simplier problem that considers no tie. Tie does not change thre result.
- They probability does not rely on the tie. Can be solved using a markov chain by defining states $S$, $+1$, $-1$, $+2$, and $-2$. Answer is $\frac{p^2}{1-2pq}$, or $\frac{p^2}{p^2+q^2}$.
- This can also solved by an imbalanced gambler’s ruin problem.
- Or see the solutions here https://www.cut-the-knot.org/Probability/InPraiseOfOdds.shtml.
Part 2
- Solve similarly using a markov chain. The solution is $\frac{p^2(1+q)}{1-pq}$.
- A more general solution for two consecutive heads before two consecutive tails. See the next problem.
$r$ heads before $s$ tails
See the solution here: https://math.stackexchange.com/questions/201531/whats-the-probability-of-tossing-r-heads-in-a-row-before-s-tails-in-a-row?rq=1
Dice First Exceeds 12
Roll a dice until multiplier of 3
Correlation of coin tosses
Random walk on a circle
Number of Sets for Pairs
When $n=1$, then two people only have 1 possible pair.
When $n=2$, then say the first team $A$ has $3$ choices to make. After this, the problem is narrowed to $n=1$ cases as there are two teams left. So in total we have $3f(1)$.
When $n=3$ then the first team $A$ has $5$ choices to make. After this, the problem become a $n=2$ cases. So we have $5f(2)$.
Overall, for $f(n)=1\times3\times \dots \times(2n-1)$.
Trading Days
Use the (long term) stable state probabilities. $$ \left[\begin{array}{lll} \pi_G & \pi_B \end{array}\right]\left[\begin{array}{lll} 0.8 & 0.2 \ 0.4 & 0.6\ \end{array}\right]=\left[\begin{array}{lll} \pi_G & \pi_B \end{array}\right] $$ Solve the above equations and we get $\pi_G=\frac{2}{3}$.
Tenth digits of the power of 2
Since we care about the tenth digits. Only need to keep track of the last two digits. And see if there is a loop in them.
x = 2
seen = set()
while x not in seen:
seen.add(x)
x = (2*x) % 100
print(seen)
{2, 4, 8, 12, 16, 24, 28, 32, 36, 44, 48, 52, 56, 64, 68, 72, 76, 84, 88, 92, 96}
21
The last number in the loop is $52$, and then the next will be $4$, which creates a loop within the set. Excluding the initial $2$ that appears only in $2^1$. We have $20$ numbers in which $2$ of them with tenth digit $1$. So the probability is $0.1$.
Written Solution
