車の鍵を見つけたい

# 背景
車の鍵をよく失くしてしまいます。対策として、車の鍵を見つけるためのデバイスを用意しておきます。でも、そのようなデバイスも失くしてしまう可能性が高いです。そこで、そのデバイスを見つけるためのデバイスを用意した方がよさそうです。このあたりについてちょっと考察してみます。

# モデル
車の鍵、及び探索用のデバイスに番号を振って区別することにします。車の鍵は$i=0$、車の鍵を見つけるための探索用デバイスは$i=1$、探索用デバイスを探索するためのデバイスは$i=2$です。つまり、番号$i$のデバイスは番号$i-1\;(i \geq 1)$のデバイスを探索するのに使うことになります。ここでは、車の鍵も($i=0$の)デバイスと呼ぶことにします。

さて、朝起きたところからスタートです。確率$q_i$で$i$番目のデバイスを失くしているとします。目視で$i$番目のデバイスを探索したとすると、見つかる確率は$p_i$であるとします。また、$i+1$番目の探索用デバイスを用いれば即座に見つかるものとします。家を出発出来る確率はどの程度でしょう。

# CASE 1: 探索用デバイスが１個の場合
探索用デバイスがひとつだけの場合を考えてみます。家を出発出来ないのは、車の鍵もデバイスも失くし、探索してもどちらも見つからなかった場合です。このような確率は
$$
q_0q_1 \times (1-p_0) \times (1-p_1)
$$
です。

# CASE 2: 探索用デバイスが２個の場合
探索用デバイスがふたつの場合を考えてみます。家を出発出来ないのは、全てのデバイスを失くした場合です。どれかひとつでもデバイスがあれば、車の鍵はすぐに見つかります。家を出発出来ない確率は
$$
q_0q_1q_2 \times (1-p_0) \times (1-p_1) \times (1-p_2)
$$
です。

# 一般の場合
デバイスが車の鍵を含めて$N$個あった場合、家を出発出来ない確率は
$$
\prod_{i=0}^{N-1}q_i(1-p_i)
$$
となります。

# 考察１
確実に出発するためには、どれかひとつでも$q_i=0$、もしくは$p_i=1$を満たしていればよいことになります。つまり、どれかひとつでもドでかくするなり確実に失くさない、見つかるようにすればよいです。

# 考察２
デバイスの順序は無関係です。つまり、見つかりやすいデバイスの番号を小さくするとか、大きくするとかは関係ありません。

# 考察３
$q_i,1-p_i \leq 1$ですが、現実的には等号が成立するケースが稀であるとすると、デバイスをたくさん用意すればするほど出発しやすくなります。どれかひとつでもデバイスが見つかればよいのであたりまえですね。

# デバイスの電池切れをモデルに入れる
モデルが単純すぎてあまり面白い結論にならなかったので、デバイスの電池切れをモデルに入れてみます。$i$番目のデバイスが電池切れの確率を$r_i$とします。電池切れしている場合、$i+1$番目のデバイスからは見つけられません（反応がない）。

# CASE 1: 探索用デバイスが１個の場合
家を出発出来ないのは、
(i) 車の鍵を失くし、見つからず、電池切れの場合
(ii) 車の鍵を失くし、見つからず、電池はあるが、デバイスを失くし、見つからない場合
です。そのような確率は
$$
q_0 (1-p_0) r_0 + q_0 \times (1-p_0)  \times (1-r_0)q_1(1-p_1)
$$
です。

# CASE 2: 探索用デバイスが２個の場合
CASE 1と同様に考えます。
```math
\begin{align}
& q_0(1-p_0)r_0 \\
+& q_0(1-p_0)(1-r_0) \times q_1(1-p_1)r_1 \\
+& q_0(1-p_0)(1-r_0) \times q_1(1-p_1)(1-r_1)q_2(1-p_2)
\end{align}
```

# 一般の場合
```math
\begin{aligned}
&\sum_{i=0}^{N-1}\left[\prod_{j=0}^{i-1}q_j(1-p_j)
(1-r_j)\right]q_i(1-p_i)r_i \\
&r_{N-1} = 1
\end{aligned}
```
となります。

# シミュレーションによる確認
```c++
#include <iostream>
#include <vector>
#include <random>

int main(int argc, char **argv)
{
	int N = atoi(argv[1]); // デバイスの数（鍵を含む）
	std::vector<double> q(N); // 失くす確率
	std::vector<double> p(N); // 見つかる確率
	std::vector<double> r(N); // 電池切れの確率

	std::mt19937_64 mt(atoi(argv[2]));
	std::uniform_real_distribution<double> u(0, 1);
	for (int i = 0; i < N; i++)
	{
		q[i] = u(mt);
		p[i] = u(mt);
		r[i] = (i==N-1 ? 1 : u(mt));
	}
	
	int count = 0, Iter = 1000000;
	for (int iter = 0; iter < Iter; iter++)
	{
		std::vector<bool> qb(N); // 失くす
		std::vector<bool> pb(N); // 見つかる
		std::vector<bool> rb(N); // 電池切れ
		for (int i = 0; i < N; i++)
		{
			qb[i] = (u(mt) < q[i] ? true : false);
			pb[i] = ((u(mt) < p[i] || qb[i]==false) ? true : false);
			rb[i] = (u(mt) < r[i] ? true : false);
		}
		if (qb[0])//鍵を失くした
		{
				for (int i = N-2; i >= 0; i--)
				{
					if(pb[i]==false) pb[i] = ((rb[i] == false && pb[i+1]==true) ? true : false); // 電池があり、デバイスi+1が手元にあればデバイスiが見つかる
				}
			if (pb[0] == false) count++;
		}
	}

	double prob = 0;
	for (int i = 0; i < N ; i++)
	{
		double tmp = 1;
		for (int j = 0; j<i; j++)
		{
			tmp *= q[j] * (1 - p[j]) * (1 - r[j]);
		}
		if(i==N-1) tmp *= q[i] * (1 - p[i]);
		else  tmp *= q[i] * (1 - p[i])*r[i];
		prob += tmp;
	}
	
	
	std::cout << (double)count / (double)Iter << " " << prob << std::endl;


	return 0;
}
```
```bash
for N in `seq 1 10`
do
        for s in `seq 0 9`
        do
                ./a.out $N $s
        done
done
```
![662fe8f609db488227b465bd6cdae310.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/520857/b696b3e8-aa5c-927c-8804-fe035cf8ce9e.png)
縦軸は、鍵が見つからない確率です。
シミュレーション結果をよく再現しています。

# 考察
$q_j(1-p_j)(1-r_j)$の小さいデバイス、つまり、失くしづらく、見つけやすく、電池の切れづらいデバイスの番号を小さくした方が有利です。また、
```math
\begin{aligned}
&\sum_{i=0}^{N-1}\left[\prod_{j=0}^{i-1}q_j(1-p_j)
(1-r_j)\right]q_i(1-p_i)r_i \\
=& q_0(1-p_0)r_0 + q_0(1-p_0)(1-r_0)q_1(1-p_1)r_1 \\
&+ q_0(1-p_0)(1-r_0)q_1(1-p_1)(1-r_1)q_2(1-p_2)r_2 \cdots
\end{aligned}
```
なので、番号の小さいデバイスの影響が大きいことがわかります。番号の極端に大きなデバイスが手元にあっても、番号の小さいデバイスを順に見つけていく過程で一度でも失敗（電池切れしていたりして）してしまうと、元のデバイスは役立たずになってしまうことを考えると直感にも合うと思います。